SM2算法原理

SM2算法1、算法原理椭圆曲线算法是通过方程确定的，SM2算法采用的椭圆曲线方程为：y2=x3+ax+b在SM2算法标准中，通过指定a、b系数，确定了唯一的标准曲线。下面通过图示展示算法原理。请参见下图：图1椭圆曲线算法原理上图为方程：y2=x3–x的曲线。1、P点为基点；2、通过P点做切线，交与点2P点，在2P’点做竖线，交与2P点，2P点即为P点的2倍点；3、进一步，P点和2P点之间做直线，交与3P’点，在3P’点做竖线，交与3P点，3P点即为P点的3倍点；4、同理，可以计算出P点的4、5、6、…倍点；5、如果给定图上Q点是P的一个倍点，请问Q是P的几倍点呢？6、直观上理解，正向计算一个倍点是容易的，反向计算一个点是P的几倍点则困难的多。在椭圆曲线算法中，将倍数d做为私钥，将Q做为公钥。2、椭圆曲线系统参数Fp上椭圆曲线系统参数包括：a)域的规模q=p，p是大于3的素数；b)(选项)一个长度至少为192的比特串SEED；c)Fp中的两个元素a和b，它们定义椭圆曲线E的方程：y2=x3+ax+b；d)基点G=(xG;yG)∈E(Fp)，G̸=O；e)基点G的阶n(要求：n2191且n4p1=2)；f)(选项)余因子h=#E(Fp)=n。3、密钥对的生成输入：一个有效的Fq(q=p且p为大于3的素数，或q=2m)上椭圆曲线系统参数的集合。输出：与椭圆曲线系统参数相关的一个密钥对(d;P)。a)用随机数发生器产生整数d∈[1;n−2]；b)G为基点，计算点P=(xP;yP)=[d]G；c)密钥对是(d;P)，其中d为私钥，P为公钥。4、加密算法及流程设需要发送的消息为比特串M，klen为M的比特长度。为了对明文M进行加密，作为加密者的用户A应实现以下运算步骤：A1：用随机数发生器产生随机数k∈[1,n-1]；A2：计算椭圆曲线点C1=[k]G=(x1,y1)，按本文本第1部分4.2.8和4.2.4给出的细节，将C1的数据类型转换为比特串；A3：计算椭圆曲线点S=[h]PB，若S是无穷远点，则报错并退出；A4：计算椭圆曲线点[k]PB=(x2,y2)，按本文本第1部分4.2.5和4.2.4给出的细节，将坐标x2、y2的数据类型转换为比特串；A5：计算t=KDF(x2∥y2,klen)，若t为全0比特串，则返回A1；A6：计算C2=M⊕t；A7：计算C3=Hash(x2∥M∥y2)；A8：输出密文C=C1∥C2∥C3。图2加密算法流程5、解密算法及流程设klen为密文中C2的比特长度。为了对密文C=C1∥C2∥C3进行解密，作为解密者的用户B应实现以下运算步骤：B1：从C中取出比特串C1，按本文本第1部分4.2.3和4.2.9给出的细节，将C1的数据类型转换为椭圆曲线上的点，验证C1是否满足椭圆曲线方程，若不满足则报错并退出；B2：计算椭圆曲线点S=[h]C1，若S是无穷远点，则报错并退出；B3：计算[dB]C1=(x2,y2)，按本文本第1部分4.2.5和4.2.4给出的细节，将坐标x2、y2的数据类型转换为比特串；B4：计算t=KDF(x2∥y2,klen)，若t为全0比特串，则报错并退出；B5：从C中取出比特串C2，计算M′=C2⊕t；B6：计算u=Hash(x2∥M′∥y2)，从C中取出比特串C3，若u̸=C3，则报错并退出；B7：输出明文M′。图3解密算法流程6、数字签名及流程设待签名的消息为M，为了获取消息M的数字签名(r,s)，作为签名者的用户A应实现以下运算步骤：A1：置M=ZA∥M；A2：计算e=Hv(M)，按本文本第1部分4.2.3和4.2.2给出的细节将e的数据类型转换为整数；A3：用随机数发生器产生随机数k∈[1,n-1]；A4：计算椭圆曲线点(x1,y1)=[k]G，按本文本第1部分4.2.7给出的细节将x1的数据类型转换为整数；A5：计算r=(e+x1)modn，若r=0或r+k=n则返回A3；A6：计算s=((1+dA)−1·(k−r·dA))modn，若s=0则返回A3；A7：将r、s的数据类型转换为字节串，消息M的签名为(r,s)。图4数字签名流程7、签名验证及流程为了检验收到的消息M′及其数字签名(r′,s′)，作为验证者的用户B应实现以下运算步骤：B1：检验r′∈[1,n-1]是否成立，若不成立则验证不通过；B2：检验s′∈[1,n-1]是否成立，若不成立则验证不通过；B3：置M′=ZA∥M′；B4：计算e′=Hv(M′)，将e′的数据类型转换为整数；B5：按本文本第1部分4.2.2给出的细节将r′、s′的数据类型转换为整数，计算t=(r′+s′)modn，若t=0，则验证不通过；B6：计算椭圆曲线点(x′1;y′1)=[s′]G+[t]PA；B7：将x′1的数据类型转换为整数，计算R=(e′+x′1)modn，检验R=r′是否成立，若成立则验证通过；否则验证不通过。图5签名验证流程