GM/T 0003.1-2012SM2椭圆曲线公钥密码算法第1部分：总则

ICS35040

L80.

备案号36826—2012

:

中华人民共和国密码行业标准

GM/T00031—2012

.

SM2椭圆曲线公钥密码算法

第1部分总则

:

PublickeycryptographicalgorithmSM2basedonellipticcurves—

Part1General

:

2012-03-21发布2012-03-21实施

国家密码管理局发布

GM/T00031—2012

.

目次

前言…………………………

Ⅰ

引言…………………………

Ⅱ

范围………………………

11

符号和缩略语……………

21

域和椭圆曲线……………

32

有限域………………

3.12

有限域上的椭圆曲线………………

3.23

数据类型及其转换………………………

45

数据类型……………

4.15

数据类型转换………………………

4.25

椭圆曲线系统参数及其验证……………

58

一般要求……………

5.18

Fp上椭圆曲线系统参数及其验证…………………

5.28

Fm上椭圆曲线系统参数及其验证………………

5.329

密钥对的生成与公钥的验证……………

69

密钥对的生成………………………

6.19

公钥的验证…………………………

6.29

附录资料性附录关于椭圆曲线的背景知识………

A()11

素域Fp……………

A.111

二元扩域Fm……………………

A.2213

椭圆曲线多倍点运算……………

A.323

求解椭圆曲线离散对数问题的方法……………

A.426

椭圆曲线上点的压缩……………

A.527

附录资料性附录数论算法…………

B()29

有限域和模运算…………………

B.129

有限域上的多项式………………

B.233

椭圆曲线算法……………………

B.335

附录资料性附录曲线示例…………

C()37

一般要求…………………………

C.137

Fp上椭圆曲线……………………

C.237

Fm上椭圆曲线……………………

C.3237

附录资料性附录椭圆曲线方程参数的拟随机生成及验证………

D()39

椭圆曲线方程参数的拟随机生成………………

D.139

椭圆曲线方程参数的验证………………………

D.240

参考文献……………………

41

GM/T00031—2012

.

前言

椭圆曲线公钥密码算法分为个部分

GM/T0003—2012《SM2》5:

第部分总则

———1:;

第部分数字签名算法

———2:;

第部分密钥交换协议

———3:;

第部分公钥加密算法

———4:;

第部分参数定义

———5:。

本部分为的第部分

GM/T00031。

本部分依据给出的规则起草

GB/T1.1—2009。

请注意本文件的某些内容可能涉及专利本文件的发布机构不承担识别这些专利的责任

。。

本部分的附录附录附录和附录为资料性附录

A、B、CD。

本部分由国家密码管理局提出并归口

。

本部分起草单位北京华大信安科技有限公司中国人民解放军信息工程大学中国科学院数据与

:、、

通信保护研究教育中心

。

本部分主要起草人陈建华祝跃飞叶顶峰胡磊裴定一彭国华张亚娟张振峰

:、、、、、、、。

Ⅰ

GM/T00031—2012

.

引言

和在年各自独立地提出将椭圆曲线应用于公钥密码系统椭圆曲线公

N.KoblitzV.Miller1985。

钥密码所基于的曲线性质如下

:

有限域上椭圆曲线在点加运算下构成有限交换群且其阶与基域规模相近

———,;

类似于有限域乘法群中的乘幂运算椭圆曲线多倍点运算构成一个单向函数

———,。

在多倍点运算中已知多倍点与基点求解倍数的问题称为椭圆曲线离散对数问题对于一般椭圆

,,。

曲线的离散对数问题目前只存在指数级计算复杂度的求解方法与大数分解问题及有限域上离散对

,。

数问题相比椭圆曲线离散对数问题的求解难度要大得多因此在相同安全程度要求下椭圆曲线密

,。,,

码较其他公钥密码所需的密钥规模要小得多

。

本部分描述必要的数学基础知识与一般技术以帮助实现其他各部分所规定的密码机制

,。

Ⅱ

GM/T00031—2012

.

SM2椭圆曲线公钥密码算法

第1部分总则

:

1范围

的本部分给出了椭圆曲线公钥密码算法涉及的必要数学基础知识与相关密码技

GM/T0003SM2

术以帮助实现其他各部分所规定的密码机制

,。

本部分适用于基域为素域和二元扩域的椭圆曲线公钥密码算法

。

2符号和缩略语

下列符号和缩略语适用于本部分

。

abFq中的元素它们定义Fq上的一条椭圆曲线E

,:,。

B

B阈正数B使得求取Fq上的离散对数至少与求取Fq上的椭圆曲线离散对数一样困难

:MOV。,。

de多项式x的次数

g(f):f()。

E有限域上由a和b定义的一条椭圆曲线

:。

EFqFq上椭圆曲线E的所有有理点包括无穷远点O组成的集合

():()。

ECDLP椭圆曲线离散对数问题

:。

Fp包含个元素的素域

:p。

Fq包含个元素的有限域

:q。

Fq*由Fq中所有非零元构成的乘法群

:。

m

Fm包含个元素的二元扩域

2:2。

G椭圆曲线的一个基点其阶为素数

:,。

xyx和y的最大公因子

gcd(,):。

h余因子hEFqn其中n是基点G的阶

:,=#()/,。

LetRotate循环左移运算

f():。

l余因子h的最大素因子的上界

max:。

m二元扩域Fm关于F的扩张次数

: