访客 一、简介
国密SM3算法是我国自研设计的商用密码杂凑算法，是在SHA-256的基础上进行改造的，其安全性与SHA-256相当。《SM3密码杂凑算法》于2010年12月份由国家密码管理局首次发布。后于2012年发布为密码行业标准《GM/T0004-2012SM3密码杂凑算法》，2016年发布为国家密码杂凑算法标准《GB/T32905-2016信息安全技术SM3密码杂凑算法》。
标准中阐述了SM3算法的基本算法、实现步骤及实现原理。SM3和MD5的迭代过程类似，也采用Merkle-Damgard结构。消息分组长度为512位，杂凑输出值长度为256位。
SM3密码杂凑算法的执行过程包括3步：消息填充、迭代压缩、输出杂凑值。其中迭代压缩的过程中又包括了消息扩展。
二、算法原理
1.填充
SM3的消息扩展步骤是使用512比特的数据分组作为输入的，所以，在开始的时候需要将输入的原始数据数据填充至512比特的倍数。
假设消息m的长度为l比特，填充的规则如下:
- 首先将比特“1”填充到消息的尾部；
- 再添加k个“0”，k是满足
l1k=448mod512的最小非负整数； - 然后再添加一个
64比特的比特串，该比特串是长度l的二进制表示，采用大端存放； - 填充后的消息
m'的比特长度为512的位数。
2.迭代压缩
2.1迭代过程
迭代的过程为先将填充后的消息m'按512比特进行分组，分成n组，其中n=(lk65)/512
然后对分组通过压缩函数执行压缩操作，如下所示
其中CF是压缩函数，V(0)为256比特初始值IV，B(i)为填充后的消息分组，迭代压缩的结果为V(n)。
2.2消息扩展
在对分组执行压缩前，需要对消息进行扩展，需要将分组扩展为132个消息字，每个消息字32比特，即4字节,在压缩函数CF中会用到。
扩展过程：
- 将消息分组
B(i)划分成16个消息字，W(0),W(1),…,W(15)。 - 根据下面公式产生其它的
W - 根据下列公式循环产生
64个W‘
2.3压缩函数
SM3整个过程中最复杂、最核心的地方就是压缩函数，令A、B、C、D、E、F、G、H为字寄存器（字的存储为大端格式），每个字为32位，初始值存储的是IV。SS1、SS2、TT1、TT2为中间变量，压缩函数V(i1)=CF(V(i),B(i)),0<=i<=n-1,压缩函数CF对ABCDEFGH8个消息字及分组扩展后的消息执行64轮相同的过程。
过程中还会涉及到其它一些函数，相当复杂，具体计算的过程如下：
- 首先将
V(i)赋值给寄存器，第一次时也就是将初始IV赋值给寄存器的ABCDEFGH。 - from0to63循环执行压缩过程
- 将寄存器的
ABCDEFGH再与B(i)进行异或运算得到V(i1) - 得到
V(i1)用于下一分组的压缩。
3.得到杂凑值
当所有的分组都执行完压缩后V(n),将V(n)赋值给ABCDEFGH，输出ABCDEFGH即为256比特的杂凑值。
整体的过程可如下图表示：
三、代码实现
在整个代码实现中，会将输入的字节数组消息转换成32字节的整数进行运算处理，输出杂凑值时再将整数转换为字节数组。
因为将所有的消息缓存后再填充，会占用大量内存，所以采用循环分组处理。即对输入的字节消息进行顺序处理，当够一个分组的数据后就执行消息扩展、压缩，压缩后的结果缓存起来，为下一分组使用作准备，直到没有消息输入后调用final时再进行填充操作，并处理填充后的分组数据，然后产生杂凑值。
1.常量定义
1.1初始化的IV
算法中规定了初始化IV为32个字节的常量，
这里我们在类中定义一个常量数组，这里我们使用int数组来存放，因为一个字为4个字节，刚好为一个int的长度。
在整个算法过程中，我们会将输入的字节转换成4字节int进行处理，最后杂凑值输出的时候再将int转换成字节数组输出。
//初始的IV值privatestaticfinalint[]IV={0x7380166F,0x4914B2B9,0x172442D7,0xDA8A0600,0xA96F30BC,0x163138AA,0xE38DEE4D,0xB0FB0E4E};1.2常量T
常量数组T在压缩的过程中会用到，算法中如下对常量T进行了定义
我们对常量T进行定义，并在静态块中进行初始化。
因为在后面的压缩过程中，常量T(j)的值会循环向左移j，所以这里初始化的时候直接完成左移操作。
//常量Tprivatestaticfinalint[]T=newint[64];//初始化常量Tstatic{for(inti=0;i<16;i){intt=0x79CC4519;//循环左移i位，等价于左移i位后按位或无符号右移32-i位T[i]=(t<<i)|(t>>>(32-i));}for(inti=16;i<64;i){//压缩算法中有mod32intn=i%32;intt=0x7A879D8A;T[i]=(t<<n)|(t>>>(32-n));}}上述代码中循环左移i位，涉及到位运算，等于是向左移动i位，然后或向右无符号右移（32-i）位，不明白的可以查阅资料。
1.3布尔函数
布尔函数也是压缩中用到的函数，其算法如下：
因为其函数都规定了0到15，和16到63的两种情况，所以我们将FF函数分别定义为FF0和FF1，将GG函数定义为GG0和GG1
privateintFF0(finalintx,finalinty,finalintz){return(x^y^z);}privateintFF1(finalintx,finalinty,finalintz){return((x&y)|(x&z)|(y&z));}privateintGG0(finalintx,finalinty,finalintz){return(x^y^z);}privateintGG1(finalintx,finalinty,finalintz){return((x&y)|((~x)&z));}1.4置换函数
置换函数包括P0和P1，P1在会消息扩展时使用，P0会在压缩过程中使用，定义如下：
代码如下
privateintP0(finalintx){finalintr9=((x<<9)|(x>>>(32-9)));finalintr17=((x<<17)|(x>>>(32-17)));return(x^r9^r17);}privateintP1(finalintx){finalintr15=((x<<15)|(x>>>(32-15)));finalintr23=((x<<23)|(x>>>(32-23)));return(x^r15^r23);}1.5其它常量
定义一个消息分组的缓存，循环存放每组的消息，以字为单位，16个字，刚好为512比特。
//每个分组多少个消息字privatestaticfinalintBLOCK_SIZE=64/4;//消息组缓存，存储的是4字节的消息字privateint[]intWord=newint[BLOCK_SIZE];//消息分组的偏移量privateintwordOff;定义一个4字节数组缓存，用来处理输入的字节数组消息，当满4个字节时转换成一个消息字，放入消息分组的缓存；
privatefinalbyte[]byteBuf=newbyte[4];//组成一个字的buffprivateintbyteBufOff;//xBuf的偏移量定义个变量来记录输入消息的总大小
//比特大小，记录输入数据长度privatelongbyteCount;定义寄存器，用来存放ABCDEFGH的值，
//寄存器，存初始IV和中间结果privateint[]V=newint[8];2.初始化
定义初始化init()方法，对上面定义的一些变量进行初始化，
/***初始化方法*/protectedvoidinit(){byteCount=0;wordOff=0;byteBufOff=0;//初始化字节数组缓存for(inti=0;i<byteBuf.length;i){byteBuf[i]=0;}//初始化寄存器this.V=IV;}3.update方法
update方法用来接收传入的字节数组消息，并对消息进行处理。消息处理过程中，先将字节数组转换成消息字，再将消息字组成分组数据，然后对调用压缩函数，
update分为两个方法，一个是处理输入字节数组，一个是内部处理单字节。
/***处理输入的字节数组*@paramdata输入数据*@paraminOff偏移量*@paramlen长度*/publicvoidupdate(byte[]data,intinOff,intlen){//防止len小于0len=Math.max(0,len);inti=0;//多次update时，前一次update最后的数据可能不够一个消息字，//字节缓存中还有数据，需要先进行处理if(byteBufOff!=0){while(i<len){//循环处理byteBuf[byteBufOff]=data[inOffi];if(byteBufOff==4){//处理消息processWord(byteBuf,0);byteBufOff=0;break;}}}//&~3的目地是变成能被4整除的最大整数intlimit=((len-i)&~3)i;for(;i<limit;i=4){processWord(data,inOffi);}//剩余不够一个消息字的数据放入字节缓存中while(i<len){byteBuf[byteBufOff]=data[inOffi];}byteCount=len;}/***处理输入的单字节*@paramin*/protectedvoidupdate(bytein){byteBuf[byteBufOff]=in;//字节数组满了后，转换成消息字if(byteBufOff==byteBuf.length){processWord(byteBuf,0);byteBufOff=0;}byteCount;}4.压缩函数方法
压缩函数是整个算法的核心，压缩过程需要先进行消息扩展，处理消息扩展的方法如下
/***消息扩展生成消息字*这里没有生成W’，因为W'可以直接通过W异或得到*/protectedvoidprocessW(){for(intj=0;j<16;j){this.W[j]=this.intWord[j];}for(intj=16;j<68;j){intwj3=this.W[j-3];intr15=((wj3<<15)|(wj3>>>(32-15)));intwj13=this.W[j-13];intr7=((wj13<<7)|(wj13>>>(32-7)));this.W[j]=P1(this.W[j-16]^this.W[j-9]^r15)^r7^this.W[j-6];}}压缩函数方法代码如下
/***压缩函数*/publicvoidCF(){processW();intA=this.V[0];intB=this.V[1];intC=this.V[2];intD=this.V[3];intE=this.V[4];intF=this.V[5];intG=this.V[6];intH=this.V[7];for(intj=0;j<16;j){inta12=((A<<12)|(A>>>(32-12)));//直接加T[j]，因为前面已经mod过了ints1_=a12ET[j];intSS1=((s1_<<7)|(s1_>>>(32-7)));intSS2=SS1^a12;intTT1=FF0(A,B,C)DSS2(this.W[j]^this.W[j4]);intTT2=GG0(E,F,G)HSS1this.W[j];D=C;C=((B<<9)|(B>>>(32-9)));B=A;A=TT1;H=G;G=((F<<19)|(F>>>(32-19)));F=E;E=P0(TT2);}for(intj=16;j<64;j){inta12=((A<<12)|(A>>>(32-12)));//直接加T[j]，因为前面已经mod过了ints1_=a12ET[j];intSS1=((s1_<<7)|(s1_>>>(32-7)));intSS2=SS1^a12;intTT1=FF1(A,B,C)DSS2(this.W[j]^this.W[j4]);intTT2=GG1(E,F,G)HSS1this.W[j];D=C;C=((B<<9)|(B>>>(32-9)));B=A;A=TT1;H=G;G=((F<<19)|(F>>>(32-19)));F=E;E=P0(TT2);}this.V[0]^=A;this.V[1]^=B;this.V[2]^=C;this.V[3]^=D;this.V[4]^=E;this.V[5]^=F;this.V[6]^=G;this.V[7]^=H;this.wordOff=0;}可以看到上面的代码调用了两个for循环，是因为布尔函数FF、GG调用不同，没有直接在一个循环里面用if判断是为了提升性能。
5.final方法
当处理完输入的数据后，调用final来进行填充并处理最后的分组，然后输出杂凑值，同时将一些变量恢复初始化。
/***杂凑结束*@paramout最终的杂凑值*@return*/publicintdoFinal(byte[]out){longbitLength=(byteCount<<3);//最后进行填充,先填充1update((byte)128);//填充后不够一个字长度时，继续补0至一个字while(this.byteBufOff!=0){update((byte)0);}//输入字节数组消息总长度填充processLength(bitLength);//处理最后的分组CF();//转换成字节并输出给outintToBigEndian(V,out,0);//初始值恢复原样init();returnDIGEST_LENGTH;}处理数据长度的填充方法如下
/***处理数据长度填充*@parambitLength*/protectedvoidprocessLength(longbitLength){//wordOff=15,说明当前块不够填充64字节的长度了if(this.wordOff>(BLOCK_SIZE-2)){this.intWord[wordOff]=0;//填充为0CF();}//填充0直到剩两个消息字while(this.wordOff<(BLOCK_SIZE-2)){this.intWord[wordOff]=0;}//填充64字节的长度this.intWord[wordOff]=(int)(bitLength>>>32);this.intWord[wordOff]=(int)(bitLength);}四、测试
完成后进行简单测试，测试代码如下
//测试publicstaticvoidmain(String[]args){SM3_1sm3Test=newSM3_1();byte[]plain=hexStringToBytes("FC7D61FD1D392EB692C5C7E0723CA637ADDA");byte[]plain1=hexStringToBytes("FC");sm3Test.update(plain,0,plain.length);sm3Test.update(plain1,0,plain1.length);byte[]out=newbyte[32];sm3Test.doFinal(out);System.out.println(bytes2HexString(out));}测试出来的杂凑结果和网上其它工具杂凑值结果一致，说明算法实现正确。
参考资料
1.https://www.oscca.gov.cn/sca/xxgk/2010-12/17/content_1002389.shtml
2.BC包的SM3算法
3.https://zhuanlan.zhihu.com/p/129692191