椭圆曲线和参数
1. 符号约定
对本文中使用到的符号约定如下： p 192比特的素数 Fp
p个元素的有限域
2
3
a,b Fp中的元素，确定了椭圆曲线方程y=x+ax+b E 以椭圆曲线方程y=x+ax+b定义的Fp上的椭圆曲线 O 椭圆曲线上的一个特殊点，称为无穷远点 E(Fp) E在Fp上的点及无穷远点构成的集合 n 曲线点集E(Fp)的阶#E(Fp)，要求为奇素数 x mod n G
用n除x所得的余数 r ，0≤r≤n−1 E(Fp)的生成元，称为基点，G =( xG , yG) 大于等于 x 且小于等于 y 的整数集合
2
3
[x, y]
⎡x⎤
取大于等于 x 的最小整数
t Fp中的元素的比特长度，t = ⎡log2 p⎤，本文中t = 192 l
Fp中的元素的字节长度，l = ⎡t / 8⎤，本文中l = 24
log2 x 以2为底的 x 的对数 || 字节串的并置 dU PU
用户U的私钥，dU∈[1，n−1] 用户U的公钥，PU＝dU · G
2. 数学基础
2.1有限域Fp
p为素数，Fp的元素表示为整数0, 1, 2, ..., p−1。
1
（1）Fp中加法运算为整数的模 p加法运算：即a, b∈Fp, a + b = (a + b) mod p。 （2）Fp中乘法运算为整数的模 p乘法运算：即a, b∈Fp, a · b = (a · b)mod p。 （3）Fp中加法群的单位元为整数0。 （4）Fp中乘法群的单位元为整数1。 （5）Fp中加法群的元素a的逆元素为p− a。
（6）Fp中乘法群的元素a的逆元素为b， b满足a · b=1 mod p ，记为a。
−1
2.2椭圆曲线定义
Fp上椭圆曲线方程为y=x+ax+b (4a+27b≠0modp)，椭圆曲线点集 E(Fp)= { ( x , y )| x，y∈Fp，且满足y=x+ax+b } ∪ {O}， 其中O是椭圆曲线的无穷远点，曲线E(Fp)的阶为n＝#E(Fp)。按2.3定义的点加运算，E(Fp)构成一个Abel群。
2
3
2
3
3
2
2.3点加运算
点P, Q ∈ E(Fp)，P=(x1 , y1 )，Q=( x2 , y2 )，加法规则如下： （1） P + O = O + P = P；
（2） −P = ( x1, −y1 ) , P + (−P) = O； （3） 若Q≠−P, 记P + Q ＝( x3, y3 )，
⎧x3=λ 2−x1−x2
⎨
⎩y3=λ (x1−x3)−y1
其中
⎧(y2−y1)(x2−x1) , 当x1≠x2λ =⎨2
⎩(3x1+a)2y1 , 当x1=x2
2.4多倍点运算
P+P2+LP。 多倍点运算：点P∈E(Fp) ，整数k >0，k · P＝1444+43
k 个
2
3. 数据类型转换约定
3.1整数至字节串的转换
输入： 非负整数x和期望得到的字节串长度k，满足： 28k>x。 输出： 长度为k的字节串M。
（1）设M1, M2, …, Mk表示M中从左至右的每个字节，字节Mi=(Mi1, Mi2, …, Mi8)代表整数
∑2
j=1
8
8−j
Mij，1≤i≤k。
（2）输出字节串M满足： x=
∑2
i=1
k
8(k−i)
Mi。
3.2字节串至整数的转换
输入： 长度为k的字节串M。 输出： 整数x。
（1）设M1, M2, …, Mk表示M中从左至右的每个字节，字节Mi=(Mi1, Mi2, …, Mi8)代表整数
∑2
j=1
8
8−j
Mij，1≤i≤k。
（2）输出整数x满足： x=
∑2
i=1
k
8(k−i)
Mi。
3.3域元素至字节串的转换
输入： 有限域Fp中元素c。 输出： 长度为 l 的字节串S。
按照3.1节描述的方法把 c转换成为一个长度为 l 的字节串S。
3.4字节串至域元素的转换
输入： 长度为 l 的字节串 S。 输出： 有限域Fp中元素c。
按照3.2节描述的方法把 S转换成为一个整数c；如果c不在区间[0, p−1]中，则报错。
3
3.5点至字节串的转换
无穷远点O用字符串方式表示为单字节PC = 00。
椭圆曲线上的非无穷远点P = ( xP , yP ) 指定使用非压缩方式表示。 输入： 椭圆曲线上的非无穷远点P = ( xP , yP )。 输出： 长度为2l + 1的字节串PO。
（1）按照3.3节描述的方法分别将xP , yP转换成长度为 l 的字节串X1，Y1。 （2）单字节PC赋值为04，输出字符串 PO = PC || X1 ||Y1。
3.6字节串至点的转换
输入： 长度为 2l + 1 的字节串PO。
输出： 椭圆曲线上的非无穷远点P = ( xP , yP )。
（1）设PO＝PC || X1 ||Y1，其中PC为单字节，X1 , Y1分别是长度为 l 的字节串，若PC不等于04则报错。
（2）按照3.4节描述的方法将字节串X1 , Y1分别转换成域元素xP , yP 。 （3）输出点P = (xP , yP)。
4. 椭圆曲线参数
ECDSA算法和ECDH算法的密钥长度选定为192比特，采用域Fp上的椭圆曲线，其参数为 { p, a, b, G, n }，以十六进制形式表示如下：
p： BDB6F4FE3E8B1D9E0DA8C0D46F4C318CEFE4AFE3B6B8551F a： BB8E5E8FBC115E139FE6A814FE48AAA6F0ADA1AA5DF91985 b： 1854BEBDC31B21B7AEFC80AB0ECD10D5B1B3308E6DBF11C1 xG：4AD5F7048DE709AD51236DE65E4D4B482C836DC6E4106640 yG：02BB3A02D4AAADACAE24817A4CA3A1B014B5270432DB27D2 n： BDB6F4FE3E8B1D9E0DA8C0D40FC962195DFAE76F56564677
5. ECDSA算法
ECDSA算法参引ISO/IEC 15946：2002（E），具体参引第2部分第6章。
4
6. ECDH算法
ECDH算法参引ISO/IEC 15946：2002（E），具体参引第3部分第8章第4节。
7. SHA-256算法
SHA-256算法参引ISO/IEC 10118：2004（E），具体参引第3部分第10章。
8. 实例
8.1 ECDSA算法实例
用户A的私钥dA：
dA： 3AC0E717EB61602EFCBB1DE81AA144A272B44BA1F16936AC
公钥PA=dA · G=(x1 , y1)：
x1： 7E1969FD0B001810A4E7F414C23F2BADF6B2DE96AE6B7856 y1： 29426771EDD3001F4A4253D8EEB9FFC18684C6C0B43ACA08
十六进制字节串消息：
M： 00FFEEDDCCBBAA998877665544332211
（1）计算M的杂凑值e=h(M)：
723AE33F076F199ECDFEFBC7169B7BE471ECB43E01ECE80ACA7539B48A4B0A90
其中，h为杂凑算法SHA-256。 （2）取随机整数k∈[1,n−1]，假定为：
5ABC270DBCEE31A4B00132331DDD596173EAF656ABCC39CB （3）将杂凑值e用用户A的私钥dA签名后得到签名结果： A9F40F155FCF18E8D35AB47EE65CD2F906465155A71DFA38 7EAFA7E5A2335CD337E37B39601D2D5022E1799799F0E262
8.2 ECDH算法实例
用户A的临时私钥记为dA，临时公钥记为PA=dA · G=(x2 , y2)： dA： 3AC0E717EB61602EFCBB1DE81AA144A272B44BA1F16936AC
5
x2： 7E1969FD0B001810A4E7F414C23F2BADF6B2DE96AE6B7856 y2： 29426771EDD3001F4A4253D8EEB9FFC18684C6C0B43ACA08
用户B的临时私钥记为dB，临时公钥记为PB=dB · G=(x3 , y3)：
dB： 25FBB32EFBEC6ECB1314332A026582DB7BE00C051CF2FA80
x3： 0621D8ADAB0952752EBEAE5007F6AE455C61860D1CEADB25 y3： 6A58D5D55087325DAC434C0DD28A9F8159070C8AAECD21D8
按照ECDH算法，用户A、B分别计算出共享信息KAB= dA · PB = KBA= dB · PA=(x4 , y4)：
x4： 3A74DDFA3080F6B5A1688C6EB7B098240B5AFC672450A425 y4： 7FF89712A653D6E1B30CD24AC6C72BD3A90F2F9EACE3F3F6
6
因篇幅问题不能全部显示，请点此查看更多更全内容