2021SC@SDUSC

SM2算法概述

SM2椭圆曲线公钥密码算法是我国自主设计的公钥密码算法，包括SM2-1椭圆曲线数字签名算法，SM2-2椭圆曲线密钥交换协议，SM2-3椭圆曲线公钥加密算法，分别用于实现数字签名密钥协商和数据加密等功能。

SM2标准包括总则，数字签名算法，密钥交换协议，公钥加密算法四个部分，并在每个部分的附录详细说明了实现的相关细节及示例。SM2算法主要考虑素域Fp和F2m上的椭圆曲线，分别介绍了这两类域的表示，运算，以及域上的椭圆曲线的点的表示，运算和多倍点计算算法。然后介绍了编程语言中的数据转换，包括整数和字节串，字节串和比特串，域元素和比特串，域元素和整数，点和字节串之间的数据转换规则。

详细说明了有限域上椭圆曲线的参数生成以及验证，椭圆曲线的参数包括有限域的选取，椭圆曲线方程参数，椭圆曲线群基点的选取等，并给出了选取的标准以便于验证。最后给椭圆曲线上密钥对的生成以及公钥的验证，用户的密钥对为（s，sP），其中s为用户的私钥，sP为用户的公钥，由于离散对数问题从sP难以得到s，并针对素域和二元扩域给出了密钥对生成细节和验证方式。总则中的知识也适用于SM9算法。

国密算法对比见下图：（来源见水印）

SM2与RSA算法

SM2算法和RSA算法都是公钥密码算法，SM2算法与RSA算法不同的是，SM2算法是基于椭圆曲线上点群离散对数难题，相对于RSA算法，256位的SM2密码强度已经比2048位的RSA密码强度要高。

对比：（来源见水印）

安全性对比：

速度对比：

SM2算法数学基础

主要内容来源是《密码学原理与实践 第三版》

明文x（也就是初态w0）经过Nr轮加密后变成y,每一轮的加密通过轮函数g完成，g的实现需要两个输入子密钥K以及上一轮加密的结束状态。

解密过程

我的理解上图中的y其实是子密钥K，该函数的输入是子密钥K以及中间状态w。

 单射函数（来源：单射_百度百科）

 SPN（代换-置换网络）是特殊的一类迭代密码。

第一轮的输入需要初态w0与K1先异或得出u1再输入S盒。

最后一轮不应用置换，需要Nr轮加密，但需要用到K(Nr+1)个子密钥。

ECC算法

SM2非对称加密算法先从ECC算法开始。
Elliptic Curve Cryptography 椭圆曲线满足函数：y²=x³+ax+b (4a³+27b² $\ne$ 0) ，
限定条件保证曲线不包含奇点。
椭圆曲线算法的基本要求：1）给定私钥k和椭圆曲线基点G，容易得到Q=k$\cdot$G；2）给定G和Q，求k的值很难。

ECC算法步骤：

1. 选择椭圆曲线，在椭圆曲线上选择基点G；
2. 生成随机数k（作为私钥），生成公钥Q=k$\cdot$G;
3. 【加密】生成随机数r，明文M，密文C，C=（rG，M+rQ）
4. 【解密】已知C，Q，求解M。M+rQ-k(rG)=M+r$\cdot$k$\cdot$G-k$\cdot$r$\cdot$G=M

SM2公钥加密算法

设：私钥d_B，公钥P_B，其中P_B=d_B$\cdot$G，明文M，解密后明文$\hat{M}$，密文C，C由3部分拼接组成，C${}_1$,C${}_2$,C${}_3$，明文长度klen。

公钥加密步骤：

1. 生成随机数k；
2. 计算C${}_1$=k$\cdot$G；
3. 计算点N（x${}_2$，y${}_2$），N=k$\cdot$P_B；
4. 计算t=KDF(x${}_2$||y${}_2$,klen)，KDF是密钥派生函数，生成和明文等长的t，用于和明文异或运算；
5. 计算C${}_2$=M$⨁$t；
6. 计算C${}_3$=Hash(x${}_2$ || M || y${}_2$)；
7. 拼接得到密文C=（C${}_1$ || C${}_2$ || C${}_3$）。

私钥解密步骤：

1. 拆分密文C，得到C${}_1$,C${}_2$,C${}_3$；
2. 利用C${}_1$得到点N（x${}_2$，y${}_2$），N=d_B$\cdot$C${}_1$=d_B$\cdot$k$\cdot$G=k$\cdot$P_B；
3. 计算t=KDF(x${}_2$||y${}_2$,klen)；
4. 计算明文$\hat{M}$ = C${}_2$$⨁$t；
5. 检验明文 Hash(x${}_2$ || M || y${}_2$)是否等于C${}_3$。

公钥加密算法需要双方共同知道的数据：明文长度，Hash函数，密钥派生函数。

SM2数字签名算法

SM2数字签名算法使用，A想发送消息M，把M和P${}_A$的杂凑值打包，进行非对称加密，得到数字签名（r,s），把M和（r,s）发送出去，收到消息的进行解密，如果正确，就采用M，如果不正确，说明M和P${}_A$存在错误。

签名过程：

1. 置$\bar{M}$=Z${}_A$ || M；
2. e=H${}_v$($\bar{M}$)，长度为v的Hash；
3. 生成随机数k；
4. 计算点N（x${}_1$，y${}_1$）=k$\cdot$G；
5. 计算r=(e+x${}_1$) mod n；
6. 计算s=((1+d${}_A$)${}^{-}1$ $\cdot$(k-r$\cdot$$d_A$)) mod n；
7. 得到的（r,s）是签名，发送M和（r,s）。

验签过程：

1. 验签方收到M${}^{\ast }$和（r${}^{\ast }$,s${}^{\ast }$），先检验r${}^{\ast }$、s${}^{\ast }$是否满足条件；
2. 计算$\bar{M}$${}^{\ast }$=Z${}_A$ || M${}^{\ast }$，Z${}_A$是通过P${}_A$计算得来的，是公开的；
3. 计算e${}^{\ast }$=H${}_v$($\bar{M}$${}^{\ast }$)；
4. 计算t=(r${}^{\ast }$+s${}^{\ast }$) mod n;
5. N${}^{\ast }$=（x${}_1$${}^{\ast }$，y${}_1$${}^{\ast }$）=[s${}^{\ast }$]G+[t]P${}_A$；
6. 计算R=（e${}^{\ast }$+x${}_1$${}^{\ast }$） mod n，如果计算得到的R和收到的r${}^{\ast }$相等，说明验签成功。

数字签名算法主要是验证收到的消息和发消息的人，主要原理是通过对N点的加密和验证，通过验证k$\cdot$G=[s${}^{\ast }$]G+[t]P${}_A$，其中
P${}_A$=d_AG；
S=((1+d${}_A$)${}^{-}1$ $\cdot$(k-r$\cdot$$d_A$)) ；
t=(r${}^{\ast }$+s${}^{\ast }$)；
化简之后得到kG=kG-rd_AG+rd_AG，验证发送方和接收方的点N相同。

SM2密钥交换协议

SM2中的密钥交换协议，通信双方信息传递，计算获得一个由双方共同决定的共享秘密密钥，通信两次或者三次确定这个密钥。

A和B确定一个共享密钥，A用随机数生成$R_A$，发给B，同时利用$R_A$经过一系列运算得到$t_A$。
B也产生一个$R_B$，利用$R_B$经过一系列运算得到$t_B$。B用$R_A$和$t_B$经过一些列计算，得到$S_B$，把$R_B$和$S_B$发送给A，其中$S_B$是可选项，如果发送$S_B$，通信两次就可以确认，如果不发送，还得通信一次。
A收到$R_B$和$S_B$，利用$R_B$和$t_A$经过一系列计算，得到$S_1$，对比$S_1$和$S_B$，如果相等，就说明协商成功，用计算S的中间变量得到$K_A$和$K_B$(这两个相等)就是协商的密钥。

以发送两次为例，具体过程如下：

1. A产生随机数$r_A$；
2. A计算$R_A$=[$r_A$]G=($x_1$,$y_1$)，发送给B；
3. B产生随机数$r_B$；
4. B计算计算$R_B$=[$r_B$]G=($x_2$,$y_2$)；
5. B计算$\overline{x2}$=$2^w$+($x_2$ & ($2^w$-1))；
6. B计算$t_B$=($d_B$+$\overline{x2}$ $\cdot$$r_B$)mod n；
7. B收到$R_A$，用$x_1$计算$\overline{x1}$=$2^w$+($x_1$ & ($2^w$-1))；
8. B计算点V=([h]$\cdot$$t_B$)($P_A$+$\overline{x1}$$R_A$)=($x_v$,$y_v$),其中h是余因子，可以取1，$t_B$只有B知道，剩下的是从A获得的；
9. B计算$K_B$=$KDF$($x_v$||$y_v$||$Z_A$||$Z_B$,klen)；
10. B计算$S_B$=Hash(0x02 || $y_v$ || Hash($y_v$||$Z_A$||$Z_B$||$x_1$||$y_1$||$x_2$||$y_2$))，把$R_B$和$S_B$发送给A；
11. A用自己的$R_A$计算$\overline{x1}$=$2^w$+($x_1$ & ($2^w$-1))；
12. A用$\overline{x1}$结合私钥$d_A$计算$t_A$=($d_A$+$\overline{x1}$ $\cdot$$r_A$)mod n；
13. A用收到的$R_B$计算$\overline{x2}$=$2^w$+($x_2$ & ($2^w$-1))；
14. A用$\overline{x2}$计算点U=([h]$\cdot$$t_A$)($P_B$+$\overline{x2}$$R_B$)=($x_u$,$y_u$);
15. A计算$K_A$=$KDF$($x_u$||$y_u$||$Z_A$||$Z_B$,klen)；
16. A计算$S_1$=Hash(0x02 || $y_u$ || Hash($y_u$||$Z_A$||$Z_B$||$x_1$||$y_1$||$x_2$||$y_2$))，如果$S_1$=$S_B$，则协商成功，公共密钥就是$K_A$、$K_B$，二者相等。

密钥协商算法的关键在于计算的U、V两点相同，假设余因子取1，即需证明：
$t_A$($P_B$+$\overline{x2}$$R_B$)=$t_B$($P_A$+$\overline{x1}$$R_A$)
化简之后，两边项都是：
$d_A$$d_B$G+$\overline{x1}$$r_A$$d_B$G+$\overline{x2}$$r_B$$d_A$G+$\overline{x1}$$\overline{x2}$$r_A$$r_B$G
所以U、V两点相同。

参考

信息安全技术 SM2椭圆曲线公钥密码算法 第2部分：数字签名算法

信息安全技术 SM2椭圆曲线公钥密码算法 第4部分：公钥加密算法

信息安全技术 SM2椭圆曲线公钥密码算法 第3部分：密钥交换协议

网上有很多网友问算法SM2怎么使用？什么是压缩公钥和非压缩公钥？xB和yB这参数是什么？怎么使用SM2做加解密？如何签名和验签？有没有工具来验证下？

这里分享个自己用QT造的一个小工具，简单好用，同时也增加支持了SM3、SM4国密算法。且有详细的过程日志，可以保存为文件。用来对SM2国密算法做加解密和签名，验签,秘钥生成再合适不过了。

需要工具的和使用上的疑问的都可以在留言区留言和评论，工具免费提供。也可以在个人的csdn资源中下载。

完整版的下载：

sm2国密算法工具完整版，包含sm2,sm3和sm4-QT文档类资源-CSDN下载

工具源码的下载：

sm2国密算法加解密、签名、验签QT工具源码（包含sm2,sm3和sm4源代码）-C文档类资源-CSDN下载

加密，解密验证：

其中xB为公钥，如果是压缩公钥，这里填33字节的16进制的压缩公钥，yB不用填，会自动计算得到。如果是非压缩公钥，则xB和yB都需要输入，分别填非压缩公钥的前32字节和后32字节。

其实说白点儿xB和yB合起来才是一串完整的非压缩公钥，只是把公钥分成了两段罢了。

况且，如果是压缩公钥，只需要32字节的xB就够了。哦不，前面的02或03可不能少，要不没法求得yB这后半段公钥。至于为啥公钥要搞成x,y两段，是因为公钥是椭圆曲线上的一个点，一个点包含(x，y)两个分量，这才确定了一个坐标。

为啥给定了x就能求得y,给定y能否求得x呢？当然了，根据椭圆曲线方程：y^2=x^3+ax+b，

a,b都是常数是已知的，给了x就能得到y,给定y就能得到x。有时候压缩公钥别人会给02开头的，有时候会给03开头的。看到这个公式知道了吧，02开头的相当于给你了x,03开头的相当于给你了y.

不压缩的公钥相当于直接给你了(x,y)一个完整坐标。

再说下那个随机数，它是固定长度的32个字节。这随机数也是为了安全。在加密时有用，解密时用不到。这个工具中，加密时之所以随时数为非必填，代码里给你指定了固定的一个值。当然，你可以输入和改变这个随机数。而且，随时数不同，加密后的内容是不同的。但是，解密时，只要私钥pB正确，都能正确的解密出明文，这厉害吧。

日志窗口中可以看到详细的加密，解密日志。 

签名验证：

其中，xB位置输入sm2的压缩公钥，长度为33字节。最前面的02或03代表压缩的参数。明文处输入消息内容，签名的输入框输入待验证的签名信息（签名信息是定长，为64个字节）。点击验签按钮。最后看到日志窗口提示 verify success则是验签成功。

签名和验签的算法过程：

签名过程：
以签名者A为例，计算 ZA=H256(ENTLA ∥ IDA ∥ a ∥ b ∥ xG ∥ yG ∥ xA ∥ yA)，其中ENTLA是IDA的比特长度转换而成的两个字节；
M' = ZA || M，其中M为待签名消息；
e = H256(M')；
用随机数发生器产生随机数k ∈[1,n-1]；
计算椭圆曲线点(x1,y1)=[k]G；
计算r=(e + x1) mod n，若r=0或r+k=n则返回step 4；
计算s = ((k − r * dA) / (1 + dA)) mod n，若s=0则返回step 4；
输出签名（r,s）；
验签过程：
ZA=H256(ENTLA ∥ IDA ∥ a ∥ b ∥ xG ∥ yG ∥ xA ∥ yA)
M′ =ZA ∥ M；
e = H256(M')；
计算t = (r ′ + s ′ ) mod n， 若t = 0，则验证不通过；
计算椭圆曲线点(x1 , y1 ) = [s']G + [t]PA；
计算R = (e + x1 ) mod n，检验R = r是否成立，若成立则验证通过；否则验证不通过；
后续打算用详细代码来展示这一过程。

上述过程中的那么多字母，如果不明白含义容易看晕。

ENTLA ∥ IDA ∥ a ∥ b ∥ xG ∥ yG ∥ xA ∥ yA拿这串来举例：

ENTLA是长度，占两字节，它可能是个变长。

IDA是，用户ID数据。国密sm2使用的是固定的值"1234567812345678"。

a,b,xG和yG是椭圆曲线算法选定的椭圆曲线参数。后面有说明。这几个都是个固定值。

xA和yA这个就是公钥的前后两段。

代码展示ZA=H256(ENTLA ∥ IDA ∥ a ∥ b ∥ xG ∥ yG ∥ xA ∥ yA)这个过程:

    userid_bitlen = userid_len << 3;
    buf[0] = (userid_bitlen >> 8) & 0xFF;
    buf[1] = userid_bitlen & 0xFF;

    // ENTLA|| IDA|| a|| b|| Gx || Gy || xA|| yA

    memcpy(buf+2, userid, userid_len);
    memcpy(buf+2+userid_len, sm2_par_dig, 128);

    memset(buf+2+userid_len+128, 0, 64);
    memcpy(buf+2+userid_len+128+32-xa_len, xa, 32);
    memcpy(buf+2+userid_len+128+32+32-ya_len, ya, 32);

    sm3(buf, 2+userid_len+128+32+32, e);

密钥对的生成:

选取合适的椭圆曲线参数{p,a,b,Gx,Gy,n}；

用随机数发生器产生整数d ∈ [1,n−2]；

计算点P = (xP,yP) = [d]G；

如果P是无穷远点O，goto step 2；

输出密钥对(d,P)，其中d为私钥，P为公钥。

代码过程：

    ......  
    cinstr(p,cfig->p);
	cinstr(a,cfig->a);
    cinstr(b,cfig->b);
	cinstr(n,cfig->n);
	cinstr(x,cfig->x);
    cinstr(y,cfig->y);
	ecurve_init(a,b,p,MR_PROJECTIVE);
    g = epoint_init();
    epoint_set(x,y,0,g); 
    irand(time(NULL));
    bigrand(n,key1);   私钥db
    ecurve_mult(key1,g,g); //计算Pb
    epoint_get(g,x,y);
    *wxlen = big_to_bytes(32, x, (char *)wx, TRUE);
   	*wylen = big_to_bytes(32, y, (char *)wy, TRUE);
	*privkeylen = big_to_bytes(32, key1, (char *)privkey, TRUE);
    ......

p,a,b,Gx,Gy,n为椭圆曲线参数，国密sm2使用的是以下的值的参数。

p是一个大的质数。a,b是方程中的两个常量。Gx,Gy为基点的x,y坐标。n 是基点G的可倍积阶数。

给定n和P，我们运算Q=nP至少需要一个多项式时间。但是如果反过来呢？如果我们知道Q和P，要反过来得到n呢？该问题被认为是对数问题。感兴趣的可以查下什么是对数问题。

查阅《GMT 0003-2012》这份标准文档，有SM2算法的设计背景知识供解读。

 使用素数域256位椭圆曲线
曲线方程：y^2=x^3+ax+b
曲线参数
 p = FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFF 
 a = FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFC 
 b = 28E9FA9E9D9F5E344D5A9E4BCF6509A7F39789F515AB8F92DDBCBD414D940E93 
 n = FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF409 39D54123 
 Gx = 32C4AE2C1F1981195F9904466A39C9948FE30BBFF2660BE1715A4589 334C74C7 
 Gy = BC3736A2F4F6779C59BDCEE36B692153D0A9877CC62A474002DF32E52139F0A0 

需要进一步的了解椭圆曲线算法，可先了解下ECC模型。

 ECC模型
ECC椭圆曲线由很多点组成，这些点由特定的方程式组成的，比如方程式可以是y^2 = x^3 + ax + b，这些点连接起来就是一条曲线，但曲线并不是一个椭圆。

椭圆曲线有个特点，任意两个点能够得到这条椭圆曲线上的另外一点，这个操作称为打点，经过多次（比如d次）打点后，能够生成一个最终点（F）。

在上面的图中，A点称为基点（G）或者生成器。A可以和自己打点从而生成B点，在实际应用的时候，一般有基点就可以了。经过多次打点，就得到了最终点G。

ECC密码学的关键点就在于就算知道具体方程式、基点（G）、最终点（F），也无法知晓一共打点了多少次（d）。

ECC中，打点次数(d)就是私钥，这通常是一个随机数，公钥就是最终点（F)，包含(x，y)两个分量，通常组合成一个数字来传输和存储。

ECC由方程式（比如a、b这样的方程式参数）、基点（G）、质数（P）组成。理论上方程式和各种参数组合可以是任意的，但是在密码学中，为了安全，系统预先定义了一系列的曲线，称为命名曲线（name curve），比如secp256k1就是一个命名曲线。对于开发者而言，在使用ECC密码学的时候，就是选择具体的命名曲线。

SM2算法是ECC算法的一种，相当于是设计了一条ECC命名曲线。

为什么要大力推广国密算法，当然是因为安全了。以下这段摘自网上：

摘自：https://www.cnblogs.com/gzhlt/p/10270913.html

椭圆曲线算法安全性，现状，运用

目前椭圆曲线应用的范围越来越广，在BTC，ETH，EOS，莱特币，DASH等都有使用。密码学中把正向计算是很容易的，但若要有效的执行反向则很困难的算法叫做陷门函数。在RSA的章节中已经介绍过，RSA会随着因式分解的数字变大而变得越有效率，对于私钥增长的需求决定了RSA并不能算作一个完美的陷门函数。事实证明在椭圆曲线中如果你有两个点，一个最初的点乘以K次到达最终点，在你只知道最终点时找到n和最初点是很难的，这就是一个非常棒的trapdoor函数的基础，最近三十年的研究，数学家还没有找到一个方法证实。密码学家Lenstra引进了“全球安全（Global Security）”的概念：假设破解一个228字节的RSA秘钥需要的能量少于煮沸一勺水的能量。那么破解一个228字节的椭圆曲线秘钥需要煮沸地球上所有水的能量。如果RSA要达到一个同样的安全水平，你需要一个2,380字节的秘钥。

最后，以交通部二维码为例，介绍下签名和验签，及工具的使用：

交通部码结构如上图所示。

原始扫码数据内容：

800149240101000004120102030412990102030404002103C28E9FFBFEBC1D1A38644B009A5019F870425145485BF580DCB096DC80BCA7436A8A847E1963930AD71C8D8509DD7FDA36C413158A4DC0E7DD80530DB4B5E1B4FEDFB3217140F255458320F1C0A92B0D4F154DF22D9FFAEE8404EFDDE0447C733230383833303234353539353434373252484E47544253414654353030303530303101000032031FACA38A116BF843720D1A078845FF7BF87C3E62CC17A06A10BAFAEEB4C896B1618B7155012C0015B5A6772E198F0251F1DFBE9CB251ADE475139D12C7BF714CF436A444CB5474F556EF82699C84EC3C74F5C62C7F69872C3477697E2A09D08BEA0224C23A089259618236D5156EA4FCDBE951017E70B2CF19F0D9A27A6ED1E798B0F85850D32F8FEE0902E458BCEFC2AC1CC7AD99478A680B929476AE1AC0236F691D4A65B044C677834DD886 

二维码解析：

80//二维码版本
0149//二维码长度
//发卡机构公钥证书117字节
240101000004120102030412990102030404002103C28E9FFBFEBC1D1A38644B009A5019F870425145485BF580DCB096DC80BCA7436A8A847E1963930AD71C8D8509DD7FDA36C413158A4DC0E7DD80530DB4B5E1B4FEDFB3217140F255458320F1C0A92B0D4F154DF22D9FFAEE8404EFDDE0447C73
xx3038383330323435353935xxxxxxxx//支付账户号16字节
52484E475442********//用户账户号10字节
35303030 //发卡机构代码
35303031//发码平台代码
01//用户账户类型
000032//单次消费金额上限

//支付账户用户公钥33字节的压缩公钥
031FACA38A116BF843720D1A078845FF7BF87C3E62CC17A06A10BAFAEEB4C896B1
618B7155//授权过期时间
012C//二维码有效时间
00//发卡机构自定义域长度，
15//签名格式
//发卡机构授权签名64字节
B5A6772E198F0251F1DFBE9CB251ADE475139D12C7BF714CF436A444CB5474F556EF82699C84EC3C74F5C62C7F69872C3477697E2A09D08BEA0224C23A089259
618236D5//二维码生成时间
15//签名格式
//支付账户用户私钥签名64字节
6EA4FCDBE951017E70B2CF19F0D9A27A6ED1E798B0F85850D32F8FEE0902E458BCEFC2AC1CC7AD99478A680B929476AE1AC0236F691D4A65B044C677834DD886

使用支付账户用户公钥33字节的压缩公钥对支付账户用户私钥签名进行验证：

总结下交通部乘车二维码的验签，过程也很简单。

总共需要三次验签。

第一步验签，验发卡机构证书的签名，使用从系统后台下载到的根公钥。

第二次验签，验发卡机构授权签名，使用发卡机构公钥证书中的公钥。

第三次验签，验支付装好用户私钥签名，使用支付账户用户公钥。

经过这三次的验签成功，则二维码的合法性通过验证。再结合二维码的有效期和授权过期时间，应用类型，白名单等验证等信息验证，就可以判断是否允许乘车啦。