非对称算法

公钥密码仅限于密钥管理和签名等应用，因为性能与对称算法差距三个数量级。

SM9

1、概述：2016年3月公布，基于双线性对的标识密码算法，非对称密码
2、公钥：由用户的标识（邮箱地址、手机号码、QQ号码等）和一组公开的数学参数计算出公钥，省略交换数字证书和公钥的过程
3、私钥：由用户标识、一组公开的数学参数、一个域范围内的秘密值（系统私钥参数）计算出
4、目的：为了降低公开密钥系统中密钥和证书管理的复杂性，让通信双方在不需要交换公私钥信息、不需要保存密钥的目录服务等基础设施、不需要使用第三方提供认证服务的情况下，保证信息交换的安全性并可以验证相互之间的签名。实现用户身份与密钥对直接绑定的密码技术。

《密码标识算法》
相关链接：
http://www.gmbz.org.cn/main/postDetail.html?id=20250123174859

https://std.samr.gov.cn/search/std?q=SM9 国家标准>行业标准

以下参考《GMT 0044-2016》，从第五部分参数定义：
签名私钥生成函数识别符 hid：0x01（数字签名）
加密私钥生成函数识别符 hid：0x02（密钥交换）
加密私钥生成函数识别符 hid：0x03（密钥封装）
注：hid用一个字节表示标识符，由KGC选择并公开

SM9椭圆曲线参数(参考SM9表示密码算法第五部分：参数定义)：

双线性对eid标识符参考《SM9标识密码算法第1部分：总则》，0x04代表R-ate对

//SM9椭圆曲线参数(y^2 = x^3 +ax +b)
//p
B640000002A3A6F1D603AB4FF58EC74521F2934B1A7AEEDBE56F9B27E351457D
//a
0000000000000000000000000000000000000000000000000000000000000000
//b
0000000000000000000000000000000000000000000000000000000000000005
//Gx
93DE051D62BF718FF5ED0704487D01D6E1E4086909DC3280E8C4E4817C66DDDD
//Gy
21FE8DDA4F21E607631065125C395BBC1C1C00CBFA6024350C464CD70A3EA616
//n
B640000002A3A6F1D603AB4FF58EC74449F2934B18EA8BEEE56EE19CD69ECF25
//h
1

SM9_辅助函数

辅助函数H₁()

辅助函数H₂()

由上图可知H<sub>2</sub>和H<sub>1</sub>的区别在于计算H<sub>a</sub>的第一个字节值，对于SM9的椭圆曲线参数，log2 N=256，hlen=8 * 5 * 256 / 32 = 320bit，占用40字节。因此计数器ct只需要[1,2]，第2次计算hash值只截取前8字节。

这里似乎可以使用预计算加速h的计算，待研究。

SM9_数字签名验签算法

系统签名主密钥产生

1.get rand ks∈[1,N-1] //主私钥
2.P_pub-s = [ks]P₂ // P₂为G₂生成元
3.return (ks, P_pub-s) //ks-32byte, 主公钥128byte--二次扩域上的点，有x、y坐标构成，每个坐标有2个分量

keypair(32B, 128B)

用户签名密钥产生

1.t₁ = H₁(ID_A||hid, N) + ks //hid=1
2.if t₁ == 0 重新生成签名主私钥ks，goto step1, 计算t₁，公开主公钥，更新已有用户的签名私钥
3.t₂ = ks * t1^(-1) mod N
4.ds_A = [t₂]P₁ //

ds_A (64B)

数字签名生成

1.产生群G_T中元素 g = e(P₁,P_pub-s)
2.产生随机数r∈[1,N-1]
3.计算群G_T中元素 w = g^r, 将w的数据类型转换为bit串(32*12byte)
4.计算整数h = h₂(M||w, N)
1) t1 = SM3(0x02||M||w||00000002), 取前8byte, 因为hlen = 8 * 5 * ⌈log₂N / 32⌉ = 40 * 8 =320bit = 40byte
2) t2 = SM3(0x02||M||w||00000001)
3) h = (t2||t1) mod (N-1) + 1
5.计算整数l = (r-h) mod N，if l==0，goto 2.
6.计算群G_T中元素S = [l]ds_A //占用65byte，第一个字节是标识04，代表非压缩点
7.return (h,S)

数字签名验证

1.if h^’ ∈ [1, N-1]是否成立，若不成立则验证不通过
2.检验S^' ∈G₁ 是否成立，若不成立则验证不通过
3.计算群G_T中的元素g=e(P₁, P_pub-s)
4.计算群G_T中的元素t=g^h'
5.计算整数h₁ = H₁(ID_A||hid, N)
6.计算群G₂中的元素 P = [h₁]P₂ + P_pub-s
7.计算群G_T中的元素u = e(S', P)
8.计算群G_T中的元素w' = u - t，将w'数据类型转换为比特串
9.计算整数h₂ = H₂(M'||w', N)，检验h₂ = h'是否成立，若成立则验证通过，否则验证不通过

签名验签的预计算值计算

//g=(P1, Ppub-s)，其中P1为系统参数群1生成元，xy各占32byte，Ppub-s为签名主公钥，是二次扩域上点，xy各有两个分量，各占32bytes
//计算数值Demo
//Ppub-s(128bytes)
9f64080b3084f733e48aff4b41b565011ce0711c5e392cfb0ab1b6791b94c408//x_re
29dba116152d1f786ce843ed24a3b573414d2177386a92dd8f14d65696ea5e32//x_rm
69850938abea0112b57329f447e3a0cbad3e2fdb1a77f335e89e1408d0ef1c25//y_re
41e00a53dda532da1a7ce027b7a46f741006e85f5cdff0730e75c05fb4e3216d//y_rm
//P1(64bytes)
93DE051D62BF718FF5ED0704487D01D6E1E4086909DC3280E8C4E4817C66DDDD
21FE8DDA4F21E607631065125C395BBC1C1C00CBFA6024350C464CD70A3EA616
//t=e(P1,Pupub-s)[32*2*3*2=32*12bytes]
4E378FB5561CD0668F906B731AC58FEE25738EDF09CADC7A29C0ABC0177AEA6D28B3404A61908F5D6198815C99AF1990C8AF38655930058C28C21BB539CE000067E0E0C2EED7A6993DCE28FE9AA2EF56834307860839677F96685F2B44D0911F5A1AE172102EFD95DF7338DBC577C66D8D6C15E0A0158C7507228EFB078F42A6B3129A75D31D17194675A1BC56947920898FBF390A5BF5D931CE6CBB3340F66D4C744E69C4A2E1C8ED72F796D151A17CE2325B943260FC460B9F73CB57C9014B38BFFE40A22D529A0C66124B2C308DAC9229912656F62B4FACFCED408E02380FA01F2C8BEE81769609462C69C96AA923FD863E209D3CE26DD889B55E2E3873DB1604A3FCFA9783E667CE9FCB1062C2A5C6685C316DDA62DE0548BAA6BA30038B93634F44FA13AF76169F3CC8FBEA880ADAFF8475D5FD28A75DEB83C44362B43984B87422330D7936EABA1109FA5A7A7181EE16F2438B0AEB2F38FD5F7554E57AAAB9F06A4EEBA4323A7833DB202E4E35639D93FA3305AF73F0F071D7D284FCFB

3）SM9_密钥交换协议算法

系统加密主密钥产生

1.get rand ke∈[1,N-1] //加密主私钥
2.P_pub-e = [ke]P₁ //P₁为N阶循环子群G₁生成元
3.return (ke, P_pub-e) //ke-32byte，加密主公钥64byte--普通点乘

keypair(32B, 64B)

用户加密私钥密钥产生

1.t₁ = H₁(ID_A||hid, N) + ke //hid--1字节
2.if t₁ == 0 重新生成加密主私钥，goto step1, 计算t₁，公开主公钥，更新已有用户的加密私钥
3.t₂ = ke * t1^(-1) mod N
4.de_A = [t₂]P₂ //128byte

de_A (128Byte)

密钥交换协议

设用户A、用户B协商klen比特密钥，A为发起方，B为响应方
用户A
1.计算群G₁中的元素Q_B = [H₁(ID_B || hid, N)]P₁ + P_pub-e //这里是生成临时密钥对(rA, RA)，注意是使用对方ID计算
2.产生随机数r_A ∈ [1, N-1]
3.计算群G₁中的元素 R_A = [r_A]Q_B
4.将R_A发送给用户B

用户B
1.计算群G₁中的元素Q_A = [H₁(ID_A || hid, N)]P₁ + P_pub-e
2.产生随机数r_B ∈ [1, N-1]
3.计算群G₁中的元素 R_B = [r_B]Q_A
4.if R_A not ∈ G₁ return fail
else
计算群G_T中元素g₁ = e(R_A, de_B), g₂ = e(P_pub-e,P₂)^rB , g₃ = g₁^rB , 将g₁ g₂ g₃转化为bit串
5.计算SK_B = KDF(ID_A || ID_B || R_A || R_B || g₁ || g₂ || g₃, klen)
6.(optional)计算 S_B = Hash(0x82 || g₁ || Hash(g₂ || g₃ || ID_A || ID_B || R_A || R_B))
7.send R_B (optional)S_B to 用户A

用户A
5.if R_B not ∈ G₁ return fail
else
计算群G_T中元素g₁‘ = e(P_pub-e, ,P₂)^rA, g₂' = e(R_B, de_A) , g₃ = (g₂')^rA , 将g₁ g₂ g₃转化为bit串
6.(optional)S₁ = Hash(0x82 || g₁' || Hash(g₂' || g₃' || ID_A || ID_B || R_A || R_B)), if S₁ != S_B return fail
7.计算SK_A = KDF(ID_A || ID_B || R_A || R_B || g₁' || g₂' || g₃', klen)
8.(optional)计算 S_A = Hash(0x83 || g₁’ || Hash(g₂‘ || g₃’ || ID_A || ID_B || R_A || R_B))，send to 用户B

用户B
8.(optional)计算S₂ = Hash(0x83 || g₁ || Hash(g₂ || g₃ || ID_A || ID_B || R_A || R_B))，if S₂ != S_A return fail

由上图可知在标准中S1/SA和SB/S2是可选项，在实际运算中，S1/SA和SB/S2的作用是为了辅助密钥对比验证，如果协商的密钥长度很低，比如1字节，假设双方因毛刺发生的1比特翻转，对方翻转概率为1/64，共同协商出错误的密钥。

SM9_密钥封装解封装

封装算法

为了封装klen长度的密钥给用户B，作为封装者的用户A需要执行以下运算步骤：
1.计算群G₁中的元素Q_B=[H₁(ID_B||hid,N)]P₁+P_pub-e
2.产生随机数r∈[1,N-1]
3.计算群G₁中的元素C=[r]Q_B，将C的数据类型转换为比特串
4.计算群G_T中的元素g=e(P_pub-e,P₂)
5.计算群G_T中的元素w=g^r，将w的数据类型转换为比特串
6.计算K=KDF(C||w||ID_B，klen)，若K全为0比特串，返回2
7.输出(K,C)，其中K是被封装的密文，C是封装密文 //只有C给到用户B

解封装算法

用户B收到封装密文C后，为了对比特长度为klen的密钥解封装，需要执行以下运算步骤

1.验证C∈G₁是否成立，若不成立则报错并退出
2.计算群G_T中的元素w'=e(C,de_B)，将w'的数据类型转换为比特串
3.将C的数据类型转换为比特串，计算封装的密文K'=KDF(C||w'||ID_B,klen)，若k'为全0比特串，则报错并退出
4.输出密钥K’

SM9_加解密

注：密钥加解密和密钥封装的主公钥是同一套系统

加密

设需要发送的消息为比特串M，mlen为M的比特长度，k1_len为分组密码算法中密钥K1的比特长度，k2_len为函数MAC(k₂,Z)中密钥K₂的比特长度

为了加密明文M给用户B，作为加密者的用户A应实现以下运算步骤：
1.计算群G₁中的元素Q_B=[H₁(ID_B||hid,N)]P₁+P_pub-e
2.产生随机数r∈[1,N-1]
3.计算群G₁中的元素C=[r]Q_B，将C的数据类型转换为比特串
4.计算群G_T中的元素g=e(P_pub-e,P₂)
5.计算群G_T中的元素w=g^r，将w的数据类型转换为比特串
6.按加密明文的方法进行计算：
a）如果加密明文的方法是基于密钥派生函数的序列密码算法，则
1）计算整数klen=mlen+k₂，然后计算K=KDF(C₁||w||ID_B,klen)，令k₁为K最左边的mlen比特，k₂为剩下的k2_len比特，若k₁为全0比特串，则返回2
2）计算C₂=M⊕k₁
b）如果加密明文的方法是结合密钥派生函数的分组密码算法，则
1）计算整数klen=mlen+k₂，然后计算K=KDF(C₁||w||ID_B,klen)，令k₁为K最左边的mlen比特，k₂为剩下的k2_len比特，若k₁为全0比特串，则返回2
2）计算C₂=Enc(K₂,M)
7.计算C₃=MAC(k₂, C₂)
8.输出密文C=C₁||C₃||C₂

解密

设mlen为密文C=C₁||C₃||C₂中C₂的比特长度，K1_len为分组密码算法中密钥K₁的比特长度，K2_len为函数MAC(K₂,Z)中密钥K₂的比特长度

为了对C进行解密，作为解密者的用户B应实现以下运算步骤：
1.从C中取出C₁，将C₁的数据类型转换为椭圆曲线上的点，验证C₁∈G₁是否成立，若不成立则报错并退出
2.计算群G_T中的元素w'=e(C₁,de_B)，将w'的数据类型转换为比特串
3.按加密明文的方法进行计算：
a）如果加密明文的方法是基于密钥派生函数的序列密码算法，则
1）计算整数klen=mlen+k₂，然后计算K=KDF(C₁||w||ID_B,klen)，令k₁为K最左边的mlen比特，k₂为剩下的k2_len比特，若k₁为全0比特串，则返回2
2）计算M'=C₂⊕k₁
b）如果加密明文的方法是结合密钥派生函数的分组密码算法，则
1）计算整数klen=mlen+k₂，然后计算K=KDF(C₁||w||ID_B,klen)，令k₁为K最左边的mlen比特，k₂为剩下的k2_len比特，若k₁为全0比特串，则返回2
2）计算C₂=Dec(K₂,M)
4.计算u=MAC(k₂',C₂)，对比C中C₃，若不相等，则报错并退出
5.输出明文M'

SM9二次扩域

//二次扩域下的点乘
//k
2
//Gx
85AEF3D078640C98597B6027B441A01FF1DD2C190F5E93C454806C11D8806141 //Gx_1
3722755292130B08D2AAB97FD34EC120EE265948D19C17ABF9B7213BAF82D65B //Gx_2
//Gy
17509B092E845C1266BA0D262CBEE6ED0736A96FA347C8BD856DC76B84EBEB96 //Gy_1
A7CF28D519BE3DA65F3170153D278FF247EFBA98A71A08116215BBA5C999A7C7 //Gy_2

//[k]G-x
513F149AB53E94BB3A0367C61FF87670E025DB30C57F84594E4BA4D7B3C656CF
2A74F8561B91993205EB512576AD56221EA5963F3DA078240D55594FB051EA86
//[k]G-y
776DE41DB0511B8976D69C982DD4757D641487C68D13CBEE7069396C20CD3459
8E3D9EC4E63D5B9F83081FB97B715430C8BFC6F1A1321A89627B9A4E8961C7BD

//以上在OSR_driver里，Gx和Gy，整体U8小端配置到寄存器

//[n-1]G
//sm9-p
B640000002A3A6F1D603AB4FF58EC74521F2934B1A7AEEDBE56F9B27E351457D
//y_1 = sm9-p - Gx_1
9EEF64F6D41F4ADF6F499E29C8CFE0581ABBE9DB7733261E6001D3BC5E6559E7
//y_2 = sm9-p - Gx_2
7F1D8AAD70909BE90358F1D02240062433CC3A0248DED72FEBB879EC33CE6F22

SM9双线性对计算

//g = e(P1, P2)，P1群的生成元P1，
//主公钥128byte--二次扩域上的点，有x、y坐标构成，每个坐标有2个分量

安全实现方案

双线性对运算

将对运算e(C, deA)转化为等价实现e(C, deA1)*e(C, deA2)

//计算g = e(C, deA), C为素数基域上的点，deA为二次扩域上的点，g为12次扩域上的点 
1.r = rand[1, N-1]
2.Q = [r]P2 //Q为二次扩域上的点(Qx0||Qx1, Qy0||Qy1)，128B  //循环群G2的点是二次扩域Fp2的点
3.R = (Qx, (p-Qy0)||(p-Qy1)) = (Qx, -Qy)
4.e(C,deA + R)*e(C, Q)
  =e(C,deA + R + Q) //R和Q互为负点
  =e(C, deA)

SM9加速（预计算）

可以发现，如果所有sm9计算都围绕在一个长期不变、稳定的系统主密钥对情况下，对于签名/验签，加解密/密钥封装/密钥交换，可以提前计算e(Ppube, P2)和e(P1, Ppubs)。

RSA

理论上加解密性能不确定，在实际在在电子签名场景中，签名性能远远低于验签，因为一般E=65537，因此模幂运算签名会很慢。

RSA-CRT（Chinese Remainder Theorem）
目的：为了加速私钥运算。一般接近4倍，如模幂可并行，则接近8倍
公钥：（e，n）
私钥：（d，n）
私钥CRT：（p、q、dp、dq、u），其中，dp=e^(-1) mod (p-1)；dq=e^(-1) mod (q-1)；u=q^(-1) mod p；e-1=d (u=qInv=q^(-1) mod p)，此外，pinv=p^(-1) mod q
RSA计算c^d mod n：
m1 = c^(dp) mod p
m2 = c^(dq) mod q
h = qInv * (m1 - m2) mod p
c = m2+h*q;

注：qinv、h、c的计算使用到Garner's formula

已知：p，q，e，非CRT私钥d可以直接计算：d=e^-1 mod ((p-1)(q-1))
已知：p，dp，公钥e可以直接计算：e=dp^-1 mod (p-1)
已知：q，dq，公钥e可以直接计算：e=dq^-1 mod (q-1)

中国剩余定理（Chinses Remainder theorem）
定义：设两两互素的模数n1,n2,...,nm ∈ N，以及任意整数a1,a2,...,am∈Z，并满足N＝n1n2...*nm，以下方程组必有解x：

x ≡ a1 (mod n1)
x ≡ a2 (mod n2)
...
x ≡ am (mod nm)

x ≡ a1n’1d1 + a2n’2d2 + ... + amn’mdm (mod N)
where n’i = N/ni and di ≡ ni-1 (mod ni)

已知(cd mod p, cd mod q)，可求cd mod N, N=p*q

//RSA2048
//e
10001
//d
58D83FB05C894A8A7CCD708B9E6DA8515E06009AC2D736A00DD2D40C552A037BECA9D30EBA86A6985D003AED2D1D233D540BBD19A13730317C4FCC18EAF171B4765E3E0809BBCAF2936EB1DD3168160174169935CB4EEBBC77B78FFA79A83467F34C2E6C93ECA3FFE528DA4E91D850BC0333D432E93682EBE7528918F920DFA0CA65B8DAC5E216A297AB4C82A35B040E95E4E95F3DC1FF71FBCE0338F8020C2DD03F0DC423FFDB4F6CD0C116E4D53248E91ED36189921D2D20F996B3D06CCF0634F1A0D68E8CC18B98E348B11EB8BEAF5F49F4DD4FE917EC2682298924B29FC5ABF1E2C751286399F2B3318980C7408AE2E73969248A9953D28F405F946D3F01
//n
F6A32EDA0C98C1D74E984DFFFD26AD5101BA6952B5D995E580AE8FD2A48C1BD310A1B30EFB497D57EAC0ABE92F6406E1485C7CFA84375CA81587294D06191F08AD0263D4B585E80A0BA3687D4D8674DE897FED6575C56EE75049A5CD44D26F63960936D59AC6920CC3CDADD75BF174349D042853408EBFBE8723D518BF7A537ABDD7F82952EAAF6226856F8C28783A2CBE85D6275C6EE089E22EC11F771F0488B04780F5B263454DB13C77188A641D5C2FA8A9248910129EEC71A2E03C05FF5BE3E83D244ABD8B89BB2274BA71D5850471F7285CF743DE7328CC74CCA7918195812153623A587B57A0AE25C5A4B440AE9181ABAA7C5B09901B47F461C09986F3

//p
FEA137FD595620504DE3CCEC7F99CB6542EB70000EF68AEE4A877321CC504B2073BF16E2FC867F95A0772126BE073BB93A08EB36E90973892B51DF96BD8739B179E3CCB1D479BA1A64CD266B5C7940410F978DD9403C122F9505FB2E101989650525F2E70607DCCD6F438476DE4ABEDFC84FAD8F253F8CCB6343620DA5578E91
//q
F7F6F437708C87628AD6DAC60134C16F52CAE67FB5E767B2068538EBEF64EE27203312DABCC2522CEAAF7F5405A90EC4687BF3B59E13E865ABE258DF687431CF800DBEDE09F6F4D33F451103F6CDDA51C36EBD656329066AA1C2A8578FF79E0D7BD0306898DC95253BF1BDB5FB94F461B41792E1272E3FA06A419CAA1C554743
//dp=eInv mod p-1
3B06744C2E6160AC3CE209A6E90D65B0DB8A68341B43DB80D1960482593263B7EA1CE9D944608942CE27CF6F83AD7992BE7942CD3FC809184B0A77A221DD2EEA8D2ED94C7FCC97EF765E78017B364046D4AE751B5F608D76AA3CF0B504D6669B1C4E67B856158C81B2C11BFBD21BD1935E83D9DFCCEAA6609F6A0758D2733181
//dq=eInv mod q-1
968C7B6E05896CD1699655318E9DE72B9DCACEF38F0FB627A249D46B7AE77EA886A63BB64E9074B00CB50CCB88BC41D901CEF002BEBD3B862F3BB7D5BC677FAE8A02CE75A4FB295DF0B61044A5DE09C546B0BF9105096D79E4487948E081E8962B2C15980BE7312E701CAFA003E54612E3F2C41CAB5B2B0A4C3915D33A6C945D
//u=qInv mod p
896EA479B6B4CD371FF8ED70EE18D2986489D31D310E1F0CC3C10139105538C811F5C355B69C2B3D74AF9F21FAD9C999D6F4B80872476D96557429C1A7C2EF31E5471BBD2AFF3E1480A5239CB1815F61719A3CAB4A1057FE4E934E7C72C4DB4129E124F5BE600F22318963BAFA7EF625C1A5E2B491310391F7774670346D8B73


//m=11223344
//m^d mod n
69717BD50F3E04B30A68FAD9439FCB023631511A3AAD9B472D30D480B79ABF89D5498882E0E0EF05F6CAB3ACDF3B0E41FC91A3C23C5BE7109EB58CF26D618BC9657454FF2CEEEC902C84399FECAD66E33A69571A5472964D52494E5F165A87C64E5B82D3DAC36E59008BF3BA6D52FAEB54FDE27B51A03CADC6D197825BF60502F21CD8C2FC35DF134ABE3D44F460F5565D00831AF21DC939C5926A05A8AC03CFB8702673F2B1819BDF44A4B4100FEA9D214D5E29267E9D5DC9775CE876B0DC608057DD1F70D16AF0E7ED1E12A2A7F9537423605CF9043637917B515EE2144CA9AA1D651EA55632F1D470235A237CFB97597E202F2504D7CCA2840B8969D36F87

//m1=m^dp mod p
E726FD1B53A390F6A482292A2C0D82A9672C8D8D175C67F9E910C1379EDACE7F81FFD9EE6CCC13DF6C46C9B85749301A4991FA059A966F89A66ADB460770EE2C9E8CB92AFA4EB4D56C6534BB0EF83DAF959656B7AB5F47734381BDB31B02892DDED0523049485E59C6BCB139448CAD3E3A39A1DFAB9D73FC2FE661661F56F199
//m2=m^dq mod q
7C98F4FFCEB47BE7A484543FD8AFA96FA872F0C7DF06FE24C445F3FDEA932F31E4DA4994F5112C65A4467BAF645A75ACABBFB9718EB9DEB3E785F25829235D3F64BCC98DED351D9FCA1D2C7540ED3CA5508FC1A7EB8E2469D498AF5091FFA66960D0795D0C368459904D6806975EBACD15B834E5CBB861CD57E91DD694D699A5

//(m1-m2) mod p
6A8E081B84EF150EFFFDD4EA535DD939BEB99CC5385569D524CACD39B4479F4D9D25905977BAE779C8004E08F2EEBA6D9DD240940BDC90D5BEE4E8EDDE4D90ED39CFEF9D0D199735A2480845CE0B010A4506950FBFD123096EE90E628902E2C47DFFD8D33D11DA00366F4932AD2DF27124816CF9DFE5122ED7FD438F8A8057F4
//h=qInv * (m1-m2) mod p
6CDC3647F6DC3050558B99A6F9129DC823102832BE44475E0832C09787A52119B855BBB66C4E64EC2DE9D949B5F62875C1436D4B889BF868F51E9EACD10EE4C0D3D2B7D1E1B26D561D66B257989D76E933818A1CB84C2392C12FB697A053F7191D16D56EF2356DB65575EF90247C3A42510F7D24F0C6BC1FD296127224C1BF76

//h*q
69717BD50F3E04B30A68FAD9439FCB023631511A3AAD9B472D30D480B79ABF89D5498882E0E0EF05F6CAB3ACDF3B0E41FC91A3C23C5BE7109EB58CF26D618BC9657454FF2CEEEC902C84399FECAD66E33A69571A5472964D52494E5F165A87C64E5B82D3DAC36E59008BF3BA6D52FAEB54FDE27B51A03CADC6D197825BF605027583E3C32D81632BA639E9051BB14BE6B48D92531316CB15014C7607BE18D49DD395DCDEFDA055363AFE2904ABB574F0758DA4B797C4BEA9E1F16A904D8D7F211B9B1391839C4D511DCFF19D61BABCAE23939EB50D7611CDBCE2A20E5014A640494CEBC1991FAE984422BB538C1E40CA43C5EB49594C75FF4A9AEDB2D4FCD5E2
//C=m2+h*q
69717BD50F3E04B30A68FAD9439FCB023631511A3AAD9B472D30D480B79ABF89D5498882E0E0EF05F6CAB3ACDF3B0E41FC91A3C23C5BE7109EB58CF26D618BC9657454FF2CEEEC902C84399FECAD66E33A69571A5472964D52494E5F165A87C64E5B82D3DAC36E59008BF3BA6D52FAEB54FDE27B51A03CADC6D197825BF60502F21CD8C2FC35DF134ABE3D44F460F5565D00831AF21DC939C5926A05A8AC03CFB8702673F2B1819BDF44A4B4100FEA9D214D5E29267E9D5DC9775CE876B0DC608057DD1F70D16AF0E7ED1E12A2A7F9537423605CF9043637917B515EE2144CA9AA1D651EA55632F1D470235A237CFB97597E202F2504D7CCA2840B8969D36F87

欧拉定理
对于正整数n，a是任意整数，gcd(a,n)=1，那么a^(Φ(N)) ≡ 1 (mod n)

rsa生成流程：

1.挑选两个不同的大素数p、q，令N=p*q
2.利用Euler函数计算Φ(N)=(p-1)(q-1)
3.挑选一个整数e，满足：1<e<Φ(N)，gcd(e,Φ(N))=1
4.计算d，满足：d*e≡1 (mod Φ(N))
5.(e,N)作为公钥，(d,N)作为私钥

RSAES-OAEP

参考文档《RFC8017》中《PKCS#1 RSA Cryptography Specifications Version 2.2》

结合RSAEP、RSADP、EME-OAEP编码
消息的最大长度：k-2hlen-2 Byte，其中hlen是hash摘要Byte长度，k是接收者的RSA模数Byte
Lable L：标签输入，在这个版本的PKCS#1，L是空字符串NULL
OAEP参数化hash函数和MGF，建议的hash和MFG见附录B
RSAEP：public-key（RSA） encryption primetive
攻击方式：CCA1、CCA2（OAEP能有效抵御）

RSAES-OAEP-ENCRYPT

【Options】
Hash：哈希算法，hlen取决于hash算法输出长度
MGF：掩码生成函数
【Input】
(n, e)：接收者的公钥
M：待加密的原始消息，其长度要求：mLen<=k - 2hlen -2
L：可选标签，关联原始消息，默认值取决于L，如果L不提供，默认为NULL
【Output】
C：密文

算法流程：
1.检查参数有效性
1.1 检查M输入长度结合hash函数，判断是否合法，if mLen > k-2hLen-2 then return "message too long"
1.2 检查关联数据标签L，是否超过hash算法要求的总长度，不满足返回“label too long” （比如sha-1字节长度不超过2⁶⁴ - 1）
2.EME-OAEP编码
2.1 计算lhash=hash(L)，L可为NULL
2.2 生成值为全0的字节串PS，长度为k-mLen-2hLen-2，可为0（当mLen= k-2hLen-2）
2.3 将lhash，PS，0x01，M构造数据块
DB = lhash || PS || 0x01 || M （if mLen=k-2hLen-2， blocks size = k - (hLen+1)）
2.4 get rand seed，randLen = hLen
2.5 dbMask = MGF(seed, k-hLen-1)
2.6 maskedDB = DB xor dbMask
2.7 seedMask = MGF(maskedDB, hLen)
2.8 maskedSeed = seed xor seedMask
2.9 EM = 0x00 || maskedSeed || maskedDB
3.RSA加密
3.1 m=OS2IP(EM)，Octet String to Integer primitive
3.2 c=RSAEP((n,e), m)，计算m^e mod n
3.3 I2OSP(c, k)，Integer to Octet String primitive

EME-OAEP Encoding

下图为编码操作

RSAES-OAEP-DECRYPT

【Options】
Hash：哈希算法，hlen取决于hash算法输出长度
MGF：掩码生成函数
【Input】
C：Cipher
K：接受者的私钥，字节长度k>=2hLen+2
L：可选标签，关联原始消息，默认值取决于L，如果L不支持，默认为NULL，解密用于校验
【Output】
M：Plaintext明文

如果校验失败，输出“decryption error”

算法流程：
1.有效性检查
1.1. 检查关联数据标签L，是否超过hash算法要求的总长度，不满足返回“label too long” （比如sha-1字节长度不超过2⁶⁴ - 1）
1.2. 密文字节长度不等于k，输出"decryption error"，这里应该是指模数要跟n对齐，并非指最高有效位
1.3 if k < 2hLen+2 return "decryption error"
1.4 if C > n, return "decryption error"
2.RSA解密
2.1 C = OS2IP(C)
2.2 m = RSA(k， C
2.3 EM = I2OSP()
3.EME-OAEP解码
3.1 计算lhash=hash(L)，L可为NULL
3.2 对EM拆分：EM = Y || maskedSeed || maskedDB，其中长度分别占比1 || hLen || k-hLen-1
3.2.1 if Y != 0 then return "decryption error"
3.3 seedMask = MFG(maskedDB, hLen)
3.4 seed = maskedSeed xor seedMask
3.5 dbMask = MGF(seed, k-hLen-1)
3.6 DB = maskedDB xor dbMask
3.7 对DB拆分，DB = lhash’ || PS || 0x01 || M
3.7.1 if lhash‘ != lhash then return error
3.7.2 if 单字节 != 0x01 then return error
4.return M

RSAES-PKCS1-v1.5

参考文档《PKCS#1 v1.5 rfc2313》

RSAES-PKCS1-v1.5-ENCRYPT

结合了RSAEP、RSADP、EME-PKCS1-v1.5编码
原始待加密消息：可操作最多k-11字节，k是模数的字节数
填充字节串PS最少8个字节

【Input】
(n, e)：接收者的公钥
M：待加密的原始消息，其长度要求：mLen<=k - 11（11字节长度包括0x00、0x02、0x00、M占用的总长度mLen，PS）
【Output】
C：密文，占用k字节

算法流程：
1.有效性检查
1.1 if mLen > k-11 return "error message too long"
2.EME-PKCS1-v1.5编码
2.1 生成随机数PS（每个元素非0），其占用长度为k-mLen-3（即减去0x00、0x02、0x00、M占用的总长度），最少占用8个字节
2.2 拼接PS、M、填充字节0x00，0x02，形成长k字节的数据块
EM = 0x00 || 0x02 || PS || 0x00 || M
3.RSA加密
3.1 m = OS2IP(EM)
3.2 C = m^e mod N
3.3 C = I2OSP(c, k)
4.return C

RSAES-PKCS1-v1.5-DECRYPT

【Input】
(n, d)：接收者的私钥
C：待解密的密文
【Output】
M：明文，其占用长度最多k-11字节（11字节长度包括0x00、0x02、0x00、M占用的总长度mLen，PS）

算法流程：
1.有效性检查：if Bytelen(C) != k and k<11 then return "decryption error"
2.RSA解密
2.1 C=OS2IP
2.2 m=C^d mod N
2.3 EM = I2OSP(m,k)
3.EME-PKCS1-v1.5解码
EM = 0x00 || 0x02 || PS || 0x00 || M
3.1 if EM[0] != 0x00 return "decryption error"
3.2 if EM[1] != 0x02 return "decryption error"
3.3 if Bytelen(PS)<8 return "decryption error"
3.4 根据PS字串每个字节为非0值特性，拆分出M，即遍历出第2个0x00值后面即为M
4.return M

RSASSA-PSS

参考文档《RFC8017》中《PKCS#1 RSA Cryptography Specifications Version 2.2》

结合了RSASP1、RSAVP1、EMSA-PSS编码

RSASSA-PSS-SIGN

【Input】
(n, d)：签名者的私钥
M：待签名的原始消息，字节串
【Output】
S：签名值，占用k字节（模数bit长度）

算法流程：
1.EMSA-PSS编码
1.1 对消息M处理为一个编码消息EM（长度为ceil(modBit - 1)/8字节，理解为小于等于模数的字节长度），ceil返回大于或等于表达式的整数，EM最多占用modBits-1比特(理解为最高有效位)
EM = EMSA-PSS-ENCODE (M, modBits - 1)
1.2 如果编码操作返回"message too long", return “message too long”
1.3 如果编码操作返回"encoding error", return "encoding error"
2.RSA签名
2.1 m = OS2IP(EM)
2.2 s = RSASP1(K, m)
2.3 S = I2OSP(s, k)
3.return S

EMSA-PSS Encoding

下图为编码操作

EMSA-PSS编码流程

EMSA-PSS-ENCODE(M, emBits)
Options:
Hash：hash函数，hLen为摘要字节长度
MGF：掩码生成函数
sLen：salt，盐值字节长度
Input：
M：待编码的消息，字节串
emBit：整数OS2IP(EM)最大的比特长度，最少8hLen+8sLen+9
Output：
EM：编码后的消息，字节串，占用emLen = ceil(emBits/8)
Error："Encoding error" "message too long"

步骤：
1.if message byte len > hash function require(2^61 -1byte for sha-1)
2.Let mHash = hash(M)，字节串，占用hLen字节
3.if emLen < hLen + sLen + 2 return "encoding error", sLen should be in [0, emLen -hLen -2]
4.generate salt, of sLen, if sLen =0, salt is empty
5.Let M' = (0x)00 00 00 00 00|| 00 00 00 00 || mHash || salt //M字节串，占用8+hLen+sLen，前面8字节初始化为全0，
这里(0x)00 00 00 00 00|| 00 00 00 00对应上图Padding1
6.Let H = hash(M')，占用hLen长度
7.生成PS，值为全0，长度占用为emLen - sLen - hLen - 2，PS的长度可以为0
8.Let DB = PS || 0x01 || salt，DB长度占用emLen - hLen - 1，这里PS || 0x01对应上图Padding2
9.Let dbMask = MFG(H, emLen - hLen -1)
10.Let maskedDB = DB xor dbMask
11.将maskedDB的高位比特（占用8 * emLen-emBits）设置为0
12.EM = maskedDB ||H||0xbc
13.return EM

RSASSA-PSS-VERIFY

【Input】
(n, e)：签名者的公钥
M：待验签的签名值，占用k字节（模数bit长度）
【Output】
S：签名值，占用k字节（模数bit长度）

算法流程：
1.长度检查：
1.1 if ByteLen(S) != k, return "invalid signature"
2.RSA校验
2.1 s = OS2IP(S)
2.2 m = RSAVP1 = s^d mod N
2.3 EM = I2OSP(m ,emLen)，注意如果modBits-1能被8整除，emLen=k-1，否则emLen=k
3.EMSA-PSS校验
3.1 Result = EMSA-PSS-VERIFY(M, EM, modBits - 1)
4.如果result是一致的，return "valid signature"

Data Conversion Primitives

RSASSA-PKCS1-v1.5

参考文档《PKCS#1 v1.5 rfc2313》

结合RSASP1、RSAVP1、EMSA-PKCS1-v1.5编码
验签单元IFSP-RSA1、IFVP-RSA1
RSASSA-PKCS1-v1.5可操作不限制的大数，取决于底层EMSA-PKCS1-v1.5方法的hash函数
如今更推荐使用RSASSA-PSS

RSASSA-PKCS1-v1.5-SIGN

【Input】
(n, d)：签名者的私钥
M：待签名的原始消息，字节串
【Output】
S：签名值，占用k字节（模数bit长度）

流程：
1.EMSA-PKCS1-v1.5编码：操作消息M处理程长度为k字节的EM
EM = EMSA-PKCS1-v1.5-ENCODE(M, k)
1.1 如果编码操作输出"message too long", return "message too long"
1.2 如果编码操作输出"intended encoded message length too short", return "RSA modulus too short"
2.return EM^d mod n

EMSA-PKCS1-v1_5 Encoding

EMSA-PKCS1-v1_5编码流程

EMSA-PKCS1-v1_5-ENCODE(M, emLen)
Options:
Hash：hash函数，hLen为摘要字节长度
Input：
M：待编码的消息，字节串
emLen：编码的字节长度，最少为tLen+11，tLen为DER编码的确定字节串（可认为签名可对空消息进行）
Output：
EM：编码后的消息，字节串，占用emLen = ceil(emBits/8)
Error："Encoding error" "intended encoded message length too short"

步骤：
1.11如果原始消息长度大于Hash所要求长度，return"message too long"，否则，H=Hash(M)
2.根据hash类型，构造T字节串，T=hashAlgID||hash(M)，长度为tLen
3.if em<tLen + 11, return "intended message length too short"
4.创建PS，字节长度为emLen-tLen-3，PS的每个字节值为0xFF，PS占用最少8个字节
5.EM = 0x00 || 0x01 || PS || 0x00 || T，其中T = hashAlgID || hash(M)
6.return EM

RSASSA-PKCS1-v1.5-VERIFY

【Input】
(n, e)：签名者的公钥
M：待验签的原始消息，字节串
S：待验签的签名值，占用字节为模数n字节长度
【Output】
“valid signature” “invalid signature” “message too long” “modulus too short”

流程：
1.如果签名值的长度不为k字节，return "invalid signature"
2.检查Signature是否满足1 < Signature < n
3.EM1 = Signature^e mod n
3.对输入的原始消息M进行EM编码
4.对比公钥运算出来的EM1和对原始消息进行编码的EM2

签名流程

验签流程

MGF1

Mask Generation Functions

依赖于hash函数，未来的版本会在IEEE 1363 和 ANSI X9.44定义其他的掩码生成函数

MFG1(mgfSeed, maskLen)
Options：
Hash：hash函数，hLen标记对应的hash输出字节长度，比如SM3为32字节摘要
Input：
mgfSeed：种子，字节串
maskLen：掩码字节长度，最多2^32 * hLen
Output：
mask：掩码，长度为maskLen字节
Error："mask too long"

流程：
1.if maskLen > 2^32 * hLen, return "mask too long"
2.let T 为空字符串
3.for counter=0 to ceil((maskLen/hLen))-1:
C = I2OSP(counter, 4) //转换counter为4字节的字节串
T = T || hash(mgfSeed || C)
4.mask，对T进行截断，取maskLen长度

f）RSA带公钥的安全模幂

安全模幂运算如下：

z=x^{(d1(1+ek)+d2(1+ek)-k)} mop p

d1(1+e * k)+d2(1+e * k) - k
=(d1+d2) + (d1 * e * k) + (d2 * e * k) - k
=d + e * k * (d1 + d2) - k
=d + e * k * d - k
=d + (e * d)k - k

M^d + (e * d)k - k
=M^d[M^(ed)]^kM^-k
=M^d

x：模幂运算的底数
z：模幂运算的结果
d1：私钥d的一分量（d=d1+d2）
d2：私钥d的另一分量
e：公钥
k：随机数
p：模数

1024bit示例：
//x
11223344
//e
10001
//d
23075234F1770E2356480F0D91ED1F51D823B8C1F23547D40F1871FD9A7193EF0EA1D22508078E76753971597BDB016D2E71CC80F565B5D530B412ACE635AE3EF2ADD0B624071F4CEA9F609E0F65B0289DD173C169729CFE36E7EF4B2033358DE63CF6E4CF9AE5078D43C428BFC38F38F4672F71BC1616EE4711A03BE3E767C1
//d1
23075234F1770E2356480F0D91ED1F51D823B8C1F23547D40F1871FD9A7193EF0EA1D22508078E76753971597BDB016D2E71CC80F565B5D530B412ACE635AE3EF2ADD0B624071F4CEA9F609E0F65B0289DD173C169729CFE36E7EF4B2033358DE63CF6E4CF9AE5078D43C428BFC38F38F4672F71BC1616EE4711A03BE3E76700
//d2
C1

//p即n
B0EAA37021B25702ED99D4DD9CC734B1DD1253722B6350AD6F0B11CBD886C1323D922A6EFF4D2627D88A637D93D13A8EFDC53008E03FFC1C89CF747F62DA3571BEA9A16DE4C65612CE49BDF9A7E5A588BA8F9B4517BEA84DE5A45CF27B53008BB66E08BE903FC9DF71E8D76F4E174A50A8B6648E74EFC45FF4612EB35E960631

//k
FF

----------calc----------
//1+e*k
1+FF00FF
=FF0100

//d1*(1+e*k)
22E46DEA0EBA888C41151D469368C41FA59D6D2CE90504C182DD68A40ED4BCCCB3823EF4B5248EEF8D3AAD2193B8A246C2B0892640F1458511588F4E4BFC5EC661FA15933E993C34BD01ABDCD1F459DE255C401F1BCA93D3D5AF3E43C45E228B8DE4A02AE1B019BD6ABE0DA85B2C8B6D4AABBCA979CBBCED6FB8D5AD483F6380670000

//d2*(1+e*k)
C03FC100

//d1*(1+e*k)+d2*(1+e*k)
22E46DEA0EBA888C41151D469368C41FA59D6D2CE90504C182DD68A40ED4BCCCB3823EF4B5248EEF8D3AAD2193B8A246C2B0892640F1458511588F4E4BFC5EC661FA15933E993C34BD01ABDCD1F459DE255C401F1BCA93D3D5AF3E43C45E228B8DE4A02AE1B019BD6ABE0DA85B2C8B6D4AABBCA979CBBCED6FB8D5AD483F6440A6C100

//t=d1*(1+e*k)+d2*(1+e*k)-k
22E46DEA0EBA888C41151D469368C41FA59D6D2CE90504C182DD68A40ED4BCCCB3823EF4B5248EEF8D3AAD2193B8A246C2B0892640F1458511588F4E4BFC5EC661FA15933E993C34BD01ABDCD1F459DE255C401F1BCA93D3D5AF3E43C45E228B8DE4A02AE1B019BD6ABE0DA85B2C8B6D4AABBCA979CBBCED6FB8D5AD483F6440A6C001

//c=x^t mod n
000FB212D1E54C45D537ADBB5CFAB00E4DA49D791BB3FCF80B6215C7EEE45D8B7B5EAFD126B4F233D2FBF2CD874F5AD275FD8B371A827636E610AF80B3D3A42781CC19B9CF6226CAA904AA379FD88001A3114FC2AFB2161DC27D93CBC8024CAEA9B540B316DDBD8E7A40DD14F17BE0575E1289F1E2101169891D655C69E87BD8

//c=x^d mod n
同上

g）费马素性检测

费马小定理：如果p是素数，a∈[1,p-1]，那么

a^(p-1) ≡ 1 mod p

//判断n是否为素数
1. rand get a, 2<=a<=n-2
2.if gcd(a,n) == 1, goto step3
3.if a^(n-1)=1 mod n, n maybe is prime
4.repeat m times tesp1-step3

n's probability is prime 1-1/2^(m)

软件安全方案

RSA-私钥运算
1.随机延时--抵御计时攻击
2.故障注入--重复比较
3.反向计算--私钥运算后，再对结果公钥运算比较原文正确性

1.对于安全版本的模幂，参考RSA带公钥的安全模幂

RSA-私钥运算非CRT

C^d
=[ (r^-1)^e * C]^d * r
= [(r^-1)^e]^d * C^d * r
=[(r^-1)^e]^d * r *C^d
=r^-1r * C^d

其中，d=d1(1+e * k)+d2(1+e * k) - k，涉及到对底数C的变换，引入随机数(r^-1)^e

RSA-私钥运算CRT

费马小定理（Fermat’s little theorem）:
对于任意素数p和整数a∈Zp，都有
ap ≡ a (mod p)
两边乘a-1： ap-1 ≡ 1 (mod p)

欧拉函数：φ(p)=p-1, p为素数

c^d mod p
= c^(d mod φ(p))^ mod p
= c^d mod (p-1)^ mod p
= c^k (p-1)+r^ mod p
= 1^kc^r mod p
= c^r mod p

基于上述特性，软件安全方案在模幂运算中，引入随机数对指数进行加扰

预计算基本流程：
dp =e-1 mod (p-1)
dq =e-1 mod (q-1)
qInv = (1/q) mod p

私钥运算流程：
m1 = c(dp) mod p ①
m2 = c(dq) mod q ②
h = qInv * (m1 - m2) mod p ③
M = m2+h*q; ④

软件安全方案流程：
流程：
1.引入随机数r，对底数变换cx = c * (r^-1)^e mod N
2.引入随机数k1, h1, p1, y1对①进行变换：
m1 = c(dp+k1h1+k1(p-1-h1)) mod (y1(p-p1)+y1(p1))
m1 = m1 mod p
3.引入随机数k2, h2, q1, y2对②进行变换：
m2 = c(dq+k2h2+k1(q-1-h2)) mod (y1(q-q1)+y1(q1))
m2 = m2 mod q
4.引入随机数u1对③进行变换：
Δ = (m1 - m2) mod (y1(p-p1)+y1(p1))
h = [Δu+Δ(qInv-u1) mod (y1(p-p1)+y1(p1))] mod p
5.计算M：M=r * (m2+h*q) mod N

DH/DHE密钥交换

依赖离散对数问题
用户A：（Xa，Ya），Xa私钥、Ya公钥
用户B：（Xb，Yb），Xb私钥、Yb公钥
双方分别把公钥发送给对方
A方计算k 同余 (Yb)^Xa 同余 (g)^(XaXb) mod p
B方计算k 同余 (Ya)^Xb 同余 (g)^(XaXb) mod p

衍生密钥协商协议：ECDH、X25519

参考标准《ANSI X9.42 2003》 //该标准需要付费购买

域元素（p，q，g）
p：素数
q：p-1的素因子
g：乘法群GF(p)* （包含所有非零元素）的生成元，阶是q

生成公钥pub：pub=g^(priv) mod p
有效性校验：
priv∈[2, q-2]
pub∈[2, p-2]，pub^q = 1 mod p，g^q = 1 mod p

openssl：没有考虑q的情况下，将q设置为p-1

DH是静态协商，DHE是临时协商，本质上是进行协商的公私钥对是否是长期固定还是临时一次性使用的区别。

SM2

国密局2010年公开公钥密码算法，属于ECC类公钥算法。
2017年11月，SM2/3/9称为ISO/IEC国际标准

Weierstrass曲线：y^2 = x^3 + ax + b
点加公式：R = P +Q
Rx = m^2-Px-Qx, Ry = m(Px-Rx)-Py
注：m = (y2-y1)/(x2-x1) => m=(x1^2 + x2^2 + x1 * x2 + a)/(y1 + y2) //斜率
涉及公式：(x-y)(x+y) = x^2 - y^2; x^3-y3 = (x-y)(x^2+y2+xy)

例如求[k]G，最多计算2^r >= k (r次)

设计公开椭圆曲线参数：p、a、b、n、Gx、Gy
私钥32字节，公钥64字节（65字节，前面04代表非压缩格式，压缩格式为33字节（只留x/y坐标），02代表x，03代表

数学介绍：
https://www.jianshu.com/p/090f605f1842/
密钥对生成：Q=d*G

预计算
a）Z = SM3(bitLenofID|| ID|| a || b || Gx || Gy || Xa || Xy)，ID缺省1234567812345678 (16bytes)
b）E = SM3(Z || M)
注：bitLenofID（16bit）只取高位8bit带入计算，即((uint8_t)(byteLenofID>>8U)) & 0xFFu
标准提到：“作为签名者的用户A具有长度为entlenA比特的可辨别标识IDA，记ENTLA是由整数entlenA转换而成的两个字节”，即ID字节长度取值为[0,8191]

椭圆曲线参数
p = FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFF
a = FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFC
b = 28E9FA9E9D9F5E344D5A9E4BCF6509A7F39789F515AB8F92DDBCBD414D940E93
n = FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54123
Gx = 32C4AE2C1F1981195F9904466A39C9948FE30BBFF2660BE1715A4589334C74C7
Gy = BC3736A2F4F6779C59BDCEE36B692153D0A9877CC62A474002DF32E52139F0A0

椭圆曲线的阶（计数），包括无穷远点0
阶（基数）计算：Schoof算法，由曲线方程和P值确定

密钥生成

//通过预计算快速点乘
令k=k1||k2，其中k1和k2分别代表k的高128bit和低128比特。
输入k1，预计算点P=2¹²⁸[G]
调用硬件Shamir点乘方法计算k1[2¹²⁸[G]]+k2[G]
该运算等价于2¹²⁸k1[G]+k2[G] = (2¹²⁸k1+k2)[G] = k[G]

签名

a）选择随机大数k->[1, n-1]
b）计算[k]G=(x1, y1)
c）将32字节的E值转为大数e，计算r = (e+x1) mod n
d）若r=0

//sign
//e=SM3(Z || M)，私钥d
while(1)
{
    k = rand(1,n-1);
    [k]G = (x1,y1);
    r = (e+x1) mod n;
    if(r == 0 || r+k == n) 
        continue;
    s = (1+d)^-1(k-r*d) mod n;//这里d不能为N-1
    if(s == 0) continue;
    return (r,s);
}

//sm2签名防护方案--数据盲化
//Δ和rg为随机值
s=((dA - Δ + 1)*rg + Δ*rg)^(-1) * (k+r)*rg - r mod N
=((dA - Δ + 1 + Δ)*rg)^(-1) * (k+r)*rg - r mod N
=[(dA+1)*rg]^(-1) * (k+r)*rg - r mod N
=(dA+1)^(-1) * rg^(-1) * (k+r)*rg - r mod N
=(dA+1)^(-1) * (k+r) -r mod N
=(dA+1)^(-1) * (k+r) -r*(dA+1)^(-1) * (dA+1) mod N
=(dA+1)^(-1) * (k+r - r*(dA+1)) mod N
=(dA+1)^(-1) * (k+r - r*dA - r) mod N
=(dA+1)^(-1) * (k- r*dA) mod N

验签

//verify
if(publickey is not on ECC and not be 0(加法群的单位元)) return fail;
if(r and s are not in [1,n-1]) return fail;
t = (r+s) mod n;
if(t == 0) return fail;
X(x1,y1) = [S]G + [t]P; //这里，[s]G + [t*dA]G = [k]G, 即s+t*dA = k
R = (e+x1) mod n;
if(R == r) return succeed;
    else return fail;

//验签安全方案
e mod n //加扰 引入假动作（不管e是否满足小于n）
x mod n //加扰 引入假动作（不管x是否满足小于n）

加密

KDF(S)是由hash函数hash(m)构造的密钥导出函数。若要生成l比特的密钥，则将KDF(S)定义为hash值hash(S||i)的级联，i是计数器，初值为1，每计算一次hash值后递增，直至取得l比特的hash值的级联后为止。

//Enc
//已知明文M，密文接收者公钥Pa
k = get_rand_from(1,n-1)
C1 = [k]G //64字节
Z = [h]Pa //h=1,该步骤省略
[k]Pa = (x2,y2) //[k]Pa = [k * dA]G
t = KDF(x2 || y2)
C2 = M XOR t
C3 = SM3(x2 || M || y2) //32字节,认证作用
return C1 || C3 || C2  //比原文多97字节

//安全方案
使用硬件版本安全点乘

SM2密文结构，一般输出C1C3C2，C1代表曲线的点，占64字节，有些协议会多一个字节0x04，代表未压缩的点，C3是密文的SM3哈希值占32字节，用于完整性校验，C2是密文，字节长度同明文。

SM2_KDF = KDF(Z||ct), ct是32bit的计数器，初始值0x00000001

解密

//dec
//已知密文C1C2C3，解密者私钥da
check_C1_On_ECC(C1)
Z = [h]C1 //h==1
if Z == 无穷远点 return fail //略
[da]C1 = (x2,y2) //[dA]C1 = [dA * k]G
t = KDF(x2 || y2)
m = C2 XOR t
u = SM3(x2 || m || y2)
if (u != C3) return fail
return m

密钥协商

依赖椭圆曲线离散对数难题

SM2密钥协商相比ECDH，增加了一些额外要求：
1.双方需生成各自的临时密钥对（一次性使用），并交换各自临时公钥？
2.双方提供各自ID并交换（用来生成Z值，参与认证值的生成）
3.协商完成后可进行认证，验真协商是否成功（可选）

协商计算前，双方都应先准备好如下材料或动作
1.己方（永久或持久）公私钥对（dA，PA），并将公钥PA发送给对方，同时获得对方公钥PB
2.己方临时公私钥对（rA。RA），并将临时公钥RA发送给对方，同时获得对方临时公钥RB
3.己方ID，并将其发送给对方，同时获得对方的ID。双方协商密钥长度klen

注：ID用来生成各自的Z值ZA和ZB，Z值生成同SM2签名的预计算1

双方生成临时密钥对，交换各自公钥、交换各自ID

//协商流程，用户A为发起方，用户B为响应方
//A方：公私钥对(dA，PA)、临时公私钥对(rA，RA)，【B方ID、B方公钥Pb,对方临时公钥Rb】,ZA,ZB
//B方：公私钥(dB,PA)、临时公私钥对(rB,RB)，【A方ID、A方公钥Pa，对方临时公钥Rb】，ZA，AB

//用户A
x1' = 2^w+(RA_x & (2^w - 1)) //w=127，取低位127bit，高位1byte异或0x80
tA = (dA + x1' * rA) mod n
if RB not on sm2_curve 
    return fail
else
    x2' = 2^w + (RB_x & (2^w - 1))
U = [h*tA](PB + [x2']RB) = (xU, yU)
if U is 0 
    return fail
else
    KA = KDF(xU||yU||ZA||ZB, klen)
(optional)
{
S1 = Hash(0x02 || yU || Hash(xU||ZA||ZB||RA_x||RA_y||RB_x||RB_y))
if S1 == SB return exchange_key success else fail
SA = Hash(0x03 || yU || Hash(xU||ZA||ZB||RA_x||RA_y||RB_x||RB_y))
}

//用户B
x2' = 2^w + (RB_x & (2^w - 1))
tB = (dB + x2' * rB) mod n
if RA not on sm2_curve 
      return fail
else
      x1' = 2^w + (RA_x & (2^w -1))
V = [h*tB](PA + [x1']RA) = (xV,yV)
if V is 0 
      return fail
else
      KB = KDF(xV||yV||ZA||ZB, klen)
SB = Hash(0x02 || yV || Hash(xV||ZA||ZB||RA_x||RA_y||RB_x||RB_y))
return RB (optional)SB to 用户A
(optional)
{
S2 = Hash(0x03 || yV || Hash(xV||ZA||ZB||RA_x||RA_y||RB_x||RB_y))
if S2 == SA return exchange_key success else return fail
}

签名速度：ECC > RSA
验签：RSA > ECC （因为RSA验签的e值很小）

Demo

//密钥交换
//IDa
31323334353637383132333435363738
//Z=SM3(bitLenofID|| ID|| a || b || Gx || Gy || Xa || Xy)
=SM3(0080||31323334353637383132333435363738||FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFC||28E9FA9E9D9F5E344D5A9E4BCF6509A7F39789F515AB8F92DDBCBD414D940E93||32C4AE2C1F1981195F9904466A39C9948FE30BBFF2660BE1715A4589334C74C7||BC3736A2F4F6779C59BDCEE36B692153D0A9877CC62A474002DF32E52139F0A0||160E12897DF4EDB61DD812FEB96748FBD3CCF4FFE26AA6F6DB9540AF49C94232||4A7DAD08BB9A459531694BEB20AA489D6649975E1BFCF8C4741B78B4B223007F)
=SM3(008031323334353637383132333435363738FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFC28E9FA9E9D9F5E344D5A9E4BCF6509A7F39789F515AB8F92DDBCBD414D940E9332C4AE2C1F1981195F9904466A39C9948FE30BBFF2660BE1715A4589334C74C7BC3736A2F4F6779C59BDCEE36B692153D0A9877CC62A474002DF32E52139F0A0160E12897DF4EDB61DD812FEB96748FBD3CCF4FFE26AA6F6DB9540AF49C942324A7DAD08BB9A459531694BEB20AA489D6649975E1BFCF8C4741B78B4B223007F)
=3B85A57179E11E7E513AA622991F2CA74D1807A0BD4D4B38F90987A17AC245B1

//Sponsor
//dA
81EB26E941BB5AF16DF116495F90695272AE2CD63D6C4AE1678418BE48230029
//ZA
3B85A57179E11E7E513AA622991F2CA74D1807A0BD4D4B38F90987A17AC245B1
//rA
D4DE15474DB74D06491C440D305E012400990F3E390C7E87153C12DB2EA60BB3
//RA
64CED1BDBC99D590049B434D0FD73428CF608A5DB8FE5CE07F15026940BAE40E//x1
376629C7AB21E7DB260922499DDB118F07CE8EAAE3E7720AFEF6A5CC062070C0//t1
//[S1]
D3A0FE15DEE185CEAE907A6B595CC32A266ED7B3367E9983A896DC32FA20F8EB
//[SA]
18C7894B3816DF16CF07B05C5EC0BEF5D655D58F779CC1B400A4F3884644DB88

//dB
785129917D45A9EA5437A59356B82338EAADDA6CEB199088F14AE10DEFA229B5
//PB
6AE848C57C53C7B1B5FA99EB2286AF078BA64C64591B8B566F7357D576F16DFB
EE489D771621A27B36C5C7992062E9CD09A9264386F3FBEA54DFF69305621C4D
//ZB
79C988D63229D97EF19FE02CA1056E01E6A7411ED24694AA8F834F4A4AB022F7
//rB
7E07124814B309489125EAED101113164EBF0F3458C5BD88335C1F9D596243D6
//RB
ACC27688A6F7B706098BC91FF3AD1BFF7DC2802CDB14CCCCDB0A90471F9BD707
2FEDAC0494B2FFC4D6853876C79B8F301C6573AD0AA50F39FC87181E1A1B46FE
//[S2]
18C7894B3816DF16CF07B05C5EC0BEF5D655D58F779CC1B400A4F3884644DB88
//[SB]
D3A0FE15DEE185CEAE907A6B595CC32A266ED7B3367E9983A896DC32FA20F8EB

//k
6C89347354DE2484C60B4AB1FDE4C6E5

//取x1'=2^127+(x1&(2^127 - 1)) //x1为RA的x坐标，保留低127bit
x1'=2^127 + CF608A5DB8FE5CE07F15026940BAE40E=CF608A5DB8FE5CE07F15026940BAE40E
//tA=(dA+x1'*rA) mod n
tA=(dA+CF608A5DB8FE5CE07F15026940BAE40E*D4DE15474DB74D06491C440D305E012400990F3E390C7E87153C12DB2EA60BB3) mod FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54123
=(81EB26E941BB5AF16DF116495F90695272AE2CD63D6C4AE1678418BE48230029+BB7D99D62C08B4264BECE7B73443579195F483A72E7239F2993AD3692DC40DE0) mod n
=3D68C0C06DC40F17B9DDFE0093D3C0E4969ED1124A187FA8AD02F81E3C11CCE6

//取x2'=2^127+(x2&(2^127 - 1)) //x2为RB的x坐标，保留低127bit
x2=2^127 + 7DC2802CDB14CCCCDB0A90471F9BD707=FDC2802CDB14CCCCDB0A90471F9BD707
//U=[h*tA](PB + x2'*RB) //h=1
=tA*PB + [tA*x2' mod n]RB
=tA*PB + [3D68C0C06DC40F17B9DDFE0093D3C0E4969ED1124A187FA8AD02F81E3C11CCE6*FDC2802CDB14CCCCDB0A90471F9BD707 mod n]RB
=tA*PB + [20B34E8F94D2B962B9CC15ADA9F3E7C83601A2C02E4BACF0D6610B668A9AAE3F]RB
=[3D68C0C06DC40F17B9DDFE0093D3C0E4969ED1124A187FA8AD02F81E3C11CCE6]PB +[20B34E8F94D2B962B9CC15ADA9F3E7C83601A2C02E4BACF0D6610B668A9AAE3F]RB
=C558B44BEE5301D9F52B44D939BB59584D75B9034DD6A9FC826872109A65739F||3252B35B191D8AE01CD122C025204334C5EACF68A0CB4854C6A7D367ECAD4DE7

//KA=KDF(Ux||Uy||ZA||ZB, klen)
//KA_16byte_0
=SM3(C558B44BEE5301D9F52B44D939BB59584D75B9034DD6A9FC826872109A65739F||3252B35B191D8AE01CD122C025204334C5EACF68A0CB4854C6A7D367ECAD4DE7||3B85A57179E11E7E513AA622991F2CA74D1807A0BD4D4B38F90987A17AC245B1||79C988D63229D97EF19FE02CA1056E01E6A7411ED24694AA8F834F4A4AB022F7||0x00000001)
=6C89347354DE2484C60B4AB1FDE4C6E579391A21FA6CB72AE8754EC21AD8B703
=6C89347354DE2484C60B4AB1FDE4C6E5//取前面16byte


//下面获取KB
...


总结:
1.己方：已方临时公钥x坐标低127bit，高bit异或上1，结合己方私钥和乙方临时私钥，计算t
2.己方：对方临时公钥x坐标低127bit，高bit异或上1，结合对方公钥和对方临时公钥，计算U
3.通过U和双方Z值计算KDF

基于SM2算法的无证书及隐式证书公钥机制

文档：《GM/T 0130-2023》

注：H_A计算的公钥参数为系统主公钥坐标

隐式证书：无需CA签名，使用通过声明公钥验证（即公钥还原数据）

ks：KGC秘密，用于派生伪随机数
ms：系统主私钥（隐式证书系统中，为CA的签名私钥）
P_Pub：系统主公钥（隐式证书系统中，为CA的签名公钥）
P_A：用户A的实际公钥
W_A：用户A的声明公钥（隐式证书系统中，为隐式证书中的公钥还原数据）==无证书身份公钥==，使用主公钥进行验证合法性
U_A：用户A生成的部分公钥
t_A：KGC为用户A生成的部分私钥
d_A：用户私钥==无证书身份私钥==

流程：
1.KGC：初始化，ms，P_pub，并公开P_pub
2.用户：生临时公私钥d_A‘ = rand()，U_A = [d_A']G
3.用户：将身份信息ID_A和临时公钥U_A给到KGC
4.KGC：生成对应用户的声明公钥W_A = U_A + [w]G （w = rand()）
5.KGC：基于声明公钥，系统参数、KGC主公钥生成私钥分片t_A = w + z * ms mod N，其中z = H₂₅₆(xw_A||yw_A||H_A) mod N
6.用户：基于实际私钥d_A，生成真正私钥d_A = t_A + d_A mod N和公钥P_A
7.用户：基于声明公钥W_A，主公钥P_pub，生成真正公钥P_A = W_A + [z]P_pub，其中，z=H₂₅₆(xW_A || yW_A || H₂₅₆(xw_A||yw_A||H_A) ) mod N

签名

验签

加密

P_A是引入了主公钥计算的公钥，理解为在KGC下变换另一个公钥进行SM2加密

解密

ECDSA

参考标准：Public Key Cryptography for the Financial Services Industry. The Elliptic Curve Digital Signature Algorithm(ECDSA). 2005. s.l. : ANS X9.62–2005
参考标准：《sec1-v2 2009.pdf》https://www.secg.org/sec1-v2.pdf
上述两个标准是一致的

签名方案，是DSA的椭圆曲线版本

曲线参数可参考密码小工具或者PKE_UHP工程

1、计算Z（according to SEC 1-V2 2009）

//以spec160k1为例，SHA1("abc")=023097D223405D8228642A477BDA255B32AADBCE4BDA0B3F7E36C9DA7
//曲线nbit=161位
//若hash长度比nbit小，实际运算大数就是hash值
//若hash长度比nbit大，实际运算大数：从左边开始截取nbit，注意2是0010开始，非10开始
//Z
0x4612fa44680bb0450c8548ef7b44ab66555b79c9 //数值从右往左4bit转换   《FIPS 186-5》


/* 以下忽略 历史描述
//(0x023097D223405D8228642A477BDA255B32AADBCE4BDA0B3F7E36C9DA7)转2进制，注意实际大数(4bit一个块)
000000100011000010010111110100100010001101000000010111011000001000101000011001000010101001000111011110111101101000100101010110110011001010101010110110111100111001001011110110100000101100111111011111100011011011001001110110100111
//从左往右截取161bit
00100011000010010111110100100010001101000000010111011000001000101000011001000010101001000111011110111101101000100101010110110011001010101010110110111100111001001
//转成U8，161比特需要高位补3bit0
00000100011000010010111110100100010001101000000010111011000001000101000011001000010101001000111011110111101101000100101010110110011001010101010110110111100111001001
//转U8
0x04612fa44680bb0450c8548ef7b44ab66555b79c9
0x04612fa44680bb0450c8548ef7b44ab66555b79c
  以上忽略 历史描述 */

//(0x023097D223405D8228642A477BDA255B32AADBCE4BDA0B3F7E36C9DA7)转2进制，注意实际大数(8bit一个块,字节对齐)
000000100011000010010111110100100010001101000000010111011000001000101000011001000010101001000111011110111101101000100101010110110011001010101010110110111100111001001011110110100000101100111111011111100011011011001001110110100111
//从左往右截取161bit
00000010001100001001011111010010001000110100000001011101100000100010100001100100001010100100011101111011110110100010010101011011001100101010101011011011110011100
//转成U8，161比特需要高位补7bit0（相当于右移7bit）
0000000||00000010001100001001011111010010001000110100000001011101100000100010100001100100001010100100011101111011110110100010010101011011001100101010101011011011110011100
//转U8
0x00||04612fa44680bb0450c8548ef7b44ab66555b79c（161bit取21Byte）

2、签名流程

//e=Hash(m)
//z=e从左边截断的Ln个bit构成大数，Ln是曲线阶n的bit长度
while(1)
{
    k = rand(1,n-1);
    [k]G = (x1,y1);  //[k-r]G + [r]G   //[k+1]G
    r = x1 mod n;
    if(r == 0) 
        continue;
    s = k^(-1)*(z+r*dA) mod n; //r=0，r*dA无意义
    if(s == 0) continue;
    return (r,s);//(rf,sf)
}

1.calc e=hash(m)
2.let z be the left most of e
3.get the k randomly chosen from [1,n-1]
4.calc the curve point(x,y)=[k]G，r=x, if r=0 return back to step 3
5.calc s=(z+r*dA)/k(mod n) if s=0 return back to step 3
6.return (r,s)

安全方案：将r和d进行拆分
k^-1(e+r₁d₁+r₂d₂) + k^-1(r₁d₂+r₂d₁)
=k^-1(e+(r₁+r₂)(d₁+d₂))
=k^-1(e+rd) mod n

//硬件算子
Input：消息hash值e, 私钥dA, 曲线参数
Output：签名值rs 
while(1)
{
    e = pre_process(e) //参考SEC1-V2—2009
    k = rand(1,n-1);
    [k]G = (x1,y1);  //1次点乘
    r = x1 mod n; //1次模运算
    if(r == 0) 
        continue;
    s = k^(-1)*(e+r*dA) mod n; //1次模逆，2次模乘，1次模加
    if(s == 0) continue;
    return (r,s);
}

3、验证流程

//使用公钥和消息m，对签名进行验证
//verify
if(publickey is not on ECC and not be 0(无穷远点，加法群的单位元)) return fail;
if(r and s are not in [1,n-1]) return fail;
e = Hash(m);
z = get(z) //e从左边截断的Ln个bit构成大数，Ln是曲线阶n的bit长度
u1 = z * s^(-1) mod n
u2 = r * s^(-1) mod n
[u1]G + [u2]Pa = (x1, y1)
if(X == 无穷远点) return fail;
v = x1 mod n
if(v == r) return succeed;
    else return fail;

z * s^(-1) * G + r * s^(-1) * Q
=z * s^(-1) + r * s^(-1) * dA * G
=[z * s^(-1) + r * s^(-1) * dA]G
=[s^(-1)](z + r * dA) * G
即要[s^(-1)](z + r * dA)等价于[k]

由s = k^(-1)*(z+r*dA) mod n，两边同乘k，除s，得到k=[s^(-1)](z + r * dA) mod n

ECDH

ECDH密钥协商是DH的椭圆曲线版本

基于EC点乘原理：(a * G ) * b = a * (G * b)

原始的ECDH协议里，密钥协商双方分别使用各自的私钥和对方的公钥，这样做有一些不便和危险。例如，若双方都用自己的固定密钥对，那么每次协商出来的密钥都一样，攻击者可以截获很多用相同的协商密钥加密的密文，这增大了破解协商密钥的可能，一旦攻击者得手，那么之前的加密会话密文都会被破解。即便其中一方使用固定的密钥对，另一方每次都实时生成密钥对，也仍然不够安全，因为一旦固定密钥被破解，则协商密钥就被破解了（用固定的私钥和公开的对方公钥即得），之前的密文也就被解密了。

因此推荐的做法是每次密钥协商前，双方各自生成自己的临时密钥对，双方均用临时密钥对进行密钥协商，这样可以最大程度避免上述的缺点。这种修正的方法即ECDHE，其中E是ephemeral的缩写，表示每次都用临时的，且只用一次的临时密钥对。

ECIES

ECIES（Elliptic Curve Integrated Encryption Scheme），即椭圆曲线集成加密方案，它是一种混合的公钥加密方案，内部用到椭圆曲线密钥交换（ECDH）、密钥派生函数（KDF）、对称加密和消息验证码（MAC）。

规定ECIES流程主要的加密标准有SECG SEC-1、ISO/IEC 18033-2、IEEE 1363a和ANSI X9.63。现在描述的是标准ANSI X9.63。在该标准中定义了基于hash算法的KDF函数（即ANSI-X9.63-KDF），规定了采用的对称算法为异或加密，MAC算法为HMAC

ECIES输出的密文由发送方的临时公钥C1、被加密的消息C2、消息验证码C3三部分组成

这里的ECIES使用的椭圆曲线方程为y^2 = x^3 +ax+b，支持这类的曲线如secp曲线、brainpoolp曲线

key pair generation

Standard Diffe-Hellman

Input
1.an EC private key d owned by A
2.an EC private key Q owned by B

Actions
1.Compute the point P=dQ
2.Check P，if P==0 stop
3.Set z=Px， Px is the x-coordinate of P

Output
z∈Fq as the shared secret value

Modified Diffe-Hellman

//同上，唯一不同是
1.Compute the point P=hdQ

hash function

1.使用摘要长度大于等于224bit（28byte）

kdf function

见KDF章节

Encryption Transformation

Input
1.a bit string EncData
2.An EC public key Q owned by receiver
3.(optional)sharedData1, sharedData2, which are shared by the sender and the receiver

Action
1.Generate an ephemeral key pair(de,Qe), corresponding to the EC domain parameters D
2.conver Qe to a bit string QE
3.use DH to derive a shared secret value z∈Fq from de and Q， if error，stop
4.conver z∈Fq to a bit string Z
5.use KDF generate keydata of bit length encdatalen+mackeylen from Z and SharedData1
6.parse keyData： KeyData = EncKey||MacKey//k1||k2
7.compute MaskedEncData=EncData xor EncKey
8.compute the tag MacTag on the bit string: MacData=MaskedEncData||[SharedData2]

Output
QE||MaskedEncData||MacTag

d）Decryption Transformation

Input
1.QE||MaskedEncData||MacTag
2.An EC private key d own by the recipient
3.(optional)SharedData1,SharedData2

Action
1.conver QE to an elliptic Qe'
2.Check public key Qe'
3.use DH z=get_x_coordinate([d]Qe)
4.convert z to a bit string Z
5.use KDF generate keydata of bit length encdatalen+mackeylen from Z and SharedData1
6.parse keyData： KeyData = EncKey||MacKey//k1(encdatalen)||k2(mackeylen)
7.Compute EncData=MaskedEncData xor EncKey
8.hmac(MacKey, MaskedEncData||SharedData2)

Output
if verify pass
    return EncData
else
    return error

//Demo
ECIES

========secp256k1==========
//receiver_pri_key
23CDCED066095AA72DE0192509A1E540DE341C1D4DC3B1DEB8A258A6BA26199C

//receiver_pub_key=[receiver_pri_key]G
E3B2EBEC783BB230F20F336E30FBA3BADD0A3453B4F6DCB77C0462B5166F795A
171C91D560427708ED15DCFF24E858233881AD2478CBA05EC9145836B9C787D9

//sender_tmp_pri_key
998943C47E19596D126BB33AC7C656F764D509F2F39AA9C0A872117B9CBA3D8C

//plain (43byte)
33333320717569636B2062726F776E20666F78206A756D7073206F76657220746865206C617A7944444444


//shared_info for KDF
//shared_info1_2  (51bytes)
A7F359B46855C48A1B672F1C65FB57A8F5581AD4A96AA0637C4D36F44BCDFBA5D0101E5ECBAF6F4FEA3CD2706B459650D9089F

//shared_info for MAC
//shared_info2_1 (5bytes)
6162636465

//hmac_key_byte
0x20

Output=Q||EncData||Hmac

//Q=[sender_tmp_pri_key]G
382A1AABFBD5B501917145D25035027DE977F65E432F0C89B7AD58A25FFF9103EB73E26421182E2F508C5C0A0D65BBDCBB0CD07D62DC628A93F7EE2F0F2B9E8D


==========without s1 s2==========
//KDF

//[sender_tmp_pri_key]receiver_pub_key
=[998943C47E19596D126BB33AC7C656F764D509F2F39AA9C0A872117B9CBA3D8C]*E3B2EBEC783BB230F20F336E30FBA3BADD0A3453B4F6DCB77C0462B5166F795A171C91D560427708ED15DCFF24E858233881AD2478CBA05EC9145836B9C787D9
=DAC75A25D3FCA8F8905FB5079C08FE8B470BD32BE22D50424660DE311DE83598||D37BA38C5D1D390CC5238DBDD404C7ED56BFE24FA1CA242BCDBD2C91EA6B151B

//get Z=coordiate x
DAC75A25D3FCA8F8905FB5079C08FE8B470BD32BE22D50424660DE311DE83598


//Compute Hash_i = H(Z||counter||Shareinfo), counter=00000001, Hash_alg=sha512
//KDF
//H(DAC75A25D3FCA8F8905FB5079C08FE8B470BD32BE22D50424660DE311DE83598||00000001)
AFC610393EDC3CE518BF8B13565B87B6D06A6787781C29F57DBC3EB8EFCFC5E963438D303F3D379BA04DA263E29F9828243D23EB65D652A5C44BB6D82D469574
//H(DAC75A25D3FCA8F8905FB5079C08FE8B470BD32BE22D50424660DE311DE83598||00000002)
AEF21C42354B0C638DCCF5CA1B5E18627EA9674103B65DA1932D78163B6339C75429A245BA82006173E92F25BEC8764404A864623363CF4BD142DC29FE117EBE

//Enc_key = MBS(KDF,sizeof(plain)=43)
AFC610393EDC3CE518BF8B13565B87B6D06A6787781C29F57DBC3EB8EFCFC5E963438D303F3D379BA04DA2

//Cipher = Plain XOR (MBS(KDF,sizeof(plain)=43))
AFC610393EDC3CE518BF8B13565B87B6D06A6787781C29F57DBC3EB8EFCFC5E963438D303F3D379BA04DA2
33333320717569636B2062726F776E20666F78206A756D7073206F76657220746865206C617A7944444444
=9CF523194FA95586739FE961392CE996B6051FA7126944850E9C51CE8ABDE59D0B26AD5C5E474EDFE409E6


//mac_key = MBS(KDF+sizeof(plain)=43, sizepf(mac_key_byte)=32)
63E29F9828243D23EB65D652A5C44BB6D82D469574AEF21C42354B0C638DCCF5
//Mac=Hmac(mac_key,Cipher||ShareInfo2=NULL),hash_alg=sha1
=(63E29F9828243D23EB65D652A5C44BB6D82D469574AEF21C42354B0C638DCCF5, 9CF523194FA95586739FE961392CE996B6051FA7126944850E9C51CE8ABDE59D0B26AD5C5E474EDFE409E6)
=E48FC0BBFAAF26897CE60A541BAFC536640CED52





================================secp256k1 SHA256==================================
//receiver_pri_key
23CDCED066095AA72DE0192509A1E540DE341C1D4DC3B1DEB8A258A6BA26199C

//receiver_pub_key=[receiver_pri_key]G
E3B2EBEC783BB230F20F336E30FBA3BADD0A3453B4F6DCB77C0462B5166F795A
171C91D560427708ED15DCFF24E858233881AD2478CBA05EC9145836B9C787D9

//sender_tmp_pri_key
998943C47E19596D126BB33AC7C656F764D509F2F39AA9C0A872117B9CBA3D8C

//plain (43byte)
33333320717569636B2062726F776E20666F78206A756D7073206F76657220746865206C617A7944444444


//shared_info for KDF
//shared_info1_2  (51bytes)
A7F359B46855C48A1B672F1C65FB57A8F5581AD4A96AA0637C4D36F44BCDFBA5D0101E5ECBAF6F4FEA3CD2706B459650D9089F

//shared_info for MAC
//shared_info2_1 (5bytes)
6162636465

//hmac_key_byte
0x20

Output=Q||EncData||Hmac

//Q=[sender_tmp_pri_key]G
382A1AABFBD5B501917145D25035027DE977F65E432F0C89B7AD58A25FFF9103EB73E26421182E2F508C5C0A0D65BBDCBB0CD07D62DC628A93F7EE2F0F2B9E8D


==========without s1 s2==========
//KDF

//[sender_tmp_pri_key]receiver_pub_key
=[998943C47E19596D126BB33AC7C656F764D509F2F39AA9C0A872117B9CBA3D8C]*E3B2EBEC783BB230F20F336E30FBA3BADD0A3453B4F6DCB77C0462B5166F795A171C91D560427708ED15DCFF24E858233881AD2478CBA05EC9145836B9C787D9
=DAC75A25D3FCA8F8905FB5079C08FE8B470BD32BE22D50424660DE311DE83598||D37BA38C5D1D390CC5238DBDD404C7ED56BFE24FA1CA242BCDBD2C91EA6B151B

//get Z=coordiate x
DAC75A25D3FCA8F8905FB5079C08FE8B470BD32BE22D50424660DE311DE83598


//Compute Hash_i = H(Z||counter||Shareinfo), counter=00000001, Hash_alg=sha256
//KDF
//H(DAC75A25D3FCA8F8905FB5079C08FE8B470BD32BE22D50424660DE311DE83598||00000001)
88ED4CCAF84134FC66360397B35B2CA9081CADE5071B8AC95A767441C8B5CA24
//H(DAC75A25D3FCA8F8905FB5079C08FE8B470BD32BE22D50424660DE311DE83598||00000002)
B8B34FFFF293CAF036AE901E590B4CD39ACCA91C7563247450185F1264FDC2F0
//H(DAC75A25D3FCA8F8905FB5079C08FE8B470BD32BE22D50424660DE311DE83598||00000003)
6B2762EB34DCA0DEA26BA6D29BEE0E1803084CAFD51B21B1C35843B2FA9FFF62

//Enc_key = MBS(KDF,sizeof(plain)=43)
88ED4CCAF84134FC66360397B35B2CA9081CADE5071B8AC95A767441C8B5CA24B8B34FFFF293CAF036AE90

//Cipher = (MBS(KDF,sizeof(plain)=43)) XOR Plain
88ED4CCAF84134FC66360397B35B2CA9081CADE5071B8AC95A767441C8B5CA24B8B34FFFF293CAF036AE90 ^
33333320717569636B2062726F776E20666F78206A756D7073206F76657220746865206C617A7944444444
=BBDE7FEA89345D9F0D1661E5DC2C42896E73D5C56D6EE7B929561B37ADC7EA50D0D66F9393E9B3B472EAD4


//mac_key = MBS(KDF+sizeof(plain)=43, sizepf(mac_key_byte)=32)
1E590B4CD39ACCA91C7563247450185F1264FDC2F06B2762EB34DCA0DEA26BA6
//Mac=Hmac(mac_key,Cipher||ShareInfo2=NULL),hash_alg=sha256
=(1E590B4CD39ACCA91C7563247450185F1264FDC2F06B2762EB34DCA0DEA26BA6, BBDE7FEA89345D9F0D1661E5DC2C42896E73D5C56D6EE7B929561B37ADC7EA50D0D66F9393E9B3B472EAD4)
=BAC23020CBB5A5DA57A9C6B98E739794C8D8023BB0DB2B9C65BBD205C93DA173



==========only with s1==========
//Compute Hash_i = H(Z||counter||Shareinfo1), counter=00000001, Hash_alg=sha256
//KDF
//H(DAC75A25D3FCA8F8905FB5079C08FE8B470BD32BE22D50424660DE311DE83598||00000001||A7F359B46855C48A1B672F1C65FB57A8F5581AD4A96AA0637C4D36F44BCDFBA5D0101E5ECBAF6F4FEA3CD2706B459650D9089F)
AD5ECFBEF03BE969B84FB07A9E0337C93D9493B07C6533BCF82A910D9F97D61F
//H(DAC75A25D3FCA8F8905FB5079C08FE8B470BD32BE22D50424660DE311DE83598||00000002||A7F359B46855C48A1B672F1C65FB57A8F5581AD4A96AA0637C4D36F44BCDFBA5D0101E5ECBAF6F4FEA3CD2706B459650D9089F)
82869BDA29490DAF6A0650F581CD6592D3EA5D5AE14B160B275F420AAF277B5F
//H(DAC75A25D3FCA8F8905FB5079C08FE8B470BD32BE22D50424660DE311DE83598||00000003||A7F359B46855C48A1B672F1C65FB57A8F5581AD4A96AA0637C4D36F44BCDFBA5D0101E5ECBAF6F4FEA3CD2706B459650D9089F)
0651C3D52DED2E9B8FFDC5D0AFF2178AF462BB46C70A63651934B3D4FFBCAAC6

AD5ECFBEF03BE969B84FB07A9E0337C93D9493B07C6533BCF82A910D9F97D61F82869BDA29490DAF6A0650 

//Enc_key = MBS(KDF,sizeof(plain)=43)
AD5ECFBEF03BE969B84FB07A9E0337C93D9493B07C6533BCF82A910D9F97D61F82869BDA29490DAF6A0650

//Cipher = (MBS(KDF,sizeof(plain)=43)) XOR Plain
AD5ECFBEF03BE969B84FB07A9E0337C93D9493B07C6533BCF82A910D9F97D61F82869BDA29490DAF6A0650
33333320717569636B2062726F776E20666F78206A756D7073206F76657220746865206C617A7944444444
=9E6DFC9E814E800AD36FD208F17459E95BFBEB9016105ECC8B0AFE7BFAE5F66BEAE3BBB6483374EB2E4214


//mac_key = MBS(KDF+sizeof(plain)=43, sizepf(mac_key_byte)=32)
F581CD6592D3EA5D5AE14B160B275F420AAF277B5F0651C3D52DED2E9B8FFDC5
//Mac=Hmac(mac_key,Cipher||ShareInfo2=NULL),hash_alg=sha256
=(F581CD6592D3EA5D5AE14B160B275F420AAF277B5F0651C3D52DED2E9B8FFDC5, 9E6DFC9E814E800AD36FD208F17459E95BFBEB9016105ECC8B0AFE7BFAE5F66BEAE3BBB6483374EB2E4214)
=8BB6E853122377B14F9E3F91A8F325ABF1D8D077A757BDB9630DCA97AAE17AF3


==========only with s2==========
//KDF

//[sender_tmp_pri_key]receiver_pub_key
=[998943C47E19596D126BB33AC7C656F764D509F2F39AA9C0A872117B9CBA3D8C]*E3B2EBEC783BB230F20F336E30FBA3BADD0A3453B4F6DCB77C0462B5166F795A171C91D560427708ED15DCFF24E858233881AD2478CBA05EC9145836B9C787D9
=DAC75A25D3FCA8F8905FB5079C08FE8B470BD32BE22D50424660DE311DE83598||D37BA38C5D1D390CC5238DBDD404C7ED56BFE24FA1CA242BCDBD2C91EA6B151B

//get Z=coordiate x
DAC75A25D3FCA8F8905FB5079C08FE8B470BD32BE22D50424660DE311DE83598


//Compute Hash_i = H(Z||counter||Shareinfo), counter=00000001, Hash_alg=sha256
//KDF
//H(DAC75A25D3FCA8F8905FB5079C08FE8B470BD32BE22D50424660DE311DE83598||00000001)
88ED4CCAF84134FC66360397B35B2CA9081CADE5071B8AC95A767441C8B5CA24
//H(DAC75A25D3FCA8F8905FB5079C08FE8B470BD32BE22D50424660DE311DE83598||00000002)
B8B34FFFF293CAF036AE901E590B4CD39ACCA91C7563247450185F1264FDC2F0
//H(DAC75A25D3FCA8F8905FB5079C08FE8B470BD32BE22D50424660DE311DE83598||00000003)
6B2762EB34DCA0DEA26BA6D29BEE0E1803084CAFD51B21B1C35843B2FA9FFF62

//Enc_key = MBS(KDF,sizeof(plain)=43)
88ED4CCAF84134FC66360397B35B2CA9081CADE5071B8AC95A767441C8B5CA24B8B34FFFF293CAF036AE90

//Cipher = (MBS(KDF,sizeof(plain)=43)) XOR Plain
88ED4CCAF84134FC66360397B35B2CA9081CADE5071B8AC95A767441C8B5CA24B8B34FFFF293CAF036AE90 ^
33333320717569636B2062726F776E20666F78206A756D7073206F76657220746865206C617A7944444444
=BBDE7FEA89345D9F0D1661E5DC2C42896E73D5C56D6EE7B929561B37ADC7EA50D0D66F9393E9B3B472EAD4


//mac_key = MBS(KDF+sizeof(plain)=43, sizepf(mac_key_byte)=32)
1E590B4CD39ACCA91C7563247450185F1264FDC2F06B2762EB34DCA0DEA26BA6
//Mac=Hmac(mac_key,Cipher||ShareInfo2=NULL),hash_alg=sha256
=(1E590B4CD39ACCA91C7563247450185F1264FDC2F06B2762EB34DCA0DEA26BA6, BBDE7FEA89345D9F0D1661E5DC2C42896E73D5C56D6EE7B929561B37ADC7EA50D0D66F9393E9B3B472EAD4||6162636465)
=490B384E5C4FF3300DDE70A3663BBE3EBBA306A523402ED595F4F10B4B63B261




==========only with s1 and s2==========
//Compute Hash_i = H(Z||counter||Shareinfo1), counter=00000001, Hash_alg=sha256
//KDF
//H(DAC75A25D3FCA8F8905FB5079C08FE8B470BD32BE22D50424660DE311DE83598||00000001||A7F359B46855C48A1B672F1C65FB57A8F5581AD4A96AA0637C4D36F44BCDFBA5D0101E5ECBAF6F4FEA3CD2706B459650D9089F)
AD5ECFBEF03BE969B84FB07A9E0337C93D9493B07C6533BCF82A910D9F97D61F
//H(DAC75A25D3FCA8F8905FB5079C08FE8B470BD32BE22D50424660DE311DE83598||00000002||A7F359B46855C48A1B672F1C65FB57A8F5581AD4A96AA0637C4D36F44BCDFBA5D0101E5ECBAF6F4FEA3CD2706B459650D9089F)
82869BDA29490DAF6A0650F581CD6592D3EA5D5AE14B160B275F420AAF277B5F
//H(DAC75A25D3FCA8F8905FB5079C08FE8B470BD32BE22D50424660DE311DE83598||00000003||A7F359B46855C48A1B672F1C65FB57A8F5581AD4A96AA0637C4D36F44BCDFBA5D0101E5ECBAF6F4FEA3CD2706B459650D9089F)
0651C3D52DED2E9B8FFDC5D0AFF2178AF462BB46C70A63651934B3D4FFBCAAC6

AD5ECFBEF03BE969B84FB07A9E0337C93D9493B07C6533BCF82A910D9F97D61F82869BDA29490DAF6A0650 

//Enc_key = MBS(KDF,sizeof(plain)=43)
AD5ECFBEF03BE969B84FB07A9E0337C93D9493B07C6533BCF82A910D9F97D61F82869BDA29490DAF6A0650

//Cipher = (MBS(KDF,sizeof(plain)=43)) XOR Plain
AD5ECFBEF03BE969B84FB07A9E0337C93D9493B07C6533BCF82A910D9F97D61F82869BDA29490DAF6A0650
33333320717569636B2062726F776E20666F78206A756D7073206F76657220746865206C617A7944444444
=9E6DFC9E814E800AD36FD208F17459E95BFBEB9016105ECC8B0AFE7BFAE5F66BEAE3BBB6483374EB2E4214


//mac_key = MBS(KDF+sizeof(plain)=43, sizepf(mac_key_byte)=32)
F581CD6592D3EA5D5AE14B160B275F420AAF277B5F0651C3D52DED2E9B8FFDC5
//Mac=Hmac(mac_key,Cipher||ShareInfo2=NULL),hash_alg=sha256
=(F581CD6592D3EA5D5AE14B160B275F420AAF277B5F0651C3D52DED2E9B8FFDC5, 9E6DFC9E814E800AD36FD208F17459E95BFBEB9016105ECC8B0AFE7BFAE5F66BEAE3BBB6483374EB2E4214||6162636465)
=686C508582CD785519A76A59E9379083F3CA4DFB6A0BF1D2E4CB8EC7427ACCBB




================================secp256k1 SM3==================================
//receiver_pri_key
23CDCED066095AA72DE0192509A1E540DE341C1D4DC3B1DEB8A258A6BA26199C

//receiver_pub_key=[receiver_pri_key]G
E3B2EBEC783BB230F20F336E30FBA3BADD0A3453B4F6DCB77C0462B5166F795A
171C91D560427708ED15DCFF24E858233881AD2478CBA05EC9145836B9C787D9

//sender_tmp_pri_key
998943C47E19596D126BB33AC7C656F764D509F2F39AA9C0A872117B9CBA3D8C

//plain (43byte)
33333320717569636B2062726F776E20666F78206A756D7073206F76657220746865206C617A7944444444


//shared_info for KDF
//shared_info1_2  (51bytes)
A7F359B46855C48A1B672F1C65FB57A8F5581AD4A96AA0637C4D36F44BCDFBA5D0101E5ECBAF6F4FEA3CD2706B459650D9089F

//shared_info for MAC
//shared_info2_1 (5bytes)
6162636465

//hmac_key_byte
0x20

Output=Q||EncData||Hmac

//Q=[sender_tmp_pri_key]G
382A1AABFBD5B501917145D25035027DE977F65E432F0C89B7AD58A25FFF9103EB73E26421182E2F508C5C0A0D65BBDCBB0CD07D62DC628A93F7EE2F0F2B9E8D


==========without s1 s2==========
//KDF

//[sender_tmp_pri_key]receiver_pub_key
=[998943C47E19596D126BB33AC7C656F764D509F2F39AA9C0A872117B9CBA3D8C]*E3B2EBEC783BB230F20F336E30FBA3BADD0A3453B4F6DCB77C0462B5166F795A171C91D560427708ED15DCFF24E858233881AD2478CBA05EC9145836B9C787D9
=DAC75A25D3FCA8F8905FB5079C08FE8B470BD32BE22D50424660DE311DE83598||D37BA38C5D1D390CC5238DBDD404C7ED56BFE24FA1CA242BCDBD2C91EA6B151B

//get Z=coordiate x
DAC75A25D3FCA8F8905FB5079C08FE8B470BD32BE22D50424660DE311DE83598


//Compute Hash_i = H(Z||counter||Shareinfo), counter=00000001, Hash_alg=SM3
//KDF
//H(DAC75A25D3FCA8F8905FB5079C08FE8B470BD32BE22D50424660DE311DE83598||00000001)
443DC3B378B234CB4FA82731B21313513FC663B2F8FAD076D2CA6551EA97CF3C
//H(DAC75A25D3FCA8F8905FB5079C08FE8B470BD32BE22D50424660DE311DE83598||00000002)
76A7FC64D6351048F8CCEB32790BB50A65404560C0DA6131D1DAFCB572BE8B33
//H(DAC75A25D3FCA8F8905FB5079C08FE8B470BD32BE22D50424660DE311DE83598||00000003)
3AEB1DD3739DCA104822DB08E9BAF59560ED71D10B2FFF1609C973DDBF8A9E9A

443DC3B378B234CB4FA82731B21313513FC663B2F8FAD076D2CA6551EA97CF3C76A7FC64D6351048F8CCEB 32790BB50A65404560C0DA6131D1DAFCB572BE8B333AEB1DD3739DCA104822DB08E9BAF59560ED71D10B2FFF1609C973DDBF8A9E9A

//Enc_key = MBS(KDF,sizeof(plain)=43)
443DC3B378B234CB4FA82731B21313513FC663B2F8FAD076D2CA6551EA97CF3C76A7FC64D6351048F8CCEB

//Cipher = (MBS(KDF,sizeof(plain)=43)) XOR Plain
443DC3B378B234CB4FA82731B21313513FC663B2F8FAD076D2CA6551EA97CF3C76A7FC64D6351048F8CCEB ^
33333320717569636B2062726F776E20666F78206A756D7073206F76657220746865206C617A7944444444
=770EF09309C75DA824884543DD647D7159A91B92928FBD06A1EA0A278FE5EF481EC2DC08B74F690CBC88AF


//mac_key = MBS(KDF+sizeof(plain)=43, sizepf(mac_key_byte)=32)
32790BB50A65404560C0DA6131D1DAFCB572BE8B333AEB1DD3739DCA104822DB
//Mac=Hmac(mac_key,Cipher||ShareInfo2=NULL),hash_alg=SM3
=(32790BB50A65404560C0DA6131D1DAFCB572BE8B333AEB1DD3739DCA104822DB, 770EF09309C75DA824884543DD647D7159A91B92928FBD06A1EA0A278FE5EF481EC2DC08B74F690CBC88AF)
=C17A7AECCA3FFA80B5DBC1E2B755022988592D642D68B9CDC18A1FFE7805F835



==========only with s1==========

//Compute Hash_i = H(Z||counter||Shareinfo), counter=00000001, Hash_alg=SM3
//KDF
//H(DAC75A25D3FCA8F8905FB5079C08FE8B470BD32BE22D50424660DE311DE83598||00000001||A7F359B46855C48A1B672F1C65FB57A8F5581AD4A96AA0637C4D36F44BCDFBA5D0101E5ECBAF6F4FEA3CD2706B459650D9089F)
B56AD8D7ECA977DA795245B84FC00ACB17914160DFDD0D2E75A2FDB6835458F4
//H(DAC75A25D3FCA8F8905FB5079C08FE8B470BD32BE22D50424660DE311DE83598||00000002||A7F359B46855C48A1B672F1C65FB57A8F5581AD4A96AA0637C4D36F44BCDFBA5D0101E5ECBAF6F4FEA3CD2706B459650D9089F)
BBA6C4C6CF1611C8717A59ABE5002646647C2356CD1D7F0814204BC646CFA882
//H(DAC75A25D3FCA8F8905FB5079C08FE8B470BD32BE22D50424660DE311DE83598||00000003||A7F359B46855C48A1B672F1C65FB57A8F5581AD4A96AA0637C4D36F44BCDFBA5D0101E5ECBAF6F4FEA3CD2706B459650D9089F)
85D971DFDFEE9A627E34AF27BE75B947B7C1C0EABB024CB2AD2F5A4F8050776D

B56AD8D7ECA977DA795245B84FC00ACB17914160DFDD0D2E75A2FDB6835458F4BBA6C4C6CF1611C8717A59 ABE5002646647C2356CD1D7F0814204BC646CFA88285D971DFDFEE9A627E34AF27BE75B947B7C1C0EABB024CB2AD2F5A4F8050776D

//Enc_key = MBS(KDF,sizeof(plain)=43)
B56AD8D7ECA977DA795245B84FC00ACB17914160DFDD0D2E75A2FDB6835458F4BBA6C4C6CF1611C8717A59

//Cipher = (MBS(KDF,sizeof(plain)=43)) XOR Plain
B56AD8D7ECA977DA795245B84FC00ACB17914160DFDD0D2E75A2FDB6835458F4BBA6C4C6CF1611C8717A59
33333320717569636B2062726F776E20666F78206A756D7073206F76657220746865206C617A7944444444
=8659EBF79DDC1EB9127227CA20B764EB71FE3940B5A8605E068292C0E6267880D3C3E4AAAE6C688C353E1D


//mac_key = MBS(KDF+sizeof(plain)=43, sizepf(mac_key_byte)=32)
ABE5002646647C2356CD1D7F0814204BC646CFA88285D971DFDFEE9A627E34AF
//Mac=Hmac(mac_key,Cipher||ShareInfo2=NULL),hash_alg=SM3
=(ABE5002646647C2356CD1D7F0814204BC646CFA88285D971DFDFEE9A627E34AF, 8659EBF79DDC1EB9127227CA20B764EB71FE3940B5A8605E068292C0E6267880D3C3E4AAAE6C688C353E1D)
=CDF90807DCB66D2E881EB76321239DC2DA45A031988EFCCD188E2EB440D44E4E



==========only with s2==========
//Compute Hash_i = H(Z||counter||Shareinfo1), counter=00000001, Hash_alg=SM3
//KDF
//H(DAC75A25D3FCA8F8905FB5079C08FE8B470BD32BE22D50424660DE311DE83598||00000001)
443DC3B378B234CB4FA82731B21313513FC663B2F8FAD076D2CA6551EA97CF3C
//H(DAC75A25D3FCA8F8905FB5079C08FE8B470BD32BE22D50424660DE311DE83598||00000002)
76A7FC64D6351048F8CCEB32790BB50A65404560C0DA6131D1DAFCB572BE8B33
//H(DAC75A25D3FCA8F8905FB5079C08FE8B470BD32BE22D50424660DE311DE83598||00000003)
3AEB1DD3739DCA104822DB08E9BAF59560ED71D10B2FFF1609C973DDBF8A9E9A

443DC3B378B234CB4FA82731B21313513FC663B2F8FAD076D2CA6551EA97CF3C76A7FC64D6351048F8CCEB 32790BB50A65404560C0DA6131D1DAFCB572BE8B333AEB1DD3739DCA104822DB08E9BAF59560ED71D10B2FFF1609C973DDBF8A9E9A

//Enc_key = MBS(KDF,sizeof(plain)=43)
443DC3B378B234CB4FA82731B21313513FC663B2F8FAD076D2CA6551EA97CF3C76A7FC64D6351048F8CCEB

//Cipher = (MBS(KDF,sizeof(plain)=43)) XOR Plain
443DC3B378B234CB4FA82731B21313513FC663B2F8FAD076D2CA6551EA97CF3C76A7FC64D6351048F8CCEB ^
33333320717569636B2062726F776E20666F78206A756D7073206F76657220746865206C617A7944444444
=770EF09309C75DA824884543DD647D7159A91B92928FBD06A1EA0A278FE5EF481EC2DC08B74F690CBC88AF


//mac_key = MBS(KDF+sizeof(plain)=43, sizepf(mac_key_byte)=32)
32790BB50A65404560C0DA6131D1DAFCB572BE8B333AEB1DD3739DCA104822DB
//Mac=Hmac(mac_key,Cipher||ShareInfo2),hash_alg=SM3
=(32790BB50A65404560C0DA6131D1DAFCB572BE8B333AEB1DD3739DCA104822DB, 770EF09309C75DA824884543DD647D7159A91B92928FBD06A1EA0A278FE5EF481EC2DC08B74F690CBC88AF||6162636465)
=65A9D394BC99BBF6FCDFA0A95EBA059497967EB653A7549625A039714CFD7BED


==========with s1 and s2==========

//Compute Hash_i = H(Z||counter||Shareinfo), counter=00000001, Hash_alg=SM3
//KDF
//H(DAC75A25D3FCA8F8905FB5079C08FE8B470BD32BE22D50424660DE311DE83598||00000001||A7F359B46855C48A1B672F1C65FB57A8F5581AD4A96AA0637C4D36F44BCDFBA5D0101E5ECBAF6F4FEA3CD2706B459650D9089F)
B56AD8D7ECA977DA795245B84FC00ACB17914160DFDD0D2E75A2FDB6835458F4
//H(DAC75A25D3FCA8F8905FB5079C08FE8B470BD32BE22D50424660DE311DE83598||00000002||A7F359B46855C48A1B672F1C65FB57A8F5581AD4A96AA0637C4D36F44BCDFBA5D0101E5ECBAF6F4FEA3CD2706B459650D9089F)
BBA6C4C6CF1611C8717A59ABE5002646647C2356CD1D7F0814204BC646CFA882
//H(DAC75A25D3FCA8F8905FB5079C08FE8B470BD32BE22D50424660DE311DE83598||00000003||A7F359B46855C48A1B672F1C65FB57A8F5581AD4A96AA0637C4D36F44BCDFBA5D0101E5ECBAF6F4FEA3CD2706B459650D9089F)
85D971DFDFEE9A627E34AF27BE75B947B7C1C0EABB024CB2AD2F5A4F8050776D

B56AD8D7ECA977DA795245B84FC00ACB17914160DFDD0D2E75A2FDB6835458F4BBA6C4C6CF1611C8717A59 ABE5002646647C2356CD1D7F0814204BC646CFA88285D971DFDFEE9A627E34AF27BE75B947B7C1C0EABB024CB2AD2F5A4F8050776D

//Enc_key = MBS(KDF,sizeof(plain)=43)
B56AD8D7ECA977DA795245B84FC00ACB17914160DFDD0D2E75A2FDB6835458F4BBA6C4C6CF1611C8717A59

//Cipher = (MBS(KDF,sizeof(plain)=43)) XOR Plain
B56AD8D7ECA977DA795245B84FC00ACB17914160DFDD0D2E75A2FDB6835458F4BBA6C4C6CF1611C8717A59
33333320717569636B2062726F776E20666F78206A756D7073206F76657220746865206C617A7944444444
=8659EBF79DDC1EB9127227CA20B764EB71FE3940B5A8605E068292C0E6267880D3C3E4AAAE6C688C353E1D


//mac_key = MBS(KDF+sizeof(plain)=43, sizepf(mac_key_byte)=32)
ABE5002646647C2356CD1D7F0814204BC646CFA88285D971DFDFEE9A627E34AF
//Mac=Hmac(mac_key,Cipher||ShareInfo2=NULL),hash_alg=SM3
=(ABE5002646647C2356CD1D7F0814204BC646CFA88285D971DFDFEE9A627E34AF, 8659EBF79DDC1EB9127227CA20B764EB71FE3940B5A8605E068292C0E6267880D3C3E4AAAE6C688C353E1D||6162636465)
=909E14F4170F8E6BAF56590EF25E9435A926A7C6FEC6C414B3CBB59174C6B243

Ed25519

参考文档《RFC 8032》

Ed25519属于EdDSA签名算法一种，后者使用的椭圆曲线是Edwards curve，即它是DSA签名算法的Edwards curve版本，这种类型的椭圆曲线方程如下：

ax^2 + y^2 = 1 + d * x^2 * y^2 --twisted Edwards曲线，当a=1时，退化为普通Edwards曲线

Curve25519曲线（Ed25519椭圆曲线）：y² = x³ + 486662x²+x，由素数2²⁵⁵-19定义素数域

这里Ed25519使用的曲线各参数如下：

p=0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED  //p=2^255-19 有效比特数255
a=-1
d=0x52036CEE2B6FFE738CC740797779E89800700A4D4141D8AB75EB4DCA135978A3
Gx=0x216936D3CD6E53FEC0A4E231FDD6DC5C692CC7609525A7B2C9562D608F25D51A
Gy=0x6666666666666666666666666666666666666666666666666666666666666658
n=0x1000000000000000000000000000000014DEF9DEA2F79CD65812631A5CF5D3ED //有效比特数253
点(Gx, Gy)是曲线的基点，其阶是素数n。

《RFC 8032》
Ed25519签名系统有11个参数
1）一个奇素数p，椭圆曲线建立在有限域GF(p)上，如Ed25519，p=2^255-19  //得p是256bit
2）一个正整数b，满足2^(b-1) > p  //公钥是b比特，对于Ed25519，b=256
3）有限域GF(p)中的元素用(b-1)比特表示，对Ed25519，元素用255个比特表示
4）一个密码学hash函数H，具有2b比特输出，对Ed25519，H=sha512
5）一个整数c，取值2或3，秘密的EdDSA标量应该是2c倍数，c是余因子的底数为2的对数，对Ed25519，c是3
6）一个整数n，满足c<=n<=b，秘密的EdDSA应该有n+1个bit，且其最高比特总是1，最低c比特总是0，如Ed25519，n即254
7）有限域GF(p)中的一个非平方元素d，通常建议取离0最近的，且能确定一个可接受的曲线的值，如对Ed25519，d=-121665/12666
8）有限域GF(p)中的一个非0元素a，考虑到性能要求，通常建议a=-1 if p mod 4=1，and a=1 if p mod 4 = 3，如Ed25519，a=-1
9）曲线上一点B != (0,1)
10）点B的阶L，是个奇素数，且曲线的阶#E = L * 2^c
11）一个预计算hash函数PH

编码
1.一个整数0<S<L-1，被编码作一个小端的b比特的串ENC(S)，从左到右，s0s1...sn，s0是低位，sn是高位，用字节串表示时，和x25519中一致
2.一个群元素，即曲线上一个点(x,y)，被编码作一个b比特的串ENC(x,y)，其中b-1比特是y的编码，之后的1比特表示x，具体的，该bit为1，则表示x是负的，若为0，则表示x是非负的
3.GF(p)中的负元素定义如下：x和-x都用这里的编码表示时，按从左到右比较大小，若x>-x mod p，则x是负的。等价说，若x数值是奇数，则为负数，反之为非负

b=256
encoding of GF(p) 255-bit little endian encoding of {0,1,...,p-1}
H(x)=SHA512(dom2(phflag, context) || x)

Ed25519密钥生成

从小端方式看，如果最低位1bit不为0，则公钥最高bit写1

1.私钥是一个b比特的串k
2.H(k)=h0h1..h62h63(字节串)
3.s为截取H(k)的前n个bit，然后将前c个bit改为0，再在最后添加一个比特1构成的一个比特大数
4.A=[s]B
5.公钥为Encode(A) //The public key A is the encoding of the point [s]B

Ed25519签名

Input：privkey(32byte)，M(任意字节，包括null)，Ed25519ctx--0 / Ed25519ph--1
Output：(R,S)--64byte

pureEd25519

1) dom2(flag, ctx)=NULL
2) PH(M) = M

Ed25519_ph

1) dom2(flag=1, ctx)="SigEd25519 no Ed25519 collisions"||1||octet(OLEN(ctx))--1byte||ctx
2) PH(M) = sha512(M)

Ed25519_ctx

1) dom2(flag=0,ctx)="SigEd25519 no Ed25519 collisions"||0||octet(OLEN(ctx))--1byte||ctx
2PH(M) = M

以上三种模式，M可以为空，对于ctx模式，ctx长度为[1,255]，对于ph模式，ctx长度为[0,255]

1.h=sha512(privkey)=h₀h₁,...h₆₃，字节串
2.prefix = h[32]||...||h[63]，s=h[0]||...||h[31]
3.r =sha512(dom2(flag, ctx) || prefix || PH(M)), r理解为小端
4.R = [r mod n]G
5.k = sha512(dom2(flag, ctx) || R || A ||PH(M))，结果理解为小端
6.S = (r + (k mod n) * (s mod n)) mod L
7.return (R,S) //S最后一字节的最高有效bit永远是0

驱动优化的地方：
1.启动R = [r mod n]G计算后，直接计算sha512(dom2(flag, ctx)
2.

1.dom2(x,y) = "SigEd25519 no Ed25519 collisions" || octet(x) || octet(OLEN(y)) || y
其中，x∈[0,255]，OLEN(y)<=255，"SigEd25519 no Ed25519 collisions" occupy 32 bytes
2.PH是身份函数，例如PH(M)=SHA512(M)

//Demo ed25519-pure-sign
//privkey
F5E5767CF153319517630F226876B86C8160CC583BC013744C6BF255F5CC0EE5
//message
08B8B2B733424243760FE426A4B54908632110A66C2F6591EABD3345E3E4EB98FA6E264BF09EFE12EE50F8F54E9F77B1E355F6C50544E23FB1433DDF73BE84D879DE7C0046DC4996D9E773F4BC9EFE5738829ADB26C81B37C93A1B270B20329D658675FC6EA534E0810A4432826BF58C941EFB65D57A338BBD2E26640F89FFBC1A858EFCB8550EE3A5E1998BD177E93A7363C344FE6B199EE5D02E82D522C4FEBA15452F80288A821A579116EC6DAD2B3B310DA903401AA62100AB5D1A36553E06203B33890CC9B832F79EF80560CCB9A39CE767967ED628C6AD573CB116DBEFEFD75499DA96BD68A8A97B928A8BBC103B6621FCDE2BECA1231D206BE6CD9EC7AFF6F6C94FCD7204ED3455C68C83F4A41DA4AF2B74EF5C53F1D8AC70BDCB7ED185CE81BD84359D44254D95629E9855A94A7C1958D1F8ADA5D0532ED8A5AA3FB2D17BA70EB6248E594E1A2297ACBBB39D502F1A8C6EB6F1CE22B3DE1A1F40CC24554119A831A9AAD6079CAD88425DE6BDE1A9187EBB6092CF67BF2B13FD65F27088D78B7E883C8759D2C4F5C65ADB7553878AD575F9FAD878E80A0C9BA63BCBCC2732E69485BBC9C90BFBD62481D9089BECCF80CFE2DF16A2CF65BD92DD597B0707E0917AF48BBB75FED413D238F5555A7A569D80C3414A8D0859DC65A46128BAB27AF87A71314F318C782B23EBFE808B82B0CE26401D2E22F04D83D1255DC51ADDD3B75A2B1AE0784504DF543AF8969BE3EA7082FF7FC9888C144DA2AF58429EC96031DBCAD3DAD9AF0DCBAAAF268CB8FCFFEAD94F3C7CA495E056A9B47ACDB751FB73E666C6C655ADE8297297D07AD1BA5E43F1BCA32301651339E22904CC8C42F58C30C04AAFDB038DDA0847DD988DCDA6F3BFD15C4B4C4525004AA06EEFF8CA61783AACEC57FB3D1F92B0FE2FD1A85F6724517B65E614AD6808D6F6EE34DFF7310FDC82AEBFD904B01E1DC54B2927094B2DB68D6F903B68401ADEBF5A7E08D78FF4EF5D63653A65040CF9BFD4ACA7984A74D37145986780FC0B16AC451649DE6188A7DBDF191F64B5FC5E2AB47B57F7F7276CD419C17A3CA8E1B939AE49E488ACBA6B965610B5480109C8B17B80E1B7B750DFC7598D5D5011FD2DCC5600A32EF5B52A1ECC820E308AA342721AAC0943BF6686B64B2579376504CCC493D97E6AED3FB0F9CD71A43DD497F01F17C0E2CB3797AA2A2F256656168E6C496AFC5FB93246F6B1116398A346F1A641F3B041E989F7914F90CC2C7FFF357876E506B50D334BA77C225BC307BA537152F3F1610E4EAFE595F6D9D90D11FAA933A15EF1369546868A7F3A45A96768D40FD9D03412C091C6315CF4FDE7CB68606937380DB2EAAA707B4C4185C32EDDCDD306705E4DC1FFC872EEEE475A64DFAC86ABA41C0618983F8741C5EF68D3A101E8A3B8CAC60C905C15FC910840B94C00A0B9D0
//h
h=sha512(F5E5767CF153319517630F226876B86C8160CC583BC013744C6BF255F5CC0EE5)
=609C888D0EF886D34B6EDEF27FB244AA04B3A49C82260E6AB86E784FF488CCC8||
6990F0F6BEFEB2651705E7F5F6CF2F13C42005C7CA8419B1FD050616F902D258
//对h前面32B进行解码,注意s被更新
out[0] &= 0xF8;            //clear lowest 3 bits
out[bytes - 1] &= 0x7F;    //clear highest 1 bit
out[bytes - 1] |= 0x40;    //set second highest bit as 1
h=sha512(F5E5767CF153319517630F226876B86C8160CC583BC013744C6BF255F5CC0EE5)
=609C888D0EF886D34B6EDEF27FB244AA04B3A49C82260E6AB86E784FF488CC48||
6990F0F6BEFEB2651705E7F5F6CF2F13C42005C7CA8419B1FD050616F902D258
//prefix取低32Byte
prefix =6990F0F6BEFEB2651705E7F5F6CF2F13C42005C7CA8419B1FD050616F902D258
//r =sha512(dom2(flag, ctx) || prefix || PH(M))
r=sha512(NULL||NULL||6990F0F6BEFEB2651705E7F5F6CF2F13C42005C7CA8419B1FD050616F902D258||08B8B2B733424243760FE426A4B54908632110A66C2F6591EABD3345E3E4EB98FA6E264BF09EFE12EE50F8F54E9F77B1E355F6C50544E23FB1433DDF73BE84D879DE7C0046DC4996D9E773F4BC9EFE5738829ADB26C81B37C93A1B270B20329D658675FC6EA534E0810A4432826BF58C941EFB65D57A338BBD2E26640F89FFBC1A858EFCB8550EE3A5E1998BD177E93A7363C344FE6B199EE5D02E82D522C4FEBA15452F80288A821A579116EC6DAD2B3B310DA903401AA62100AB5D1A36553E06203B33890CC9B832F79EF80560CCB9A39CE767967ED628C6AD573CB116DBEFEFD75499DA96BD68A8A97B928A8BBC103B6621FCDE2BECA1231D206BE6CD9EC7AFF6F6C94FCD7204ED3455C68C83F4A41DA4AF2B74EF5C53F1D8AC70BDCB7ED185CE81BD84359D44254D95629E9855A94A7C1958D1F8ADA5D0532ED8A5AA3FB2D17BA70EB6248E594E1A2297ACBBB39D502F1A8C6EB6F1CE22B3DE1A1F40CC24554119A831A9AAD6079CAD88425DE6BDE1A9187EBB6092CF67BF2B13FD65F27088D78B7E883C8759D2C4F5C65ADB7553878AD575F9FAD878E80A0C9BA63BCBCC2732E69485BBC9C90BFBD62481D9089BECCF80CFE2DF16A2CF65BD92DD597B0707E0917AF48BBB75FED413D238F5555A7A569D80C3414A8D0859DC65A46128BAB27AF87A71314F318C782B23EBFE808B82B0CE26401D2E22F04D83D1255DC51ADDD3B75A2B1AE0784504DF543AF8969BE3EA7082FF7FC9888C144DA2AF58429EC96031DBCAD3DAD9AF0DCBAAAF268CB8FCFFEAD94F3C7CA495E056A9B47ACDB751FB73E666C6C655ADE8297297D07AD1BA5E43F1BCA32301651339E22904CC8C42F58C30C04AAFDB038DDA0847DD988DCDA6F3BFD15C4B4C4525004AA06EEFF8CA61783AACEC57FB3D1F92B0FE2FD1A85F6724517B65E614AD6808D6F6EE34DFF7310FDC82AEBFD904B01E1DC54B2927094B2DB68D6F903B68401ADEBF5A7E08D78FF4EF5D63653A65040CF9BFD4ACA7984A74D37145986780FC0B16AC451649DE6188A7DBDF191F64B5FC5E2AB47B57F7F7276CD419C17A3CA8E1B939AE49E488ACBA6B965610B5480109C8B17B80E1B7B750DFC7598D5D5011FD2DCC5600A32EF5B52A1ECC820E308AA342721AAC0943BF6686B64B2579376504CCC493D97E6AED3FB0F9CD71A43DD497F01F17C0E2CB3797AA2A2F256656168E6C496AFC5FB93246F6B1116398A346F1A641F3B041E989F7914F90CC2C7FFF357876E506B50D334BA77C225BC307BA537152F3F1610E4EAFE595F6D9D90D11FAA933A15EF1369546868A7F3A45A96768D40FD9D03412C091C6315CF4FDE7CB68606937380DB2EAAA707B4C4185C32EDDCDD306705E4DC1FFC872EEEE475A64DFAC86ABA41C0618983F8741C5EF68D3A101E8A3B8CAC60C905C15FC910840B94C00A0B9D0)
=C191ED996744E0E280359D6BF0C762179F17EBD84EC4D4DFD287A33AAA58FB2D||
9F16171155E4C109E70579E15790E6EFCDEFB8BA66E21D659140D09356E0D609
//R = [r mod n]G 注意此处模运算hash已认为是小端
r mod n
=9D6E05693D04091651DE266BAB8EFCDEFE69057E17905E709C1E4551117169F2DFB58AA3AA387D2DFD4C44ED8EB179F1762C7F06B9D3580E2E0446799ED91C1 mod 1000000000000000000000000000000014DEF9DEA2F79CD65812631A5CF5D3ED
=D5B57538A9A43A6CDC255B8C040ABB4E174635A018C973D7B9DF09B1F613F57 //注意此处r值默认小端输出
R = [r mod n]G
=[39B6CFFBFC21B42CABAA8A646D56465B3C2C7360E7E266FF080D151055D7EA5]G
=0aab4c900501b3e24d7cdf4663326a3a87df5e4843b2cbdb67cbf6e460fec350//目前小工具没有点乘计算，公钥非直接点乘，最终输出的r
//k = sha512(dom2(flag, ctx) || R || A ||PH(M)), A是公钥
k=sha512(NULL||0aab4c900501b3e24d7cdf4663326a3a87df5e4843b2cbdb67cbf6e460fec350||278117FC144C72340F67D0F2316E8386CEFFBF2B2428C9C51FEF7C597F1D426E||08B8B2B733424243760FE426A4B54908632110A66C2F6591EABD3345E3E4EB98FA6E264BF09EFE12EE50F8F54E9F77B1E355F6C50544E23FB1433DDF73BE84D879DE7C0046DC4996D9E773F4BC9EFE5738829ADB26C81B37C93A1B270B20329D658675FC6EA534E0810A4432826BF58C941EFB65D57A338BBD2E26640F89FFBC1A858EFCB8550EE3A5E1998BD177E93A7363C344FE6B199EE5D02E82D522C4FEBA15452F80288A821A579116EC6DAD2B3B310DA903401AA62100AB5D1A36553E06203B33890CC9B832F79EF80560CCB9A39CE767967ED628C6AD573CB116DBEFEFD75499DA96BD68A8A97B928A8BBC103B6621FCDE2BECA1231D206BE6CD9EC7AFF6F6C94FCD7204ED3455C68C83F4A41DA4AF2B74EF5C53F1D8AC70BDCB7ED185CE81BD84359D44254D95629E9855A94A7C1958D1F8ADA5D0532ED8A5AA3FB2D17BA70EB6248E594E1A2297ACBBB39D502F1A8C6EB6F1CE22B3DE1A1F40CC24554119A831A9AAD6079CAD88425DE6BDE1A9187EBB6092CF67BF2B13FD65F27088D78B7E883C8759D2C4F5C65ADB7553878AD575F9FAD878E80A0C9BA63BCBCC2732E69485BBC9C90BFBD62481D9089BECCF80CFE2DF16A2CF65BD92DD597B0707E0917AF48BBB75FED413D238F5555A7A569D80C3414A8D0859DC65A46128BAB27AF87A71314F318C782B23EBFE808B82B0CE26401D2E22F04D83D1255DC51ADDD3B75A2B1AE0784504DF543AF8969BE3EA7082FF7FC9888C144DA2AF58429EC96031DBCAD3DAD9AF0DCBAAAF268CB8FCFFEAD94F3C7CA495E056A9B47ACDB751FB73E666C6C655ADE8297297D07AD1BA5E43F1BCA32301651339E22904CC8C42F58C30C04AAFDB038DDA0847DD988DCDA6F3BFD15C4B4C4525004AA06EEFF8CA61783AACEC57FB3D1F92B0FE2FD1A85F6724517B65E614AD6808D6F6EE34DFF7310FDC82AEBFD904B01E1DC54B2927094B2DB68D6F903B68401ADEBF5A7E08D78FF4EF5D63653A65040CF9BFD4ACA7984A74D37145986780FC0B16AC451649DE6188A7DBDF191F64B5FC5E2AB47B57F7F7276CD419C17A3CA8E1B939AE49E488ACBA6B965610B5480109C8B17B80E1B7B750DFC7598D5D5011FD2DCC5600A32EF5B52A1ECC820E308AA342721AAC0943BF6686B64B2579376504CCC493D97E6AED3FB0F9CD71A43DD497F01F17C0E2CB3797AA2A2F256656168E6C496AFC5FB93246F6B1116398A346F1A641F3B041E989F7914F90CC2C7FFF357876E506B50D334BA77C225BC307BA537152F3F1610E4EAFE595F6D9D90D11FAA933A15EF1369546868A7F3A45A96768D40FD9D03412C091C6315CF4FDE7CB68606937380DB2EAAA707B4C4185C32EDDCDD306705E4DC1FFC872EEEE475A64DFAC86ABA41C0618983F8741C5EF68D3A101E8A3B8CAC60C905C15FC910840B94C00A0B9D0)
=60F83D247242CB144548DDA50BC649CAB8CD2AD24CF46D7D25F13118E4A96F5C49AF3FD726BA59B012B2D2410214FD60B3924F84AC85312514F08F43EC3BD3D1
//k mod n
=D1D33BEC438FF014253185AC844F92B360FD140241D2B212B059BA26D73FAF495C6FA9E41831F1257D6DF44CD22ACDB8CA49C60BA5DD484514CB4272243DF860 mod 1000000000000000000000000000000014DEF9DEA2F79CD65812631A5CF5D3ED
=3A96A76606CEE099A04A61B43317A9FE8A3F37EBA34209DD4C647D06E08A069
//s mod n
=48CC88F44F786EB86A0E26829CA4B304AA44B27FF2DE6E4BD386F80E8D889C60 mod 1000000000000000000000000000000014DEF9DEA2F79CD65812631A5CF5D3ED
=8CC88F44F786EB86A0E26829CA4B30456C8CB0566FFFAF2733D6BA519B14CAC
//k*s mod n
=3A96A76606CEE099A04A61B43317A9FE8A3F37EBA34209DD4C647D06E08A069 *8CC88F44F786EB86A0E26829CA4B30456C8CB0566FFFAF2733D6BA519B14CAC mod n
=62EC0F6E60EBD05D86DC8AF8F8CE3A97F43CD48C555F1C1221401CFEF05E840
//r+k*s mod n
=D5B57538A9A43A6CDC255B8C040ABB4E174635A018C973D7B9DF09B1F613F57 + 62EC0F6E60EBD05D86DC8AF8F8CE3A97F43CD48C555F1C1221401CFEF05E840 mod n
=38A184A70A900ACA6301E684FCD8F5E4BD936C423EAEC28459F8F50B17153AA，最终输出s值，注意直接小端输出
//RS
=0AAB4C900501B3E24D7CDF4663326A3A87DF5E4843B2CBDB67CBF6E460FEC350||
AA5371B1508F9F4528ECEA23C436D94B5E8FCD4F681E30A6AC00A9704A188A03

C25519与X25519

C25519即Curve 25519，它是Montgomery曲线，曲线方程是v^2 = u^3+Au2+u，具体的，各个参数是：

   p =  2^255 – 19
   A =  486662
   B =  1
   Gx = 9 //u
   Gy = 14781619447589544791020593568409986887264606134616475288964881837755586237401
   order(G) = 2^252 + 0x14def9dea2f79cd65812631a5cf5d3ed     //素数
   h = 8   //余因子

C25519可以转换为twisted Edwards curve y²-x²=1+dx²y²:

(x, y) = (sqrt(-486664)*u/v, (u-1)/(u+1))

C25519用于构建快速密钥协商算法X25519

X25519其实是ECDH的C25519版本，二者非常相似，区别在于后者的点乘发生了变化，输入点和输出点都只有x坐标，于是公钥只有x坐标，协商使用的点乘也只有输出x坐标。因为去除了y坐标及其计算，于是X25519需要的存储空间更少，性能更高。

X25519的安全级别是O(2128)，2017年和X448一起被NIST批准作为美国联邦政府标准算法。

X25519中，充分考虑了当前主流CPU是大端的事实，其大数表示采用字节小端方式，例如，若私钥用字节序列表示是
D8375C6C3E8A4611ED1487D9F2E044277B98A2AD3C44A39D859F92A67096E750
那么其对应的大数是：
0x50E79670A6929F859DA3443CADA2987B2744E0F2D98714ED11468A3E6C5C37D8
这么做的好处是可直接转换为U32类型之间小端表示的大数形式，这是大数处理最常采用的方式，从而省去字节串到大数之间的转换，有利于提升性能。以上面的私钥字节序列表示为例，按U32数组方式去访问它，得到的是：
0x6C5C37D8,0x11468A3E,0xD98714ED,……,0x9DA3443C,0xA6929F85,0x50E79670

椭圆曲线

维尔斯特拉斯曲线(Weierstrass Curve)

y² = x³ + ax + b

蒙哥马利曲线

By² = x³ + Ax² + x，其中A，B∈K且B(A² - 4)

基于蒙哥马利曲线的Curve25519密钥协商(DH)算法
Curve25519曲线（Ed25519椭圆曲线）：y² = x³ + 486662x²+x，由素数2²⁵⁵-19定义素数域，用于现代加密协议(如TLS1.3和SSH)的椭圆曲线。

爱德华曲线

基于爱德华曲线的Ed25519数字签名算法

爱德华曲线：x² + y² = 1 + dx²y²
Ed25519曲线：-x² + y² = 1 - 121665/121666x²y²

Curve25519/Ed25519/X25519

Daniel J. Bernstein在2006年独立设计的椭圆曲线加密/签名/密钥交换算法，Ed25519用于签名，X25519密钥交换

优势：
a.快速的签名验签
b.高安全性，等同于NIST P-256，RSA3000，128-block-cipher
c.少的签名值，64bytes
d.少的key，32bytes，私钥长度和公钥长度为32bytes

安全方案参考文档：
《SCA-secure ECC in software-mission.pdf》
《rfc7748.pdf》
《rfc8032.pdf》
《20240903_eucleak.pdf》

1.考虑蒙哥马利阶梯过程中地址泄露
2.考虑单条曲线横向分析

椭圆曲线点加

//计算点(x₁,y₂)+(x₂,y₂) = (x₃, y₃)

x₃ = s² - x₁ - x₂ mod p
y₃ = s(x₁ - x₃) - y₁ mod p

//斜率s
s = (y₂ - y₁)/(x₂ - x₁) mod p 当P≠Q （不同点相加）
s = (3x₁² + a)/(2y₁) mod p 当P=Q（相同点相加）

推导
1.P、Q为不同点的斜率
k = (y₂ - y₁)/(x₂ - x₁) ————(2)

2.P、Q为相同点的斜率
对曲线表达式两边求导，得
2yy‘ = 3x² + a，得
y' = (3x² + a)/(2y) ————(3)
y'就是曲线上任意一点的切线的斜率

通过点(x₁,y₁)的直线L(x)可以表示为：
y = k(x - x₁) + y₁ ————(4)

求(x₃,y₃)坐标-横坐标x₃的计算
将(4)带入(1)，消去y，得
(k(x-x₁)+y₁)² = x³ + ax + b
k²(x-x₁)² + 2k(x-x₁)y₁ + y₁² = x³ + ax + b
k²x² - 2k²xx₁ + k²x₁² + 2kxy - 2kx₁y₁ + y₁² = x³ + ax + b
k²x² - 2k²xx₁ + k²x₁² + 2kxy - 2kx₁y₁ + y₁² - x³ - ax - b = 0 //将等式右边移到左边
-k²x² + 2*k²xx₁ - k²x₁² - 2kxy + 2kx₁y₁ - y₁²+ x³ + ax + b = 0 //取反
x³ - k²x² + (a + 2k²x₁ - 2ky₁)x + b - (k²x₁² - 2kx₁y₁ + y₁²) = 0 //合并x
————(5)

根据韦达定理(Vieta's Formulas)，三次方程ax³ + bx + cx + d = 0的三个根x₁，x₂，x₃有以下关系

x₁ + x₂ + x₃ = -b/a
x₁x₂ + x₁x₃ + x₂x₃ = -c/a
x₁x₂x₃ = -d/a

对应(5)，x₁ + x₂ + x₃ = -b/a = k²/1
因此，x₃ = k² - x₁ - x₂

求(x₃,y₃)坐标-横坐标y₃的计算
方法：通过两点斜率直接计算得到，通过所求R(x₃, y₃)的镜像点R‘(x₃, -y₃)

k = (y₁ - (-y₃))/(x₁ - x₃)，得
y₃ = k(x₁ - x₃) - y₁

高效点乘

快速对点P的任意乘法，使用一种称为“double-and-add”方法
1）循环倍点P得到(2P, 4P, 8P, 16P)
2）通过上述组合，得到所需要的任意倍数的P

NIST曲线

ECC NIST P256 = secp256r1
ECC NIST P384 = secp384r1
ECC NIST P521 = secp521r1

ECDLP问题

DLP（离散对数问题）：给定基数g和元素x = g^y mod p，求解y
ECDLP椭圆曲线密码学（椭圆曲线离散对数问题）：给定G，Q=[k]G，求解k

区别：ECDLP允许使用更小的数

破解：c1 * P + d1 * Q = c2 * P + d2 * Q (Q=[k]P)

大数运算

模运算

/* function: c = a mod b
 * parameters:
 *     a -------------------------- input, integer a
 *     aWordLen ------------------- input, word length of integer
 *     b -------------------------- input, integer b, modulus
 *     b_h ------------------------ input, H parameter of b
 *     b_n0 ----------------------- input, - modulus ^(-1) mod 2^w, here w is 32 actually
 *     bWordLen ------------------- input, word length of integer b and b_h
 *     c -------------------------- output, c = a mod b
 * return: PKE_SUCCESS(success), other(error)
 * caution:
 *     1. b must be odd, and please make sure bWordLen is real word length of b
 *     2. real bit length of a can not be bigger than 2*(real bit length of b), so aWordLen can
 *        not be bigger than 2*bWordLen
 *     3. pleae make sure aWordLen <= 2*OPERAND_MAX_WORD_LEN, bWordLen <= OPERAND_MAX_WORD_LEN
 */
uint32_t pke_mod(const uint32_t *a, uint32_t aWordLen, const uint32_t *b, const uint32_t *b_h, const uint32_t *b_n0, uint32_t bWordLen, uint32_t *c)

//a
11223344||FF4DA38170E229215E01ADF8D4CF5207808C037878FCBB6AFE76B8E3CA92C3B5
//b（a的有效bit长度不能超过b的2倍）
ED17045630B452D89F6A4D4B8873220B4127A63D94DE7179C1F584E1E3095D4F
//a mod b
C8D957C5A8CB5D78409E680B456F77A403961DB4A9FC3D87EC893603367D5C5A

//t2 = a high part mod b
11223344
//t1 = 1000...000 mod b
10000000000000000000000000000000000000000000000000000000000000000-0ED17045630B452D89F6A4D4B8873220B4127A63D94DE7179C1F584E1E3095D4F
=12E8FBA9CF4BAD276095B2B4778CDDF4BED859C26B218E863E0A7B1E1CF6A2B1
//t2 = a_high * t1 mod b = a_high * （1000...000 mod b） mod b
11223344 * 12E8FBA9CF4BAD276095B2B4778CDDF4BED859C26B218E863E0A7B1E1CF6A2B1 mod ED17045630B452D89F6A4D4B8873220B4127A63D94DE7179C1F584E1E3095D4F
=B6A2B89A689D872F8207075DF91347A7C431C079C5DDF396B00802014EF3F5F4
//t1 = a low part mod b
FF4DA38170E229215E01ADF8D4CF5207808C037878FCBB6AFE76B8E3CA92C3B5 mod b
=12369F2B402DD648BE9760AD4C5C2FFC3F645D3AE41E49F13C813401E7896666
//a mod b=t1+t2 mod b
=C8D957C5A8CB5D78409E680B456F77A403961DB4A9FC3D87EC893603367D5C5A

标准文档

椭圆曲线参数标准文档《RFC5639》

Elliptic Curve Cryptography (ECC) Brainpool Standard Curves and Curve Generation

//工具缺少brainpoop224r1
3.3.  Domain Parameters for 224-Bit Curves
   Curve-ID: brainpoolP224r1
      p = D7C134AA264366862A18302575D1D787B09F075797DA89F57EC8C0FF
      A = 68A5E62CA9CE6C1C299803A6C1530B514E182AD8B0042A59CAD29F43
      B = 2580F63CCFE44138870713B1A92369E33E2135D266DBB372386C400B
      x = 0D9029AD2C7E5CF4340823B2A87DC68C9E4CE3174C1E6EFDEE12C07D
      y = 58AA56F772C0726F24C6B89E4ECDAC24354B9E99CAA3F6D3761402CD
      q = D7C134AA264366862A18302575D0FB98D116BC4B6DDEBCA3A5A7939F
      h = 1

数学理论

有限域(伽罗瓦域)

域是一个可以在其上进行加法、减法、乘法和除法运算而结果不会超出域的集合。如有理数集合、实数集合、复数集合都是域，但整数集合不是（很明显，使用除法得到的分数或小数已超出整数集合）。

如果域F只包含有限个元素，则称其为有限域。有限域中元素的个数称为有限域的阶。尽管存在有无限个元素的无限域，但只有有限域在密码编码学中得到了广泛的应用。每个有限域的阶必为素数的幂，即有限域的阶可表示为pⁿ（p是素数、n是正整数），该有限域通常称为Galois域(Galois Fields)，记为GF(pⁿ)。

注：为什么P一定要是个素数？这是因为当P为素数时，才能保证集合中所有元素加法和乘法都有逆元，假如p等于10，尽管所有元素都有加法逆元，但乘法不行，如元素2，因为找不到一个数a，使得2*a mod 10等于1；若p为素数，那么它就能保证域中的所有元素都有逆元。利用反证法和余数的定义即可证明。

定理1 一个有限域E有pⁿ个元素，这里p是E的特征，而n是E在它的素域△上的次数。 [1]
定理2 令有限域E的特征是素数p，E所含的素域是△，而E有q=pⁿ个元素，那么E就是多项式在△上的分裂域。任何两个这样的域都同构。
定理3 令△是特征为p的素域，而q=pⁿ(n≥1)，那么多项式在△上的分裂域E就是一个有q个元的有限域。定理4 一个有限域E是它的素域△的一个单扩域。 [1]

【四则运算】
若任意a、b、c∈GF(q)，则必有：
1．封闭性：a+b∈GF(q)，a·b∈GF(q)；
2．结合律：(a+b)+c=a+(b+c)，(a·b)c=a(b·c)；
3．交换律：a+b=b+a，a·b=b·a；
4．乘对加分配律：a(b+c)=a·b+a·c；
5．必有加法恒等元0和乘法恒等元e，使：a+0=a，a·e=a，e可理解为1；
6．必有加法负元-a和乘法逆元a-1，使：a+(-a)=0，a.a-1=e，但0-1无定义。

【有限域GF(2^8)多项式运算】
这是GF(p^{n)的特例，p=2，n=8。例如多项式:f(x)=x}6+x^4+x2+x+1，特点：

特点1：多项式的系数只能是0或1（即【0，p-1】）。若p=3，那么系数是可以取0，1，2的；
特点2：合并同类项“加法”即“⊕”，对系数进行异或操作，如x^4+x4=0；
特点3：减法就等于加法（即无所谓的减法），或者负系数。所以，x^4–x4就等于x^4+x4，-x^3就是x3
例如，设f(x)=x^6+x4+x^{2+x+1，g(x)=x}7+x+1，则：
f(x)+g(x)=x^7+x6+x^4+x2+(1+1)x+(1+1)1=x^7+x6+x^4+x2；
f(x)–g(x)=f(x)+g(x)；
f(x)*g(x)=(x^13+x11+x^9+x8+x^7)+(x7+x^5+x3+x^2+x)+(x6+x^4+x2+x+1)=x^13+x11+x^9+x8+x^6+x5+x^4+x3+1；
f(x)/g(x)=x^6+x4+x^3+x2+1

伽罗华域的元素可以通过该域上的本原多项式生成。通过本原多项式得到的域，其加法单位元都是0，乘法单位元是1。本原多项式是一个素多项式（素多项式不能表示为其他两个多项式相乘的乘积，类似于素数）。以GF(2^{3)为例，指数小于3的多项式共8个：0，1，x，x+1，x}2，x^2+1，x2+x，x^2+x+1。其系数刚好就是000,001,010,011,100,101,110,111，是0到7这8个数的二进制形式。多项式对应一个值，我们可以称这个值为多项式值（有时看成一个向量）。GF(2^{3)上有不只一个本原多项式，选一个本原多项式x}3+x+1，这8个多项式进行四则运算后 mod (x^3+x+1)的结果都是8个之中的某一个。

weierstrass椭圆曲线

https://blog.csdn.net/weixin_44830789/article/details/106671946

采用weierstrass方程，当特征域不为2、3，方程：

y^2 = x^3 + ax + b (mod p)

p：大素数，构成有限域GF(p) ，椭圆曲线点的坐标，曲线方程系数，以及点群上的运算均是在该域上的。
a，b：曲线方程系数。
G：曲线生成元，即基点G (G_x，G_y)，其生成椭圆曲线上所有点，构成一个群。
n：点G的阶，也即曲线的阶，要求为与p规模接近的大素数。即要求曲线的余因子为1。

ECDSA/ECDH/ECIES/SM2

secp192r1, secp224r1, secp256r1, secp384r1, secp521r1
brainpoolP160r1, brainpoolP192r1, brainpoolP256r1, brainpoolP320r1, brainpoolP384r1, brainpoolP512r1
sm2p256v1

P ⊕ Q = R ，椭圆曲线两点PQ，L是过P、Q两点（如果P==Q，L是椭圆曲线的切线），与椭圆曲线相交于R‘，过R’做平行于y轴的直线，与椭圆曲线E相交于点R。

求乘法逆元

a）拓展的欧几里得算法

要求a与p互素

b）基于费马小定理的计算

a<sup>p-1</sup> = 1 mod p  等价于a的逆元为 a<sup>-1</sup> = a<sup>p-2</sup> mod p，要求a与p素数

c）

素数域

F_p ：对于模数p的乘法集合{0,1,2, ..., p-1}，p为素数

模p加法：a,b ∈ Fp，则a+b = (a+b) mod p
模p乘法：a,b ∈ Fp，则a · b = (a · b) mod p
加法单位元：e=0
乘法单位元：e=1
存在逆元：对于集合中的非0元素x，都存在集合内对应元素x^-1，使得x^-1x = 1 (mod p)，x^-1为x模p下的逆元

攻击与防护

故障攻击：在合适的时间点进行故障注入，单bit、多bit、如X射线、电磁场、光学诱发设备

CPA/DPA（相关性/差分功耗分析）：根据输入明文与侧信道信息（能量、功耗）的相关性分析私钥指数如：模幂、模乘
SPA（简单功耗分析）：当运算时由于操作数据的不同而导致功耗曲线存在可观察的差异如：椭圆曲线点乘
措施：伪操作、掩码、指数加扰/拆分

中间值故障注入：在运算过程中，向运算中间值注入故障，通过错误结果和数学分析反推私钥指数如：ECDSA
RSA公钥e被改成1：验签阶段公钥被改成 1，构造签名值使其与消息值相同，则验签通过
措施：重复计算，校验公钥，反向计算

模乘的模板攻击：根据模乘输入的两个已知操作数建立模板，利用模板分析实际运算中的模乘操作数
具体例子比如模乘：采集一组功耗曲线，所有密钥已知，选定特定中间值，根据不同的中间值建立模板。采集一组新的曲线，密钥未知，根据模板进行匹配，恢复密钥。这里的密钥指的是模数p

采集模乘计算a*b mod p计算过程中的功耗。在CRT的mod p实现中，调用硬件实现了一个64bit随机数和一个固定数计算以p为模数的蒙哥马利模乘操作。所以采集的是64bit随机数乘以512bit固定数的蒙哥马利模乘功耗。
A组：a为64bit数，全随机；b为512bit数，2^512 % p；p为512bit模数，最高比特和最低比特置1，其余比特全随机。采样率2.5GS/s，采样点数50000，采集100万条曲线。
B组：a为64bit数，全随机；b为固定的512bit数；p为固定的512bit模数。采样率2.5GS/s，采样点数50000，采集100万条曲线。

safe-error 攻击：向特定运算时刻或特定地址数据注入故障，根据运算结果是否正确推测密钥信息。
模加 DPA/CPA：根据模乘输入的两个已知操作数建立模板，利用模板分析实际运算中的模乘操作数
选择明文攻击：选择特殊值作为明文输入，使运算过程出现 1 值、0 值、两次相同值等，这类数值产生的侧信道信息易于区分，从而分析出私钥
措施：明文掩码、指数加扰/指数拆分，蒙哥马利阶梯无伪运算

辅助工具

RFC中英文档阅读网址

https://rfc2cn.com/

素数检测

在线网站：https://username1565.github.io/Javascript-Primality-Tester/
缺点：只支持10进制输入

密码小工具

myblockcipher-对称算法
myPAETool-非对称算法
chacha

计算蒙哥马利模乘参数

C = R^2 mod N
D = -N^(-1) mod 2^w
其中，R=1<<N_bit ，w为位宽

以brainpoolp512r1计算与计算值为例
n_h = R^2 mod n
n_n0 = -N^(-1) mod 2^w //这里根据位宽改变，默认32bit

随机数发生器

好的随机数发生器要满足以下特性：
1、统计测试（good statistical poperties）
2、不可预测性（unpredictable）

PRNG：Algorithm

TRNG：physical
Source：
1、时钟抖动（Clock Jitter）
2、Meta Stability（”亚平衡“，元稳定性）
3、Chaos（混沌）
4、Thermal noise（热噪声）

HRNG：PRNG+TRNG(增熵)

专利

1.一种基于椭圆曲线签名，应用于抗错误故障注入实现安全签名的方法

本发明技术关键点
    ECDSA(Elliptic curve digital signature algorithm)是基于椭圆曲线的数字签名算法，它是一种采用公私钥体系实现数字签名的算法，其安全性基于椭圆曲线离散对数问题(ECC)。与传统的数字签名算法(如DSA和RSA)相比，ECDSA使用较短的密钥却能达到相同的安全级别，且计算速度更快，签名更加短小，在密码学和网络安全领域得到广泛应用。
    很多已有的设备如通用MCU上以集成硬件ECC点乘加速器，通过软硬件结合方式，实现ECDSA签名算法。在实际应用中，如果教科书式按步骤实现ECDSA，存在安全风险，攻击者可通过错误注入ECC点乘加速器，导致私钥泄露，本发明公开一种安全的签名方法，所述方法包括，在执行点乘结束后，引入随机标量执行一次点加，结合一次点校验，结果对比校验来判断是否受到攻击，解决ECC点乘硬件加速器被错误故障注入导致私钥泄露的问题，提高签名的安全性.

现有技术方案
    现有技术问题在于只进行点校验，实际是依旧有风险，点校验只保证点乘结果在曲线上，但没有保证点乘结果与签名随机生成的标量k之间的绑定关系，存在安全缺陷。本发明则利用已有的ECC硬件加速器，增加安全防护，引入随机标量进行一次点加校验，再结合一次点校验，最终保证硬件加速器中参与点乘计算的参数k和椭圆曲线参数G、以及计算流程均正确执行，防止私钥泄露，提高ECDSA签名的安全性。

错误故障注入导致私钥泄露的原理：d=h(s-s_f)[(s_f* r - s * r_f)^-1] mod p
参考文档：https://asecuritysite.com/ecdsa/ecd7

首先对于签名有两步：
1.r = [k]G
2.s = k^-1(h+r * d)

给定两组签名，一组正确，一组错误（使r值发生错误）
s_f = k^-1 (h + r_f * d) ①
s = k^-1(h + r * d) ②

②-①，得到：
s - s_f = k^-1(h + d * r) - k^-1(h+d * r_f)
s - s_f = k^-1(d * r - d * r_f)
k(s - s_f) = d * r - d * r_f
k = (d * r - d * r_f)(s - s_f)^-1 ③

把③代入签名公式：
s = k^-1(h+r * d)
s = (d * r - d * r_f)^-1(s - s_f)(h+r * d)
s(d * r - d * r_f) = (s - s_f)(h+r * d)
sdr - sdr_f = sh + sdr - hs_f - s_fdr
-sdr_f = sh - hs_f - s_fdr
s_fdr - sdr_f = sh - hs_f
d(s_fr - sr_f) = h(s-s_f)
d = h(s-s_f)(s_fr - sr_f)^-1 (mod p)

//测试Demo
//secp256k1
//privkey
FF890E39083268830B89118290750B5B2FD511C5CB3D501E7F21AD79095E4B69
//pubkey
0401FF01346CEC0529FCF4F18C355F4E9B2F02DCC05E4141BEC0F910468D13A4F9A6202628700E19E305C22C9E05A6D1515813DECDC31405F4E0E54F47B8E571D3

//sign-true
//e
1122
//k
5566
//r
DAFA79E07CA3928CE4AA1D65984F335F08454EDA1819A10D978D1CB79806434A 
//s
FD7E0AF3DDDDD592918452501D3EA4EEB1D889C70E0A6E1BC7F9A3F6A9EA99B5


============================ 假设故障导致计算结果错误（非曲线点） ================================
//sign-false//change r，keep k
//e
1122
//k
5566
//r=[k]G-x
DAFA79E07CA3928CE4AA1D65984F335F08454EDA1819A10D978D1CB79806434A
//change rf=[k]G-x
DAFA79E07CA3928CE4AA1D65984F335F08454EDA1819A10D978D1CB798064340 //k-A
//s=k^-1 * (e+rf * dA) mod n
//k^-1 mod n
A4AFD5A845227F4324E2CBB436CD4BE65B91D11C6C2BD119A06D4A268C44888
//rf*dA mod n
DE80C79ABC54AD9876B2B687CF26F1FF865ED5E239031D4AEA46207E413A191D
//(e+rf*dA) mod n
DE80C79ABC54AD9876B2B687CF26F1FF865ED5E239031D4AEA46207E413A2A3F
//sf=k^-1 * (e+rf * dA) mod n
537D4D094AFF8F1416DCECF1DC5A63CCEDCE2F67FB6D4813A3AD22E28F3170A4


//r
DAFA79E07CA3928CE4AA1D65984F335F08454EDA1819A10D978D1CB79806434A
//s
FD7E0AF3DDDDD592918452501D3EA4EEB1D889C70E0A6E1BC7F9A3F6A9EA99B5
//rf
DAFA79E07CA3928CE4AA1D65984F335F08454EDA1819A10D978D1CB798064340
//sf
537D4D094AFF8F1416DCECF1DC5A63CCEDCE2F67FB6D4813A3AD22E28F3170A4



//d=e*(s-sf)*[(sf*r - s*rf)^-1] mod p
//sf*r
1DA41944C4EA3AC2C8BB3ED77C09A8E75BBB5156F94DD4B83FA8D6389359612
//s*rf
8A03A97E00A969F17303F071A5EF9560CB7D710BF3D42D582F47CE68C2349556
//sf*r - s*rf
77D698164BA539BAB987C37BD1D1052C64ED20F02B09502F14851D87973741FD
//(sf*r - s*rf)^-1
2BDB7C3ABDB7C3ABDB7C3ABDB7C3ABDB447F328B89FC5E21419B4EE87EF50D90


//s-sf
AA00BDEA92DE467E7AA7655E40E44121C40A5A5F129D2608244C81141AB92911
//e*(s-sf)
A0B5CCE84433C2F167F6B8D3C6A3F2F5344F90D30E46EFD7EDC7F8B16F2B51E2
//d=e*(s-sf)*[(sf*r - s*rf)^-1] mod p
FF890E39083268830B89118290750B5B2FD511C5CB3D501E7F21AD79095E4B69





============================ 假设故障导致计算结果错误（结果不在曲线点上） ================================
//sign-false//change r，keep k
//e
1122
//k
5566
//r=[k]G-x
DAFA79E07CA3928CE4AA1D65984F335F08454EDA1819A10D978D1CB79806434A
//change rf=[k]G-x
DAFA79E07CA3928CE4AA1D65984F335F08454EDA1819A10D978D1CB798064340 //之前的安全方案只考虑点校验，但没有校验点与k的关系
//s=k^-1 * (e+rf * dA) mod n
//k^-1 mod n
A4AFD5A845227F4324E2CBB436CD4BE65B91D11C6C2BD119A06D4A268C44888
//rf*dA mod n
DE80C79ABC54AD9876B2B687CF26F1FF865ED5E239031D4AEA46207E413A191D
//(e+rf*dA) mod n
DE80C79ABC54AD9876B2B687CF26F1FF865ED5E239031D4AEA46207E413A2A3F
//sf=k^-1 * (e+rf * dA) mod n
537D4D094AFF8F1416DCECF1DC5A63CCEDCE2F67FB6D4813A3AD22E28F3170A4


//r
DAFA79E07CA3928CE4AA1D65984F335F08454EDA1819A10D978D1CB79806434A
//s
FD7E0AF3DDDDD592918452501D3EA4EEB1D889C70E0A6E1BC7F9A3F6A9EA99B5
//rf
DAFA79E07CA3928CE4AA1D65984F335F08454EDA1819A10D978D1CB798064340
//sf
537D4D094AFF8F1416DCECF1DC5A63CCEDCE2F67FB6D4813A3AD22E28F3170A4



//d=e*(s-sf)*[(sf*r - s*rf)^-1] mod p
//sf*r
1DA41944C4EA3AC2C8BB3ED77C09A8E75BBB5156F94DD4B83FA8D6389359612
//s*rf
8A03A97E00A969F17303F071A5EF9560CB7D710BF3D42D582F47CE68C2349556
//sf*r - s*rf
77D698164BA539BAB987C37BD1D1052C64ED20F02B09502F14851D87973741FD
//(sf*r - s*rf)^-1
2BDB7C3ABDB7C3ABDB7C3ABDB7C3ABDB447F328B89FC5E21419B4EE87EF50D90


//s-sf
AA00BDEA92DE467E7AA7655E40E44121C40A5A5F129D2608244C81141AB92911
//e*(s-sf)
A0B5CCE84433C2F167F6B8D3C6A3F2F5344F90D30E46EFD7EDC7F8B16F2B51E2
//d=e*(s-sf)*[(sf*r - s*rf)^-1] mod p
FF890E39083268830B89118290750B5B2FD511C5CB3D501E7F21AD79095E4B69



============================ 假设故障导致计算结果错误（结果在曲线上，但非对应k） ================================
//sign-false//change r，keep k
//e
1122
//k
5566
//r=[k]G-x
DAFA79E07CA3928CE4AA1D65984F335F08454EDA1819A10D978D1CB79806434A
//change rf=[k]G-x //
DAFA79E07CA3928CE4AA1D65984F335F08454EDA1819A10D978D1CB798064340
//s=k^-1 * (e+rf * dA) mod n
//k^-1 mod n
A4AFD5A845227F4324E2CBB436CD4BE65B91D11C6C2BD119A06D4A268C44888
//rf*dA mod n
DE80C79ABC54AD9876B2B687CF26F1FF865ED5E239031D4AEA46207E413A191D
//(e+rf*dA) mod n
DE80C79ABC54AD9876B2B687CF26F1FF865ED5E239031D4AEA46207E413A2A3F
//sf=k^-1 * (e+rf * dA) mod n
537D4D094AFF8F1416DCECF1DC5A63CCEDCE2F67FB6D4813A3AD22E28F3170A4



//r
DAFA79E07CA3928CE4AA1D65984F335F08454EDA1819A10D978D1CB79806434A
//s
FD7E0AF3DDDDD592918452501D3EA4EEB1D889C70E0A6E1BC7F9A3F6A9EA99B5
//rf
DAFA79E07CA3928CE4AA1D65984F335F08454EDA1819A10D978D1CB798064340
//sf
537D4D094AFF8F1416DCECF1DC5A63CCEDCE2F67FB6D4813A3AD22E28F3170A4



//d=e*(s-sf)*[(sf*r - s*rf)^-1] mod p
//sf*r

//s*rf
8A03A97E00A969F17303F071A5EF9560CB7D710BF3D42D582F47CE68C2349556
//sf*r - s*rf
77D698164BA539BAB987C37BD1D1052C64ED20F02B09502F14851D87973741FD
//(sf*r - s*rf)^-1
2BDB7C3ABDB7C3ABDB7C3ABDB7C3ABDB447F328B89FC5E21419B4EE87EF50D90


//s-sf
AA00BDEA92DE467E7AA7655E40E44121C40A5A5F129D2608244C81141AB92911
//e*(s-sf)
A0B5CCE84433C2F167F6B8D3C6A3F2F5344F90D30E46EFD7EDC7F8B16F2B51E2
//d=e*(s-sf)*[(sf*r - s*rf)^-1] mod p
FF890E39083268830B89118290750B5B2FD511C5CB3D501E7F21AD79095E4B69



安全方案：
1.抵抗中间值故障注入（增加安全性），硬件点乘算子 //外部传入k值
    点乘运算结束后，在计算签名值s部分时，对计算结果[k]G做一次曲线上点校验
    a）点校验
    b）随机标量点乘校验
    c）[k+N]G = [k]G

2、一种利用已有模加模乘运算加速器实现大数取模的方法

    很多已有的设备如通用MCU上已集成了硬件模运算加速器，包括模加、模乘、模逆、点乘、点加、模幂，用于参与实现经典的密码运算如Ed25519签名等。对于Ed25519签名，集成的硬件加速器算子操作数位宽，往往只支持Ed25519标准曲线最大数据位宽256bit。
本发明提出了一种方法，将大数从低位到高位，按模数的实际有效位宽为单位，切分为若干分组，利用已有的支持模数位宽的模加、模乘硬件加速器，实现大数求余计算，，减少硬件电路面积成本，充分发挥已有硬件加速器的计算潜力。

3、一种利用有限位宽硬件加速器实现更大位宽RSA CRT运算的方法

在支持1024位宽硬件加速器（模乘、模加、模幂）基础上实现更高位宽RSA1026-RSA2048 CRT运算
在支持2048位宽硬件加速器（模乘、模加、模幂）基础上实现更高位宽RSA2048-RSA4096 CRT运算
在支持4096位宽硬件加速器（模乘、模加、模幂）基础上实现更高位宽RSA4096-RSA8192 CRT运算

本发明提出了一种方法，将大数从低位到高位，按模数的实际有效位宽为单位，切分为若干分组，利用已有的支持模数位宽的模加、模乘硬件加速器，实现大数求余计算，同时结合幂运算性质，减少硬件电路面积成本，充分发挥已有硬件加速器的计算潜力。

p、q、dp、dq、qinv位宽：nbit
c位宽：2*nbit

m1 = (c mod p)^dp

//Demo
//p
E885BA6181AD24D7B8AA1F1A92FD2F3841EEC04120CD06142E96E99D8370725AA32C10D0134FB2B6C20771E27F8CBDBD858073DA3A0E13C6F801AAF2D2AE8588BF293727A80209C18275CE82745CF8D04BC43C1A12880AB73AD7BD0A7DDB8042634CAE44AE2635B40F52AED1A0293A158769F2F0BFDD2B0C8A6B460522914561
//q CB63B7462B37640A4940C39CA60F6E843B9EBC26EEFB4E3B62C40A74AB157E25594B7781C5AA885ED509480144E6841BC2DF87B8444940BEE7EF842ECC4952158D43D8AE46E9FF06198A35DA4D882882BEEA80D59CC7DC2D29803E503FCAAAC4058BBF4A9CBF4732E2F66DF918CCA8A50E372ACEAA6526E50CFD21C1053410AB
//dp
AAD75691BDCD917C4E59F0707DFF386A8546FE4ADBE6C7C89C529562FDE7E89D5FB648C418EC3DCAB9D4EE8014673C21BBAD1D7201A5C6323296471C125FD80D1927173733E20B78FA79C4396575C9FA8130B55812B591E9FE79F49378D585EF41365DF4685FFAA5497CDEA5769FD3E56D9112C680B1E7A7572C6A4DEB900101
//dq
3801F293290D6CC8045A0843D7DAC20539E1C1503B590AB701C0985C7E4C41DB891666075F66517D43CEF57C1BFC1A7F068FC570F1A4F6665BBA323D2CD637FB65563C91E9474089EE7887D1E0ADD0F2081ECD718565E7F4ABCBFBDCDF6430D81FEAD6B776289A33A21A58385322F081DB4347CF774EB98233AC7522110BC057
//u
205850F94496A6F922FF11B140DF253A09AB49661BC9EF4BF5C4CC2D8D15CD1A679652D9E8D707014680401E447EFEBA9E8097C43816A36EDAB26B37D7FD800B6F7EE8488F26CCC4AF5E713FC7591A19C9D3FAF1CFB58F355D2B7216E576FFCE18B9011F7C14F75C08950110101AAD59AAD889B591441A1A7E699C8FB9B333FE

//msg-2048
11BC9CF9B996E26F89D4DD8C99C07017365EF703C5AC3C0B8B16BF37A1A8E53047CE5246E9309880A4E788A9B814A87DAB577618176E7897BBA7964C687D0E4558320467EE8753AEE0B0DF0503AF014FFD197EE36A9EE474CE495616C39969ACFEA661F6745023689E752ADB9CE4ACE52C00EE11C352127E29DAF2CEB18DD6956D2EDF3BAD13DD595B107E7D5529AB407B50679AF51DBE4908B350115BBC1DB16DB0BF225C3937AB672DF6654A99883A437EA9F00DA08D35368C420DD9DB34A10B0892C9BDC5B628F0373D8930177C74D6F87FF2A2E1BACDE146F7CE25E5A4BD5882B99A94E8ACA0570EF14AF9A909DA0D3AC254DDC9A21A6313C295281367CB

4、一种基于现有硬件加速器应用于RSA-CRT来实现安全运算的方法

本发明提供了一种RSA-CRT运算方法和装置，应用现有的模运算硬件加速器，真随机数发生器将运算所参与的底数、模数、指数进行加扰，用于提高数据运算的安全性，抵御侧信道攻击。所述方法包括：获取随机数r、随机数k1、随机数h1、随机数y1、随机数k2、随机数h2、随机数q1、随机数y2，底数c、公钥e，私钥五元组（p、q、dp、dq、qInv），模数N。计算第一值，所述第一值为；计算第二值，所述第二值为 mod (y1*(p-p1)+y1*p1)；计算第三值，所述第三值为；计算第四值，所述第四值为 mod (y2*(q-q1)+y2*q1)；计算第五值，所述第五值为；计算第六值，所述第六值为Δ = (m1-m2) mod (y1*(p-p1)+y1*p1)；计算第七值，所述第七值为；计算第八值，所述第八值为。第八值为最终的RSA-CRT运算的结果。所述的数据防攻击方法，包括运算所参与所有的底数、模数、指数随机化和扩大了模数和指数的实际有效比特长度，增加分析破解难度，最大程度降低攻击者通过侧信道分析获得RSA私钥的关键信息的可能，提高应用RSA-CRT运算安全性。

4、一种SM9预计算来加速签名运算的方法

提前预计消息、双线性对