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
引言 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