《信息安全技術 SM2橢圓曲線公鑰密碼算法第1部分總則-GB》

ICS35.040

點擊此處添加中國標準文獻分類號

中華人民共和國國家標準

GB/TXXXXX—XXXX

SM2橢圓曲線公鑰密碼算法

第1部分：總則

PublickeycryptographicalgorithmSM2basedonellipticcurves-

Part1：General

點擊此處添加與國際標準一致性程度的標識

（送審稿）

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

GB/TXXXXX—XXXX

目??次

前言.................................................................錯誤！未定義書簽。

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

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

2符號和縮略語........................................................................1

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

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

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

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

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

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

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

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

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

FP

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

F2m

6密鑰對的生成與公鑰的驗證...........................................................10

6.1密鑰對的生成...................................................................10

6.2公鑰的驗證.....................................................................10

附錄A（資料性附錄）關于橢圓曲線的背景知識......................................11

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

FP

A.2二元擴域...................................................................13

F2m

A.3橢圓曲線多倍點運算.............................................................23

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

A.5橢圓曲線上點的壓縮.............................................................27

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

B.1有限域和模運算.................................................................29

B.2有限域上的多項式...............................................................33

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

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

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

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

FP

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

F2m

I

GB/TXXXXX—XXXX

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

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

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

參考文獻...........................................................................41

II

GB/TXXXXX—XXXX

引言

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

密碼所基于的曲線性質如下：

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

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

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

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

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

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

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

III

GB/TXXXXX—XXXX

SM2橢圓曲線公鑰密碼算法

第1部分：總則

1范圍

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

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

本部分適用于基域為素域和二元擴域的橢圓曲線公鑰密碼算法。

2符號和縮略語

下列符號和縮略語適用于本部分。

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

a,bFqFqE

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

FqBFq

對數(shù)一樣困難。

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

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

上橢圓曲線的所有有理點包括無窮遠點組成的集合。

E(Fq)FqE(O)

ECDLP橢圓曲線離散對數(shù)問題。

Fp包含p個元素的素域。

Fq包含q個元素的有限域。

*

Fq由Fq中所有非零元構成的乘法群。

包含m個元素的二元擴域。

F2m2

G橢圓曲線的一個基點，其階為素數(shù)。

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

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

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

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

m二元擴域F2m關于F2的擴張次數(shù)。

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

modn模n運算。例如，23mod7=2。

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

O橢圓曲線上的一個特殊點，稱為無窮遠點或零點，是橢圓曲線加法群的單位元。

PP=(xP,yP)是橢圓曲線上除O之外的一個點，其坐標xP，yP滿足橢圓曲線方程。

P1+P2橢圓曲線E上兩個點P1與P2的和。

1

GB/TXXXXX—XXXX

p大于3的素數(shù)。

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

rmin基點G的階n的下界。

Tr()跡函數(shù)。

xP點P的x坐標。

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點P的y坐標。

~

yPyP的點壓縮表示。

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

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

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

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

k個

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

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

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

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

⊕長度相等的兩個比特串按比特的異或運算。

3域和橢圓曲線

3.1有限域

3.1.1概述

本條給出有限域Fq的描述及其元素的表示，q是一個奇素數(shù)或者是2的方冪。當q是奇素數(shù)p時，

要求p>2191；當q是2的方冪2m時，要求m>192且為素數(shù)。

3.1.2素域

FP

當q是奇素數(shù)p時，素域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二元擴域

F2m

m

當q是2的方冪2時，二元擴域F2m可以看成F2上的m維向量空間，其元素可用長度為m的比特

串表示。

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

規(guī)基(NB)表示(參見附錄A.2.1.3)?；倪x擇原則是使得F2m中的運算效率盡可能高。本標準并不規(guī)定基

的選擇。下面以多項式基表示為例說明二元擴域F2m。

mm-12

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

2

GB/TXXXXX—XXXX

m-1m-2

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

m-1m-2

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

好構成了長度為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))modf(x)對應的比特串。

3.2有限域上的橢圓曲線

有限域Fq上的橢圓曲線是由點組成的集合。在仿射坐標系下，橢圓曲線上點P(非無窮遠點)的坐

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

準中，稱Fq為基域。

關于橢圓曲線更多的背景知識，參見附錄A的A.1和A.2。

在本標準中，如果不做特別說明，橢圓曲線上的點均采用仿射坐標表示。

3.2.1上的橢圓曲線

FP

定義在Fp(p是大于3的素數(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是無窮遠點。

橢圓曲線E(Fp)上的點的數(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是無窮遠點。

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

3.2.3橢圓曲線群

上的橢圓曲線群

FP

橢圓曲線E(Fp)上的點按照下面的加法運算規(guī)則，構成一個交換群：

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

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

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

x2xx,

312

y3(x1x3)y1,

3

GB/TXXXXX—XXXX

其中

yy

21；

x2x1

e)倍點規(guī)則：

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

則

x22x,

31

y3(x1x3)y1,

其中

3x2a

1。

2y1

上的橢圓曲線群

F2m

橢圓曲線E(F2m)上的點按照下面的加法運算規(guī)則，構成一個交換群：

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

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

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

x2xxa,

312

y3(x1x3)x3y1,

其中

yy

12；

x1x2

e)倍點規(guī)則：

設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橢圓曲線多倍點運算

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

稱點的次加為點的倍點運算，記為。因為-，所以倍點

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

k

可以遞歸求得。

多倍點運算的輸出有可能是無窮遠點O。

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

3.2.5橢圓曲線離散對數(shù)問題(ECDLP)

4

GB/TXXXXX—XXXX

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

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

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

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

3.2.6弱橢圓曲線

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

在本標準中禁止使用弱橢圓曲線。

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

都是弱橢圓曲線。

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

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

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

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

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

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

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

橢圓曲線方程，或者是無窮遠點O。

點的字節(jié)串表示有多種形式，用一個字節(jié)PC加以標識。無窮遠點O的字節(jié)串表示是單一的零字節(jié)

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

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

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

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

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

表示形式。

對于橢圓曲線上點的壓縮表示形式和混合表示形式，本標準中定為可選形式。橢圓曲線上點的壓縮

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

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

4.2.1數(shù)據(jù)類型轉換關系

圖1提供了各種數(shù)據(jù)類型之間的轉換關系，線上的標志是相應數(shù)據(jù)轉換方法所在的條。

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條

點

5

GB/TXXXXX—XXXX

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

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

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

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

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

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

k1

8i。

x2Mi

i0

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

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

輸出：整數(shù)x。

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

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

k1

8i。

x2Mi

i0

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

輸入：長度為m的比特串s。

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

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

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

Mi=s8i+7s8i+6…s8i+1s8i，其中0≤i<k，當8i+jm，0<j≤7時，s8i+j=0。

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

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

輸出：長度為m的比特串s，其中m=8k。

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

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

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

輸入：Fq中的元素α。

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

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

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

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

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

輸出：Fq中的元素α。

a)若q是奇素數(shù)，則按4.2.3的方法將S轉換為整數(shù)α，若α[0,q-1],則報錯；

6

GB/TXXXXX—XXXX

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

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

輸入：域Fq中的元素α。

輸出：整數(shù)x。

a)若q為奇素數(shù)，則x=α(不需要轉換)；

m

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

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

m1

i。

x2si

i0

4.2.9點到字節(jié)串的轉換

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

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

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

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

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

~

b.1)計算比特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轉換成長度為l的字節(jié)串Y1；

c.2)令PC=04；

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

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

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

~

d.2)計算比特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é)串到點的轉換

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

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

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

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

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

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

7

GB/TXXXXX—XXXX

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

c.1)檢驗PC=02或者是PC=03，若不是這種情形，則報錯；

~~

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

將~轉換為橢圓曲線上的一個點參見附錄的；

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

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

d.1)檢驗PC=04，若不是這種情形，則報錯；

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

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

e.1)檢驗PC=06或者PC=07，若不是這種情形，則報錯；

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

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

~~

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

~

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

若為奇素數(shù)，則驗證23，若不是這種情形，則報錯；

f)qyPyP+axP+b(modq)

m232

若，則在m中驗證，若不是這種情形，則報錯；

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

g)P=(xP,yP)。

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

5.1一般要求

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

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

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

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

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

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

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

FP

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

FP

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

FP

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

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

23

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

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

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

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

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

FP

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

8

GB/TXXXXX—XXXX

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

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

a)驗證q=p是奇素數(shù)(參見附錄B的B.1.10)；

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

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

b由SEED派生得到；

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

23

e)驗證yGxG+axG+b(modp)；

f)驗證n是素數(shù)，n>2191且n>4p1/2(參見附錄B的B.1.10)；

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

h)(選項)計算h=(p1/2+1)2/n，并驗證h=h；

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

j)若以上任何一個驗證失敗，則輸出“無效”；否則，輸出“有效”。

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

F2m

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

F2m

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

m

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

識，一個F2上的m次約化多項式(若所用的基是TPB或PPB)；

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

232

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

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

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

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

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

F2m

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

證。

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

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

m

a)對某個m，驗證q=2；若所用的是TPB，則驗證約化多項式是F2上的不可約三項式(參見表

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

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

b)驗證a,b,xG和yG是長度為m的比特串；

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

b由SEED派生得到；

d)驗證b≠0；

232

e)在F2m中驗證yG+xGyG=xG+axG+b；

f)驗證n是一個素數(shù)，n>2191且n>22+m/2(參見附錄B的B.1.10)；

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

h)(選項)計算h=(2m/2+1)2/n，驗證h=h；

9

GB/TXXXXX—XXXX

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

j)若以上任何一個驗證失敗，則輸出“無效”；否則輸出“有效”。

6密鑰對的生成與公鑰的驗證

6.1密鑰對的生成

m

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

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

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

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

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

6.2公鑰的驗證

6.2.1上橢圓曲線公鑰的驗證

FP

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

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

a)驗證P不是無窮遠點O；

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

23

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

d)驗證[n]P=O；

e)若通過了所有驗證，則輸出“有效”；否則輸出“無效”。

6.2.2上橢圓曲線公鑰的驗證

F2m

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

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

a)驗證P不是無窮遠點O；

b)驗證公鑰P的坐標xP和yP是域F2m中的元素(即驗證xP和yP是長度為m的比特串)；

232

在m中驗證；

c)F2yP+xPyP=xP+axP+b

d)驗證[n]P=O；

e)若通過了所有驗證，則輸出“有效”；否則輸出“無效”。

注：公鑰的驗證是可選項。

10

GB/TXXXXX—XXXX

附錄A

（資料性附錄）

關于橢圓曲線的背景知識

A.1素域

FP

A.1.1素域的定義

FP

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

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

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

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

**

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

**i

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

i*-1p-1-i

設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的一個生成元，則F19中元素可由13的方冪表示出來：

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上橢圓曲線常用的表示形式有兩種：仿射坐標表示和射影坐標表示。

11

GB/TXXXXX—XXXX

A.1.2.2仿射坐標表示

23

當p是大于3的素數(shù)時，F(xiàn)p上橢圓曲線方程在仿射坐標系下可以簡化為y=x+ax+b，其中a,b∈Fp，

3223

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

{O}，其中O是橢圓曲線的無窮遠點。

E(Fp)上的點按照下面的加法運算規(guī)則，構成一個阿貝爾群：

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}，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上曲線的點為：

(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個點(包括無窮遠點O)。

a)取P1=(10,2)，P2=(9,6)，計算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)，計算[2]P1：

3x2a3102135116

1