GB/T 38635.1-2020.Information security technology-Identity-based cryptographic algorithms SM9-Part 1 : General.
1范围
GB/T 38635的本部分规定了SM9标识密码算法涉及的必要相关数学基础知识、密码技术和具体参数。
GB/T 38635.1适用于SM9标识密码的实现和应用。
2规范性引用文件
下列文件对于本文件的应用是必不可少的。凡是注日期的引用文件，仅注日期的版本适用于本文件。凡是不注日期的引用文件,其最新版本(包括所有的修改单)适用于本文件。
GB/T 32905信息安全技术 SM3 密码杂凑算法
GB/T 32907信息安全技术 SM4 分组密码算法
3术语和定义
下列术语和定义适用于本文件。
3.1
标识 identity
由实体无法否认的信息组成,如实体的可识别名称、电子邮箱、身份证号、电话号码、街道地址等,可唯一确定一个实体的身份。
3.2
主密钥 master key
处于标识密码密钥分层结构最顶层的密钥,包括主私钥和主公钥,其中主公钥公开,主私钥由KGC秘密保存。KGC用主私钥和用户的标识生成用户的私钥。在标识密码中,主私钥一般由KGC通过随机数发生器产生,主公钥由主私钥结合系统参数产生。
3.3
密钥生成中心 key generation center; KGC
在SM9标识密码中,负责选择系统参数、生成主密钥并产生用户私钥的可信机构。
3.4
SM3算法 SM3 algorithm
由GB/T 32905定义的一种杂凑算法。
3.5
SM4算法 SM4 algorithm
由GB/T 32907定义的一种分组加密算法。

ICS35.040
中华人民共和国国家标准
GB/T38635.1—2020
信息安全技术
SM9标识密码算法
第1部分：总则
Information security technology-Identity-based cryptographic algorithms SM9-Part 1:General
2020-04-28发布
国家市场监督管理总局
国家标准化管理委员会
2020-11-01实施
规范性引用文件
术语和定义
有限域和椭圆曲线
有限域
有限域上的椭圆曲线
椭圆曲线群
椭圆曲线多倍点运算
椭圆曲线子群上点的验证
离散对数问题
双线性对及安全曲线
双线性对
安全性
嵌人次数及安全曲线
数据类型及其转换
数据类型
数据类型转换
8系统参数及其验证：
系统参数
系统参数的验证
附录A（规范性附录）
附录B（资料性附录）
附录C（资料性附录）
附录D（资料性附录）
参考文献
参数定义
关于椭圆曲线的背景知识
椭圆曲线上双线性对的计算
数论算法wwW.bzxz.Net
GB/T38635.1—2020
GB/T38635《信息安全技术SM9标识密码算法》分为两个部分：第1部分：总则；
第2部分：算法。
本部分为GB/T38635的第1部分
本部分按照GB/T1.1—2009给出的规则起草。GB/T38635.1-—2020
请注意本文件的某些内容可能涉及专利。本文件的发布机构不承担识别这些专利的责任。本部分由全国信息安全标准化技术委员会（SAC/TC260)提出并归口。本部分起草单位：国家信息安全工程技术研究中心、北京国脉信安科技有限公司、深圳奥联信息安全技术有限公司、中国科学院软件研究所、武汉大学、中科院信息工程研究所。本部分主要起草人：陈晓、程朝辉、张振峰、叶顶峰、胡磊、陈建华、季庆光、袁文恭、刘平、马宁、袁峰，李增欣、王学进、杨恒亮、张青坡、马艳丽、浦雨三、唐英、孙移盛、安萱、封维端、张立圆。m
GB/T38635.1—2020
A.Shamir在1984年提出了标识密码（Identity-basedcryptography）的概念，在标识密码系统中，用户的私钥由密钥生成中心（KGC）根据主密钥和用户标识计算得出，用户的公钥由用户标识唯一确定，由标识管理者保证标识的真实性。与基于证书的公钥密码系统相比，标识密码系统中的密钥管理环节可以得到适当简化。
1999年，K.Ohgishi、R.Sakai和M.Kasahara在日本提出了用椭圆曲线对（pairing）构造基于标识的密钥共享方案；2001年，D.Boneh和M.Franklin，以及R.Sakai、K.Ohgishi和M.Kasahara等人独立提出了用椭圆曲线对构造标识公钥加密算法。这些工作引发了标识密码的新发展，出现了一批用椭圆曲线对实现的标识密码算法，其中包括数字签名算法、密钥交换协议、密钥封装机制和公钥加密算法等。椭圆曲线对具有双线性的性质，它在椭圆曲线的循环子群与扩域的乘法循环子群之间建立联系，构成了双线性DH、双线性逆DH、判定性双线性逆DH、t-双线性逆DH和t-GaP-双线性逆DH等难题，当椭圆曲线离散对数问题和扩域离散对数问题的求解难度相当时，可用椭圆曲线对构造出安全性和实现效率兼顾的标识密码。
HiiKaeerKAca
1范围
信息安全技术SM9标识密码算法
第1部分：总则
GB/T38635.1—2020
GB/T38635的本部分规定了SM9标识密码算法涉及的必要相关数学基础知识、密码技术和具体参数。
本部分适用于SM9标识密码的实现和应用。规范性引用文件
下列文件对于本文件的应用是必不可少的。凡是注日期的引用文件，仅注日期的版本适用于本文件。凡是不注日期的引用文件，其最新版本（包括所有的修改单）适用于本文件。GB/T32905
信息安全技术SM3密码杂凑算法
KaeeiKAca
GB/T32907
3术语和定义
信息安全技术SM4分组密码算法
下列术语和定义适用于本文件。3.1
标识identity
由实体无法否认的信息组成，如实体的可识别名称、电子邮箱、身份证号、电话号码、街道地址等，可唯一确定一个实体的身份。
主密钥
masterkey
处于标识密码密钥分层结构最顶层的密钥，包括主私钥和主公钥，其中主公钥公开，主私钥由KGC秘密保存。KGC用主私钥和用户的标识生成用户的私钥。在标识密码中，主私钥一般由KGC通过随机数发生器产生，主公钥由主私钥结合系统参数产生。3.3
密钥生成中心keygenerationcenter；KGC在SM9标识密码中，负责选择系统参数、生成主密钥并产生用户私钥的可信机构，3.4
SM3算法SM3algorithm
由GB/T32905定义的一种杂凑算法。3.5
去SM4algorithm
SM4算法
由GB/T32907定义的一种分组加密算法。4符号
下列符号适用于本文件
GB/T38635.1—2020
cf：椭圆曲线阶相对于N的余因子。cid：用一个字节表示的曲线识别符，用以区分所用曲线的类型。deg(f）：多项式f（r)的次数。di、d2:k的两个因子。
E：定义在有限域上的椭圆曲线。ECDLP：椭圆曲线离散对数问题
E（F，）：有限域F上椭圆曲线E的所有有理点（包括无穷远点O）组成的集合。E（F)[r]：E（F，）上r-扭点的集合［即曲线E（F）上的r阶扭子群]。e:从GIXGz到G-的双线性对。
eid：用一个字节表示的双线性对e的识别符，用以区分所用双线性对的类型，FDLP：有限域上离散对数问题。F，：包含p个元素的素域。
F：包含q个元素的有限域。
F，：由F，中所有非零元构成的乘法群。F：有限域F的m次扩域
GT：阶为素数N的乘法循环群。
Gi：阶为素数N的加法循环群。
G2：阶为素数N的加法循环群。
gcd(x，y）：x和y的最大公因子。KAca
k：曲线E（F)相对于N的嵌人次数，其中N是#E（F)的素因子。m：有限域F关于F,的扩张次数。modf(）：模多项式f（r）的运算。modn：模n运算。
示例：23mod7=2。
N：循环群G、G和Gr的阶，为大于21的素数。0：椭圆曲线上的一个特殊点，称为无穷远点或零点，是椭圆曲线加法群的单位元P：P=（rpy,）是椭圆曲线上除O之外的一个点，其坐标ap，yp满足椭圆曲线方程。P1：G的生成元。
P2:G的生成元。
P+Q：椭圆曲线E上两个点P与Q的和。p：大于21\的素数。
q：有限域F.中元素的数目。
Tp：点P的坐标。
xy：r与y的拼接，其中和y是比特串或字节串。x=y（modg)：x与y模q同余。即，rmodq=ymodqyp:点P的y坐标。
#E(K)：E（K)上点的数目，称为椭圆曲线群E（K)的阶，其中K为有限域（包括F，和F）。

：由椭圆曲线上点P生成的循环群。[u]P：椭圆曲线上点P的u倍点
[xy]：不小于且不大于y的整数的集合。「α：顶函数，不小于x的最小整数。例如，-7=7「8.3=9。-：底函数，不大于α的最大整数。例如，L7|=7,L8.3=8。β:扭曲线参数
：G到G的同态映射.满足P,=W(P2）。?：长度相等的两个比特串按比特的模2加运算。有限域和椭圆曲线
5.1有限域
5.1.1概述
GB/T38635.1—2020
域由一个非空集合F和两种运算共同组成，这两种运算分别为加法（用“十”表示）和乘法（用\”表示），并且满足下列算术特性：a）（F，十）对于加法运算构成加法交换群，单位元用0表示：b）（F1(0)，·）对于乘法运算构成乘法交换群，单位元用1表示；c）分配律成立对于所有的a.b.cEF.都有（a十b）·c=a·c十b·c若集合F是有限集合，则称域为有限域。有限域的元素个数称为有限域的阶。5.1.2素域F
阶为素数的有限域是素域。
设p是一个素数，则整数模p的全体余数的集合(0,1.2.pb-1)关于模p的加法和乘法构成—aeeiKA
个p阶素域，用符号F，表示。
F，具有如下性质：
a）加法单位元是0；
b）乘法单位元是1；
c）域元素的加法是整数的模p加法，即着a,bEF，，则a+b=（a+b）modp；d）域元素的乘法是整数的模p乘法，即若a,bEF，，则a·b=（a·b）modp。5.1.3有限域F。的m次扩域Fgm
设g是一个素数或素数方幂，f（r）是多项式环F.[上的一个m（m>1)次不可约多项式（称为约化多项式或域多项式)，商环F[a]/（f（r))是含q\个元素的有限域（记为F）,称F是有限域F,的扩域，域F,为域F的子域，m为扩张次数。F可以看成F，上的m维向量空间。F的每一个元可以唯—地写成aβ十aiβ十十a-iβ.-的形式.其中a,EF而β..i...β.-i是向量空间F.在F上的一组基。
F中的元素可以用多项式基或正规基表示。在本部分中，如果不作特别说明，F中元素均采用多项式基表示。
不可约多项式f()可取为首一的多项式f(）=r\+f-i\-1+.…+f?+fia十f（其中fFi=01，...，m一1），F中的元素由多项式环F.Lr中所有次数低于m的多项式构成。多项式集合《\-，r\-2，..,r，1)是F在F上的一组基，称为多项式基。域F上的任意一个元素a（α）=am-1z\-1+am-22\-2+…十ai十a在F，上的系数恰好构成了一个m维向量，用a=（am-1,am-2..，ai.a.)表示.其中分量a,EF..i=0,l....m-1。F具有如下性质：
a）零元0用m维向量（0.....0.0）表示；b）乘法单位元1用m维向量（0.....0,1）表示两个域元素的加法为向量加法，各个分量用域F，的加法；c
d）域元素a和b的乘法定义如下：设a和b对应的F，上多项式为a(x)和b（r），则α·b定义为3
GB/T38635.1—2020
多项式（a（a）·b（a)）modf（α)对应的向量；e）逆元：设a对应的F。上多项式为a（r）.a的逆元a-对应的F。上多项式为a-l（r）,那么有a(x)·a-(r)=lmod f(x)。
本部分使用F。上的12次扩域见附录A。关于有限域的扩域F更多细节，参见附录B中的B.1。5.2有限域上的椭圆曲线
有限域F（m≥1）上的椭圆曲线是由点组成的集合。在仿射坐标系下，椭圆曲线上点P（非无穷远点）用满足一定方程的两个域元素a，和y表示，py分别称为点P的坐标和y坐标，并记P=(xp.yp).
本部分描述特征为大素数P的域上的曲线。本部分如果不作特别说明，椭圆曲线上的点均采用仿射坐标表示。定义在F\上的椭圆曲线方程见式（1)：y=x+a+b.a.bEF，且4a+2760
椭圆曲线E（F）定义为：
E（F）=(（α，y)lx.yEF，且满足式（1))UO).其中O是无穷远点。椭圆曲线E（F）上的点的数目用#E（F,）表示，称为椭圆曲线E（F）的阶。本部分规定素数p>21\1。
设E和E是定义在F，上的椭圆曲线，如果存在一个同构映射Φ：E（F）→E（F），其中d是使映射存在的最小整数，则称E为E的d次扭曲线。当p5时，d的取值有三种情况：a）若a=0.b0.那么d=6.E:y=+3bE→E：x.y)H(β-1/aβ-1/2y)；b）若b=0.a0,那么d=4E:y=+Bax,：E'→E：(x.y)H(β-1/2r.β-3/4y）;若a≠0.b≠0，那么d=2E：=
椭圆曲线群
+par+b,Φ2:E-E:(a.y)H(-xβ-3/2y)椭圆曲线E（F）（m≥1）上的点按照下面的加法运算规则，构成一个交换群：a) 0+0=0。
VP=(ry)EE(F)\\O),P+O=O+P=P。VP=(,y)EE(F,)IO).P的逆元素-P=(,-y),P+(-P)=O。c)
d两个非互逆的不同点相加的规则：设P=()EEF(O),P=()EE(FO)且2
设P=（y)=P+P2则：
[=2— —x2
其中：
e）倍点规则：
设P=(y)EE(F,m)(O),且y0,P=(y)=P+P则：
[x3=入2—2
其中：
5.4椭圆曲线多倍点运算
_32i+a
GB/T38635.1—2020
椭圆曲线上同二个点的重复相加称为该点的多倍点运算。设u是一个正整数，P是椭圆曲线上的点，其u倍点Q=[u]P=P+P+…+P。个
多倍点运算可以扩展到o倍点运算和负数倍点运算:[o]P=O,[一u]P=［u]（-P）。多倍点运算可以通过一些技巧有效地实现，参见B.25.5椭圆曲线子群上点的验证
输入：定义F上（q为奇素数，m≥1）椭圆曲线方程的参数a、b，椭圆曲线E（F）上子群G的阶N，F上的一对元素（r，y）。
输出：若（x，y）是群G中的元素，则输出“有效”；否则输出无效”。计算步骤为：
a）在F上验证（r，y）是否满足椭圆曲线方程y=x十ar十b；b）令Q=（α，y）,验证[N]Q=O。若以上任何一项验证失败，则输出“无效”，否则，输出“有效”。5.6离散对数问题
5.6.1有限域上离散对数问题（FDLP）有限域F（q为奇素数，m≥1)的全体非零元素构成一个乘法循环群，记为F.。F中存在元素g，使得F=（g|0≤i≤q\一2)，称g为生成元。F中元素a的阶是满足α=1的最小正整数t。群Fm的阶为g\-1,因此tlg\—1
设乘法循环群F的生成元为g，yEF，有限域上离散对数问题是指确定整数rE[0.q\-2]，使得y=g在F上成立。
5.6.2椭圆曲线离散对数问题（ECDLP）已知椭圆曲线E（F㎡）（m≥1），阶为n的点PEE（F㎡）及QE

，椭圆曲线离散对数问题是指确定整数lE[0,n-1],使得Q=[]P成立。6双线性对及安全曲线
6.1双线性对
设Gi，十）、（G2，十）和(GT，）是三个循环群,G、G和G的阶均为素数N,Pi是G的生成元，P2是G2的生成元，存在G2到G的同态映射使得（P,）=P1。双线性对e是G,XG2→GT的映射，满足以下条件：a）双线性性：对任意的PEGi.QEG2a，bEZv,有e([a]P[b]Q)=e（P,Q)；b）非退化性：e(Pi,P）≠1g；
c）可计算性：对任意的PEG1QEG存在有效的算法计算e(P,Q)。所用的双线性对定义在椭圆曲线群上，主要有Weil对、Tate对、Ate对、R-ate对等，相关描述参见GB/T38635.1—2020
附录C。
2安全性
双线性对的安全性主要建立在以下几个问题的难解性基础之上：问题1［双线性逆DH(BIDH)]对a，bE[1N-1].给定（[a]P.[b]P,）,计算e（P，P,）/a是困难的。
问题2［判定性双线性逆DH(DBIDH)]对a,b,rE[1,N-1],区分(P1P2.[a]P1,[b]P2,e(Pi，P)6)和(PP[aP1,[b]P2e(P,P,)\)是困难的问题3[t-双线性逆DH(t-BDHI)]对正整数和rE[I,N-1].给定（P1,[]PI,P2,[]P2[P2..[r\]P,),计算e(P,P,)是困难的。问题4［t-Gap-双线性逆DH(t-Gap-BDHI)]对正整数和E[1,N—1],给定（P1，[]P1,P2［P,[r]P2，,[]P2)和DBIDH确定算法，计算e（P1,P,)1/是困难的。上述问题的难解性是SM9标识密码的安全性的重要基础，这些问题的难解性都意味着G1、G和G上的离散对数问题难解，选取的椭圆曲线应首先使得离散对数问题难解。3嵌入次数及安全曲线
设G是椭圆曲线E（F）的N阶子群，使NIq-1成立的最小正整数k称为子群G相对于N的嵌人次数，也称为曲线E（F,）相对于N的嵌人次数。设G是E（Fdt）（d.整除k）的N阶子群，G2是E（Fa）（d整除k）的N阶子群，则椭圆曲线双线性对的值域G是F的子群，因此椭圆曲线双线性对可将椭圆曲线离散对数问题转化为有限域F上离散对数问题。嵌入次数越大安全性越高，但双线性对的计算越困难，因而需要采用嵌人次数适中且达到安全性标准的椭圆曲线。本部分规定q>21536。本部分规定选用如下的曲线：
a）基域q为大于219的素数、嵌人次数k=23的常曲线，其中i>0,j≥0；b）基域q为大于2768的素数、嵌人次数k=2的超奇异曲线。对小于236的N.建议：
a）N-1含有大于219\的素因子；b）N十1含有大于212的素因子。7数据类型及其转换
7.1数据类型
本部分规定的数据类型包括比特串、字节串、域元素、椭圆曲线上的点和整数。比特串：有序的0和1的序列。
字节串：有序的字节序列，其中8比特为1个字节，最左边的比特为最高位。域元素：有限域Fm（m≥1)中的元素。椭圆曲线上的点：椭圆曲线E（F）（m≥1)上的点P或者是无穷远点O.或者是一对域元素（rp，）.其中域元素p和yp满足椭圆曲线方程。点的字节串表示有多种形式，用一个字节PC加以标识。无穷远点的字节串表示是单一的零字节PC=00。非无穷远点P=（p.yp）有以下三种字节串表示形式：a）压缩表示形式，PC=02或03；b）未压缩表示形式，PC=04；
c）混合表示形式，PC=06或07。GB/T38635.1—2020
注：混合表示形式既包含压缩表示形式又包含未压缩表示形式。在实现中，它允许转换到压缩表示形式或者未压缩表示形式。对于椭圆曲线上点的压缩表示形式和混合表示形式，本部分定为可选形式。椭圆曲线上点的压缩表示形式参见B.4。
数据类型转换
7.2.1数据类型转换关系
图1表示了各种数据类型之间的转换关系，线上的标志是相应数据转换方法所在的条号域元素
比特串
数据类型和转换约定示意图
7.2.2整数到字节串的转换
输入：非负整数x.以及字节串的目标长度1（其中1满足28>）。输出：长度为1的字节串M。
计算步骤为：
a）设M,-1,M,-2...,M。是M从最左边到最右边的字节；b）M的字节满足：
28M。
7.2.3字节串到整数的转换
输入：长度为1的字节串M。
输出：整数x。
计算步骤为：
a）设M,-1，M,-2，...，M。是M从最左边到最右边的字节；b）将M转换为整数r：
2\M,。
7.2.4比特串到字节串的转换
输入：长度为n的比特串。
GB/T38635.1—2020
输出：长度为的字节串M.其中1=「n/81计算步骤为：
a）设sn-1,s-2....,s。是s从最左边到最右边的比特；b)
设M,-1,M,-2.,M。是M从最左边到最右边的字节，则：M,=s8++2+6s8+15s其中0≤i输入：长度为1的字节串M。
输出：长度为n的比特串s，其中n=8l计算步骤为：
a）设M,-1,M,-2，..,M。是M从最左边到最右边的字节；b）设sa-1.s,-2...,s。是从最左边到最右边的比特，则s，是M，右起第i一8j十1比特，其中=Li/8]。
7.2.6域元素到字节串的转换
输入：F（m≥1)中的元素a-（am-1,am-2....a1a），q=p。输出：长度l的字节串S，其中1=[1og29/8Xm。计算步骤为：
a）若m=1，则α=a（q=p），α必为区间[0.q一1]中的整数，按7.2.2的细节把α转换成长度为l的字节串S；
若m>l,则α=（am-i.am-2,....ai.a.）（q=p),其中a,EF..i=0.l.....m-1;1)置r=[log2q/8];
2）对i从m-1到0执行：
按7.2.2的细节把a（q=p）转换成长度为r的字节串s3) S=sm-1 ll sm-2 Il... ll sg。7.2.7字节串到域元素的转换
情形1：转换为基域中元素
输入：域F，q=p，长度为1的字节串S，l=[1og29/8输出：F，中的元素α。
若q=p.则按7.2.3的细节将S转换为整数α，若α[0.q一1].则报错。情形2：转换为扩域中元素
输入：域F，（m2)，q=p，长度为l的字节串S，其中l=「log2g/8xm。输出：F。中的元素α。
计算步骤为：
a）将字节串S平均分成m段，每段长度为l/m，记作S=（Sm-i.Sm-2，..,Si.S。）；b）对i从m-1到0执行：
按7.2.3的细节将S转换为整数a，若a.4[0q一1],则报错c）若q=p，输出α=（am-1.am-2.....ai.a。）。7.2.8点到字节串的转换
点到字节串的转换分为两种情形：一种是在计算过程中，将椭圆曲线点转换为字节串后才能作为某个函数（如杂凑函数）的输人，这种情况下只需直接将点转换为字节串；一种是在传输或存储椭圆曲线点8
小提示：此标准内容仅展示完整标准里的部分截取内容，若需要完整标准请到上方自行免费下载完整标准文档。