引言 N.Koblitz和V.Miller在1985年各自独立地提出将椭圆曲线应用于公钥密码系统。椭圆曲线公钥密码 所基于的曲线性质如下： 一有限域上椭圆曲线在点加运算下构成有限交换群，且其阶与基域规模相近： 一类似于有限域乘法群中的乘幂运算，椭圆曲线多倍点运算构成一个单向函数。 在多倍点运算中，己知多倍点与基点，求解倍数的问题称为椭圆曲线离散对数问题。对于一般椭 圆曲线的离散对数问题，目前只存在指数级计算复杂度的求解方法。与大数分解问题及有限域上离散 对数问题相比，椭圆曲线离散对数问题的求解难度要大得多。因此，在相同安全程度要求下，椭圆曲 线密码较其它公钥密码所需的密钥规模要小得多。 本部分描述必要的数学基础知识与一般技术，以帮助实现其它各部分所规定的密码机制
引 言 N.Koblitz和V.Miller在1985年各自独立地提出将椭圆曲线应用于公钥密码系统。椭圆曲线公钥密码 所基于的曲线性质如下： ──有限域上椭圆曲线在点加运算下构成有限交换群，且其阶与基域规模相近； ──类似于有限域乘法群中的乘幂运算，椭圆曲线多倍点运算构成一个单向函数。 在多倍点运算中，已知多倍点与基点，求解倍数的问题称为椭圆曲线离散对数问题。对于一般椭 圆曲线的离散对数问题，目前只存在指数级计算复杂度的求解方法。与大数分解问题及有限域上离散 对数问题相比，椭圆曲线离散对数问题的求解难度要大得多。因此，在相同安全程度要求下，椭圆曲 线密码较其它公钥密码所需的密钥规模要小得多。 本部分描述必要的数学基础知识与一般技术，以帮助实现其它各部分所规定的密码机制。 V
SM2椭圆曲线公钥密码算法 第1部分：总则 1范围 本部分给出了SM2椭圆曲线公钥密码算法涉及的必要数学基础知识与相关密码技术，以帮助实现 其它各部分所规定的密码机制。 本部分适用于基域为素域和二元扩域的椭圆曲线公钥密码算法。 2符号和缩略语 下列符号和缩略语适用于本部分。 a,b:F,中的元素，它们定义F,上的一条椭圆曲线E。 B:MOV阈。正数B,使得求取F上的离散对数至少与求取F,上的椭圆曲线离散对数一样困难。 deg(f):多项式fx)的次数。 E:有限域上由a和b定义的一条椭圆曲线。 E(F):F,上椭圆曲线E的所有有理点（包括无穷远点O)组成的集合。 ECDLP:椭圆曲线离散对数问题。 Fp:包含p个元素的素域。 Fg:包含q个元素的素域。 F:由F,中所有非零元构成的乘法群。 F2m:包含2m个元素的二元扩域。 G:椭圆曲线的一个基点，其阶为素数。 gcd(x,y):x和y的最大公因子。 h:余因子，h=#E(F)/n,其中n是基点G的阶。 Le ft Rotate():循环左移运算。 lmar:余因子h的最大素因子的上界。 m:二元扩域Fm关于F3的扩张次数。 modf(x):模多项式f(x)的运算。若f(x)是二元域上的多项式，则所有系数执行模2运算。 modn:模n运算。例如，23mod7=2。 n:基点G的阶(n是#E(F)的素因子)。 O:椭圆曲线上的一个特殊点，称为无穷远点或零点，是椭圆曲线加法群的单位元。 P:P=(xp,yp)是椭圆曲线上除O之外的一个点，其坐标xp,yp满足椭圆曲线方程。 P+P:椭圆曲线E上两个点P与P的和。 p:大于3的素数。 q:有限域F,中元素的数目。 rmim:基点G的阶n的下界。 T():迹函数。 xp:点P的x坐标。 x-1modn:使得xy≡1(modn)成立的唯一整数y,1≤y≤n-1,gcd(x,n)=l。 x‖y:x与y的拼接，其中x和y是比特串或字节串。 x三y(modn):x与y模n同余。亦即，x modn=y modn。. yp:点P的y坐标。 p:yp的点压缩表示。 Zp:整数模p的剩余类环。 1
SM2椭圆曲线公钥密码算法 第1部分：总则 1 范围 本部分给出了SM2椭圆曲线公钥密码算法涉及的必要数学基础知识与相关密码技术，以帮助实现 其它各部分所规定的密码机制。 本部分适用于基域为素域和二元扩域的椭圆曲线公钥密码算法。 2 符号和缩略语 下列符号和缩略语适用于本部分。 a，b：Fq中的元素，它们定义Fq上的一条椭圆曲线E。 B：MOV阈。正数B，使得求取Fq B上的离散对数至少与求取Fq上的椭圆曲线离散对数一样困难。 deg(f)：多项式f(x)的次数。 E：有限域上由a和b定义的一条椭圆曲线。 E(Fq)：Fq上椭圆曲线E的所有有理点(包括无穷远点O)组成的集合。 ECDLP：椭圆曲线离散对数问题。 Fp：包含p个元素的素域。 Fq：包含q个元素的素域。 F ∗ q ：由Fq中所有非零元构成的乘法群。 F2 m：包含2 m个元素的二元扩域。 G：椭圆曲线的一个基点，其阶为素数。 gcd(x,y)：x和y的最大公因子。 h：余因子，h = #E(Fq)/n，其中n是基点G的阶。 Le ftRotate( )：循环左移运算。 lmax：余因子h的最大素因子的上界。 m：二元扩域F2 m关于F2的扩张次数。 mod f(x)：模多项式f(x)的运算。若f(x)是二元域上的多项式，则所有系数执行模2运算。 modn：模n运算。例如，23mod7=2。 n：基点G的阶(n是#E(Fq)的素因子)。 O：椭圆曲线上的一个特殊点，称为无穷远点或零点，是椭圆曲线加法群的单位元。 P：P = (xP,yP)是椭圆曲线上除O之外的一个点，其坐标xP，yP满足椭圆曲线方程。 P1 +P2：椭圆曲线E上两个点P1与P2的和。 p：大于3的素数。 q：有限域Fq中元素的数目。 rmin：基点G的阶n的下界。 Tr( )：迹函数。 xP：点P的x坐标。 x −1 modn：使得x · y ≡ 1 (modn)成立的唯一整数y，1 ≤ y ≤ n−1，gcd(x,n)=1。 x ∥ y：x与y的拼接，其中x和y是比特串或字节串。 x ≡ y (modn)：x与y模n同余。亦即，x modn = y modn。 yP：点P的y坐标。 y˜P：yP的点压缩表示。 Zp：整数模p的剩余类环。 1
(G):基点G生成的循环群。 [kP:椭圆曲线上点P的k倍点，即：[P=P+P+…+P,其中k是正整数。 k个 [x,小：大于或等于x且小于或等于y的整数的集合。 「x:顶函数，大于或等于x的最小整数。例如，「7]=7，「8.3]=9。 Lx小：底函数，小于或等于x的最大整数。例如，7=7,8.3)=8。 #E(F):E(F)上点的数目，称为椭圆曲线E(F)的阶。 ⊕：长度相等的两个比特串按比特的异或运算。 3域和椭圆曲线 3.1有限域 3.1.1概述 本条给出有限域F,的描述及其元素的表示，q是一个奇素数或者是2的方幂。当q是奇素数时，要 求p>2191:当g是2的方幂2m时，要求m>192且为素数。 3.1.2素域Fp 当q是奇素数p时，素域F中的元素用整数0,1,2，·，p-1表示。 a)加法单位元是整数0： b)乘法单位元是整数1： c)域元素的加法是整数的模p加法，即若a,b∈Fp,则a+b=(a+b)modp: d)域元素的乘法是整数的模p乘法，即若a,b∈Fp,则ab=(a·b)modp。 3.13二元扩域F2 当q是2的方幂2m时，二元扩域F2.可以看成F2上的m维向量空间，其元素可用长度为m的比特串表 示。 F2中的元素有多种表示方法，其中最常用的两种方法是多项式基(PB)表示（参见附录A.2.1.I)和正 规基NB)表示（参见附录A.2.1.3)。基的选择原则是使得F中的运算效率尽可能高。本文本并不规定基 的选择。下面以多项式基表示为例说明二元扩域F2m。 设F3上m次不可约多项式f(x)=xm+fm-1xm-1++fx2+fx+f6(其中f后∈乃2，i=0,1,…,m-1)是 二元扩域F2的约化多项式。F由E上所有次数低于m的多项式构成。多项式集合{m-1,m-2,…,x,1}是 F在B上的一组基，称为多项式基。F中的任意一个元素a(x)=am-1xm-1+am-2x-2+…十ax十 ao在F2上的系数恰好构成了长度为m的比特串，用a=(am-1,am-2,…,a1,ao)表示。 a)零元0用全0比特串表示： b)乘法单位元1用比特串(00.001)表示： c)两个域元素的加法为比特串的按比特异或运算： d)域元素a和b的乘法定义如下：设a和b对应的F上多项式为a(x)和b(x),则a·b定义为多项 式(a(x)b(x)modf(x)对应的比特串。 3.2有限域上的椭圆曲线 有限域F,上的椭圆曲线是由点组成的集合。在仿射坐标系下，椭圆曲线上点P(非无穷远点)的坐标 表示为P=(x,yp),其中xp,yp为满足一定方程的域元素，分别称为点P的x坐标和y坐标。在本文本中， 称F,为基域。 2
⟨G⟩：基点G生成的循环群。 [k]P：椭圆曲线上点P的k倍点，即：[k]P = P+P+···+P | {z } k个 ，其中k是正整数。 [x,y]：大于或等于x且小于或等于y的整数的集合。 ⌈x⌉：顶函数，大于或等于x的最小整数。例如，⌈7⌉ = 7, ⌈8.3⌉ = 9。 ⌊x⌋：底函数，小于或等于x的最大整数。例如，⌊7⌋ = 7, ⌊8.3⌋ = 8。 #E(Fq)：E(Fq)上点的数目，称为椭圆曲线E(Fq)的阶。 ⊕：长度相等的两个比特串按比特的异或运算。 3 域和椭圆曲线 3.1 有限域 3.1.1 概述 本条给出有限域Fq的描述及其元素的表示，q是一个奇素数或者是2的方幂。当q是奇素数p时，要 求p > 2 191；当q是2的方幂2 m时，要求m > 192且为素数。 3.1.2 素域Fp 当q是奇素数p时，素域Fp中的元素用整数0,1,2,··· , p−1表示。 a) 加法单位元是整数0； b) 乘法单位元是整数1； c) 域元素的加法是整数的模p加法，即若a,b ∈ Fp，则a+b = (a+b) modp； d) 域元素的乘法是整数的模p乘法，即若a,b ∈ Fp，则a · b = (a · b) modp。 3.1.3 二元扩域F2 m 当q是2的方幂2 m时，二元扩域F2 m可以看成F2上的m维向量空间，其元素可用长度为m的比特串表 示。 F2 m中的元素有多种表示方法，其中最常用的两种方法是多项式基(PB)表示(参见附录A.2.1.1)和正 规基(NB)表示(参见附录A.2.1.3)。基的选择原则是使得F2 m中的运算效率尽可能高。本文本并不规定基 的选择。下面以多项式基表示为例说明二元扩域F2 m。 设F2上m次不可约多项式f(x) = x m + fm−1x m−1 +···+ f2x 2 + f1x+ f0(其中fi ∈ F2, i = 0,1,··· ,m−1)是 二元扩域F2 m的约化多项式。F2 m由F2上所有次数低于m的多项式构成。多项式集合{x m−1 ,x m−2 ,··· ,x,1}是 F2 m 在F2上的一组基，称为多项式基。F2 m中的任意一个元素a(x) = am−1x m−1 + am−2x m−2 + ··· + a1x + a0在F2上的系数恰好构成了长度为m的比特串，用a = (am−1,am−2,··· ,a1,a0)表示。 a) 零元0用全0比特串表示； b) 乘法单位元1用比特串(00···001)表示； c) 两个域元素的加法为比特串的按比特异或运算； d) 域元素a和b的乘法定义如下：设a和b对应的F2上多项式为a(x)和b(x)，则a · b定义为多项 式(a(x)b(x)) mod f(x)对应的比特串。 3.2 有限域上的椭圆曲线 有限域Fq上的椭圆曲线是由点组成的集合。在仿射坐标系下，椭圆曲线上点P(非无穷远点)的坐标 表示为P = (xP,yP)，其中xP, yP为满足一定方程的域元素，分别称为点P的x坐标和y坐标。在本文本中， 称Fq为基域。 2
关于椭圆曲线更多的背景知识，参见附录A.1和A.2。 在本文本中，如果不做特别说明，椭圆曲线上的点均采用仿射坐标表示。 3.2.1Fn上的椭圆曲线 定义在F,(p是大于3的素数)上的椭圆曲线方程为： y2=x3+ax+b,a,b∈Fp,且(43+27b2)modp≠0. ……(1) 椭圆曲线E(F)定义为： E(F)={(x,y)x,y∈Fp,且满足方程(1)LU{O},其中O是无穷远点。 椭圆曲线E(F)上的点的数目用#E(F)表示，称为椭圆曲线E(F)的阶。 3.2.2F2m上的椭圆曲线 定义在F上的椭圆曲线方程为： y2+xy=x3+ax2+b, a,b∈Fm,且b≠0。 ……(2) 椭圆曲线E(F2)定义为： E(F)={(x,y)x,y∈F2,且满足方程(2)儿U{O},其中O是无穷远点。 椭圆曲线E(F)上的点的数目用#E(F2)表示，称为椭圆曲线E(F2)的阶。 3.2.3椭圆曲线群 3.2.31F,上的椭圆曲线群 椭圆曲线E(F,)上的点按照下面的加法运算规则，构成一个交换群： a)0+0=0: b)P=(x,y)∈E(F)八{O},P+O=O+P=P: c)P=(x,y)∈E(E八{O,P的逆元素-P=(x,-y),P+(-P)=O: d)两个非互逆的不同点相加的规则： 设P=(x1,y)∈E(Fp)八{O},B=(2,y2)∈E(F)八{O},且≠x2, 设P=(x3,y3)=P+B,则 x3=入2-x1-2 y3=入(x1-x3)-y1, 其中 1=2-” 2一x1 e)倍点规则： 设B=(x1y1)∈E(F)八{O},且y1卡0，P=(y)=乃+B,则 x3=22-2x1 y3=入(x1-x3)-y1, 其中 -3+a 2y1 3
关于椭圆曲线更多的背景知识，参见附录A.1和A.2。 在本文本中，如果不做特别说明，椭圆曲线上的点均采用仿射坐标表示。 3.2.1 Fp上的椭圆曲线 定义在Fp(p是大于3的素数)上的椭圆曲线方程为： y 2 = x 3 +ax+b， a,b ∈ Fp，且(4a 3 +27b 2 ) modp ̸= 0。 ·····················(1) 椭圆曲线E(Fp)定义为： E(Fq) = {(x,y)|x,y ∈ Fp，且满足方程(1)} ∪ {O}，其中O是无穷远点。 椭圆曲线E(Fp)上的点的数目用#E(Fq)表示，称为椭圆曲线E(Fp)的阶。 3.2.2 F2 m上的椭圆曲线 定义在F2 m上的椭圆曲线方程为： y 2 +xy = x 3 +ax2 +b， a,b ∈ F2 m，且b ̸= 0。 ·····················(2) 椭圆曲线E(F2 m )定义为： E(F2 m ) = {(x,y)|x,y ∈ F2 m，且满足方程(2)} ∪ {O}，其中O是无穷远点。 椭圆曲线E(F2 m )上的点的数目用#E(F2 m )表示，称为椭圆曲线E(F2 m )的阶。 3.2.3 椭圆曲线群 3.2.3.1 Fp上的椭圆曲线群 椭圆曲线E(Fp)上的点按照下面的加法运算规则，构成一个交换群： a) O+O = O； b) ∀P = (x,y) ∈ E(Fp)\{O}，P+O = O+P = P； c) ∀P = (x,y) ∈ E(Fp)\{O}，P的逆元素−P = (x,−y)，P+ (−P) = O； d) 两个非互逆的不同点相加的规则： 设P1 = (x1,y1) ∈ E(Fp)\{O}，P2 = (x2,y2) ∈ E(Fp)\{O}，且x1 ̸= x2， 设P3 = (x3,y3) = P1 +P2，则 { x3 = λ 2 −x1 −x2, y3 = λ(x1 −x3)−y1, 其中 λ = y2 −y1 x2 −x1 ； e) 倍点规则： 设P1 = (x1,y1) ∈ E(Fp)\{O}，且y1 ̸= 0，P3 = (x3,y3) = P1 +P1，则 { x3 = λ 2 −2x1, y3 = λ(x1 −x3)−y1, 其中 λ = 3x 2 1 +a 2y1 。 3
3.2.3.2F2m上的椭圆曲线群 椭圆曲线E(F)上的点按照下面的加法运算规则，构成一个交换群： a)0+0=O: b)P=(x,y)∈E(F)八{O},P+O=O+P=P; c)P=(x,y)∈E(F3)八{O},P的逆元素-P=(x,x+y),P+(-P)=O: d)两个非互逆的不同点相加的规则： 设P=(x1,y)∈E(F)八{O,B=(x2,2)∈E(F=八{O},且x卡， 设P=(xy3)=B+B,则 x3=2+入+x1+x+a, 、y3=入(x1+x3)+3十y1, 其中 入=4+2； x1十x2 e)倍点规则： 设B=(m,y1)∈E(F=)八{O},且x≠0，P=(x3y3)=P+A,则 x3=22+入+a, y=x+(2+1)x3, 其中 1=:+上。 3.2.4椭圆曲线多倍点运算 椭圆曲线上同一个点的多次加称为该点的多倍点运算。设k是一个正整数，P是椭圆曲线上的点， 称点P的k次加为点P的k倍点运算，记为Q=[kP=P+P+…+P。因为[kP=[k-1P+P,所以k倍点 k个 可以递归求得。 多倍点运算的输出有可能是无穷远点O。 多倍点运算也可以通过一些技巧更有效地实现，参见附录A3。 3.2.5椭圆曲线离散对数问题(ECDLP) 已知椭圆曲线E(F,小阶为的点P∈E(E,)及Q∈(P),椭圆曲线离散对数问题是指确定整数l∈ [0,n-1,使得Q=[P成立。 椭圆曲线离散对数问题关系到椭圆曲线密码系统的安全，因此必须选择安全的椭圆曲线。关于如 何选择安全椭圆曲线，参见附录A.4。 3.2.6弱椭圆曲线 若某椭圆曲线存在优于n2级（是基点的阶）计算复杂度的攻击方法，则称此曲线为弱椭圆曲线。 在本文本中禁止使用弱椭圆曲线。 Fg上的超奇异曲线（有限域F,的特征整除q+1-#E(Fg)和Fp上的异常(Anomalous)曲线(#E(Fg)= p)都是弱椭圆曲线。 4
3.2.3.2 F2 m上的椭圆曲线群 椭圆曲线E(F2 m )上的点按照下面的加法运算规则，构成一个交换群： a) O+O = O； b) ∀P = (x,y) ∈ E(F2 m )\{O}，P+O = O+P = P； c) ∀P = (x,y) ∈ E(F2 m )\{O}，P的逆元素−P = (x,x+y)，P+ (−P) = O； d) 两个非互逆的不同点相加的规则： 设P1 = (x1,y1) ∈ E(F2 m )\{O}，P2 = (x2,y2) ∈ E(F2 m )\{O}，且x1 ̸= x2， 设P3 = (x3,y3) = P1 +P2，则 { x3 = λ 2 +λ+x1 +x2 +a, y3 = λ(x1 +x3) +x3 +y1, 其中 λ = y1 +y2 x1 +x2 ； e) 倍点规则： 设P1 = (x1,y1) ∈ E(F2 m )\{O}，且x1 ̸= 0，P3 = (x3,y3) = P1 +P1，则 { x3 = λ 2 +λ+a, y3 = x 2 1 + (λ+1)x3, 其中 λ = x1 + y1 x1 。 3.2.4 椭圆曲线多倍点运算 椭圆曲线上同一个点的多次加称为该点的多倍点运算。设k是一个正整数，P是椭圆曲线上的点， 称点P的k次加为点P的k倍点运算，记为Q = [k]P = P+P+···+P | {z } k个 。因为[k]P = [k −1]P+P，所以k倍点 可以递归求得。 多倍点运算的输出有可能是无穷远点O。 多倍点运算也可以通过一些技巧更有效地实现，参见附录A.3。 3.2.5 椭圆曲线离散对数问题(ECDLP) 已知椭圆曲线E(Fq)、阶为n的点P ∈ E(Fq)及Q ∈ ⟨P⟩，椭圆曲线离散对数问题是指确定整数l ∈ [0,n−1]，使得Q = [l]P成立。 椭圆曲线离散对数问题关系到椭圆曲线密码系统的安全，因此必须选择安全的椭圆曲线。关于如 何选择安全椭圆曲线，参见附录A.4。 3.2.6 弱椭圆曲线 若某椭圆曲线存在优于n 1/2级(n是基点的阶)计算复杂度的攻击方法，则称此曲线为弱椭圆曲线。 在本文本中禁止使用弱椭圆曲线。 Fq上的超奇异曲线(有限域Fq的特征整除q + 1 − #E(Fq))和Fp上的异常(Anomalous)曲线(#E(Fq) = p)都是弱椭圆曲线。 4