GB/T 32918.1-2016 信息安全技术 SM2椭圆曲线公钥密码算法 第1部分：总则

ICS35.040

L80GB

中华人民共和国国彖标准

GB/T32918.1—2016

信息安全技术

SM2椭圆曲线公钥密码算法

第1部分：总则

Informationsecuritytechnology—

PublickeycryptographicalgorithmSM2basedonellipticcurves—

Part1:General

2016-08-29发布2017-03-01实施

GB/T32918.1—2016

目次

,、/d•、-T

刖BI

引言n

1范围1

2符号和缩略语1

3域和椭圆曲线2

3.1有限域2

3.2有限域上的椭圆曲线3

4数据类型及其转换5

4.1数据类型5

4.2数据类型转换5

5椭圆Ittl线系统参数及其验证8

5.1一般要求8

5.2F”上椭圆曲线系统参数及其验证8

5.3F2，”上椭圆曲线系统参数及其验证9

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

6.1密钥对的生成9

6.2公钥的验证10

附录A（资料性附录）关于椭圆曲线的背景知识11

A.1素域F”11

A.2二元扩域F2”，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.2F„上椭圆曲线37

C.3F2，”上椭圆曲线37

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

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

D.2椭圆曲线方程参数的验证40

参考文献41

GB/T32918.1—2016

■ir■■i

刖吕

GB/T32918《信息安全技术SM2椭圆曲线公钥密码算法》分为以下5个部分：

——第1部分:总则；

——第2部分:数字签名算法；

——第3部分:密钥交换协议；

——第4部分:公钥加密算法；

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

本部分为GB/T32918的第1部分.

本部分按照GB/T1.1—2009给出的规则起草。

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

本部分由全国信息安全标准化技术委员会(SAC/TC260)归口。

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

通信保护研究教育中心。

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

T

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部分，描述了必要的数学基础知识与一般技术，以帮助实现其他各部

分所规定的密码机制。

n

GB/T32918.1—2016

信息安全技术

SM2椭圆曲线公钥密码算法

第1部分：总则

1范围

GB/T32918的本部分规定了SM2椭圆曲线公钥密码算法涉及的必要数学基础知识与相关密码

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

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

2符号和缩略语

下列符号和缩略语适用于本文件。

BM（）V阈。正数使得求取F/上的离散对数至少与求取化上的椭圆曲线离

散对数一样困难。

deg(/)多项式_/©）的次数。

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

E(F“)F（,上椭圆曲线E的所有有理点（包括无穷远点O）组成的集合。

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

F»包含〃个元素的素域。

F“包含q个元素的有限域。

FJ由F“中所有非零元构成的乘法群。

F2,,!包含2"个元素的二元扩域。

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

分和y的最大公因子。

h余因子,/?=#E（F“）/”，其中"是基点&的阶。

LeftRotateO循环左移运算。

1max余因子〃的最大素因子的上界。

m二元扩域f2».关于F2的扩张次数。

mod/(n、)模多项式于Cr）的运算。若土（工）是二元域上的多项式，则所有系数执行模2

运算。

modn模"运算。例如，23mod7=2。

n基点&的阶5是#E（F„）的素因子］。

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

PP=（；rp,）5）是椭圆曲线上除O之外的一个点，其坐标满足椭圆曲线

方程。

Pi+P2椭圆曲线E上两个点P】与局的和。

P大于3的素数。

q有限域F“中元素的数目。

1

GB/T32918.1—2016

aF„中的元素，它们定义F“上的一条椭圆曲线E。

•min基点&的阶”的下界。

Tr()迹函数。

Xp点P的坐标。

j'-1modn使得分•j，'=l(mod")成立的唯一整数y,lWy一1,gcdO,”)=1。

才1y■r与)的拼接，其中才和y是比特串或字节串。

x=y(modn)与y模”同余。亦即,jtmodn=,ymodn。

yp点、P的)坐标。

yryr的点压缩表示。

Z”整数模”的剩余类环。

<G>基点&生成的循环群。

阴p椭圆曲线上点P的怡倍点，即：|>]P=P十PP，其中k是正整数。

JV'

小个

[•rO'l大于或等于才且小于或等于的整数的集合。

「厂顶函数，大于或等于工的最小整数。例如，「7]=7,「8.3]=9。

底函数，小于或等于力的最大整数。例如，|_7」=7,|_&3」=8。

#E(F„)E(F“)上点的数目，称为椭圆曲线E(FQ的阶。

e长度相等的两个比特串按比特的异或运算。

3域和椭圆曲线

3.1有限域

3.1.1概述

本条给出有限域F“的描述及其元素的表示,q是一个奇素数或者是2的方幕。当g是奇素数P

时，要求A>2,!"；当q是2的方幕2"时，要求加>192且为素数。

3.1.2素域F”

当q是奇素数°时，素域F”中的元素用整数0,1,2,-,/p-l表示。素域特性如下:

a)加法单位元是整数0；

b)乘法单位元是整数1;

c)域兀素的加法是整数的模p加法，即若a,bGF，则a+6=(a+/>)modp;

d)域元素的乘法是整数的模p乘法，即若a,bGF，则a•b=d•ZOmod”。

3.1.3二元扩域Fl，

当g是2的方幕2"，时，二元扩域F2，”可以看成F2上的丹维向量空间，其元素可用长度为必的比特

串表示。

F2，”中的元素有多种表示方法，其中最常用的两种方法是多项式基(PB)表示(参见A.2.1.1)和正规

基(NB)表示(参见A.2.1.3)。基的选择原则是使得F2，”中的运算效率尽可能高。本部分并不规定基的

选择。下面以多项式基表示为例说明二元扩域F2，”。

设F2Jim次不可约多项式f(j-)—rm+f,n-\xm~x4/2-r2+/ir+fQ(其中/,CF2,/=0,1,

…，加一1)是二元扩域F2，”的约化多项式。F2”，由F2上所有次数低于加的多项式构成。多项式集合

｛才宀，才"一2,...,厂1｝是F2，„在F2上的一组基，称为多项式基。F2，”中的任意一个元素aQ)=

2

GB/T32918.1—2016

a,”-i.r"'T+a”,_2.r"'—$4axx+<20在F?上的系数恰好构成了长度为m的比特串，用a=(a,”_i,

a,”-2,S,a$)表示。多项式域特性如下：

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

b)乘法单位元1用比特串00001表示；

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

d)域元素a和”的乘法定义如下:设a和”对应的F2上多项式为aCr)和〔心),则a-b定义为

多项式(a(才”(工))mod,/'(.r)对应的比特串。

3.2有限域上的椭圆曲线

有限域F“上的椭圆曲线是由点组成的集合。在仿射坐标系下，椭圆曲线上点P(非无穷远点)的坐

标表示为P=Op,yr)，其中,rP为满足一定方程的域元素，分別称为点P的才坐标和坐标。在

本部分中，称F“为基域。

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

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

3.2.1F”上的椭圆曲线

定义在F/p是大于3的素数)上的椭圆曲线方程为：

j'2+ax+/丿，aGF”，且(4a+27，)mod“工0。(1)

橢圆曲线E(F”)定义为，参见C.2：

E(F”)={Cr,y)",)CF”，且满足方程(1)}U{O},其中O是无穷远点。

椭圆曲线E(F”)上的点的数目用井E(F”)表示，称为椭圆曲线E(FQ的阶。

3.2.2F2，”上的椭圆曲线

定义在F2，”上的椭圆曲线方程为：

y2+—jt3+ux2-\~b,a,bGF2，”，且Z>HO。(2)

橢圆曲线E(F2，”)定义为，参见C.3：

E(F2，”)={Cr,y)",yCF2”，，且满足方程(2)}U{O},其中O是无穷远点。

椭圆曲线E(F2，”)上的点的数目用#E(F2，”)表示,称为椭圆曲线E(F2”，)的阶。

3.2.3椭圆曲线群

F”上的椭圆曲线群

懈圆曲线E(F”)上的点按照下面的加法运算规则，构成一个交换群：

a)0+0=0；

b)VP=Cz,y)WE(F”)\{O},P+O=O+P=P；

c)\/P=Cr,y)GE(F”)\{C>},P的逆元素一P=&,—)，),P+(—P)=O；

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

设P】=S，小)GE(F”)\{O},P2=&2,y2)GE(F”)\{G>},且，工心，

设P—Cxy—P\P2,则

|J73=A2——X2,

|y-i=入(,—)—>•i,

式中：

>'2—X

A

■T1

3

GB/T32918.1—2016

e）倍点规则：

设巴=（,，w）GE（F”）\{O},且几=（心，恥）=巴+巴，

则

|3—A22.J"1,

|）3=入O1—心）一卩，

式中：

3j~?+a

Q=—

2yi

F2，”上的椭圆曲线群

陆圆曲线E（F2，”）上的点按照下面的加法运算规则，构成一个交换群：

a）0+0=0；

b）VP=Cr,y）GE（F2，”）\{O},P+O=O+P=P；

c）VP=（f）WE（F2，”）\{O},P的逆元素-P=a,^+y）,P+（~P）=O；

d）两个非互逆的不同点相加的规则：

设Fi=（jci）|GE（F21"）\{O},P>—（_z'2,丿2）€E（F2"）\{O},且/工几,

设凡；=（心，*）=巴+几，则

/、r：-；—A2+A+j"i+jc2+a,

I）：•；=入（^i+x3）+jr3+）i,

式中：

j"i+、r2'

e）倍点规则：

设Fi=（jci,3/!）6E（F2™）\{O}»且厂工0,尸3=（夂3,》3）=Fi+P1，则

|x?,—A2+A+a,

Iy's=./'i+（入+1）心,

式中：

3.2.4椭圆曲线多倍点运算

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

点，称点P的沧次加为点P的沧倍点运算，记为Q=[k]P=P+P+-+Po因为=1]P+

k

p,所以沧倍点可以递归求得。

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

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

3.2.5椭圆曲线离散对数问题（ECDLP）

已知椭圆曲线E（F“）、阶为"的点G6E（F„）及QC〈（；〉，椭圆曲线离散对数问题是指确定整数

/G[O,/z—1],使得Q=[/]G成立。

橢圆曲线离散对数问题关系到椭圆曲线密码系统的安全，因此应选择安全的椭圆曲线。关于如何

选择安全椭圆曲线，参见附录A中A.4。

4

GB/T32918.1—2016

3.2.6弱椭圆曲线

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

在本部分中禁止使用弱椭圆曲线。

F“上的超奇异曲线［有限域F„的特征整除Q+1—#E(F,,)］和F»上的异常(Anomalous)曲线

屏E(F”)=”］都是弱椭圆曲线。

4数据类型及其转换

4.1数据类型

在本部分中，数据类型包括比特串、字节串、域元素、椭圆曲线上的点和整数。

比特串：有序的0和1的序列。

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

域元素：有限域F“中的元素。

椭圆曲线上的点：椭圆曲线上的点FCE(F“)，或者是一对域元素("”),其中域元素厂,和歹卩

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

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

节P('=00。非无穷远点P=,小,)有如下三种字节串表示形式：

a)压缩表示形式，PC=02或03；

b)未压缩表示形式,PC=04；

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

注：混合表示形式既包含压缩表示形式又包含未压缩表示形式。在实现中，它允许转换到压缩表示形式或者未压

缩表示形式。

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

缩表示形式参见附录A中A.5。

4.2数据类型转换

4.2.1数据类型转换关系

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

图1数据类型和转换约定

5

GB/T32918.1—2016

4.2.2整数到字节串的转换

输入：非负整数.7-,以及字节串的目标长度k（其中k满足2嵌＞r）0

输出：长度为怡的字节串M。

a）设Mk-i,M\_2,…是M的从最左边到最右边的字节；

b）A4的字节满足：

k-1

x=Y28iM,

»=0

4.2.3字节串到整数的转换

输入：长度为怡的字节串M。

输出：整数才。

a）设M一是M的从最左边到最右边的字节；

b）将M转换为整数乂：

.r=丈嘶。

/■=0

4.2.4比特串到字节串的转换

输入:长度为m的比特串s。

输出：长度为怡的字节串M,其中怡=「加/8[。

a）设s,”_i,s,”_2，…，s°是$从最左边到最右边的比特；

b）设Mk-i,M\_2,…是M从最左边到最右边的字节，贝9

A4,=.皿+7$8,+….皿+1皿，其中OWe，当8/,0＜jM7时,.g+j=0。

4.2.5字节串到比特串的转换

输入：长度为怡的字节串M。

输出：长度为加的比特串S,其中m=8ko

a）设Ml】，M*_2,…,是M从最左边到最右边的字节；

b）设s,”-i,s,”-2,…,s＜）是$从最左边到最右边的比特，则s：是M,右起第i—8）+1比特，其中j—

4.2.6域元素到字节串的转换

输入:F“中的元素a。

输出：长度/=「〃8-的字节串S,其中/=「log2厂。

a）若q为奇素数，则a必为区间中的整数，按4.2.2的方法把a转换成长度为/的字节

串S；

b）若q=2“，则a必为长度为加的比特串，按4.2.4的方法把a转换成长度为/的字节串S。

4.2.7字节串到域元素的转换

输入:基域F“的类型，长度为/=//8-的字节串S,其中log2Q^

输出：F“中的元素a。

a）若q是奇素数，贝9按4.2.3的方法将S转换为整数a,若a@[0,g—1],则报错；

b）若q=2",则按4.2.5的方法将S转换为长度为加的比特串a。

6

GB/T32918.1—2016

4.2.8域元素到整数的转换

输入:域F“中的元素a。

输出：整数工。

a）若g为奇素数，则z=a（不需要转换）；

b）若q=2"，则a必为长度为加的比特串，设s,”_i,s”,_2,…，s。是a的从最左边到最右边的比特，

将a转化为整数分：

1

./■—〉:2*5iO

■■-0

4.2.9点到字节串的转换

输入:椭圆曲线上的点P=Grp且PMO。

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

缩表示形式,则输出字节串长度为Z+l（/=「（log2g）/8］）。

a）按4.2.6中的方法把域元素转换成长度为/的字节串X】；

b）若选用压缩表示形式，则：

1）计算比特几（参见附录A中A.5）；

2）若>'/>—0,则令PC=02；若y=1，则令PC=03；

3）字节串S=PC||X.；

c）若选用未压缩表示形式，则：

1）按4.2.6的方法把域元素>5转换成长度为I的字节串V,；

2）令PC=04；

3）字节串S=PC||X.||Y,；

d）若选用混合表示形式，则：

1）按4.2.6的方法把域元素*转换成长度为I的字节串Y,；

2）计算比特in（参见附录A中A.5）；

3）若yp=0,则令P（；=06；若yI'—1,则令PC=07；

4）字节串S=PC||X,||Y1

4.2.10字节串到点的转换

输入：定义F“上椭圆曲线的域元素a』，字节串S。若选用未压缩表示形式或混合表示形式，则字

节串S长度为2/+1；若选用压缩表示形式，则字节串PO长度为/+1（/=「（1。£2（/）/8“。

输出：椭圆曲线上的点P=S,*）,且PHO。

a）若选用压缩表示形式，则S=P（；||X】；若选用未压缩表示形式或混合表示形式，则S=

PC||X,||V,，其中PC是单一字节,X|和匕都是长度为/的字节串；

b）按4.2.7的方法把字节串X】转换成域元素、z>；

c）若选用压缩表示形式，则：

1）检验PC=02或者是PC=03,若不是这种情形，则报错；

2）若FC=02,则令彳”=0；若FC=03,则令无=1;

3）将（I,亍卩）转换为椭圆曲线上的一个点（心，*）（参见附录A中A.5）；

d）若选用未压缩表示形式，则：

1）检验PC=04,若不是这种情形，则报错；

7

GB/T32918.1—2016

2）按4.2.7的方法把字节串匕转换成域元素>5；

e）若选用混合表示形式，则：

1）检验P（'=O6或者PC=07,若不是这种情形，则报错；

2）执行步骤如下：

——按4.2.7的细节把字节串转换成域元素*;

——若PC=O6,则令算=0,否则令乔=1;

3）将Gp®p）转换为椭圆曲线上的一个点Gp』p）（参见附录A中A.5）；

f）若q为奇素数,则验证处三处+mp+/‘（modg）,若不是这种情形，则报错；

若q=2"，则在F2，”中验证丿+pj卩=若不是这种情形,则报错;

g）P=Gi>，》“）。

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

5.1一般要求

椭圆曲线系统参数是可以公开的，系统的安全性不依赖于对这些参数的保密。本部分不规定椭圆

曲线系统参数的生成方法，但规定了系统参数的验证方法。椭圆曲线阶的计算和基点的选取方法可参

见附录B中B.3,曲线参数的生成方法可参见附录D。

椭圆曲线系统参数按照基域的不同可以分为两种情形：

——当基域是Fg为大于3的素数）时,F”上的椭圆曲线系统参数；

——当基域是F2，”时,F2，”上的椭圆曲线系统参数。

5.2F.±椭圆曲线系统参数及其验证

5.2.1Fp上椭圆曲线系统参数

F„上椭圆曲线系统参数包括：

a）域的规模q=p,p是大于3的素数；

b）（选项）一个长度至少为192的比特串SEEDC若按照附录D描述的方法产生椭圆曲线）；

c）F”中的两个元素a和"，它们定义椭圆曲线E的方程:b=/+“+"；

d）基点G=（%o'<；）&E（F”）,GHC»;

e）基点G的阶"（要求:h>2191且”>4pz）；

f）（选项）余因子/?=#E（Fp）/"。

5.2.2F„±椭圆曲线系统参数的验证

椭圆曲线系统参数的生成者应验证下面的条件。椭圆曲线系统参数的用户可选择验证这些条件。

输入:F”上椭圆曲线系统参数的集合。

输出：若椭圆曲线系统参数是有效的，则输出“有效”;否则输出“无效”。

a）验证q=p是奇素数（参见附录B中B.1.1O）；

b）验证a,b,xG和是区间［O,“一叮中的整数；

c）若按照附录D描述的方法拟随机产生椭圆曲线，验证SEED是长度至少为192的比特串，且

a,b由SEED派生得到；

d）验证（4a?+27//）modpH0；

e）验证y；'三,；"+a「，+"（mod“）；

f）验证"是素数,«>21!"且">4夕气参见附录B中B.1.10）；

8

GB/T32918.1—2016

g）验证5］（；=C>（参见附录A中A.3）；

h）（选项）计算L=+/"」'并验证h=h'；

i）验证抗MOV攻击条件和抗异常曲线攻击条件成立（参见附录A中A.4.2.1和A.4.2.2）；

j）若以上任何一个验证失败，则输出“无效”;否则，输出“有效”。

5.3F2”，上椭圆曲线系统参数及其验证

5.3.1F2"'_t椭圆曲线系统参数

F2，”上的椭圆曲线系统参数包括：

a）域的规模g=2-，对F2，”中元素表示法（三项式基TPB、五项式基PPB或高斯正规基GNB）的

标识，一个F2上的m次约化多项式（若所用的基是TPB或PPB）；

b）（选项）一个长度至少为192的比特串SEEDC若按照附录D描述的方法拟随机产生椭圆

曲线）;

c）F2，”中的两个元素。和/儿它们定义椭圆曲线E的方程:护+巧,=『；+必2+〃；

d）基点G=仇，九）E（F2，”）,GHO；

e）基点G的阶”（要求：»>2191且">2汀皿）；

f）（选项）余因子h=#E（F2«）/n

5.3.2F2，”上椭圆曲线系统参数的验证

下面的条件椭圆曲线系统参数的生成者应加以验证。这些条件椭圆曲线系统参数的用户可选择

验证。

输入：F2，”上椭圆曲线系统参数的集合。

输岀：若椭圆曲线系统参数是有效的，则输出“有效”;否则输出“无效”。

a）对某个加，验证q=2"；若所用的是TPB,则验证约化多项式是F2上的不可约三项式（参见

表A.3）；若所用的是PPB,则验证不存在m次不可约三项式，且约化多项式是F2上的不可约

五项式（参见表A.4）；若所用的是GNB,则验证m不能被8整除；

b）验证a,1），:r（；和y；是长度为m的比特串；

c）若按照附录D描述的方法拟随机产生椭圆曲线，验证SEED是长度至少为192的比特串，且

a,b由SEED派生得到；

d）验证"H0；

e）在F2”中验证yG2+.『<；）<；=4；3+a.r（；2+6;

f）验证"是一个素数,«>2|!"且”>2汁皿（参见附录B中B.1.10）；

g）验证参见附录A.3.2）；

h）（选项）计算//=|_（2皿+1）2/”」,验证h=h'；

i）验证抗MOV攻击条件成立（参见附录A中A.4.2.1）；

j）若以上任何一个验证失败，则输出“无效”;否则输出“有效”。

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

6.1密钥对的生成

输入:一个有效的F.,（q=P且”为大于3的素数，或q=2“）上椭圆曲线系统参数的集合。

输出：与椭圆曲线系统参数相关的一个密钥对W,P）0

a）用随机数发生器产生整数dC口皿一2］；

9

GB/T32918.1—2016

b）G为基点，计算点P=G,）p）=［〃］G（参见附录A中A.3.2）；

c）密钥对是（d,P）,其中d为私钥，P为公钥。

6.2公钥的验证

6.2.1Fp±椭圆曲线公钥的验证

输入:一个有效的F”（“>3且”为素数）上椭圆曲线系统参数集合及一个相关的公钥P。

输岀：对于给定的椭圆曲线系统参数,若公钥P是有效的，则输出“有效”；否则输出“无效”。

a）验证P不是无穷远点（J;

b）验证公钥P的坐标'，和*是域F”中的元素（即验证I和*是区间［0,/p-l］中的整数）;

c）验证yJ,'3H-uj-p+/>（mod/?）；

d）验证S］P=（）;

e）若通过了所有验证，则输出“有效”；否则输出“无效”。

6.2.2F2-±椭圆曲线公钥的验证

输入:一个有效的F2，”上椭圆曲线系统参数集合及一个相关的公钥P。

输出：对于给定的椭圆曲线系统参数，若公钥P是有效的，则输出“有效”；否则输出“无效”。

a）验证P不是无穷远点O；

b）验证公钥P的坐标和*是域凡”，中的元素（即验证厂,和*是长度为必的比特串）；

c）在F2”，中验证+5;

d）验证［?2］P=O;

e）若通过了所有验证，则输出“有效”；否则输出“无效”。

注：公钥的验证是可选项。

10

GB/T32918.1—2016

附录A

（资料性附录）

关于椭圆曲线的背景知识

A.1素域F”

A.1.1素域F”的定义

设P是一个素数,F”由{0,1,2,・・・，“一1}中p个元素构成，称F”为素域。加法单位元是整数0,乘

法单位元是整数1,F”的元素满足如下运算法则：

加法：设a,bEF„,则a=厂，其中厂=（a+〃）mod”，厂C[0,“一1]。

乘法：设a,厶CF”，则a•b=s,其中$=（a•/>）mod",$C[0,p—1]。

记F；是由F”中所有非零元构成的乘法群，由于F；是循环群，所以在F”中至少存在一个元素g,

使得F”中任一非零元都可以由g的一个方幕表示，称g为F；的生成元（或本原元）.即F；={g，|0<

2}。设a=giGF；,其中0Wp—2,则a的乘法逆元为:u_1=gA_1_i

示例1：素域f2,f2={0,1}

卩2的加法表如表A.1,乘法表如表A.2：

表A.1

□□n

□□EJ

□□□

表A.2

□□□

二EJ

□□LZJ

示例2：素域Fi9,Fi9={0,l,2,・“,18}

中加法的示例：10,14eF19,10+14=Z4,Z4mod19=5,则10+14=5。

F2中乘法的示例：7,8€Fm,7X8=56,56mod19=18,则7•8=18。

13是Fv/的一个生成元，则中元素可由13的方幕表示出来：

130=1,13'=13,132=17,133=12,131=4,135=14,136=11,137=10,138=16,139=18,

13"=6,13"=2,13"=7,13"=15,13"=5,13"=8,13"=9,13"=3,1318=1。

A.1.2Fp±椭圆曲线的定义

A.1.2.1概述

F”上椭圆曲线常用的表示形式有两种：仿射坐标表示和射影坐标表示。

11

GB/T32918.1—2016

A.1.2.2仿射坐标表示

当p是大于3的素数时,F”上椭圆曲线方程在仿射坐标系下可以简化为)2=.尸+心+/八其中a,

bCFp,且使得(4a计27夕)mod"HO。椭圆曲线上的点集记为E(F”)={(")I工,yCF”且满足曲线

方程b=r』+a_z+b}U{O}，其中O是椭圆曲线的无穷远点。

E(F”)上的点按照下面的加法运算规则，构成一个阿贝尔群:

a)0+0=0；

b)X/P=(d)€E(F”)\{O},_P+O=O+F=P；

c)VP=(^0')6E(F,)\{0},P的逆元素一P=Cr,—y),P+(—P)=O；

d)点P】=Cn，E)€E(Fp)\{()},P2=(U2)€E(F”)\{O},P：<=(G,%)=Pi+P2H

O,则

|y-3—A3—.r3)—ji,

其中

JC2—Xi

A=«

3jti2-\~a卄,

--,右久1=兀2且卩2工一卩1。

、2夕1

示例3：有限域F】9上一条椭圆曲线

F]<3上方程:>2=j*3+jt+1,其中a=l,b=lo则F]<3上曲线的点为：

(0,1),(0,18),(2,7),(2,12),(5,6),(5,13),(7,3),(7,16),(9,6),(9,13),(10,2),(10,17),(13,8),(13,11),

(14,2),(14,17),(15,3),(15,16),(16,3),(16,16),

则Eg)有21个点(包括无穷远点O)

a)取Pi=(10,2),卩2=(9,6)，计算卩3=已+Pz:

6-24

—7=—4三15(modi9)

9-10一1

^3=152-10-9=225-10-9^16-10-9=-3=16(modl9),

^3=15X(10-16)-2=15X(-6)-2^3(modl9),

所以卩3=(16,3)。

b)取P】=(10,2),计算[2]P]:

3,2~\~a3X102+l3X5+l=^=4(m°di9)

2vi~2X2~44

心=42—10—10=—4=15(modl9),

*=4X(10—15)—2=—22三16(modl9),

所以：2]P1=(15,16)O

A.1.2.3射影坐标表示

A.标准射影坐标系

当P是大于3的素数时，F”上椭圆川|线方程在标准射影