SM国产密码算法

2020/12/06 密码学

国产密码算法(SM国密算法)是国家密码局认定的国产商用密码算法,目前比较常见的有SM2、SM3、SM4三类算法,分别是非对称密码算法、哈希算法和对称密码算法。本篇文章主要对SM2、SM3、SM4做简单介绍,并与美国标准的密码算法做对比。

关于国密算法

国密算法是国家商用密码算法的简称。自2012年以来,国家密码管理局以《中华人民共和国密码行业标准》的方式,陆续公布了SM2/SM3/SM4等密码算法标准及其应用规范。其中“SM”代表“商密”,即用于商用的、不涉及国家秘密的密码技术。其中SM2为基于椭圆曲线密码的公钥密码算法标准,包含数字签名、密钥交换和公钥加密,用于替换RSA/Diffie-Hellman/ECDSA/ECDH等国际算法;SM3为密码哈希算法,用于替代MD5/SHA-1/SHA-256等国际算法;SM4为分组密码,用于替代DES/AES等国际算法;SM9为基于身份的密码算法,可以替代基于数字证书的PKI/CA体系。通过部署国密算法,可以降低由弱密码和错误实现带来的安全风险和部署PKI/CA带来的开销。

SM2与RSA、ECDSA

SM2与RSA、ECDSA都是基于非对称密码算法体系,下列的表格显示了它们的区别:

  SM2 ECDSA RSA
类型 非对称密码算法 非对称密码算法 非对称密码算法
归约 椭圆曲线上的离散对数问题 椭圆曲线上的离散对数问题 大整数分解问题
应用 数字签名
加解密
密钥交换
数字签名 数字签名
加解密
密钥交换
长度 SM2曲线
私钥:256 bit
公钥:512 bit
NIST P-256曲线
私钥:256 bit
公钥:512 bit

NIST P-384曲线
私钥:384 bit
公钥:768 bit
RSA 2048

SM2与ECDSA使用的曲线

SM2与ECDSA都使用了椭圆曲线,有限域上椭圆曲线在点加运算下构成有限交换群,在点乘运算下构成一个单项函数。在椭圆曲线的点乘运算中,已知点乘结果与基点,求解倍数的问题称为椭圆曲线离散对数问题。对于一般的椭圆曲线的离散对数问题,目前只有指数级计算复杂度的求解方法。SM2曲线与ECDSA使用的NIST P-256曲线有着相似的地方,下面是他们的区别。

  1. NIST P-256曲线:NIST是美国国家标准,曲线的表达式为

    \(E/\mathbb{F}_{p}:y^2=x^3+ax+b\),群的秩为\(n\),满足

  2. SM2曲线:SM2曲线是国密标准,曲线的表达式为

    \(E/\mathbb{F}_{p}:y^2=x^3+ax+b\),群的秩为\(n\),满足

两条曲线的群的秩都是256 bit,基于椭圆曲线离散对数困难问题,安全性等级是128 bit(也有的说120 bit),对应RSA的安全等级是RSA2048。

在NIST发布的素域椭圆曲线的公开文档中,将类似于梅森素数生成方式的素数称为广义梅森素数(Generalized Mersenne primes),其中这两条曲线都使用了广义梅森素数,其中NIST使用的素数是

\[p_{256} = 2^{256} - 2^{224} + 2^{192} + 2^{96} - 1\]

而SM2使用的素数是

\[p_{sm2} = 2^{256} - 2^{224} - 2^{96} + 2^{64} - 1\]

SM2公钥加密算法

假设用户A、B之间进行加密通信,并使用SM2公钥加密算法。用户A作为发送者,用户B作为接收者,即用户A完成加密过程,用户B完成解密过程。

加密过程如下图所示,假设需要发送的数据是\(M\),消息\(M\)的比特长度是\(klen\)。

步骤如下(注意符号\([a]P\)表示点乘操作\(a \cdot P\)):

  1. 用随机数发生器产生随机数\(k \in [1, n-1]\);
  2. 计算椭圆曲线上的点\(C_1 = [k]G\);
  3. (按照标准里该步可选)
  4. 计算椭圆曲线上的点\((x_2,y_2) = [k]P_B\);
  5. 使用密钥派生函数KDF生成密钥数据流\(t=KDF(x_2 \parallel y_2, klen)\);
  6. 计算\(C_2 = M \oplus t\);
  7. 计算\(C_3 = Hash(x_2 \parallel M \parallel y_2)\);
  8. 得到密文\(C = C_1 \parallel C_2 \parallel C_3\);

解密过程如下图所示:假设需要解密的数据是\(C\),消息\(C_3\)的比特长度是\(klen\)。

步骤如下:

  1. 从密文\(C\)中取出\(C_1\)并判断是否满足椭圆曲线方程。
  2. (按照标准里该步可选)
  3. 计算椭圆曲线上的点\((x_2,y_2) = [d_B]C_1\);
  4. 使用密钥派生函数KDF生成密钥数据流\(t=KDF(x_2 \parallel y_2, klen)\);
  5. 计算\(M = C_2 \oplus t\);
  6. 计算\(U = Hash(x_2 \parallel M \parallel y_2)\),并判断\(U = C_3\)是否满足;
  7. 得到解密结果\(M\);

SM2密钥交换协议

我们先回顾一下经典的基于模p有限域下的椭圆曲线实现DH密钥磋商(ECDH):

  1. Alice和Bob共享关于椭圆曲线的参数\((p,a,b,G,n)\)。
  2. Alice选择小于n的整数\(n_{A}\),计算\(P_{A}=n_{A}\times G\),发送给Bob。
  3. 同样的,Bob选择小于n的整数\(n_{B}\),计算\(P_{B}=n_{B}\times G\),发送给Alice。
  4. Alice计算出共同密钥\(K_{A}=n_{A}\times P_{B}\),Bob计算出共同密钥\(K_{B}=n_{B}\times P_{B}\),容易证明\(K_{A}=K_{B}\),因为有\(K_{A}=n_{A}\times P_{B}=n_{A}\times (n_{B}\times G)=n_{B}\times (n_{A}\times G)= K_{B}\)

此时Alice和Bob得到共同密钥,而敌手获取的\(P_{A}\)和\(P_{B}\)无法计算出该密钥。

另外有一个术语容易混淆,那就是ECDHE:

ECDHE 中的 E 代表着「短暂的」,是指交换的密钥是暂时的动态的,而不是固定的静态的。例如在 TLS 中就使用了 ECDHE,连接建立时,服务器和客户端都动态生成公私钥,这些密钥在之后会用于 TLS 认证和通信双方之间的信息交换。

SM2密钥交换协议则要复杂一些。假设用户A和用户B协商获得密钥数据长度为\(klen\)比特,用户A是发起方,用户B是响应方,设\(w = \lceil(\lceil log_2(n) \rceil /2)\rceil-1\)。它的完整流程如下图所示:

需要注意几点地方:

  1. 符号\([a]P\)表示点乘操作\(a \cdot P\)。
  2. Trunc(x)是截断函数,它的表达式是\(2^w + (x \& (2^w - 1))\)。
  3. 进入KDF函数中的参数\(Z_A、Z_B\)分别是关于用户A、B的可辨别标识、部分椭圆曲线系统参数和用户A、B公钥的杂凑值,一般是用SM3算法生成。
  4. \(h\)是公共参数余因子。

上面这张图采用了左右对称的设计,不容易看出通信过程,我们将其简化为:

上面密钥协商过程的关键点在于两个椭圆曲线上的点\(U\)和\(V\)是否相等,当满足相等下有\(K_A = K_B\)。下面给出简单的证明:

$$\begin{align} V &= [h \cdot t_B](P_A + [\bar x_1]R_A) \\ &= [h \cdot t_B]([d_A]G + [\bar x_1 \cdot r_A]G) \\ &= [h \cdot t_B \cdot (d_A + \bar x_1 \cdot r_A)]G \\ &= [h \cdot t_B \cdot t_A]G \\ &= [h \cdot t_A]([t_B]G) \\ &= [h \cdot t_A]([d_B]G + [\bar x_2 \cdot r_B]G) \\ &= [h \cdot t_A](P_B + [\bar x_2]R_B) \\ &= U \end{align}$$

SM2数字签名

我们先来回顾一下ECDSA椭圆曲线数字签名算法,对于模\(p\)有限域下的椭圆曲线\(E\),选择小于\(n\)的整数\(d\),生成下列参数:

\[Q=[d]G\] \[{E,G,d,p,Q}\]

生成签名过程,其中\(H(m)\)是对消息\(m\)进行哈希的结果。

  1. 取随机数\(k\),计算\([k]G=(x_{1}, y_{1})\)
  2. 计算\(r=x_{1}\mod p\)
  3. 计算\(s=k^{-1}*(H(m)+dr)\mod p\)
  4. 签名结果为\((r,s)\)

验证签名的过程:

  1. 计算\(w=s^{-1}\mod p\)
  2. 计算\(u_{1}=wH(m)\mod p\)
  3. 计算\(u_{2}=rw\mod p\)
  4. 计算\([u_{1}]G+[u_{2}]Q=(x_{0},y_{0})\)
  5. 令\(v=x_{0}\mod p\),如果\(v=r\),则验证签名通过。

而SM2签名算法与ECDSA非常相似:

SM2生成签名过程,其中\(H(m)\)是对消息\(m\)进行哈希的结果。

  1. 取随机数\(k\),计算\([k]G=(x_{1}, y_{1})\)
  2. 计算\(r=H(Z_A \parallel M) + x_{1}\mod n\)
  3. 计算\(s=(1 + d_A)^{-1}(k - r \cdot d_A) \mod n\)
  4. 签名结果为\((r,s)\)

SM2验证签名的过程:

  1. 计算\(t = r + s \mod n\)
  2. 计算\((x_1, y_1) = [s]G + [t]P_A\)
  3. 计算\(R = H(Z_A \parallel M) + x_1 \mod n\)
  4. 如果\(r=R\),则验证签名通过。

\(r=R\)的先验条件是\([k]G = [s]G + [t]P_A\),下面给出简单的证明:

$$\begin{align} [s]G + [t]P_A &= [s]G + [r + s]P_A \\ &= [s]G + [r \cdot d_A + s \cdot d_A]G \\ &= [s + r \cdot d_A + s \cdot d_A]G \\ &= [(1 + d_A) \cdot s + r \cdot d_A]G \\ &= [k - r \cdot d_A + r \cdot d_A]G \\ &= [k]G \end{align}$$

SM3与SHA-256

待定

SM4与AES-128

待定

实验与性能分析

待定

参考资料

  1. Lightweight Implementations of NIST P-256 and SM2 ECC on 8-bit Resource-Constraint Embedded Device
  2. Comments on the SM2 Key Exchange Protocol
  3. On the Design and Performance of Chinese OSCCA-approved Cryptographic Algorithms
  4. 知乎专栏-椭圆曲线加密算法和国密算法

附录

SM2椭圆曲线公钥密码算法第1部分:数字签名算法

SM2椭圆曲线公钥密码算法第1部分:密钥交换协议

SM2椭圆曲线公钥密码算法第1部分:公钥加密算法

SM3密码杂凑算法

SM4分组密码算法

支持国密SM2、SM3、SM4、SM9的密码工具箱GmSSL

国密实验室

Search

    Table of Contents