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

ICs35,040

L80

备案号:36826-⒛12

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

GM/TO003.1—2012

SM2椭圆曲线公钥密码算法

1部分:总则

PubIickeycryptographicalgorithms⒈

/Ι

Part1:General

⒛12-0S-21发布⒛12-03-21实施

国家密码管理局发布

:

GM/T0003.⒈-2012

目次

…………·……………

前言∵I

…………………………

引言Ⅱ

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.2Fp上及证…………8

椭圆曲线系统参数其验

5,3F2″上椭圆曲线系统参数及其验证………………9

6密钥对的生成与公钥的验证·…………∴………………9

·……………·

6.1密钥对的生成…·……………………9

6.2公钥的验证……………·……………9

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

A.1素域Fp……………11

A.2二元扩域F2″……………………13

A.3椭圆曲线多倍点运算………·……………………23

A`伞求解椭圆曲线离散对数问题的方法·……………26

………·…………………¨

⒋5椭圆曲线上点的压缩27

附录B(资料性附录)数论算法……………·……………29

B.1有限域和模运算…………………29

B.2有限域上的多项式………………33

B.3椭圆曲线算法…∵………………35

附录C(资料性附录)曲线示例…·………37

C.1一般要求………………………¨37

C。2F夕上椭圆曲线·………·…………·………………37

……·……………

C.3F2″上椭圆曲线…37

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

D,1椭圆曲线方程参数的拟随机生成………………¨……………39

D。2椭圆曲线方程参数的验证………………·………40

参考文献……·…………¨…···……………41

〓

丶

●

△

噫{

蕊

畿

盥

缀

GM/T0003.1-2012

邋

如

稷

觳

弘

蘧

弪

扭目刂舀

Ⅱ

Ⅱr

Ⅱ

江

ⅡGM/T0003-2012《SM2椭5个

■

圆曲线公钥密码法》为:

算分部分

■——

■

1部:葸

第分贝刂;

臣rD——第2部分:数字签名算法;

阝r"——第3部分:密钥交换协议;

——第吐部分:公钥加密算法;

——第5部分:参数定义。

本部分为GM/T0003的第1部分。

本部分依据GB/T1,1—2009给出的规则起草。

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

本部分的附录A、附录B、俯录C和附录D为资料性附录。

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

本部分起草单位:北京华大安科限司、工

信技有公中国人民解放军信息程大学、

中国科学院数据与

通信保护研究教育中心。

主:陈、一

本要起人建祝飞、、、

部分草华跃叶顶峰磊、、亚、

胡裴定彭国华张娟张振峰。

时

豺

蜘

——ˉ—ˉ—

————-———·

-2012

GM/T0003。卜

引言

Miller在

N。Kobhtz和V。1985年各自独立地提出将椭圆曲线应用于公钥密码系统。椭圆曲线公

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

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

——

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

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

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

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

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

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

渖

GM/T0003,1-2012

sM2椭

圆曲线公钥密码算法

第1部分:总则

1范围

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

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

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

2符号和缩略语

‘

J·

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

@,D:Fg中的元素,它们定义F日上的一条椭圆曲线E。

B:MOV阈。正数B,使得求取F日:上的离散对数至少与求取F日上的椭圆曲线离散对数一样困难。

g(D:多

d召项式)的次数。

r(∞

E:有限域上由@和乙定义的一条椭圆曲线。

E(F日):Fg上圆E的(包o)组

椭曲线所有有理点括无穷远点成的集合。

ECDLP:椭圆曲线离散对数问题。

Fp:包元

含夕个素的素域。

Fg:包g个

含元素的有限域。

F扌:由F日中所有非零元构成的乘法群。

F2″:包含2″个元素的二元扩域。

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

gcd(茁y的

,丿):茁和最大公因子。

九:余因子,凡=艹E(Fg)/刀,其中刀是基点G的阶。

L犭尕o莎伤彦纟

O:循环左移运算。

Jmax:余九

因子的最大素因子的上界。

勿:二元扩域F2狃关于F2的扩张次数。

mod只

茁

):模多项式)的运算。)是二元上,则2运

r(∝若r(￡域的多项式所有系数执行模算。

mod″刀

:模运算。例如,23mod7=2。

勿:基点G的(m是E(FQ)的)。

阶艹素因子

o:椭圆曲线上的一个特殊点,称为无穷远点或零点,是椭圆曲线加法群的单位元。

P:P=(姊,丿P)是椭圆曲线上除O之外的一,其坐∞

个点标P,丿P满足椭圆曲线方程。

P1+P2:椭圆曲线E上两个点P1与P-的和。

p:大3的。

于素数

g:有限域Fg中元素的数目。

/nlh:基G的勿

点阶的下界

TrO:迹。

函数

∞P的多坐。

P:点标

劣1mod勿劣·≡1(mod刀y,1≤″

:使得)成立-1,gcd(J,彳

丿的唯整数≤)=1。

一丿

CbI/T0003.⒈-2012

J‖:J与y的,其J和

丿拼接中丿是比特串或字节串。

J≡(mod″y模″

):J与mod″

γ同余。亦即,￡=ym°d″。

yP:点P的y坐。

标

yP:yP的压示。

点缩表

z':整环。

数模夕的剩余类

(G):基G/L成的环。

点循群

E硐P:椭圆曲线上点P的乃倍点,即:E乃P=P+P+…+P,其乃正

彐中是整数。

芡

个

Er,列:大于或等于J且小于或等于γ的整数的集合。

Jl:顶函,大J的8.31=9。

「数于或等于最小整数

[别:底函数,小于或等于J的∶,[7J=7,

例如

#E(F〃):E(F日)上点的

⊙:长度相等的两个的异或运算。

3域和椭圆曲线

3.1有限域

3,1.1概

本条给

素数夕时,

要求夕)

3.1,2素

当g是

a)口

力

b)乘法

C)域元整数的模加法,即若伤,乙∈Fp,贝@+乃=(勿+乙)m

夕刂

。

d)ΩFp,贝Ω沙·

域元素数的模夕乘法,即若,D∈刂=(夕a)

3.1.3二元扩域F2淑

当g是2的方幂a9a的

元素可用长度为比特

串表示。

F2″中的元素有多种表示方法,其中最常法是多项式基(PB)表示(参见附录A,2,1,1)

和正规基(NB)表示(参见附录A.2.1.3)。基的选择原则是使得F2″中的运算效率尽可能高。本标准

并不规定基的选择。下面以多项式基表示为例说明二元扩域F2″。

设F2上P9t次不可约多项式F(J)=J刀+F扭1r″1+…+r2J2+F1J+yO(其∈F2,￡=0,1,…,

中氵

∫

9/z-1)是二元扩域F2″的约化多项式。F2″由F2上所有次Paz的。1,

数低于多项式构成多项式集合{J″

2,…″l+

r″,r,1)是F2″在F2上的一组基,称为多项式基。凡中的任意一个元素曰(劣)=‰1J″

夕2+…宓F2上

+夕+勿勿￠

″u″】0在的系数恰好构成了长度为的比特串,用=(@〃l,@″2,…,夕1,@。)

表示。

a)零元0用全0比特串表示;

b)法元1用比00…clO1表

乘单位特串示;

c)两个域元素的加法为比特串的按比特异或运算;

2

GM/T0003.1—⒛12

d)夕3的曰乃F2上@(r)和·

域元素和乘法定义如下:设和对应的多项式D(J),则曰b定

为义为

(曰(J)沙(r))mod∫

多项式(宓)对应的比特串。

3.2有限域上的椭圆曲线

有限Fq上的椭圆是由组。坐,椭上P(非)的

域曲线点成的集合在仿射标系下圆曲线点无穷远点坐

P=(JP,yP),其JP,yP为一,分P的J坐

标表示为中满足定方程的域元素别称为点标和丿坐标。在本

,称Fq为。

标准中基域

关于椭圆曲线更多的背景知识,参见附录A的A.1和A。2。

在本标准中,如果不做特别说明,椭圆曲线上的点均采用仿射坐标表示。

3.2.1FP上的椭圆曲线

定义在Fp(夕是大于3的

ΩF夕2)………………(1)

,,莎∈,ΙL(4沪+27乙

椭圆曲线E(Fp)

E(Fp)=((r,丿p,且(1))∪(o),其O是。

满足方程中无穷远点

椭圆曲线E(

3.2.2凡″

上

定义在F

椭圆曲线

E(F2″)

椭圆曲线)上的点的

3.2.3椭圆曲

3,2.3.1Fp上

椭圆曲线E(F丿照下面的加法运算规则,构成一个交换群:

a)O+O=O;

b)VP=(J,丿

)∈+O=O+P=P;

E(F;

c)VP=(~T,y)∈

d)两个非互逆的不同点相

设P1=(rl,y1)∈E(F户)\{O),且Jl≠J2,

设Ρ〓Jy'3`〓Ρ+Ρ贝

J

=^2~∝1~J2,

γ=^(宓1—r3)一1,

丿

其中

1;

ˉˉˉ

~r2jr1

^=y2^丿

e)倍点规则:

Pl=臼E(Fp)\(O},且yl≠0,P3=(臼,丿

设l,γl)∈3)=P1+P1,

贝刂

J=尸-2rl,

丿(Jl~J3)—

=λy1,

G卜江2012

/T0003.1-ˉ

其中

汪屮。

F2祝上的椭圆曲线群

椭圆曲线E(F2″)上的点按照下面的加法运算规则,构成一个交换群:

°

a)O+O=O;

b)VP=(J,丿)∈E(F2″)\(O),P+O=O+P=P;

c)VP=(劣,丿)∈E(F2″)\(O),P的逆元素一P=(∝,r+y),P+(—P)=O;

d)两个非互逆的不同点相加的规则:

设P1=(Jl,γ1)∈E(F2润)\(O),P2=(宓2,γ2)∈E(F2″)\(O),且Jl≠J2,

设P3=(J3,γ3)=Pl+P2,贝刂

≡!i~∶∶

Ⅰ∴∶∶∶

忮J∶3Ⅰ,

罗∶

f1’

黯

其中

荟

^=蚩∷←⒈

倍占灬删J··

设Ρ冖丿∈EFO岛且~~白白2尸+≠+,0爷〓D,⒍”,γ凵`〓Ρ+Ρ贝

其中力〓⑾马

。

￡

]

^=r1+垫

3,2.4椭圆曲线多倍点运算

椭圆曲线上同一个点的多次加称为该点的多倍点运算。设乃是一个正整数,P是椭圆曲线上的点,

称点P的茈次加为点P的乃倍点运算,记为Q=E乃P=P+P车+P。

彐二因为E乃]P=[乃-1]P+P,所

乃

个

以乃倍点可以递归求得。

多倍点运算的输出有可能是无穷远点O。

多倍点运算也可以通过一些技巧更有效地实现,参见附录A的A.3。

3.2.5椭圆曲线离散对数问题(ECDLP)

已知椭圆曲线E(Fg)、阶为″的点G∈E(Fg)及Q∈(G),椭圆曲线离散对数问题是指确定整数

J∈E0,″-1彐,使得Q=EJ彐G成立。

椭圆曲线离散对数问题关系到椭圆曲线密码系统的安全,因此必须选择安全的椭圆曲线。关于如

何选择安全椭圆曲线,参见附录A的A.4。

3.2.6弱椭圆曲线

l″

(刀

若某椭圆曲线存在优于″级是基点的阶)计算复杂度的攻击方法,则称此曲线为弱椭圆曲线。

在本标准中禁止使用弱椭圆曲线。

Fg上的超奇异曲线(有限域Fg的g+1—Fp上(An。

特征整除#E(F日))和的异malous)曲

常线

(#E(Fp)=夕

)都是弱椭圆曲线。

碴

Gˇ-2012

VT0003。⒈

4数据类型及其转换

4.1数据类型

,数型包比、、、

在本标准中据类括特串字节串域元素椭圆曲线上的点和整数。

比特串:有序的Q和1的序列。

字节串:有序的字节序列,其中8比特为1个字节。

域元素:有限域F日中的元素。

圆曲线上的点:椭圆曲线上的P∈E(Fg),或一(茁免

椭点者是对域元素P,丿P),其中域元素P和P满

丿

足椭圆曲线方程,或者是无穷远点O。

点的字节串表示有多种形式,用一个字节PC加以标识。无穷远点0的字节串表示是单一的零字

节PC=00。非无穷远点P=(JP,γP)有如下三种字节串表示形式:

a)压缩表示形式,PC=02或03;

b)未压缩表示形式,P%=0准;

c)混合表示形式,PC=06或07。

注:混示既包压示又压。,它

合表形式含缩表形式包含未缩示形现

表式在实中允压

许转换到缩表示形式或者未压

示。

缩表形式

对于椭圆曲线上点的压缩表示形式和混合表示形式,本标准中定为可选形式。椭圆曲线上点的压

缩表示形式参见附录A的A,5。

4.2数据类型转换

4.2.1数据类型转换关系

图1提供了各种数据类型之间的转换关系,线上的标志是相应数据转换方法所在的条。

4.2.8条

域元素

4.2.⒍蒸7条

客

比字节串塑∶

特串数

4~2~4屡4.23条

0条9条

点

图1数据类型和转换约定

4.2.2整数到字节串的转换

人:非整J,以及节的目长花(其勿足2:虍>￡)。

输负数字串标度中满

输出:长度为乃的字节串M。

Ι

GM/T0003.1-ˉ2012

a)加f虍·M的

设f乃1,Ⅳ2/·,M是从最左边到最右边的字节;

b)M的:

字节满足

J=∑2⒏M氵

4.2.3字节串到整数的转换

输人:长度为乃的字节串M。

输出:整数J。

a)设·f。M的

吼1,″f乃2'·,Ⅳ是从最左边到最右边的字节;

b)将M转换为整数J:

4.2.4比特串到字

输入:长度

输出:长M,其乃9,z/81。

字节串中=「

a)设

b)

4.2,5

输

输

a)

b)

第f一町+1

4,2.6域元串的转换

输人:Fq中

:长氵=「氵g2ql。

输出度f,其中r=「l。

a)g为

若奇素数,法将α

转换成长度为字节

'的

b)q=2″,贝αr/z

若刂必为长度为4的方法将αJ的

转换成长度为字节串S。

4.2.7字节串到域元素的转换

输人:F日的类型,长度z=「81的S,其=「

为〃字节串中莎log2gl。

输出:F。α

中的元素。

a)g是,则4.2.3的

若奇素数按方法S转αα

将换为整数,若备E0,q-1彐,则报错;

b)若g=2″,贝刂按4.2.5的方法将S转换为长度为9,z的比α

特串。

4.2.8域元素到整数的转换

入:F″α

输中的元素。

输出:整数J。

6

GM/T0003,1-⒛12

a)q为,则J=α(不需要);

若奇素数转换

b)q=2″,贝α,,z的s″α

若刂必为长度为比特串,设1,s″2,…,so是的从最左边到最右边的比特,

α整J:

将转化为数

J=∑2`J

42,9点到字节串的转换

茕人:椭圆曲线上的点P=(幻,yP),且P≠O。

输出:字节串S。若选用未压缩表示形式或混合表示形式,则输出字节串长度为2/+1;若选用压缩

(log,q2/81)。

示,则z+1(z=「

袤形式输出字节串长度为

a)按4.2.6的方法将域元素

b)若选用压缩表示形

b.1)计算A的A,5);

b,2)若1P()=02;若3P=1,则令PC=03;

b,3)PC‖XI。

c)若选示形式,则:

c,1)

⒊

P=O,则

4.2。10字

曰b,字S。

输入:定义线的域元素、节串若选用未压缩表示合表示形式,则字

节串S长度为2'+缩表示形式,则字节串PO长度为Z+1(z/81)。

输出:椭圆曲线工,”),且P≠O。

a)选用压缩表示X1;若选用未示,则S=PC‖

若