ICS35.040

點(diǎn)擊此處添加中國(guó)標(biāo)準(zhǔn)文獻(xiàn)分類號(hào)

中華人民共和國(guó)國(guó)家標(biāo)準(zhǔn)

GB/TXXXXX—XXXX

SM2橢圓曲線公鑰密碼算法

第1部分：總則

PublickeycryptographicalgorithmSM2basedonellipticcurves-

Part1：General

點(diǎn)擊此處添加與國(guó)際標(biāo)準(zhǔn)一致性程度的標(biāo)識(shí)

（送審稿）

XXXX-XX-XX發(fā)布XXXX-XX-XX實(shí)施

GB/TXXXXX—XXXX

目??次

前言.................................................................錯(cuò)誤！未定義書簽。

引言............................................................................III

1范圍................................................................................1

2符號(hào)和縮略語(yǔ)........................................................................1

3域和橢圓曲線........................................................................2

3.1有限域..........................................................................2

3.2有限域上的橢圓曲線..............................................................3

4數(shù)據(jù)類型及其轉(zhuǎn)換....................................................................5

4.1數(shù)據(jù)類型........................................................................5

4.2數(shù)據(jù)類型轉(zhuǎn)換....................................................................5

5橢圓曲線系統(tǒng)參數(shù)及其驗(yàn)證............................................................8

5.1一般要求........................................................................8

5.2上橢圓曲線系統(tǒng)參數(shù)及其驗(yàn)證...................................................8

FP

5.3上橢圓曲線系統(tǒng)參數(shù)及其驗(yàn)證..................................................9

F2m

6密鑰對(duì)的生成與公鑰的驗(yàn)證...........................................................10

6.1密鑰對(duì)的生成...................................................................10

6.2公鑰的驗(yàn)證.....................................................................10

附錄A（資料性附錄）關(guān)于橢圓曲線的背景知識(shí)......................................11

A.1素域........................................................................11

FP

A.2二元擴(kuò)域...................................................................13

F2m

A.3橢圓曲線多倍點(diǎn)運(yùn)算.............................................................23

A.4求解橢圓曲線離散對(duì)數(shù)問(wèn)題的方法.................................................26

A.5橢圓曲線上點(diǎn)的壓縮.............................................................27

附錄B（資料性附錄）數(shù)論算法....................................................29

B.1有限域和模運(yùn)算.................................................................29

B.2有限域上的多項(xiàng)式...............................................................33

B.3橢圓曲線算法...................................................................35

附錄C（資料性附錄）曲線示例....................................................37

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

C.2上橢圓曲線.................................................................37

FP

C.3上橢圓曲線.................................................................37

F2m

I

GB/TXXXXX—XXXX

附錄D（資料性附錄）橢圓曲線方程參數(shù)的擬隨機(jī)生成及驗(yàn)證..........................39

D.1橢圓曲線方程參數(shù)的擬隨機(jī)生成..................................................39

D.2橢圓曲線方程參數(shù)的驗(yàn)證........................................................40

參考文獻(xiàn)...........................................................................41

II

GB/TXXXXX—XXXX

引言

N.Koblitz和V.Miller在1985年各自獨(dú)立地提出將橢圓曲線應(yīng)用于公鑰密碼系統(tǒng)。橢圓曲線公鑰

密碼所基于的曲線性質(zhì)如下：

──有限域上橢圓曲線在點(diǎn)加運(yùn)算下構(gòu)成有限交換群，且其階與基域規(guī)模相近；

──類似于有限域乘法群中的乘冪運(yùn)算，橢圓曲線多倍點(diǎn)運(yùn)算構(gòu)成一個(gè)單向函數(shù)。

在多倍點(diǎn)運(yùn)算中，已知多倍點(diǎn)與基點(diǎn)，求解倍數(shù)的問(wèn)題稱為橢圓曲線離散對(duì)數(shù)問(wèn)題。對(duì)于一般橢圓

曲線的離散對(duì)數(shù)問(wèn)題，目前只存在指數(shù)級(jí)計(jì)算復(fù)雜度的求解方法。與大數(shù)分解問(wèn)題及有限域上離散對(duì)數(shù)

問(wèn)題相比，橢圓曲線離散對(duì)數(shù)問(wèn)題的求解難度要大得多。因此，在相同安全程度要求下，橢圓曲線密碼

較其它公鑰密碼所需的密鑰規(guī)模要小得多。

本部分描述必要的數(shù)學(xué)基礎(chǔ)知識(shí)與一般技術(shù)，以幫助實(shí)現(xiàn)其它各部分所規(guī)定的密碼機(jī)制。

III

GB/TXXXXX—XXXX

SM2橢圓曲線公鑰密碼算法

第1部分：總則

1范圍

GB/TXXXX的本部分給出了SM2橢圓曲線公鑰密碼算法涉及的必要數(shù)學(xué)基礎(chǔ)知識(shí)與相關(guān)密碼技

術(shù)，以幫助實(shí)現(xiàn)其它各部分所規(guī)定的密碼機(jī)制。

本部分適用于基域?yàn)樗赜蚝投獢U(kuò)域的橢圓曲線公鑰密碼算法。

2符號(hào)和縮略語(yǔ)

下列符號(hào)和縮略語(yǔ)適用于本部分。

中的元素，它們定義上的一條橢圓曲線。

a,bFqFqE

BMOV閾。正數(shù)B，使得求取上的離散對(duì)數(shù)至少與求取上的橢圓曲線離散

FqBFq

對(duì)數(shù)一樣困難。

deg(f)多項(xiàng)式f(x)的次數(shù)。

E有限域上由a和b定義的一條橢圓曲線。

上橢圓曲線的所有有理點(diǎn)包括無(wú)窮遠(yuǎn)點(diǎn)組成的集合。

E(Fq)FqE(O)

ECDLP橢圓曲線離散對(duì)數(shù)問(wèn)題。

Fp包含p個(gè)元素的素域。

Fq包含q個(gè)元素的有限域。

*

Fq由Fq中所有非零元構(gòu)成的乘法群。

包含m個(gè)元素的二元擴(kuò)域。

F2m2

G橢圓曲線的一個(gè)基點(diǎn)，其階為素?cái)?shù)。

gcd(x,y)x和y的最大公因子。

h余因子，h=#E(Fq)/n，其中n是基點(diǎn)G的階。

LeftRotate()循環(huán)左移運(yùn)算。

lmax余因子h的最大素因子的上界。

m二元擴(kuò)域F2m關(guān)于F2的擴(kuò)張次數(shù)。

modf(x)模多項(xiàng)式f(x)的運(yùn)算。若f(x)是二元域上的多項(xiàng)式，則所有系數(shù)執(zhí)行模2運(yùn)算。

modn模n運(yùn)算。例如，23mod7=2。

n基點(diǎn)G的階(n是#E(Fq)的素因子)。

O橢圓曲線上的一個(gè)特殊點(diǎn)，稱為無(wú)窮遠(yuǎn)點(diǎn)或零點(diǎn)，是橢圓曲線加法群的單位元。

PP=(xP,yP)是橢圓曲線上除O之外的一個(gè)點(diǎn)，其坐標(biāo)xP，yP滿足橢圓曲線方程。

P1+P2橢圓曲線E上兩個(gè)點(diǎn)P1與P2的和。

1

GB/TXXXXX—XXXX

p大于3的素?cái)?shù)。

q有限域Fq中元素的數(shù)目。

rmin基點(diǎn)G的階n的下界。

Tr()跡函數(shù)。

xP點(diǎn)P的x坐標(biāo)。

x-1modn使得x?y1(modn)成立的唯一整數(shù)y，1≤y≤n-1，gcd(x,n)=1。

x||yx與y的拼接，其中x和y是比特串或字節(jié)串。

xy(modn)x與y模n同余。亦即，xmodn=ymodn。

yP點(diǎn)P的y坐標(biāo)。

~

yPyP的點(diǎn)壓縮表示。

Zp整數(shù)模p的剩余類環(huán)。

<G>基點(diǎn)G生成的循環(huán)群。

橢圓曲線上點(diǎn)的倍點(diǎn)，即：，其中是正整數(shù)。

[k]PPk[k]PPP...Pk

k個(gè)

[x,y]大于或等于x且小于或等于y的整數(shù)的集合。

x頂函數(shù)，大于或等于x的最小整數(shù)。例如，77,8.39。

x底函數(shù)，小于或等于x的最大整數(shù)。例如,77,8.38。

#E(Fq)E(Fq)上點(diǎn)的數(shù)目，稱為橢圓曲線E(Fq)的階。

⊕長(zhǎng)度相等的兩個(gè)比特串按比特的異或運(yùn)算。

3域和橢圓曲線

3.1有限域

3.1.1概述

本條給出有限域Fq的描述及其元素的表示，q是一個(gè)奇素?cái)?shù)或者是2的方冪。當(dāng)q是奇素?cái)?shù)p時(shí)，

要求p>2191；當(dāng)q是2的方冪2m時(shí)，要求m>192且為素?cái)?shù)。

3.1.2素域

FP

當(dāng)q是奇素?cái)?shù)p時(shí)，素域Fp中的元素用整數(shù)0,1,2,…,p-1表示。

a)加法單位元是整數(shù)0；

b)乘法單位元是整數(shù)1；

c)域元素的加法是整數(shù)的模p加法，即若a,bFp，則a+b=(a+b)modp；

d)域元素的乘法是整數(shù)的模p乘法，即若a,bFp，則a?b=(a?b)modp。

3.1.3二元擴(kuò)域

F2m

m

當(dāng)q是2的方冪2時(shí)，二元擴(kuò)域F2m可以看成F2上的m維向量空間，其元素可用長(zhǎng)度為m的比特

串表示。

F2m中的元素有多種表示方法，其中最常用的兩種方法是多項(xiàng)式基(PB)表示(參見附錄A.2.1.1)和正

規(guī)基(NB)表示(參見附錄A.2.1.3)。基的選擇原則是使得F2m中的運(yùn)算效率盡可能高。本標(biāo)準(zhǔn)并不規(guī)定基

的選擇。下面以多項(xiàng)式基表示為例說(shuō)明二元擴(kuò)域F2m。

mm-12

設(shè)F2上m次不可約多項(xiàng)式f(x)=x+fm-1x+…+f2x+f1x+f0(其中fi∈F2,i=0,1,…,m-1)是二元擴(kuò)域

2

GB/TXXXXX—XXXX

m-1m-2

F2m的約化多項(xiàng)式。F2m由F2上所有次數(shù)低于m的多項(xiàng)式構(gòu)成。多項(xiàng)式集合{x,x,…,x,1}是F2m在F2

m-1m-2

上的一組基，稱為多項(xiàng)式基。F2m中的任意一個(gè)元素a(x)=am-1x+am-2x+…+a1x+a0在F2上的系數(shù)恰

好構(gòu)成了長(zhǎng)度為m的比特串，用a=(am-1,am-2,…,a1,a0)表示。

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

b)乘法單位元1用比特串00…001表示；

c)兩個(gè)域元素的加法為比特串的按比特異或運(yùn)算；

d)域元素a和b的乘法定義如下：設(shè)a和b對(duì)應(yīng)的F2上多項(xiàng)式為a(x)和b(x)，則a?b定義為多項(xiàng)

式(a(x)b(x))modf(x)對(duì)應(yīng)的比特串。

3.2有限域上的橢圓曲線

有限域Fq上的橢圓曲線是由點(diǎn)組成的集合。在仿射坐標(biāo)系下，橢圓曲線上點(diǎn)P(非無(wú)窮遠(yuǎn)點(diǎn))的坐

標(biāo)表示為P=(xP,yP)，其中xP,yP為滿足一定方程的域元素，分別稱為點(diǎn)P的x坐標(biāo)和y坐標(biāo)。在本標(biāo)

準(zhǔn)中，稱Fq為基域。

關(guān)于橢圓曲線更多的背景知識(shí)，參見附錄A的A.1和A.2。

在本標(biāo)準(zhǔn)中，如果不做特別說(shuō)明，橢圓曲線上的點(diǎn)均采用仿射坐標(biāo)表示。

3.2.1上的橢圓曲線

FP

定義在Fp(p是大于3的素?cái)?shù))上的橢圓曲線方程為：

2332

y=x+ax+b,a,b∈Fp，且(4a+27b)modp0?！?1)

橢圓曲線E(Fp)定義為：

E(Fp)={(x,y)|x,y∈Fp，且滿足方程(1)}∪{O}，其中O是無(wú)窮遠(yuǎn)點(diǎn)。

橢圓曲線E(Fp)上的點(diǎn)的數(shù)目用#E(Fp)表示，稱為橢圓曲線E(Fp)的階。

3.2.2上的橢圓曲線

F2m

定義在F2m上的橢圓曲線方程為：

232

y+xy=x+ax+b,a,b∈F2m，且b0。……(2)

橢圓曲線E(F2m)定義為：

E(F2m)={(x,y)|x,y∈F2m，且滿足方程(2)}∪{O}，其中O是無(wú)窮遠(yuǎn)點(diǎn)。

橢圓曲線E(F2m)上的點(diǎn)的數(shù)目用#E(F2m)表示，稱為橢圓曲線E(F2m)的階。

3.2.3橢圓曲線群

上的橢圓曲線群

FP

橢圓曲線E(Fp)上的點(diǎn)按照下面的加法運(yùn)算規(guī)則，構(gòu)成一個(gè)交換群：

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)兩個(gè)非互逆的不同點(diǎn)相加的規(guī)則：

設(shè)P1=(x1,y1)∈E(Fp)\{O}，P2=(x2,y2)∈E(Fp)\{O}，且x1x2，

設(shè)P3=(x3,y3)=P1+P2，則

x2xx,

312

y3(x1x3)y1,

3

GB/TXXXXX—XXXX

其中

yy

21；

x2x1

e)倍點(diǎn)規(guī)則：

設(shè)P1=(x1,y1)∈E(Fp)\{O}，且y1≠0，P3=(x3,y3)=P1+P1，

則

x22x,

31

y3(x1x3)y1,

其中

3x2a

1。

2y1

上的橢圓曲線群

F2m

橢圓曲線E(F2m)上的點(diǎn)按照下面的加法運(yùn)算規(guī)則，構(gòu)成一個(gè)交換群：

a)O+O=O；

b)P=(x,y)∈E(F2m)\{O}，P+O=O+P=P；

c)P=(x,y)∈E(F2m)\{O}，P的逆元素-P=(x,x+y)，P+(-P)=O；

d)兩個(gè)非互逆的不同點(diǎn)相加的規(guī)則：

設(shè)P1=(x1,y1)∈E(F2m)\{O}，P2=(x2,y2)∈E(F2m)\{O}，且x1x2，

設(shè)P3=(x3,y3)=P1+P2，則

x2xxa,

312

y3(x1x3)x3y1,

其中

yy

12；

x1x2

e)倍點(diǎn)規(guī)則：

設(shè)P1=(x1,y1)∈E(F2m)\{O}，且x1≠0，P3=(x3,y3)=P1+P1，則

2

x3a,

2

y3x1(1)x3,

其中

y1

x1。

x1

3.2.4橢圓曲線多倍點(diǎn)運(yùn)算

橢圓曲線上同一個(gè)點(diǎn)的多次加稱為該點(diǎn)的多倍點(diǎn)運(yùn)算。設(shè)k是一個(gè)正整數(shù)，P是橢圓曲線上的點(diǎn)，

稱點(diǎn)的次加為點(diǎn)的倍點(diǎn)運(yùn)算，記為。因?yàn)?，所以倍點(diǎn)

PkPkQ[k]PPPP[k]P=[k1]P+Pk

k

可以遞歸求得。

多倍點(diǎn)運(yùn)算的輸出有可能是無(wú)窮遠(yuǎn)點(diǎn)O。

多倍點(diǎn)運(yùn)算也可以通過(guò)一些技巧更有效地實(shí)現(xiàn)，參見附錄A的A.3。

3.2.5橢圓曲線離散對(duì)數(shù)問(wèn)題(ECDLP)

4

GB/TXXXXX—XXXX

已知橢圓曲線E(Fq)、階為n的點(diǎn)G∈E(Fq)及Q∈<G>，橢圓曲線離散對(duì)數(shù)問(wèn)題是指確定整數(shù)l∈

[0,n-1]，使得Q=[l]G成立。

橢圓曲線離散對(duì)數(shù)問(wèn)題關(guān)系到橢圓曲線密碼系統(tǒng)的安全，因此必須選擇安全的橢圓曲線。關(guān)于如何

選擇安全橢圓曲線，參見附錄A的A.4。

3.2.6弱橢圓曲線

若某橢圓曲線存在優(yōu)于n1/2級(jí)(n是基點(diǎn)的階)計(jì)算復(fù)雜度的攻擊方法，則稱此曲線為弱橢圓曲線。

在本標(biāo)準(zhǔn)中禁止使用弱橢圓曲線。

Fq上的超奇異曲線(有限域Fq的特征整除q+1-#E(Fq))和Fp上的異常（Anomalous）曲線(#E(Fp)=p)

都是弱橢圓曲線。

4數(shù)據(jù)類型及其轉(zhuǎn)換

4.1數(shù)據(jù)類型

在本標(biāo)準(zhǔn)中，數(shù)據(jù)類型包括比特串、字節(jié)串、域元素、橢圓曲線上的點(diǎn)和整數(shù)。

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

字節(jié)串：有序的字節(jié)序列，其中8比特為1個(gè)字節(jié)。

域元素：有限域Fq中的元素。

橢圓曲線上的點(diǎn)：橢圓曲線上的點(diǎn)PE(Fq)，或者是一對(duì)域元素(xP,yP)，其中域元素xP和yP滿足

橢圓曲線方程，或者是無(wú)窮遠(yuǎn)點(diǎn)O。

點(diǎn)的字節(jié)串表示有多種形式，用一個(gè)字節(jié)PC加以標(biāo)識(shí)。無(wú)窮遠(yuǎn)點(diǎn)O的字節(jié)串表示是單一的零字節(jié)

PC=00。非無(wú)窮遠(yuǎn)點(diǎn)P=(xP,yP)有如下三種字節(jié)串表示形式：

a)壓縮表示形式，PC=02或03；

b)未壓縮表示形式，PC=04；

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

注：混合表示形式既包含壓縮表示形式又包含未壓縮表示形式。在實(shí)現(xiàn)中，它允許轉(zhuǎn)換到壓縮表示形式或者未壓縮

表示形式。

對(duì)于橢圓曲線上點(diǎn)的壓縮表示形式和混合表示形式，本標(biāo)準(zhǔn)中定為可選形式。橢圓曲線上點(diǎn)的壓縮

表示形式參見附錄A的A.5。

4.2數(shù)據(jù)類型轉(zhuǎn)換

4.2.1數(shù)據(jù)類型轉(zhuǎn)換關(guān)系

圖1提供了各種數(shù)據(jù)類型之間的轉(zhuǎn)換關(guān)系，線上的標(biāo)志是相應(yīng)數(shù)據(jù)轉(zhuǎn)換方法所在的條。

4.2.8條

域元素

4.2.6條4.2.7條

4.2.5條4.2.2條

比特串字節(jié)串整數(shù)

4.2.4條4.2.3條

4.2.10條4.2.9條

點(diǎn)

5

GB/TXXXXX—XXXX

圖1數(shù)據(jù)類型和轉(zhuǎn)換約定

4.2.2整數(shù)到字節(jié)串的轉(zhuǎn)換

輸入：非負(fù)整數(shù)x，以及字節(jié)串的目標(biāo)長(zhǎng)度k(其中k滿足28k>x)。

輸出：長(zhǎng)度為k的字節(jié)串M。

a)設(shè)Mk-1，Mk-2，…，M0是M的從最左邊到最右邊的字節(jié)；

b)M的字節(jié)滿足：

k1

8i。

x2Mi

i0

4.2.3字節(jié)串到整數(shù)的轉(zhuǎn)換

輸入：長(zhǎng)度為k的字節(jié)串M。

輸出：整數(shù)x。

a)設(shè)Mk-1，Mk-2，…，M0是M的從最左邊到最右邊的字節(jié)；

b)將M轉(zhuǎn)換為整數(shù)x：

k1

8i。

x2Mi

i0

4.2.4比特串到字節(jié)串的轉(zhuǎn)換

輸入：長(zhǎng)度為m的比特串s。

輸出：長(zhǎng)度為k的字節(jié)串M，其中k=m/8。

a)設(shè)sm-1，sm-2，…，s0是s從最左邊到最右邊的比特；

b)設(shè)Mk-1，Mk-2，…，M0是M從最左邊到最右邊的字節(jié)，則

Mi=s8i+7s8i+6…s8i+1s8i，其中0≤i<k，當(dāng)8i+jm，0<j≤7時(shí)，s8i+j=0。

4.2.5字節(jié)串到比特串的轉(zhuǎn)換

輸入：長(zhǎng)度為k的字節(jié)串M。

輸出：長(zhǎng)度為m的比特串s，其中m=8k。

a)設(shè)Mk-1，Mk-2，…，M0是M從最左邊到最右邊的字節(jié)；

b)設(shè)sm-1，sm-2，…，s0是s從最左邊到最右邊的比特，則si是Mj右起第i-8j+1比特，其中j=i/8。

4.2.6域元素到字節(jié)串的轉(zhuǎn)換

輸入：Fq中的元素α。

輸出：長(zhǎng)度l=t/8的字節(jié)串S，其中tlog2q。

a)若q為奇素?cái)?shù)，則α必為區(qū)間[0,q-1]中的整數(shù)，按4.2.2的方法把α轉(zhuǎn)換成長(zhǎng)度為l的字節(jié)串S；

b)若q=2m，則α必為長(zhǎng)度為m的比特串，按4.2.4的方法把α轉(zhuǎn)換成長(zhǎng)度為l的字節(jié)串S。

4.2.7字節(jié)串到域元素的轉(zhuǎn)換

輸入：基域Fq的類型，長(zhǎng)度為l=t/8的字節(jié)串S，其中tlog2q。

輸出：Fq中的元素α。

a)若q是奇素?cái)?shù)，則按4.2.3的方法將S轉(zhuǎn)換為整數(shù)α，若α[0,q-1],則報(bào)錯(cuò)；

6

GB/TXXXXX—XXXX

b)若q=2m，則按4.2.5的方法將S轉(zhuǎn)換為長(zhǎng)度為m的比特串α。

4.2.8域元素到整數(shù)的轉(zhuǎn)換

輸入：域Fq中的元素α。

輸出：整數(shù)x。

a)若q為奇素?cái)?shù)，則x=α(不需要轉(zhuǎn)換)；

m

b)若q=2，則α必為長(zhǎng)度為m的比特串，設(shè)sm-1，sm-2，…，s0是α的從最左邊到最右邊的比特，

將α轉(zhuǎn)化為整數(shù)x：

m1

i。

x2si

i0

4.2.9點(diǎn)到字節(jié)串的轉(zhuǎn)換

輸入：橢圓曲線上的點(diǎn)P=(xP,yP)，且P≠O。

輸出：字節(jié)串S。若選用未壓縮表示形式或混合表示形式，則輸出字節(jié)串長(zhǎng)度為2l+1；若選用壓縮

表示形式，則輸出字節(jié)串長(zhǎng)度為l+1(l(log2q)/8)。

a)按4.2.6中的方法把域元素xP轉(zhuǎn)換成長(zhǎng)度為l的字節(jié)串X1；

b)若選用壓縮表示形式，則：

~

b.1)計(jì)算比特yP(參見附錄A的A.5)；

~~

b.2)若yP=0，則令PC=02；若yP=1，則令PC=03；

b.3)字節(jié)串S=PC||X1；

c)若選用未壓縮表示形式，則：

c.1)按4.2.6的方法把域元素yP轉(zhuǎn)換成長(zhǎng)度為l的字節(jié)串Y1；

c.2)令PC=04；

c.3)字節(jié)串S=PC||X1||Y1；

d)若選用混合表示形式，則：

d.1)按4.2.6的方法把域元素yP轉(zhuǎn)換成長(zhǎng)度為l的字節(jié)串Y1；

~

d.2)計(jì)算比特yP(參見附錄A的A.5)；

~~

d.3)若yP=0，則令PC=06；若yP=1，則令PC=07；

d.4)字節(jié)串S=PC||X1||Y1。

4.2.10字節(jié)串到點(diǎn)的轉(zhuǎn)換

輸入：定義Fq上橢圓曲線的域元素a、b，字節(jié)串S。若選用未壓縮表示形式或混合表示形式，則

字節(jié)串S長(zhǎng)度為2l+1；若選用壓縮表示形式，則字節(jié)串PO長(zhǎng)度為l+1(l(log2q)/8)。

輸出：橢圓曲線上的點(diǎn)P=(xP,yP)，且P≠O。

a)若選用壓縮表示形式，則S=PC||X1；若選用未壓縮表示形式或混合表示形式，則S=PC||X1||Y1，

其中PC是單一字節(jié)，X1和Y1都是長(zhǎng)度為l的字節(jié)串；

b)按4.2.7的方法把字節(jié)串X1轉(zhuǎn)換成域元素xP；

7

GB/TXXXXX—XXXX

c)若選用壓縮表示形式，則：

c.1)檢驗(yàn)PC=02或者是PC=03，若不是這種情形，則報(bào)錯(cuò)；

~~

c.2)若PC=02，則令yP=0；若PC=03，則令yP=1；

將~轉(zhuǎn)換為橢圓曲線上的一個(gè)點(diǎn)參見附錄的；

c.3)(xP,yP)(xP,yP)(AA.5)

d)若選用未壓縮表示形式，則：

d.1)檢驗(yàn)PC=04，若不是這種情形，則報(bào)錯(cuò)；

d.2)按4.2.7的方法把字節(jié)串Y1轉(zhuǎn)換成域元素yP；

e)若選用混合表示形式，則：

e.1)檢驗(yàn)PC=06或者PC=07，若不是這種情形，則報(bào)錯(cuò)；

e.2)執(zhí)行步驟e.2.1)和e.2.2)：

e.2.1)按4.2.7的細(xì)節(jié)把字節(jié)串Y1轉(zhuǎn)換成域元素yP；

~~

e.2.2)若PC=06，則令yP=0，否則令yP=1；

~

e.3)將(xP,yP)轉(zhuǎn)換為橢圓曲線上的一個(gè)點(diǎn)(xP,yP)(參見附錄A的A.5)；

若為奇素?cái)?shù)，則驗(yàn)證23，若不是這種情形，則報(bào)錯(cuò)；

f)qyPyP+axP+b(modq)

m232

若，則在m中驗(yàn)證，若不是這種情形，則報(bào)錯(cuò)；

q=2F2yP+xPyP=xP+axP+b

g)P=(xP,yP)。

5橢圓曲線系統(tǒng)參數(shù)及其驗(yàn)證

5.1一般要求

橢圓曲線系統(tǒng)參數(shù)是可以公開的，系統(tǒng)的安全性不依賴于對(duì)這些參數(shù)的保密。本標(biāo)準(zhǔn)不規(guī)定橢圓曲

線系統(tǒng)參數(shù)的生成方法，但規(guī)定了系統(tǒng)參數(shù)的驗(yàn)證方法。橢圓曲線階的計(jì)算和基點(diǎn)的選取方法可參見附

錄B的B.3，曲線參數(shù)的生成方法可參見附錄D。

橢圓曲線系統(tǒng)參數(shù)按照基域的不同可以分為兩種情形：

——當(dāng)基域是Fp(p為大于3的素?cái)?shù))時(shí)，F(xiàn)p上的橢圓曲線系統(tǒng)參數(shù)；

——當(dāng)基域是F2m時(shí)，F(xiàn)2m上的橢圓曲線系統(tǒng)參數(shù)。

5.2上橢圓曲線系統(tǒng)參數(shù)及其驗(yàn)證

FP

5.2.1上橢圓曲線系統(tǒng)參數(shù)

FP

上橢圓曲線系統(tǒng)參數(shù)包括：

FP

a)域的規(guī)模q=p，p是大于3的素?cái)?shù)；

b)(選項(xiàng))一個(gè)長(zhǎng)度至少為192的比特串SEED(若按照附錄D描述的方法產(chǎn)生橢圓曲線)；

23

c)Fp中的兩個(gè)元素a和b，它們定義橢圓曲線E的方程：y=x+ax+b；

d)基點(diǎn)G=(xG,yG)E(Fp)，G≠O；

e)基點(diǎn)G的階n(要求：n>2191且n>4p1/2)；

f)(選項(xiàng))余因子h=#E(Fp)/n。

5.2.2上橢圓曲線系統(tǒng)參數(shù)的驗(yàn)證

FP

橢圓曲線系統(tǒng)參數(shù)的生成者應(yīng)驗(yàn)證下面的條件。橢圓曲線系統(tǒng)參數(shù)的用戶可選擇驗(yàn)證這些條件。

8

GB/TXXXXX—XXXX

輸入：Fp上橢圓曲線系統(tǒng)參數(shù)的集合。

輸出：若橢圓曲線系統(tǒng)參數(shù)是有效的，則輸出“有效”；否則輸出“無(wú)效”。

a)驗(yàn)證q=p是奇素?cái)?shù)(參見附錄B的B.1.10)；

b)驗(yàn)證a,b,xG和yG是區(qū)間[0，p-1]中的整數(shù)；

c)若按照附錄D描述的方法擬隨機(jī)產(chǎn)生橢圓曲線，驗(yàn)證SEED是長(zhǎng)度至少為192的比特串，且a,

b由SEED派生得到；

d)驗(yàn)證(4a3+27b2)modp0；

23

e)驗(yàn)證yGxG+axG+b(modp)；

f)驗(yàn)證n是素?cái)?shù)，n>2191且n>4p1/2(參見附錄B的B.1.10)；

g)驗(yàn)證[n]G=O(參見附錄A的A.3)；

h)(選項(xiàng))計(jì)算h=(p1/2+1)2/n，并驗(yàn)證h=h；

i)驗(yàn)證抗MOV攻擊條件和抗異常曲線攻擊條件成立(參見附錄A的A.4.2.1和A.4.2.2)；

j)若以上任何一個(gè)驗(yàn)證失敗，則輸出“無(wú)效”；否則，輸出“有效”。

5.3上橢圓曲線系統(tǒng)參數(shù)及其驗(yàn)證

F2m

5.3.1上橢圓曲線系統(tǒng)參數(shù)

F2m

F2m上的橢圓曲線系統(tǒng)參數(shù)包括：

m

a)域的規(guī)模q=2，對(duì)F2m中元素表示法(三項(xiàng)式基TPB、五項(xiàng)式基PPB或高斯正規(guī)基GNB)的標(biāo)

識(shí)，一個(gè)F2上的m次約化多項(xiàng)式(若所用的基是TPB或PPB)；

b)(選項(xiàng))一個(gè)長(zhǎng)度至少為192的比特串SEED(若按照附錄D描述的方法擬隨機(jī)產(chǎn)生橢圓曲線)；

232

c)F2m中的兩個(gè)元素a和b，它們定義橢圓曲線E的方程：y+xy=x+ax+b；

d)基點(diǎn)G=(xG,yG)E(F2m)，G≠O；

e)基點(diǎn)G的階n(要求：n>2191且n>22+m/2)；

f)(選項(xiàng))余因子h=#E(F2m)/n。

5.3.2上橢圓曲線系統(tǒng)參數(shù)的驗(yàn)證

F2m

下面的條件橢圓曲線系統(tǒng)參數(shù)的生成者應(yīng)加以驗(yàn)證。這些條件橢圓曲線系統(tǒng)參數(shù)的用戶可選擇驗(yàn)

證。

輸入：F2m上橢圓曲線系統(tǒng)參數(shù)的集合。

輸出：若橢圓曲線系統(tǒng)參數(shù)是有效的，則輸出“有效”；否則輸出“無(wú)效”。

m

a)對(duì)某個(gè)m，驗(yàn)證q=2；若所用的是TPB，則驗(yàn)證約化多項(xiàng)式是F2上的不可約三項(xiàng)式(參見表

A.3)；若所用的是PPB，則驗(yàn)證不存在m次不可約三項(xiàng)式，且約化多項(xiàng)式是F2上的不可約五

項(xiàng)式(參見表A.4)；若所用的是GNB，則驗(yàn)證m不能被8整除；

b)驗(yàn)證a,b,xG和yG是長(zhǎng)度為m的比特串；

c)若按照附錄D描述的方法擬隨機(jī)產(chǎn)生橢圓曲線，驗(yàn)證SEED是長(zhǎng)度至少為192的比特串，且a,

b由SEED派生得到；

d)驗(yàn)證b≠0；

232

e)在F2m中驗(yàn)證yG+xGyG=xG+axG+b；

f)驗(yàn)證n是一個(gè)素?cái)?shù)，n>2191且n>22+m/2(參見附錄B的B.1.10)；

g)驗(yàn)證[n]G=O(參見附錄A.3.2)；

h)(選項(xiàng))計(jì)算h=(2m/2+1)2/n，驗(yàn)證h=h；

9

GB/TXXXXX—XXXX

i)驗(yàn)證抗MOV攻擊條件成立(參見附錄A的A.4.2.1)；

j)若以上任何一個(gè)驗(yàn)證失敗，則輸出“無(wú)效”；否則輸出“有效”。

6密鑰對(duì)的生成與公鑰的驗(yàn)證

6.1密鑰對(duì)的生成

m

輸入：一個(gè)有效的Fq(q=p且p為大于3的素?cái)?shù),或q=2)上橢圓曲線系統(tǒng)參數(shù)的集合。

輸出：與橢圓曲線系統(tǒng)參數(shù)相關(guān)的一個(gè)密鑰對(duì)(d，P)。

a)用隨機(jī)數(shù)發(fā)生器產(chǎn)生整數(shù)d[1，n-2]；

b)G為基點(diǎn)，計(jì)算點(diǎn)P=(xP,yP)=[d]G(參見附錄A的A.3.2)；

c)密鑰對(duì)是(d，P)，其中d為私鑰，P為公鑰。

6.2公鑰的驗(yàn)證

6.2.1上橢圓曲線公鑰的驗(yàn)證

FP

輸入：一個(gè)有效的Fp(p>3且p為素?cái)?shù))上橢圓曲線系統(tǒng)參數(shù)集合及一個(gè)相關(guān)的公鑰P。

輸出：對(duì)于給定的橢圓曲線系統(tǒng)參數(shù)，若公鑰P是有效的，則輸出“有效”；否則輸出“無(wú)效”。

a)驗(yàn)證P不是無(wú)窮遠(yuǎn)點(diǎn)O；

b)驗(yàn)證公鑰P的坐標(biāo)xP和yP是域Fp中的元素(即驗(yàn)證xP和yP是區(qū)間[0，p-1]中的整數(shù))；

23

c)驗(yàn)證yP≡xP+axP+b(modp)；

d)驗(yàn)證[n]P=O；

e)若通過(guò)了所有驗(yàn)證，則輸出“有效”；否則輸出“無(wú)效”。

6.2.2上橢圓曲線公鑰的驗(yàn)證

F2m

輸入：一個(gè)有效的F2m上橢圓曲線系統(tǒng)參數(shù)集合及一個(gè)相關(guān)的公鑰P。

輸出：對(duì)于給定的橢圓曲線系統(tǒng)參數(shù)，若公鑰P是有效的，則輸出“有效”；否則輸出“無(wú)效”。

a)驗(yàn)證P不是無(wú)窮遠(yuǎn)點(diǎn)O；

b)驗(yàn)證公鑰P的坐標(biāo)xP和yP是域F2m中的元素(即驗(yàn)證xP和yP是長(zhǎng)度為m的比特串)；

232

在m中驗(yàn)證；

c)F2yP+xPyP=xP+axP+b

d)驗(yàn)證[n]P=O；

e)若通過(guò)了所有驗(yàn)證，則輸出“有效”；否則輸出“無(wú)效”。

注：公鑰的驗(yàn)證是可選項(xiàng)。

10

GB/TXXXXX—XXXX

附錄A

（資料性附錄）

關(guān)于橢圓曲線的背景知識(shí)

A.1素域

FP

A.1.1素域的定義

FP

設(shè)p是一個(gè)素?cái)?shù)，F(xiàn)p由{0,1,2,…,p-1}中p個(gè)元素構(gòu)成，稱Fp為素域。加法單位元是整數(shù)0，乘法

單位元是整數(shù)1，F(xiàn)p的元素滿足如下運(yùn)算法則：

——加法：設(shè)a,bFp，則a+b=r，其中r=(a+b)modp,r[0,p-1]。

——乘法：設(shè)a,bFp，則a?b=s,其中s=(a?b)modp,s[0,p-1]。

**

記Fp是由Fp中所有非零元構(gòu)成的乘法群，由于Fp是循環(huán)群，所以在Fp中至少存在一個(gè)元素g，

**i

使得Fp中任一非零元都可以由g的一個(gè)方冪表示，稱g為Fp的生成元(或本原元)，即Fp={g|0ip-2}。

i*-1p-1-i

設(shè)a=g∈Fp，其中0ip-2，則a的乘法逆元為：a=g。

示例1：素域F2，F(xiàn)2={0,1}

F2的加法表如表A.1，乘法表如表A.2：

表A.1

+01

001

110

表A.2

?01

000

101

示例2：素域F19，F(xiàn)19={0,1,2,…,18}

F19中加法的示例：10,14∈F19，10+14=24，24mod19＝5，則10+14=5。

F19中乘法的示例：7,8∈F19，7×8=56，56mod19＝18，則78=18。

**

13是F19的一個(gè)生成元，則F19中元素可由13的方冪表示出來(lái)：

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

1310=6，1311=2，1312=7，1313=15，1314=5，1315=8，1316=9，1317=3，1318=1。

A.1.2上橢圓曲線的定義

FP

A.1.2.1概述

Fp上橢圓曲線常用的表示形式有兩種：仿射坐標(biāo)表示和射影坐標(biāo)表示。

11

GB/TXXXXX—XXXX

A.1.2.2仿射坐標(biāo)表示

23

當(dāng)p是大于3的素?cái)?shù)時(shí)，F(xiàn)p上橢圓曲線方程在仿射坐標(biāo)系下可以簡(jiǎn)化為y=x+ax+b，其中a,b∈Fp，

3223

且使得(4a+27b)modp0。橢圓曲線上的點(diǎn)集記為E(Fp)={(x,y)|x,y∈Fp且滿足曲線方程y=x+ax+b}∪

{O}，其中O是橢圓曲線的無(wú)窮遠(yuǎn)點(diǎn)。

E(Fp)上的點(diǎn)按照下面的加法運(yùn)算規(guī)則，構(gòu)成一個(gè)阿貝爾群：

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)點(diǎn)P1=(x1,y1)∈E(Fp)\{O}，P2=(x2,y2)∈E(Fp)\{O}，P3=(x3,y3)=P1+P2≠O，則

x2xx,

312

y3(x1x3)y1,

其中

yy

21若

,x1x2,

x2x1

2

3x1a

,若x1x2且P2P1。

2y1

示例3：有限域F19上一條橢圓曲線

23

F19上方程：y=x+x+1，其中a=1，b=1。則F19上曲線的點(diǎn)為：

(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)，

則E(F19)有21個(gè)點(diǎn)(包括無(wú)窮遠(yuǎn)點(diǎn)O)。

a)取P1=(10,2)，P2=(9,6)，計(jì)算P3=P1+P2：

yy624

21415(mod19)，

x2x19101

2

x3=15-10-9=225–10-916-10-9=-316(mod19)，

y3=15×(10–16)–2=15×(–6)–23(mod19)，

所以P3=(16,3)。

b)取P1=(10,2)，計(jì)算[2]P1：

3x2a3102135116

1