浅析国家商用密码标准算法

中国商用密码概况

概况

国产商密算法是我国自主研发、具有自主知识产权的一系列密码算法，具有较高安全性，由国家密码局公开并大力推广。我国公开的国产商用密码算法包括SM1、SM2、SM3、SM4、SM7、SM9及祖冲之算法，其中SM2、SM3、SM4最为常用，用于对应替代RSA、DES、3DES、SHA等国际通用密码算法体系。

历史

我国在密码理论与分析上一直具有优势，但是长期依赖不公开密码算法，只提供密码芯片。密码芯片由少数专家设计，难于标准化，应用成本高，不利于推广应用。因此近年来陆续公布了商用密码算法，2006年公布了分组密码算法SM4，2011年公布了椭圆曲线密码算法SM2和杂凑算法SM3。商用密码的管理更加科学化，也和国际接轨。

原则

我国在商用密码的设计上，遵循了坚持密码的公开设计原则，也就是说，密码的安全应仅依赖于密钥的保密，不依赖与算法的保密。对于商用密码，美国DES开创了公开算法的先例。

SM4分组加密算法

概况

1. 分组密码，数据分组（包括明文、密文）和密钥长度都为128位；
2. 对合运算，加解密算法相同；
3. 滑动窗口结构，明文与密钥在滑动窗口控制下，通过基本轮函数运算，然后进行迭代，生成密文。

运算方式与部件

1. 基本运算方式

   • 模2加，用符号⊕表示，意为32比特异或运算；
   • 循环移位，符号<<<i，表示32位字循环左移i位；

2. 基本密码部件

   • 非线性字节变换部件S盒，进行8位的非线性置换，输入前半字节为行号，后半字节为列号，输出值参考S盒变换表行与列交叉点的值；
   • 非线性字变换τ，进行32位字的非线性变换，方式是4个S盒并行置换；
   • 线性L变换部件，32位输入，32位输出，设输入为B，输出为C，表示为C=L(B)，运算规则为;
   • 字合成变换T，由非线性字变换τ和线性L变换符合而成，T(X)=L(τ(X))，先进行S盒变换，后进行L变换；

轮函数F

1. 输入128位数据，4个32位字；

2. 输入32位字轮密钥rk，输出32位字，轮密钥由加密密钥通过密钥扩展算法生成；

3. 轮函数，如图所示

SM4轮函数.png

密钥扩展算法

1. 使用常数FK，;

2. 32个固定参数CK, ;

3. 输入加密秘钥MK，；

4. 中间数据Ki，i=0,1,...,34,35，；

5. For i=0,1,2...,31 Do
   

T'和轮函数中的T基本相同，将L变换修改为L‘，L'(B)=B⊕(B<<<13)⊕(B<<<23)

6. 输出轮密钥rki，i=0,1,...,30,31；

加解密算法

1. 输入明文，共128位，4个字；

2. 输入轮密钥, i=0,1,...,31，共32个轮密钥；

3. 算法结构为32轮轮函数迭代，每轮使用一个轮密钥；

4. 

    $=X_i⊕T(X_{i+1}⊕X_{i+2}⊕X_{i+3}⊕rk_i), i=0,1,...,31$
   

   

5. 输出密文，128位，4个字;

SM4加密.png

6. 解密算法与加密相同，只是轮函数密钥使用顺序相反；

7. 

    $=Y_i⊕T(Y_{i+1}⊕Y_{i+2}⊕Y_{i+3}⊕rk_i), i=0,1,...,31$
   

   

SM3杂凑算法

概况

1. hash函数也称报文摘要，将任意长的数据M变换为定长的码h，具有极强的错误检测能力，可以作为消息认证码，可以用于辅助数字签名和保密；
2. SM3算法由国家密码管理局在2010年12月正式颁布，适用于商用密码中的数字签名和验证、消息认证码的生成与验证以及随机数的生成；
3. 面向32比特字设计，输出的Hash长度为256比特；
4. 基本框架：压缩函数+迭代结构

消息填充

SM3的消息扩展步骤是以512位的数据分组作为输入的。因此，我们需要在一开始就把数据长度填充至512位的倍数，数据填充规则和MD5一样。

1. 假设消息m为长度为l的比特；
2. 先填充一个“1”，后面加上k个“0”。其中k是满足(n+1+k) mod 512 = 448的最小正整数；
3. 追加64位的比特串，是长度l的二进制表示，在内存中大端序存放；
4. 填充后的消息为m'，m'的长度是512的倍数，表示第i个消息分组，其中n=(l+k+65)/512。

消息扩展

1. 置换函数为P，字为X

   • 
   • 

2. 将消息分组扩展生成132个字，扩展方式为：

   FOR j=16 TO 67
   
   ENDFOR
   FOR j=0 TO 63
   
   ENDFOR

迭代压缩

1. 初始值IV，用于确定压缩函数寄存器的处态，IV =7380166f 4914b2b9 172442d7 da8a0600 a96f30bc 163138aa e38dee4d b0fb0e4e；

2. 布尔函数为FF, GG, 字为XYZ

   • 
   • 

3. 令A,B,C,D,E,F,G,H为字寄存器,SS1,SS2,TT1,TT2为中间变量,压缩函数, 0 ≤ i ≤ n−1，压缩方式为：

   

   FOR j=0 TO 63

   

   SS2 ← SS1 ⊕ (A ≪ 12)

   

   

   D ← C

   C ← B ≪ 9

   B ← A

   A ← TT1

   H ← G

   G ← F ≪ 19

   F ← E

   

   ENDFOR

   

   图示如下


4. 令，最后输出256位杂凑值y=ABCDEFG；

SM2椭圆曲线公钥算法

概况

SM2算法属于公开密钥密码，公钥密码的基本思想是，

1. 将密钥K一分为二，，专门加密，专门解密，两者不相等；
2. 不能计算出，所以可以将公开；
3. 成为用户的指纹，可以实现数字签名；

SM2是国家密码管理局于2010年12月17日发布的椭圆曲线公钥密码算法，在我们国家商用密码体系中被用来替换RSA算法。RSA基于特殊的可逆模幂运算实现，而SM2基于基本椭圆曲线（ECC）实现，相比于RSA密码复杂度高、处理速度快、机器性能消耗更小。

椭圆曲线

椭圆曲线简单的理解为描述了特定点的集合的公式，, a和b的取值变化决定了曲线在坐标系上的不同形状，椭圆曲线相对X轴是对称的；

令p是大于3的素数，且，称为有限域GF(p)上的椭圆曲线；

GF(p)上椭圆曲线密码的基础参数T=<p,a,b,G,n,h>，具体含义为

• p是大于3的素数，确定了有限域GF(p)；
• 元素a,b∈GF(p)， a和b确定了椭圆曲线；
• G为循环子群的生成元点，n为素数且为生成元G的阶，G和n确定了循环子群；
• h=|E|/n，并称为余因子，h将交换群E和循环子群联系起来；

椭圆曲线图示如下

SM2的曲线方程中，推荐使用256位素域GF(p)上的椭圆曲线，所有曲线参数都是定值。

SM2的曲线方程中，推荐使用256位素域GF(p)上的椭圆曲线，参数选取有如下几个要求，

1. p越大越安全，但计算速度会变慢，160位可以满足；
2. n为大素数，对于固定有限域F(p)，n应当尽可能大；
3. ;
4. 保证P的阶n足够大，h≤4;
5. 不能选取超奇异椭圆曲线和异常椭圆曲线等两类特殊曲线。

密钥生成

选取一条满足安全要求的椭圆曲线，通过随机数发生器产生用户B的私钥，其中n为基点G的阶。其次通过以G 为基点，计算点得到用户B的公钥。

密钥派生函数为KDF，通过输入比特串和整数len，得到一个长度为len的比特串，杂凑函数一般选用国密算法SM3。

加密算法

令要发送的消息为比特串M，len为M的比特长度，加密者A进行以下步骤，

1. 用随机数发生器产生随机数;
2. 计算椭圆曲线点;
3. 计算椭圆曲线上的点，S不能为无穷远点O；
4. 计算椭圆曲线点;
5. 计算密钥派生函数结果不能全为0，否则需要重新选择随机数k重新计算；
6. 计算;
7. 计算，Hash是密码杂凑函数；
8. 输出密文；

解密算法

解密者B进行以下步骤，

1. 从C中取出比特串，验证是否满足椭圆曲线方程，若不满足这种解密错误；
2. 计算椭圆曲线点，验证是否为无穷远点，若为无穷远点则解密错误；
3. 计算;
4. 计算，验证t是否为全0比特串，若为全0则解密错误；
5. 从C中取出比特串，计算⊕t；计算，从C中取出比特串，若≠C_3则解密错误；
6. M’为解密后的明文；

总结与展望

国密算法经过了国家专业机构设计，算法简洁，难以破解，十分安全。但是算法只公开了SM2，SM3和SM4，而且公开时间较短，需要进行更多的实践，在实践应用进一步验证算法。