ICS35040

L80.

備案號(hào)36826—2012

:

中華人民共和國(guó)密碼行業(yè)標(biāo)準(zhǔn)

GM/T00031—2012

.

SM2橢圓曲線(xiàn)公鑰密碼算法

第1部分總則

:

PublickeycryptographicalgorithmSM2basedonellipticcurves—

Part1General

:

2012-03-21發(fā)布2012-03-21實(shí)施

國(guó)家密碼管理局發(fā)布

GM/T00031—2012

.

目次

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

Ⅰ

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

Ⅱ

范圍………………………

11

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

21

域和橢圓曲線(xiàn)……………

32

有限域………………

3.12

有限域上的橢圓曲線(xiàn)………………

3.23

數(shù)據(jù)類(lèi)型及其轉(zhuǎn)換………………………

45

數(shù)據(jù)類(lèi)型……………

4.15

數(shù)據(jù)類(lèi)型轉(zhuǎn)換………………………

4.25

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

58

一般要求……………

5.18

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

5.28

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

5.329

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

69

密鑰對(duì)的生成………………………

6.19

公鑰的驗(yàn)證…………………………

6.29

附錄資料性附錄關(guān)于橢圓曲線(xiàn)的背景知識(shí)………

A()11

素域Fp……………

A.111

二元擴(kuò)域Fm……………………

A.2213

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

A.323

求解橢圓曲線(xiàn)離散對(duì)數(shù)問(wèn)題的方法……………

A.426

橢圓曲線(xiàn)上點(diǎn)的壓縮……………

A.527

附錄資料性附錄數(shù)論算法…………

B()29

有限域和模運(yùn)算…………………

B.129

有限域上的多項(xiàng)式………………

B.233

橢圓曲線(xiàn)算法……………………

B.335

附錄資料性附錄曲線(xiàn)示例…………

C()37

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

C.137

Fp上橢圓曲線(xiàn)……………………

C.237

Fm上橢圓曲線(xiàn)……………………

C.3237

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

D()39

橢圓曲線(xiàn)方程參數(shù)的擬隨機(jī)生成………………

D.139

橢圓曲線(xiàn)方程參數(shù)的驗(yàn)證………………………

D.240

參考文獻(xiàn)……………………

41

GM/T00031—2012

.

前言

橢圓曲線(xiàn)公鑰密碼算法分為個(gè)部分

GM/T0003—2012《SM2》5:

第部分總則

———1:;

第部分?jǐn)?shù)字簽名算法

———2:;

第部分密鑰交換協(xié)議

———3:;

第部分公鑰加密算法

———4:;

第部分參數(shù)定義

———5:。

本部分為的第部分

GM/T00031。

本部分依據(jù)給出的規(guī)則起草

GB/T1.1—2009。

請(qǐng)注意本文件的某些內(nèi)容可能涉及專(zhuān)利本文件的發(fā)布機(jī)構(gòu)不承擔(dān)識(shí)別這些專(zhuān)利的責(zé)任

。。

本部分的附錄附錄附錄和附錄為資料性附錄

A、B、CD。

本部分由國(guó)家密碼管理局提出并歸口

。

本部分起草單位北京華大信安科技有限公司中國(guó)人民解放軍信息工程大學(xué)中國(guó)科學(xué)院數(shù)據(jù)與

:、、

通信保護(hù)研究教育中心

。

本部分主要起草人陳建華祝躍飛葉頂峰胡磊裴定一彭國(guó)華張亞娟張振峰

:、、、、、、、。

Ⅰ

GM/T00031—2012

.

引言

和在年各自獨(dú)立地提出將橢圓曲線(xiàn)應(yīng)用于公鑰密碼系統(tǒng)橢圓曲線(xiàn)公

N.KoblitzV.Miller1985。

鑰密碼所基于的曲線(xiàn)性質(zhì)如下

:

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

———,;

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

———,。

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

,,。

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

,。

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

,。,,

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

。

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

,。

Ⅱ

GM/T00031—2012

.

SM2橢圓曲線(xiàn)公鑰密碼算法

第1部分總則

:

1范圍

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

GM/T0003SM2

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

,。

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

。

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

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

。

abFq中的元素它們定義Fq上的一條橢圓曲線(xiàn)E

,:,。

B

B閾正數(shù)B使得求取Fq上的離散對(duì)數(shù)至少與求取Fq上的橢圓曲線(xiàn)離散對(duì)數(shù)一樣困難

:MOV。,。

de多項(xiàng)式x的次數(shù)

g(f):f()。

E有限域上由a和b定義的一條橢圓曲線(xiàn)

:。

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

():()。

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

:。

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

:p。

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

:q。

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

:。

m

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

2:2。

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

:,。

xyx和y的最大公因子

gcd(,):。

h余因子hEFqn其中n是基點(diǎn)G的階

:,=#()/,。

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

f():。

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

max:。

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

: