GM/T 0003.1-2012SM2橢圓曲線公鑰密碼算法第1部分：總則

ICS35040

L80.

備案號36826—2012

:

中華人民共和國密碼行業(yè)標準

GM/T00031—2012

.

SM2橢圓曲線公鑰密碼算法

第1部分總則

:

PublickeycryptographicalgorithmSM2basedonellipticcurves—

Part1General

:

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

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

GM/T00031—2012

.

目次

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

Ⅰ

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

Ⅱ

范圍………………………

11

符號和縮略語……………

21

域和橢圓曲線……………

32

有限域………………

3.12

有限域上的橢圓曲線………………

3.23

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

45

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

4.15

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

4.25

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

58

一般要求……………

5.18

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

5.28

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

5.329

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

69

密鑰對的生成………………………

6.19

公鑰的驗證…………………………

6.29

附錄資料性附錄關于橢圓曲線的背景知識………

A()11

素域Fp……………

A.111

二元擴域Fm……………………

A.2213

橢圓曲線多倍點運算……………

A.323

求解橢圓曲線離散對數(shù)問題的方法……………

A.426

橢圓曲線上點的壓縮……………

A.527

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

B()29

有限域和模運算…………………

B.129

有限域上的多項式………………

B.233

橢圓曲線算法……………………

B.335

附錄資料性附錄曲線示例…………

C()37

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

C.137

Fp上橢圓曲線……………………

C.237

Fm上橢圓曲線……………………

C.3237

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

D()39

橢圓曲線方程參數(shù)的擬隨機生成………………

D.139

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

D.240

參考文獻……………………

41

GM/T00031—2012

.

前言

橢圓曲線公鑰密碼算法分為個部分

GM/T0003—2012《SM2》5:

第部分總則

———1:;

第部分數(shù)字簽名算法

———2:;

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

———3:;

第部分公鑰加密算法

———4:;

第部分參數(shù)定義

———5:。

本部分為的第部分

GM/T00031。

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

GB/T1.1—2009。

請注意本文件的某些內容可能涉及專利本文件的發(fā)布機構不承擔識別這些專利的責任

。。

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

A、B、CD。

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

。

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

:、、

通信保護研究教育中心

。

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

:、、、、、、、。

Ⅰ

GM/T00031—2012

.

引言

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

N.KoblitzV.Miller1985。

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

:

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

———,;

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

———,。

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

,,。

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

,。

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

,。,,

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

。

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

,。

Ⅱ

GM/T00031—2012

.

SM2橢圓曲線公鑰密碼算法

第1部分總則

:

1范圍

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

GM/T0003SM2

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

,。

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

。

2符號和縮略語

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

。

abFq中的元素它們定義Fq上的一條橢圓曲線E

,:,。

B

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

:MOV。,。

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

g(f):f()。

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

:。

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

():()。

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

:。

Fp包含個元素的素域

:p。

Fq包含個元素的有限域

:q。

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

:。

m

Fm包含個元素的二元擴域

2:2。

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

:,。

xyx和y的最大公因子

gcd(,):。

h余因子hEFqn其中n是基點G的階

:,=#()/,。

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

f():。

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

max:。

m二元擴域Fm關于F的擴張次數(shù)

: