GB-T 32918.1-2016 信息安全技术 SM2椭圆曲线公钥密码算法 第1部分：总则.pdf

《GB-T 32918.1-2016 信息安全技术 SM2椭圆曲线公钥密码算法 第1部分：总则.pdf》由会员分享，可在线阅读，更多相关《GB-T 32918.1-2016 信息安全技术 SM2椭圆曲线公钥密码算法 第1部分：总则.pdf（46页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、I C S3 5.0 4 0L8 0中 华 人 民 共 和 国 国 家 标 准G B/T3 2 9 1 8.12 0 1 6信息安全技术S M 2椭圆曲线公钥密码算法第1部分:总则I n f o r m a t i o ns e c u r i t y t e c h n o l o g yP u b l i ck e yc r y p t o g r a p h i ca l g o r i t h mS M 2b a s e do ne l l i p t i cc u r v e sP a r t 1:G e n e r a l2 0 1 6-0 8-2 9发布2 0 1 7-0 3-0

2、 1实施中华人民共和国国家质量监督检验检疫总局中 国 国 家 标 准 化 管 理 委 员 会发 布知识星球https:/ 次前言引言1 范围12 符号和缩略语13 域和椭圆曲线2 3.1 有限域2 3.2 有限域上的椭圆曲线34 数据类型及其转换5 4.1 数据类型5 4.2 数据类型转换55 椭圆曲线系统参数及其验证8 5.1 一般要求8 5.2 Fp上椭圆曲线系统参数及其验证8 5.3 F2m上椭圆曲线系统参数及其验证96 密钥对的生成与公钥的验证9 6.1 密钥对的生成9 6.2 公钥的验证1 0附录A(资料性附录)关于椭圆曲线的背景知识1 1 A.1 素域Fp1 1 A.2 二元扩域F

3、2m1 3 A.3 椭圆曲线多倍点运算2 3 A.4 求解椭圆曲线离散对数问题的方法2 6 A.5 椭圆曲线上点的压缩2 7附录B(资料性附录)数论算法2 9 B.1 有限域和模运算2 9 B.2 有限域上的多项式3 3 B.3 椭圆曲线算法3 5附录C(资料性附录)曲线示例3 7 C.1 一般要求3 7 C.2 Fp上椭圆曲线3 7 C.3 F2m上椭圆曲线3 7附录D(资料性附录)椭圆曲线方程参数的拟随机生成及验证3 9 D.1 椭圆曲线方程参数的拟随机生成3 9 D.2 椭圆曲线方程参数的验证4 0参考文献4 1G B/T3 2 9 1 8.12 0 1 6知识星球https:/ 言 G

4、 B/T3 2 9 1 8 信息安全技术 S M 2椭圆曲线公钥密码算法 分为以下5个部分:第1部分:总则;第2部分:数字签名算法;第3部分:密钥交换协议;第4部分:公钥加密算法;第5部分:参数定义。本部分为G B/T3 2 9 1 8的第1部分。本部分按照G B/T1.12 0 0 9给出的规则起草。本部分由国家密码管理局提出。本部分由全国信息安全标准化技术委员会(S A C/T C2 6 0)归口。本部分起草单位:北京华大信安科技有限公司、中国人民解放军信息工程大学、中国科学院数据与通信保护研究教育中心。本部分主要起草人:陈建华、祝跃飞、叶顶峰、胡磊、裴定一、彭国华、张亚娟、张振峰。G B

5、/T3 2 9 1 8.12 0 1 6知识星球https:/ 言 N.K o b l i t z和V.M i l l e r在1 9 8 5年各自独立地提出将椭圆曲线应用于公钥密码系统。椭圆曲线公钥密码所基于的曲线性质如下:有限域上椭圆曲线在点加运算下构成有限交换群,且其阶与基域规模相近;类似于有限域乘法群中的乘幂运算,椭圆曲线多倍点运算构成一个单向函数。在多倍点运算中,已知多倍点与基点,求解倍数的问题称为椭圆曲线离散对数问题。对于一般椭圆曲线的离散对数问题,目前只存在指数级计算复杂度的求解方法。与大数分解问题及有限域上离散对数问题相比,椭圆曲线离散对数问题的求解难度要大得多。因此,在相同安

6、全程度要求下,椭圆曲线密码较其他公钥密码所需的密钥规模要小得多。S M 2是国家密码管理局组织制定并提出的椭圆曲线密码算法标准。G B/T3 2 9 1 8的主要目标如下:G B/T3 2 9 1 8.1定义和描述了S M 2椭圆曲线密码算法的相关概念及数学基础知识,并概述了该部分同其他部分的关系。G B/T3 2 9 1 8.2描述了一种基于椭圆曲线的签名算法,即S M 2签名算法。G B/T3 2 9 1 8.3描述了一种基于椭圆曲线的密钥交换协议,即S M 2密钥交换协议。G B/T3 2 9 1 8.4描述了一种基于椭圆曲线的公钥加密算法,即S M 2加密算法,该算法需使用G B/T3

7、 2 9 0 52 0 1 6定义的S M 3密码杂凑算法。G B/T3 2 9 1 8.5给出了S M 2算法使用的椭圆曲线参数,以及使用椭圆曲线参数进行S M 2运算的示例结果。本部分为G B/T3 2 9 1 8的第1部分,描述了必要的数学基础知识与一般技术,以帮助实现其他各部分所规定的密码机制。G B/T3 2 9 1 8.12 0 1 6知识星球https:/ M 2椭圆曲线公钥密码算法第1部分:总则1 范围G B/T3 2 9 1 8的本部分规定了S M 2椭圆曲线公钥密码算法涉及的必要数学基础知识与相关密码技术,以帮助实现其他各部分所规定的密码机制。本部分适用于基域为素域和二元扩

8、域的椭圆曲线公钥密码算法的设计、开发、使用。2 符号和缩略语下列符号和缩略语适用于本文件。B MOV阈。正数B,使得求取FqB上的离散对数至少与求取Fq上的椭圆曲线离散对数一样困难。d e g(f)多项式f(x)的次数。E有限域上由a和b定义的一条椭圆曲线。E(Fq)Fq上椭圆曲线E的所有有理点(包括无穷远点O)组成的集合。E C D L P椭圆曲线离散对数问题。Fp包含p个元素的素域。Fq包含q个元素的有限域。Fq*由Fq中所有非零元构成的乘法群。F2m包含2m个元素的二元扩域。G椭圆曲线的一个基点,其阶为素数。g c d(x,y)x和y的最大公因子。h余因子,h=#E(Fq)/n,其中n是

9、基点G的阶。L e f t R o t a t e()循环左移运算。lm a x余因子h的最大素因子的上界。m二元扩域F2m关于F2的扩张次数。m o df(x)模多项式f(x)的运算。若f(x)是二元域上的多项式,则所有系数执行模2运算。m o dn模n运算。例如,2 3m o d7=2。n基点G的阶n是#E(Fq)的素因子。O椭圆曲线上的一个特殊点,称为无穷远点或零点,是椭圆曲线加法群的单位元。PP=(xP,yP)是椭圆曲线上除O之外的一个点,其坐标xP,yP满足椭圆曲线方程。P1+P2椭圆曲线E上两个点P1与P2的和。p大于3的素数。q有限域Fq中元素的数目。1G B/T3 2 9 1

10、8.12 0 1 6知识星球https:/ i n基点G的阶n的下界。T r()迹函数。xP点P的x坐标。x-1m o dn使得xy1(m o dn)成立的唯一整数y,1yn-1,g c d(x,n)=1。xyx与y的拼接,其中x和y是比特串或字节串。xy(m o dn)x与y模n同余。亦即,xm o dn=ym o dn。yP点P的y坐标。yPyP的点压缩表示。Zp整数模p的剩余类环。基点G生成的循环群。kP椭圆曲线上点P的k倍点,即:kP=P+P+P k个,其中k是正整数。x,y大于或等于x且小于或等于y的整数的集合。x顶函数,大于或等于x的最小整数。例如,7=7,8.3=9。x底函数,小

11、于或等于x的最大整数。例如,7=7,8.3=8。#E(Fq)E(Fq)上点的数目,称为椭圆曲线E(Fq)的阶。长度相等的两个比特串按比特的异或运算。3 域和椭圆曲线3.1 有限域3.1.1 概述本条给出有限域Fq的描述及其元素的表示,q是一个奇素数或者是2的方幂。当q是奇素数p时,要求p21 9 1;当q是2的方幂2m时,要求m1 9 2且为素数。3.1.2 素域Fp当q是奇素数p时,素域Fp中的元素用整数0,1,2,p-1表示。素域特性如下:a)加法单位元是整数0;b)乘法单位元是整数1;c)域元素的加法是整数的模p加法,即若a,bFp,则a+b=(a+b)m o dp;d)域元素的乘法是整

12、数的模p乘法,即若a,bFp,则ab=(ab)m o dp。3.1.3 二元扩域F2m当q是2的方幂2m时,二元扩域F2m可以看成F2上的m维向量空间,其元素可用长度为m的比特串表示。F2m中的元素有多种表示方法,其中最常用的两种方法是多项式基(P B)表示(参见A.2.1.1)和正规基(N B)表示(参见A.2.1.3)。基的选择原则是使得F2m中的运算效率尽可能高。本部分并不规定基的选择。下面以多项式基表示为例说明二元扩域F2m。设F2上m次不可约多项式f(x)=xm+fm-1xm-1+f2x2+f1x+f0(其中fiF2,i=0,1,m-1)是二元扩域F2m的约化多项式。F2m由F2上所

13、有次数低于m的多项式构成。多项式集合xm-1,xm-2,x,1 是F2m在F2上的一组基,称为多项式基。F2m中的 任意一个元 素a(x)=2G B/T3 2 9 1 8.12 0 1 6知识星球https:/ 00 0 1表示;c)两个域元素的加法为比特串的按比特异或运算;d)域元素a和b的乘法定义如下:设a和b对应的F2上多项式为a(x)和b(x),则ab定义为多项式(a(x)b(x)m o df(x)对应的比特串。3.2 有限域上的椭圆曲线有限域Fq上的椭圆曲线是由点组成的集合。在仿射坐标系下,椭圆曲线上点P(非无穷远点)的坐标表示为P=(xP,yP),其中xP,yP为满足一定方程的域元

14、素,分别称为点P的x坐标和y坐标。在本部分中,称Fq为基域。关于椭圆曲线更多的背景知识,参见附录A中A.1和A.2。在本部分中,如果不做特别说明,椭圆曲线上的点均采用仿射坐标表示。3.2.1 Fp上的椭圆曲线定义在Fp(p是大于3的素数)上的椭圆曲线方程为:y2=x3+a x+b,a,bFp,且(4a3+2 7b2)m o dp0。(1)椭圆曲线E(Fp)定义为,参见C.2:E(Fp)=(x,y)|x,yFp,且满足方程(1)O,其中O是无穷远点。椭圆曲线E(Fp)上的点的数目用#E(Fp)表示,称为椭圆曲线E(Fp)的阶。3.2.2 F2m上的椭圆曲线定义在F2m上的椭圆曲线方程为:y2+x

15、 y=x3+a x2+b,a,bF2m,且b0。(2)椭圆曲线E(F2m)定义为,参见C.3:E(F2m)=(x,y)|x,yF2m,且满足方程(2)O,其中O是无穷远点。椭圆曲线E(F2m)上的点的数目用#E(F2m)表示,称为椭圆曲线E(F2m)的阶。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=

16、(x2,y2)E(Fp)O,且x1x2,设P3=(x3,y3)=P1+P2,则x3=2-x1-x2,y3=(x1-x3)-y1,式中:=y2-y1x2-x1;3G B/T3 2 9 1 8.12 0 1 6知识星球https:/ F2m上的椭圆曲线群椭圆曲线E(F2m)上的点按照下面的加法运算规则,构成一个交换群:a)O+O=O;b)P=(x,y)E(F2m)O,P+O=O+P=P;c)P=(x,y)E(F2m)O,P的逆元素-P=(x,x+y),P+(-P)=O;d)两个非互逆的不同点相加的规则:设P1=(x1,y1)E(F2m)O,P2=(x2,y2)E(F2m)O,且x1x2,设P3=(

17、x3,y3)=P1+P2,则x3=2+x1+x2+a,y3=(x1+x3)+x3+y1,式中:=y1+y2x1+x2;e)倍点规则:设P1=(x1,y1)E(F2m)O,且x10,P3=(x3,y3)=P1+P1,则x3=2+a,y3=x21+(+1)x3,式中:=x1+y1x1。3.2.4 椭圆曲线多倍点运算椭圆曲线上同一个点的多次加称为该点的多倍点运算。设k是一个正整数,P是椭圆曲线上的点,称点P的k次加为点P的k倍点运算,记为Q=kP=P+P+P k。因为kP=k-1P+P,所以k倍点可以递归求得。多倍点运算的输出有可能是无穷远点O。多倍点运算也可以通过一些技巧更有效地实现,参见附录A中

18、A.3。3.2.5 椭圆曲线离散对数问题(E C D L P)已知椭圆曲线E(Fq)、阶为n的点GE(Fq)及Q,椭圆曲线离散对数问题是指确定整数l0,n-1,使得Q=lG成立。椭圆曲线离散对数问题关系到椭圆曲线密码系统的安全,因此应选择安全的椭圆曲线。关于如何选择安全椭圆曲线,参见附录A中A.4。4G B/T3 2 9 1 8.12 0 1 6知识星球https:/ 弱椭圆曲线若某椭圆曲线存在优于n1/2级(n是基点的阶)计算复杂度的攻击方法,则称此曲线为弱椭圆曲线。在本部分中禁止使用弱椭圆曲线。Fq上的超奇异曲线 有限域Fq的特征整除q+1-#E(Fq)和Fp上的异常(A n o m a

19、l o u s)曲线#E(Fp)=p 都是弱椭圆曲线。4 数据类型及其转换4.1 数据类型在本部分中,数据类型包括比特串、字节串、域元素、椭圆曲线上的点和整数。比特串:有序的0和1的序列。字节串:有序的字节序列,其中8比特为1个字节。域元素:有限域Fq中的元素。椭圆曲线上的点:椭圆曲线上的点PE(Fq),或者是一对域元素(xP,yP),其中域元素xP和yP满足椭圆曲线方程,或者是无穷远点O。点的字节串表示有多种形式,用一个字节P C加以标识。无穷远点O的字节串表示是单一的零字节P C=0 0。非无穷远点P=(xP,yP)有如下三种字节串表示形式:a)压缩表示形式,P C=0 2或0 3;b)未

20、压缩表示形式,P C=0 4;c)混合表示形式,P C=0 6或0 7。注:混合表示形式既包含压缩表示形式又包含未压缩表示形式。在实现中,它允许转换到压缩表示形式或者未压缩表示形式。对于椭圆曲线上点的压缩表示形式和混合表示形式,本部分中定为可选形式。椭圆曲线上点的压缩表示形式参见附录A中A.5。4.2 数据类型转换4.2.1 数据类型转换关系图1提供了各种数据类型之间的转换关系,线上的标志是相应数据转换方法所在的条。图1 数据类型和转换约定5G B/T3 2 9 1 8.12 0 1 6知识星球https:/ 整数到字节串的转换输入:非负整数x,以及字节串的目标长度k(其中k满足28kx)。输

21、出:长度为k的字节串M。a)设Mk-1,Mk-2,M0是M的从最左边到最右边的字节;b)M的字节满足:x=k-1i=028iMi。4.2.3 字节串到整数的转换输入:长度为k的字节串M。输出:整数x。a)设Mk-1,Mk-2,M0是M的从最左边到最右边的字节;b)将M转换为整数x:x=k-1i=028iMi。4.2.4 比特串到字节串的转换输入:长度为m的比特串s。输出:长度为k的字节串M,其中k=m/8。a)设sm-1,sm-2,s0是s从最左边到最右边的比特;b)设Mk-1,Mk-2,M0是M从最左边到最右边的字节,则Mi=s8i+7s8i+6s8i+1s8i,其中0ik,当8i+jm,0

22、21 9 1且n4p1/2);f)(选项)余因子h=#E(Fp)/n。5.2.2 Fp上椭圆曲线系统参数的验证椭圆曲线系统参数的生成者应验证下面的条件。椭圆曲线系统参数的用户可选择验证这些条件。输入:Fp上椭圆曲线系统参数的集合。输出:若椭圆曲线系统参数是有效的,则输出“有效”;否则输出“无效”。a)验证q=p是奇素数(参见附录B中B.1.1 0);b)验证a,b,xG和yG是区间0,p-1 中的整数;c)若按照附录D描述的方法拟随机产生椭圆曲线,验证S E E D是长度至少为1 9 2的比特串,且a,b由S E E D派生得到;d)验证(4a3+2 7b2)m o dp0;e)验证yG2xG

23、3+a xG+b(m o dp);f)验证n是素数,n21 9 1且n4p1/2(参见附录B中B.1.1 0);8G B/T3 2 9 1 8.12 0 1 6知识星球https:/ F2m上椭圆曲线系统参数及其验证5.3.1 F2m上椭圆曲线系统参数F2m上的椭圆曲线系统参数包括:a)域的规模q=2m,对F2m中元素表示法(三项式基T P B、五项式基P P B或高斯正规基GN B)的标识,一个F2上的m次约化多项式(若所用的基是T P B或P P B);b)(选项)一个长度至少为1 9 2的比特串S E E D(若按照附录D描述的方法拟随机产生椭圆曲线);c)F2m中的两个元素a和b,它们

24、定义椭圆曲线E的方程:y2+x y=x3+a x2+b;d)基点G=(xG,yG)E(F2m),GO;e)基点G的阶n(要求:n21 9 1且n22+m/2);f)(选项)余因子h=#E(F2m)/n。5.3.2 F2m上椭圆曲线系统参数的验证下面的条件椭圆曲线系统参数的生成者应加以验证。这些条件椭圆曲线系统参数的用户可选择验证。输入:F2m上椭圆曲线系统参数的集合。输出:若椭圆曲线系统参数是有效的,则输出“有效”;否则输出“无效”。a)对某个m,验证q=2m;若所用的是T P B,则验证约化多项式是F2上的不可约三项式(参见表A.3);若所用的是P P B,则验证不存在m次不可约三项式,且约

25、化多项式是F2上的不可约五项式(参见表A.4);若所用的是GN B,则验证m不能被8整除;b)验证a,b,xG和yG是长度为m的比特串;c)若按照附录D描述的方法拟随机产生椭圆曲线,验证S E E D是长度至少为1 9 2的比特串,且a,b由S E E D派生得到;d)验证b0;e)在F2m中验证yG2+xGyG=xG3+axG2+b;f)验证n是一个素数,n21 9 1且n22+m/2(参见附录B中B.1.1 0);g)验证nG=O(参见附录A.3.2);h)(选项)计算h=(2m/2+1)2/n,验证h=h;i)验证抗MOV攻击条件成立(参见附录A中A.4.2.1);j)若以上任何一个验证

26、失败,则输出“无效”;否则输出“有效”。6 密钥对的生成与公钥的验证6.1 密钥对的生成输入:一个有效的Fq(q=p且p为大于3的素数,或q=2m)上椭圆曲线系统参数的集合。输出:与椭圆曲线系统参数相关的一个密钥对(d,P)。a)用随机数发生器产生整数d1,n-2;9G B/T3 2 9 1 8.12 0 1 6知识星球https:/ 公钥的验证6.2.1 Fp上椭圆曲线公钥的验证输入:一个有效的Fp(p3且p为素数)上椭圆曲线系统参数集合及一个相关的公钥P。输出:对于给定的椭圆曲线系统参数,若公钥P是有效的,则输出“有效”;否则输出“无效”。a)验证P不是无穷远点O;b)验证公钥P的坐标xP

27、和yP是域Fp中的元素(即验证xP和yP是区间0,p-1 中的整数);c)验证yP2xP3+a xP+b(m o dp);d)验证nP=O;e)若通过了所有验证,则输出“有效”;否则输出“无效”。6.2.2 F2m上椭圆曲线公钥的验证输入:一个有效的F2m上椭圆曲线系统参数集合及一个相关的公钥P。输出:对于给定的椭圆曲线系统参数,若公钥P是有效的,则输出“有效”;否则输出“无效”。a)验证P不是无穷远点O;b)验证公钥P的坐标xP和yP是域F2m中的元素(即验证xP和yP是长度为m的比特串);c)在F2m中验证y2P+xPyP=x3P+a x2P+b;d)验证nP=O;e)若通过了所有验证,则

28、输出“有效”;否则输出“无效”。注:公钥的验证是可选项。01G B/T3 2 9 1 8.12 0 1 6知识星球https:/ 录 A(资料性附录)关于椭圆曲线的背景知识A.1 素域FpA.1.1 素域Fp的定义设p是一个素数,Fp由0,1,2,p-1 中p个元素构成,称Fp为素域。加法单位元是整数0,乘法单位元是整数1,Fp的元素满足如下运算法则:加法:设a,bFp,则a+b=r,其中r=(a+b)m o dp,r0,p-1。乘法:设a,bFp,则ab=s,其中s=(ab)m o dp,s0,p-1。记F*p是由Fp中所有非零元构成的乘法群,由于F*p是循环群,所以在Fp中至少存在一个元素

29、g,使得Fp中任一非零元都可以由g的一个方幂表示,称g为F*p的生成元(或本原元),即F*p=gi|0ip-2。设a=giF*p,其中0ip-2,则a的乘法逆元为:a-1=gp-1-i。示例1:素域F2,F2=0,1 F2的加法表如表A.1,乘法表如表A.2:表A.1+01001110表A.201000101 示例2:素域F1 9,F1 9=0,1,2,1 8 F1 9中加法的示例:1 0,1 4F1 9,1 0+1 4=2 4,2 4m o d1 9=5,则1 0+1 4=5。F1 9中乘法的示例:7,8F1 9,78=5 6,5 6m o d1 9=1 8,则78=1 8。1 3是F1 9

30、*的一个生成元,则F1 9*中元素可由1 3的方幂表示出来:1 30=1,1 31=1 3,1 32=1 7,1 33=1 2,1 34=4,1 35=1 4,1 36=1 1,1 37=1 0,1 38=1 6,1 39=1 8,1 31 0=6,1 31 1=2,1 31 2=7,1 31 3=1 5,1 31 4=5,1 31 5=8,1 31 6=9,1 31 7=3,1 31 8=1。A.1.2 Fp上椭圆曲线的定义A.1.2.1 概述Fp上椭圆曲线常用的表示形式有两种:仿射坐标表示和射影坐标表示。11G B/T3 2 9 1 8.12 0 1 6知识星球https:/ 仿射坐标表示

31、当p是大于3的素数时,Fp上椭圆曲线方程在仿射坐标系下可以简化为y2=x3+a x+b,其中a,bFp,且使得(4a3+2 7b2)m o dp0。椭圆曲线上的点集记为E(Fp)=(x,y)|x,yFp且满足曲线方程y2=x3+a x+bO,其中O是椭圆曲线的无穷远点。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,P3=(x3,y3)=P1+P2O,则x3=2-x

32、1-x2,y3=(x1-x3)-y1,其中=y2-y1x2-x1,若x1x2,3x12+a2y1,若x1=x2且P2-P1。示例3:有限域F1 9上一条椭圆曲线 F1 9上方程:y2=x3+x+1,其中a=1,b=1。则F1 9上曲线的点为:(0,1),(0,1 8),(2,7),(2,1 2),(5,6),(5,1 3),(7,3),(7,1 6),(9,6),(9,1 3),(1 0,2),(1 0,1 7),(1 3,8),(1 3,1 1),(1 4,2),(1 4,1 7),(1 5,3),(1 5,1 6),(1 6,3),(1 6,1 6),则E(F1 9)有2 1个点(包括无穷

33、远点O)。a)取P1=(1 0,2),P2=(9,6),计算P3=P1+P2:=y2-y1x2-x1=6-29-1 0=4-1=-41 5(m o d 1 9),x3=1 52-1 0-9=2 2 5-1 0-91 6-1 0-9=-31 6(m o d 1 9),y3=1 5(1 0-1 6)-2=1 5(-6)-23(m o d 1 9),所以P3=(1 6,3)。b)取P1=(1 0,2),计算2P1:=3x12+a2y1=31 02+122=35+14=1 64=4(m o d 1 9),x3=42-1 0-1 0=-41 5(m o d 1 9),y3=4(1 0-1 5)-2=-2

34、 21 6(m o d 1 9),所以2P1=(1 5,1 6)。A.1.2.3 射影坐标表示A.1.2.3.1 标准射影坐标系当p是大于3的素数时,Fp上椭圆曲线方程在标准射影坐标系下可以简化为y2z=x3+a x z2+b z3,其中a,bFp,且4a3+2 7b20m o dp。椭圆曲线上的点集记为E(Fp)=(x,y,z)|x,y,zFp且满足曲线方程y2z=x3+a x z2+b z3。对于(x1,y1,z1)和(x2,y2,z2),若存在某个uFp且u0,使得:x1=u x2,y1=u y2,z1=u z2,则称这两个三元组等价,表示同一个点。若z0,记X=x/z,Y=y/z,则可

35、从标准射影坐标表示转化为仿射坐标表示:Y2=X3+a X+b;若z=0,(0,1,0)对应的仿射坐标系下的点即无穷远点O。21G B/T3 2 9 1 8.12 0 1 6知识星球https:/ x,-u y,u z),uFp且u 0,P+(-P)=O;d)设点P1=(x1,y1,z1)E(Fp)O,P2=(x2,y2,z2)E(Fp)O,P3=P1+P2=(x3,y3,z3)O,若P1P2,则:1=x1z2,2=x2z1,3=1-2,4=y1z2,5=y2z1,6=4-5,7=1+2,8=z1z2,9=32,1 0=39,1 1=862-79,x3=31 1,y3=6(91-1 1)-41

36、0,z3=1 08;若P1=P2,则:1=3x12+a z12,2=2y1z1,3=y12,4=3x1z1,5=22,6=12-84,x3=26,y3=1(44-6)-253,z3=25。A.1.2.3.2 J a c o b i a n加重射影坐标系Fp上椭圆曲线方程在J a c o b i a n加重射影坐标系下可以简化为y2=x3+a x z4+b z6。其中a,bFp,且4a3+2 7b20m o dp。椭圆曲线上的点集记为E(Fp)=(x,y,z)|x,y,zFp且满足曲线方程y2=x3+a x z4+b z6。对于(x1,y1,z1)和(x2,y2,z2),若存在某个uFp且u0,

37、使得:x1=u2x2,y1=u3y2,z1=u z2,则称这两个三元组等价,表示同一个点。若z0,记X=x/z2,Y=y/z3,则可从J a c o b i a n加重射影坐标表示转化为仿射坐标表示:Y2=X3+a X+b;若z=0,(1,1,0)对应的仿射坐标系下的点即无穷远点O。J a c o b i a n加重射影坐标系下,E(Fp)上点的加法运算定义如下:a)O+O=O;b)P=(x,y,z)E(Fp)O,P+O=O+P=P;c)P=(x,y,z)E(Fp)O,P的逆元素-P=(u2x,-u3y,u z),uFp且u 0,P+(-P)=O;d)设点P1=(x1,y1,z1)E(Fp)O

38、,P2=(x2,y2,z2)E(Fp)O,P3=P1+P2=(x3,y3,z3)O,若P1P2,则:1=x1z22,2=x2z12,3=1-2,4=y1z23,5=y2z13,6=4-5,7=1+2,8=4+5,x3=62-732,y3=6(132-x3)-433,z3=z1z23;若P1=P2,则:1=3x12+a z14,2=4x1y12,3=8y14,x3=12-22,y3=1(2-x3)-3,z3=2y1z1。A.1.3 Fp上椭圆曲线的阶Fp(p为大于3的素数)上一条椭圆曲线的阶是指点集E(Fp)中元素的个数,记为#E(Fp)。由H a s s e定理知:p+1-2p1/2#E(Fp

39、)p+1+2p1/2。若一条曲线的阶#E(Fp)=p+1,则称此曲线为超奇异的,否则为非超奇异的。A.2 二元扩域F2mA.2.1 二元扩域F2m的定义由2m个元素构成的有限域F2m是F2的m次扩张,称为m次二元扩域。F2m可以看成F2上维数为31G B/T3 2 9 1 8.12 0 1 6知识星球https:/ 为F2m在F2上的一组基。给定这样一组基,就可以由向量(a0,a1,am-1)来表示域元素。F2m在F2上的基有多种选择,域元素的加法在不同的基下的运算规则是一致的,都可以通过向量按分量异或运算得到;域元素的乘法在不同的基下有不同的运算规则(如用多项式基表示和用正规基表示时其运算规

40、则就不一致)。A.2.1.1 多项式基设F2上m次不可约多项式f(x)=xm+fm-1xm-1+f2x2+f1x+f0(其中fiF2,i=0,1,m-1)是二元扩域F2m的约化多项式。F2m由F2上所有次数低于m的多项式构成,即:F2m=am-1xm-1+am-2xm-2+a1x+a0|aiF2,i=0,1,m-1。多项式集合xm-1,xm-2,x,1 是F2m作为向量空间在F2上的一组基,称为多项式基。域元素am-1xm-1+am-2xm-2+a1x+a0相对多项式基可以由长度为m的比特串(am-1am-2a1a0)来表示,所以F2m=(am-1am-2a1a0)|aiF2,i=0,1,m-

41、1。乘法单位元1由(0 00 1)表示,零元由(0 00 0)表示。域元素的加法和乘法定义如下:加法运算(am-1am-2a1a0),(bm-1bm-2b1b0)F2m,则(am-1am-2a1a0)+(bm-1bm-2b1b0)=(cm-1cm-2c1c0),其中ci=aibi,i=0,1,m-1,亦即,加法运算按分位异或运算执行。乘法运算(am-1am-2a1a0),(bm-1bm-2b1b0)F2m,则(am-1am-2a1a0)(bm-1bm-2b1b0)=(rm-1rm-2r1r0),其中多项式(rm-1xm-1+rm-2xm-2+r1x+r0)是(am-1xm-1+am-2xm-2

42、+a1x+a0)(bm-1xm-1+bm-2xm-2+b1x+b0)在F2上m o df(x)的余式。注意,F2m恰包含2m个元素。记F2m*是由F2m中所有非零元构成的乘法群,F2m*是循环群,在F2m中至少存在一个元素g,使得F2m中任一非零元都可以由g的一个方幂表示,称g为F2m*的生成元(或本原元),即:F2m*=gi|0i2m-2。设a=giF2m*,其中0i2m-2,则a的乘法逆元为:a-1=g2m-1-i。示例4:二元扩域F25的多项式基表示取F2上的一个不可约多项式f(x)=x5+x2+1,则F25中的元素是:(0 0 0 0 0),(0 0 0 0 1),(0 0 0 1 0

43、),(0 0 0 1 1),(0 0 1 0 0),(0 0 1 0 1),(0 0 1 1 0),(0 0 1 1 1),(0 1 0 0 0),(0 1 0 0 1),(0 1 0 1 0),(0 1 0 1 1),(0 1 1 0 0),(0 1 1 0 1),(0 1 1 1 0),(0 1 1 1 1),(1 0 0 0 0),(1 0 0 0 1),(1 0 0 1 0),(1 0 0 1 1),(1 0 1 0 0),(1 0 1 0 1),(1 0 1 1 0),(1 0 1 1 1),(1 1 0 0 0),(1 1 0 0 1),(1 1 0 1 0),(1 1 0 1 1

44、),(1 1 1 0 0),(1 1 1 0 1),(1 1 1 1 0),(1 1 1 1 1)。加法:(1 1 0 1 1)+(1 0 0 1 1)=(0 1 0 0 0)乘法:(1 1 0 1 1)(1 0 0 1 1)=(0 0 1 0 0)(x4+x3+x+1)(x4+x+1)=x8+x7+x4+x3+x2+1=(x5+x2+1)(x3+x2+1)+x2x2(m o df(x)即x2是(x4+x3+x+1)(x4+x+1)除以f(x)的余式。乘法单位元是(0 0 0 0 1),=x是F25*的一个生成元,则的方幂为:0=(0 0 0 0 1),1=(0 0 0 1 0),2=(0 0

45、 1 0 0),3=(0 1 0 0 0),4=(1 0 0 0 0),5=(0 0 1 0 1),6=(0 1 0 1 0),7=(1 0 1 0 0),8=(0 1 1 0 1),9=(1 1 0 1 0),1 0=(1 0 0 0 1),1 1=(0 0 1 1 1),1 2=(0 1 1 1 0),1 3=(1 1 1 0 0),1 4=(1 1 1 0 1),1 5=(1 1 1 1 1),1 6=(1 1 0 1 1),1 7=(1 0 0 1 1),1 8=(0 0 0 1 1),1 9=(0 0 1 1 0),2 0=(0 1 1 0 0),2 1=(1 1 0 0 0),2

46、2=(1 0 1 0 1),2 3=(0 1 1 1 1),41G B/T3 2 9 1 8.12 0 1 6知识星球https:/ 4=(1 1 1 1 0),2 5=(1 1 0 0 1),2 6=(1 0 1 1 1),2 7=(0 1 0 1 1),2 8=(1 0 1 1 0),2 9=(0 1 0 0 1),3 0=(1 0 0 1 0),3 1=(0 0 0 0 1)。A.2.1.2 三项式和五项式基A.2.1.2.1 概述三项式基(T P B)和五项式基(P P B)是特殊的多项式基。A.2.1.2.2 三项式基F2上的三项式是形如xm+xk+1的多项式,其中1km-1。F2m

47、的一个三项式基表示是由F2上一个m次不可约三项式决定的,只有某些特定的m值存在这样的三项式。上述示例4即为F25的三项式基表示。对1 9 2m5 1 2,表A.3给出了存在m次不可约三项式的每一个m值;并对每个这样的m,给出了最小的k,使得三项式xm+xk+1在F2上是不可约的。表A.3m,km,km,km,km,km,k1 9 3,1 51 9 4,8 71 9 6,31 9 8,91 9 9,3 42 0 1,1 42 0 2,5 52 0 4,2 72 0 7,4 32 0 9,62 1 0,72 1 2,1 0 52 1 4,7 32 1 5,2 32 1 7,4 52 1 8,1 1

48、2 2 0,72 2 3,3 32 2 5,3 22 2 8,1 1 32 3 1,2 62 3 3,7 42 3 4,3 12 3 6,52 3 8,7 32 3 9,3 62 4 1,7 02 4 2,9 52 4 4,1 1 12 4 7,8 22 4 9,3 52 5 0,1 0 32 5 2,1 52 5 3,4 62 5 5,5 22 5 7,1 22 5 8,7 12 6 0,1 52 6 3,9 32 6 5,4 22 6 6,4 72 6 8,2 52 7 0,5 32 7 1,5 82 7 3,2 32 7 4,6 72 7 6,6 32 7 8,52 7 9,52 8 1

49、,9 32 8 2,3 52 8 4,5 32 8 6,6 92 8 7,7 12 8 9,2 12 9 2,3 72 9 4,3 32 9 5,4 82 9 7,53 0 0,53 0 2,4 13 0 3,13 0 5,1 0 23 0 8,1 53 1 0,9 33 1 3,7 93 1 4,1 53 1 6,6 33 1 8,4 53 1 9,3 63 2 1,3 13 2 2,6 73 2 4,5 13 2 7,3 43 2 9,5 03 3 0,9 93 3 2,8 93 3 3,23 3 7,5 53 4 0,4 53 4 2,1 2 53 4 3,7 53 4 5,2 23 4

50、 6,6 33 4 8,1 0 33 5 0,5 33 5 1,3 43 5 3,6 93 5 4,9 93 5 8,5 73 5 9,6 83 6 2,6 33 6 4,93 6 6,2 93 6 7,2 13 6 9,9 13 7 0,1 3 93 7 2,1 1 13 7 5,1 63 7 7,4 13 7 8,4 33 8 0,4 73 8 2,8 13 8 3,9 03 8 5,63 8 6,8 33 8 8,1 5 93 9 0,93 9 1,2 83 9 3,73 9 4,1 3 53 9 6,2 53 9 9,2 64 0 1,1 5 24 0 2,1 7 14 0 4,6 5