SM2国密分析

简介

SM2是非对称加密算法

它是基于椭圆曲线密码的公钥密码算法标准，其秘钥长度256bit，包含数字签名、密钥交换和公钥加密，用于替换RSA/DH/ECDSA/ECDH等国际算法。可以满足电子认证服务系统等应用需求，由国家密码管理局于2010年12月17号发布。

SM2采用的是ECC 256位的一种，其安全强度比RSA 2048位高，且运算速度快于RSA。随着密码技术和计算技术的发展，目前常用的1024位RSA算法面临严重的安全威胁，我们国家密码管理部门经过研究，决定采用SM2椭圆曲线算法替换RSA算法。SM2算法在安全性、性能上都具有优势。

前置知识

椭圆曲线

椭圆曲线的定义

$y^2+axy+by=x^3+cx^2+dx+e\\$

最常用的方程是维尔斯特拉斯标准形式。

$y^2=x^3+ax+b$

椭圆曲线阿尔贝群

O 为零元，相反数 P 为关于X轴对称的另一边的点，加法规则为直线三点 P+Q+R=0。

几何加法

普通相交三点：P+Q+R=0

普通相交两点：P+P+Q=0，P+Q+Q=0（一点相切）

垂直相交两点：P+Q+0=0（垂直X轴）

垂直相交一点：P+P+0=0(垂直X轴+一点相切）

代数加法

$去掉特殊情况，只考虑两个非零非对称的点 P=(x_P,y_P) 和 Q=(x_Q,y_Q)。$

若P和Q不同，斜率为

$k=\frac{y_P-y_Q}{x_P-x_Q}$

若P和Q相同，斜率为

$k=\frac{3x_P^{2}+a}{2y_P}$

这条直线和椭圆曲线的交点

$R=(x_R,y_R)$

$x_R=k^2-x_P-x_Q\\ y_R=y_P+k(x_R-x_Q)=y_Q+k(x_R-x_Q)\\ P+Q=(x_P,y_P)+(x_Q,y_Q)=-R=(x_R,-y_R)\\$

标量积（点积/数乘/倍乘）

$Q=nP=P+P+...+P=\\\sum_{i=0}^{n-1}(b_i*2^i)P,\\bi=\begin{Bmatrix} 0 & 1\end{Bmatrix},\\ b_i为n的各比特位值$

有限域椭圆曲线

椭圆曲线是连续的，并不适合用于加密，所以必须把椭圆曲线变成离散的点，把椭圆曲线定义在有限域上。有限域上的椭圆曲线是指在椭圆曲线的定义式中，所有的系数都是在某个有限域 GF(p) 中的元素，其中 p 为一个大素数。

点的阶

如果椭圆曲线上一点 P，存在最小的正整数 n 使得数乘 nP=O ，则将 n 称为 P 的阶；若 n 不存在，则 P 是无限阶的。

加密原理

考虑 K=kG ，其中 K,G 为椭圆曲线 Ep*(a,b) 上的点，n 为 G 的阶（nG*=O），*k为小于 n 的整数。

给定 k 和 G ，根据加法法则，计算 K 很容易，但反过来，给定 K 和 G，求 k 就非常困难。因为实际使用中的ECC原则上把 p 取得相当大，n 也相当大，要把 n个解点逐一算出来列成上表是不可能的。

这就是椭圆曲线加密算法的数学依据。

点 G 称为基点 (base point)，k (k<n) 为私有密钥 (private key)，K 为公开密钥 (public key)。

通信算法

$A选定一条椭圆曲线 Ep(a,b)，并取椭圆曲线上一点作为基点 G；\\ A选择一个私有密钥 k (k<n)，并生成公开密钥 K=kG；\\ A将 Ep(a,b) 和点 K,G 传给B;\\ B收到信息后，将待传输的明文编码到 Ep(a,b) 上的一点 M，并产生一个随机整数 r（r<n，n 为 G 的阶数）；\\ B计算点 C1=M+rK 和 C2=rG；\\ B将 C1,C2 传给A；\\ A收到信息后，计算 C1−kC2，结果就应该是点 M\\ C1−kC2=M+rK−krG=M+rkG−krG=M\\$

这些就是椭圆曲线的大部分内容了

SM2曲线

SM2算法定义了5个默认参数，即有限域模数p，椭圆曲线参数a,b,椭圆曲线的基点G(x,y),与G的阶n。

p:FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFF
n:FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54123
a:FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFC
b:28E9FA9E9D9F5E344D5A9E4BCF6509A7F39789F515AB8F92DDBCBD414D940E93
Gx:32C4AE2C1F1981195F9904466A39C9948FE30BBFF2660BE1715A4589334C74C7
Gy:BC3736A2F4F6779C59BDCEE36B692153D0A9877CC62A474002DF32E52139F0A0

然后我没来看公私钥

私钥d，一般位数为256bits，也就是32bytes，32字节

公钥和基底有关系

P=d*G

所以公私钥为（d,P）,P是一个坐标，一般知道了d，G就会被知道，sagemath有一个函数是可以还原的

P.division_points(d) 

这个返回的就是基底

SM2签名

M为待签名消息，数字签名结果为(r,s) ，用户密钥对(d,P)。

$1.e=hash(M)\\ 2. 产生随机数K\\因为是随机的,所以对同一消息加密结果也是不同的\\ 3.使用随机数计算(x_1,x_2)=k*G\\ 其实也就是标量积\\ 4.\ r=(e+x_1) \ mod n\\ 5.\ s=((1+d)^{-1} * (k-r*d))\ modn \ n \ne0\\ 6.\ r,s为签名信息$

SM2验签

M为明文，(r,s)为签名结果,用户公钥 P。

$1.e=hash(M)\\ 2.t=(r+s)\ mod n\\ 3.(x,y)=s*G+t*P\\ 4.R=(e+x)mod\ n$

然后计算R等不等于r

推导过程

$s*G+t*P=s*G+(r+s)*P\\ =s*G+(r+s)*d*G\\ =(1+d)*s*G+r*d*G\\ 因为s=((1+d)^{-1} * (k-r*d))\\ 带回到式子里\\ =(k-r*d)*G+r*d*G\\= k*G\\ 证明完毕$

SM2加密

SM2加密数据使用公钥(x,y)进行加密，加密结果为c1c3c2部分算法中定义为c1c2c3,下面介绍密文中各个结构实际含义

c1: 随机数K与G(x,y)的多倍点运算结果，结果也是一个点，记录为(kx,ky)
c2: 实际密文值
c3：使用SM3对于 kx||data||ky的hash值，在解密时校验解密结果是否正确

我们一个个来看

$c_1=k*G\\ G为基点，是个坐标(x,y)\\ 那么c_1的结果其实也是个坐标\\$

再来看c2

$c_2=密钥流xor\ data\\$

密钥流的计算逻辑如下：

1. 复用计算c1时产生的随机数k
2. 计算 kpk(x,y),得到kpx，kpy
3. 根据data的长度与kpx,kpy生成与data等长的密钥流，用于c2的最终计算

整体密钥流计算采用KDF方法计算，KDF可以理解成根据输入的因子，产生期望长度的数据流，目前直流的KDF计算采用HASH方法。SM2中的KDF使用的是SM3摘要。

c3是一个SM3的摘要值，作用是用于解密时校验解密出的原文数据的正确性

c3 = HASH(kpx,data,kpy)

在解密时需要在解密出原文后计算HASH值做最后确认，确认一致后认定解密成功，不一致则解密失败。

SM2 解密数据

SM2的解密流程实际是根据c1计算出加密时使用的密钥流，使用密文数据与密钥流进行异或得到数据明文，后续在确认计算出的摘要值与密文中c3是否一致。

1. 从密文中分离出 c1(x,y)
2. 使用私钥d与c1进行多倍点运算，得到计算结果 (cx,cy)，d·c1(cx,cy)
3. 根据c2长度计算密钥流，KDF(cipherlen,cx,cy)
原文 = 密钥流 (异或) 密文
1. 基于以上的运算结果的cx,cy与得到的原文
2. SM3(cx,计算得到的明文,cy)
3. 对比计算结果与c1，一致解密成功，不一致则解密失败