SM2椭圆曲线公钥密码算法 第1部分：总则 Public Key Cryptographic Algorithm SM2 Based on Elliptic Curves Part 1:General 国家密码管理局 2010年12月
SM2椭圆曲线公钥密码算法 第1部分：总则 Public Key Cryptographic Algorithm SM2 Based on Elliptic Curves Part 1: General 国家密码管理局 2010年12月
目次 前言… IV 引言… v 1范围。 2符号和缩略语，，，，，，，，·，，，·，，，， 3域和椭圆曲线 2 31有限域… 2 3.11概述………… 2 3.12素域F。… 2 3.13二元扩域F2m 2 32有限域上的椭圆曲线，，....·.，， 3.2.1F。上的椭圆曲线 3 3.2.2F2m上的椭圆曲线 323椭圆曲线群，，，.，，.，.，，，.，， 3.2.4椭圆曲线多倍点运算 3.2.5椭圆曲线离散对数问题(ECDLP) 4 3.2.6弱椭圆曲线 4数据类型及其转换 5 4.1数据类型…… 5 4.2数据类型转换。 4.2.1整数到字节串的转换 4.2.2字节串到整数的转换...... 6 4.2.3比特串到字节串的转换 6 4.2.4字节串到比特串的转换。 6 4.2.5域元素到字节串的转换 6 4.2.6字节串到域元素的转换 6 4.2.7域元素到整数的转换.·...·.·..· 6 4.2.8点到字节串的转换… > 4.2.9字节串到点的转换.......，..... > 5椭圆曲线系统参数及其验证………… 8 51一般要求，，… 8 5.2F上椭圆曲线系统参数及其验证.. 8 521Fn上椭圆曲线系统参数..... 5.22F。上椭圆曲线系统参数的验证 8 5.3F上椭圆曲线系统参数及其验证… 8 5.3.1F2m上椭圆曲线系统参数… P 532Fm上椭圆曲线系统参数的验证.，.·..··，.. 9 6密钥对的生成与公钥的验证 9 61密钥对的生成，，， 9 62公钥的验证…………… 9 621F2上椭圆曲线公钥的验证… 9 6.2.2F2上椭圆曲线公钥的验证…· 10 I
目 次 前 言 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · IV 引 言 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · V 1 范围· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 1 2 符号和缩略语· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 1 3 域和椭圆曲线· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 2 3.1 有限域 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 2 3.1.1 概述 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 2 3.1.2 素域Fp · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 2 3.1.3 二元扩域F2 m · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 2 3.2 有限域上的椭圆曲线· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 2 3.2.1 Fp上的椭圆曲线 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 3 3.2.2 F2 m上的椭圆曲线 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 3 3.2.3 椭圆曲线群 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 3 3.2.4 椭圆曲线多倍点运算 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 4 3.2.5 椭圆曲线离散对数问题(ECDLP) · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 4 3.2.6 弱椭圆曲线 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 4 4 数据类型及其转换 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 5 4.1 数据类型 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 5 4.2 数据类型转换 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 5 4.2.1 整数到字节串的转换 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 5 4.2.2 字节串到整数的转换 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 6 4.2.3 比特串到字节串的转换 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 6 4.2.4 字节串到比特串的转换 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 6 4.2.5 域元素到字节串的转换 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 6 4.2.6 字节串到域元素的转换 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 6 4.2.7 域元素到整数的转换 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 6 4.2.8 点到字节串的转换 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 7 4.2.9 字节串到点的转换 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 7 5 椭圆曲线系统参数及其验证· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 8 5.1 一般要求 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 8 5.2 Fp上椭圆曲线系统参数及其验证· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 8 5.2.1 Fp上椭圆曲线系统参数 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 8 5.2.2 Fp上椭圆曲线系统参数的验证· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 8 5.3 F2 m上椭圆曲线系统参数及其验证 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 8 5.3.1 F2 m上椭圆曲线系统参数· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 8 5.3.2 F2 m上椭圆曲线系统参数的验证 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 9 6 密钥对的生成与公钥的验证· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 9 6.1 密钥对的生成 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 9 6.2 公钥的验证· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 9 6.2.1 Fp上椭圆曲线公钥的验证 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 9 6.2.2 F2 m上椭圆曲线公钥的验证 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 10 I
附录A(资料性附录)关于椭圆曲线的背景知识. A1素域Fp……………… 11 A11素域Fn的定义… 11 A12F,上椭圆曲线的定义……………… 11 A13F。上椭圆曲线的阶. 13 A2二元扩域F2m 13 A2.1二元扩域Fm的定义.. 13 A22F上椭圆曲线的定义.. 19 A2.3F2上椭圆曲线的阶 22 A3椭圆曲线多倍点运算 22 A.3.1概述·，，，， 22 A3.2椭圆曲线多倍点运算的实现· 22 A.3.3椭圆曲线多倍点运算复杂度估计，.·..，·， 23 A.4求解椭圆曲线离散对数问题的方法 24 A41椭圆曲线离散对数求解方法. 24 A.4.2安全椭圆曲线满足的条件.… 25 A5椭圆曲线上点的压缩… 26 A51概述 26 A5.2F,上椭圆曲线点的压缩与解压缩方法…。 26 A53F2上椭圆曲线点的压缩与解压缩方法…… 26 附录B(资料性附录)数论算法 27 B1有限域和模运算 27 B.1.1有限域中的指数运算 27 B.1.2有限域中的逆运算.…… 27 B.1.3 Lucas序列的生成 27 B.1.4模素数平方根的求解… 28 B1.5迹函数和半迹函数...… 28 B.1.6F2上二次方程的求解 28 B.1.7整数模素数阶的检查… 29 B1.8整数模素数阶的计算. 29 B.1.9模素数的阶为给定值的整数的构造·… 30 B.1.10概率素性检测... 30 B.111近似素性检测… 30 B2有限域上的多项式…… 31 B.21最大公因式… 31 B.2.2F上不可约多项式在Fm中根的求解 31 B.23基的转换……… 31 B.2.4F2上多项式不可约性的检测… 33 B3椭圆曲线算法… 33 B.3.1椭圆曲线阶的计算.… 33 B.32椭圆曲线上点的寻找.....，.... 33 附录C(资料性附录)曲线示例… 35 C1一般要求… 35 C2F。上椭圆曲线… 35 Ⅱ
附录A (资料性附录) 关于椭圆曲线的背景知识 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 11 A.1 素域Fp · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 11 A.1.1 素域Fp的定义 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 11 A.1.2 Fp上椭圆曲线的定义· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 11 A.1.3 Fp上椭圆曲线的阶 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 13 A.2 二元扩域F2 m · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 13 A.2.1 二元扩域F2 m的定义 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 13 A.2.2 F2 m上椭圆曲线的定义 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 19 A.2.3 F2 m上椭圆曲线的阶 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 22 A.3 椭圆曲线多倍点运算 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 22 A.3.1 概述 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 22 A.3.2 椭圆曲线多倍点运算的实现· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 22 A.3.3 椭圆曲线多倍点运算复杂度估计 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 23 A.4 求解椭圆曲线离散对数问题的方法 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 24 A.4.1 椭圆曲线离散对数求解方法· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 24 A.4.2 安全椭圆曲线满足的条件 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 25 A.5 椭圆曲线上点的压缩 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 26 A.5.1 概述 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 26 A.5.2 Fp上椭圆曲线点的压缩与解压缩方法 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 26 A.5.3 F2 m上椭圆曲线点的压缩与解压缩方法 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 26 附录B (资料性附录) 数论算法· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 27 B.1 有限域和模运算 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 27 B.1.1 有限域中的指数运算· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 27 B.1.2 有限域中的逆运算 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 27 B.1.3 Lucas序列的生成 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 27 B.1.4 模素数平方根的求解· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 28 B.1.5 迹函数和半迹函数 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 28 B.1.6 F2 m上二次方程的求解 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 28 B.1.7 整数模素数阶的检查· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 29 B.1.8 整数模素数阶的计算· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 29 B.1.9 模素数的阶为给定值的整数的构造 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 30 B.1.10 概率素性检测 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 30 B.1.11 近似素性检测 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 30 B.2 有限域上的多项式· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 31 B.2.1 最大公因式· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 31 B.2.2 F2上不可约多项式在F2 m中根的求解· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 31 B.2.3 基的转换 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 31 B.2.4 F2上多项式不可约性的检测 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 33 B.3 椭圆曲线算法 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 33 B.3.1 椭圆曲线阶的计算 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 33 B.3.2 椭圆曲线上点的寻找· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 33 附录C (资料性附录) 曲线示例· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 35 C.1 一般要求· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 35 C.2 Fp上椭圆曲线 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 35 II
C3F上椭圆曲线……35 附录D(资料性附录)椭圆曲线方程参数的拟随机生成及验证·····，，，··，，·····，····，····， 37 D1椭圆曲线方程参数的拟随机生成…………………… 37 D11F。上椭圆曲线方程参数的拟随机生成… 37 D12F上椭圆曲线方程参数的拟随机生成……37 D2椭圆曲线方程参数的验证…… 37 D21F。上椭圆曲线方程参数的验证………… 38 D22F2m上椭圆曲线方程参数的验证…… 38 参考文献 39 Ⅲ
C.3 F2 m上椭圆曲线· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 35 附录D (资料性附录) 椭圆曲线方程参数的拟随机生成及验证 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 37 D.1 椭圆曲线方程参数的拟随机生成 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 37 D.1.1 Fp上椭圆曲线方程参数的拟随机生成 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 37 D.1.2 F2 m上椭圆曲线方程参数的拟随机生成 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 37 D.2 椭圆曲线方程参数的验证 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 37 D.2.1 Fp上椭圆曲线方程参数的验证· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 38 D.2.2 F2 m上椭圆曲线方程参数的验证 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 38 参考文献 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 39 III
前言 《SM2椭圆曲线公钥密码算法》分为四个部分： 一第1部分：总则 一第2部分：数字签名算法 一第3部分：密钥交换协议 —第4部分：公钥加密算法 本部分为第1部分。 本部分的附录A、附录B、附录C和附录D为资料性附录。 IV
前 言 《SM2椭圆曲线公钥密码算法》分为四个部分： ──第1部分：总则 ──第2部分：数字签名算法 ──第3部分：密钥交换协议 ──第4部分：公钥加密算法 本部分为第1部分。 本部分的附录A、附录B、附录C和附录D为资料性附录。 IV