ICS35.040 L80 中华人民共和国国家标准 GB/T32918.1—2016 信息安全技术 SM2椭圆曲线公钥密码算法 第1部分:总则 Informationsecuritytechnology— PublickeycryptographicalgorithmSM2basedonellipticcurves— Part1:General 2016-08-29发布 2017-03-01实施 中华人民共和国国家质量监督检验检疫总局 中国国家标准化管理委员会发布目 次 前言 Ⅰ ………………………………………………………………………………………………………… 引言 Ⅱ ………………………………………………………………………………………………………… 1 范围 1 ……………………………………………………………………………………………………… 2 符号和缩略语 1 …………………………………………………………………………………………… 3 域和椭圆曲线 2 …………………………………………………………………………………………… 3.1 有限域 2 ……………………………………………………………………………………………… 3.2 有限域上的椭圆曲线 3 ……………………………………………………………………………… 4 数据类型及其转换 5 ……………………………………………………………………………………… 4.1 数据类型 5 …………………………………………………………………………………………… 4.2 数据类型转换 5 ……………………………………………………………………………………… 5 椭圆曲线系统参数及其验证 8 …………………………………………………………………………… 5.1 一般要求 8 …………………………………………………………………………………………… 5.2 Fp上椭圆曲线系统参数及其验证 8 ………………………………………………………………… 5.3 F2m上椭圆曲线系统参数及其验证 9 ………………………………………………………………… 6 密钥对的生成与公钥的验证 9 …………………………………………………………………………… 6.1 密钥对的生成 9 ……………………………………………………………………………………… 6.2 公钥的验证 10 ………………………………………………………………………………………… 附录A(资料性附录) 关于椭圆曲线的背景知识 11 ……………………………………………………… A.1 素域Fp 11 …………………………………………………………………………………………… A.2 二元扩域F2m 13 ……………………………………………………………………………………… A.3 椭圆曲线多倍点运算 23 …………………………………………………………………………… A.4 求解椭圆曲线离散对数问题的方法 26 …………………………………………………………… A.5 椭圆曲线上点的压缩 27 …………………………………………………………………………… 附录B(资料性附录) 数论算法 29 ………………………………………………………………………… B.1 有限域和模运算 29 …………………………………………………………………………………… B.2 有限域上的多项式 33 ………………………………………………………………………………… B.3 椭圆曲线算法 35 ……………………………………………………………………………………… 附录C(资料性附录) 曲线示例 37 ………………………………………………………………………… C.1 一般要求 37 …………………………………………………………………………………………… C.2 Fp上椭圆曲线 37 …………………………………………………………………………………… C.3 F2m上椭圆曲线 37 …………………………………………………………………………………… 附录D(资料性附录) 椭圆曲线方程参数的拟随机生成及验证 39 ……………………………………… D.1 椭圆曲线方程参数的拟随机生成 39 ………………………………………………………………… D.2 椭圆曲线方程参数的验证 40 ………………………………………………………………………… 参考文献 41 ……………………………………………………………………………………………………GB/T32918.1—2016 前 言 GB/T32918《信息安全技术 SM2椭圆曲线公钥密码算法》分为以下5个部分: ———第1部分:总则; ———第2部分:数字签名算法; ———第3部分:密钥交换协议; ———第4部分:公钥加密算法; ———第5部分:参数定义。 本部分为GB/T32918的第1部分。 本部分按照GB/T1.1—2009给出的规则起草。 本部分由国家密码管理局提出。 本部分由全国信息安全标准化技术委员会(SAC/TC260)归口。 本部分起草单位:北京华大信安科技有限公司、中国人民解放军信息工程大学、中国科学院数据与 通信保护研究教育中心。 本部分主要起草人:陈建华、祝跃飞、叶顶峰、胡磊、裴定一、彭国华、张亚娟、张振峰。 ⅠGB/T32918.1—2016 引 言 N.Koblitz和V.Miller在1985年各自独立地提出将椭圆曲线应用于公钥密码系统。椭圆曲线公 钥密码所基于的曲线性质如下: ———有限域上椭圆曲线在点加运算下构成有限交换群,且其阶与基域规模相近; ———类似于有限域乘法群中的乘幂运算,椭圆曲线多倍点运算构成一个单向函数。 在多倍点运算中,已知多倍点与基点,求解倍数的问题称为椭圆曲线离散对数问题。对于一般椭圆 曲线的离散对数问题,目前只存在指数级计算复杂度的求解方法。与大数分解问题及有限域上离散对 数问题相比,椭圆曲线离散对数问题的求解难度要大得多。因此,在相同安全程度要求下,椭圆曲线密 码较其他公钥密码所需的密钥规模要小得多。 SM2是国家密码管理局组织制定并提出的椭圆曲线密码算法标准。GB/T32918的主要目标如下: ———GB/T32918.1定义和描述了SM2椭圆曲线密码算法的相关概念及数学基础知识,并概述了 该部分同其他部分的关系。 ———GB/T32918.2描述了一种基于椭圆曲线的签名算法,即SM2签名算法。 ———GB/T32918.3描述了一种基于椭圆曲线的密钥交换协议,即SM2密钥交换协议。 ———GB/T32918.4描述了一种基于椭圆曲线的公钥加密算法,即SM2加密算法,该算法需使用 GB/T32905—2016定义的SM3密码杂凑算法。 ———GB/T32918.5给出了SM2算法使用的椭圆曲线参数,以及使用椭圆曲线参数进行SM2运算 的示例结果。 本部分为GB/T32918的第1部分,描述了必要的数学基础知识与一般技术,以帮助实现其他各部 分所规定的密码机制。 ⅡGB/T32918.1—2016 信息安全技术 SM2椭圆曲线公钥密码算法 第1部分:总则 1 范围 GB/T32918的本部分规定了SM2椭圆曲线公钥密码算法涉及的必要数学基础知识与相关密码 技术,以帮助实现其他各部分所规定的密码机制。 本部分适用于基域为素域和二元扩域的椭圆曲线公钥密码算法的设计、开发、使用。 2 符号和缩略语 下列符号和缩略语适用于本文件。 B MOV阈。正数B,使得求取FqB上的离散对数至少与求取Fq上的椭圆曲线离 散对数一样困难。 deg(f) 多项式f(x)的次数。 E 有限域上由a和b定义的一条椭圆曲线。 E(Fq) Fq上椭圆曲线E的所有有理点(包括无穷远点O)组成的集合。 ECDLP 椭圆曲线离散对数问题。 Fp 包含p个元素的素域。 Fq 包含q个元素的有限域。 Fq*由Fq中所有非零元构成的乘法群。 F2m 包含2m个元素的二元扩域。 G 椭圆曲线的一个基点,其阶为素数。 gcd(x,y) x和y的最大公因子。 h 余因子,h=#E(Fq)/n,其中n是基点G的阶。 LeftRotate()循环左移运算。 lmax 余因子h的最大素因子的上界。 m 二元扩域F2m关于F2的扩张次数。 modf(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中元素的数目。 1GB/T32918.1—2016 a,b Fq中的元素,它们定义Fq上的一条椭圆曲线E。 rmin 基点G的阶n的下界。 Tr() 迹函数。 xP 点P的x坐标。 x-1modn 使得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同余。亦即,xmodn=ymodn。 yP 点P的y坐标。 y~ P yP的点压缩表示。 Zp 整数模p的剩余类环。 <G> 基点G生成的循环群。 [k]P 椭圆曲线上点P的k倍点,即:[k]P=P+P+…+P􀮩􀮫 􀮪􀪁