GB／T 38635.1-2020标准规范下载简介：

内容预览由机器从pdf转换为word，准确率92%以上，供参考

GB／T 38635.1-2020 信息安全技术 SM9标识密码算法 第1部分：总则

5.6.1有限域上离散对数问题（FDLP）

5.6.2椭圆曲线离散对数问题（ECDLP）

6.3嵌入次数及安全曲

设G是椭圆曲线E（F。)的N阶子群，使NIg*一1成立的最小正整数k称为子群G相对于N的嵌 人次数，也称为曲线E（F。）相对于N的嵌入次数， 设G，是E（F，）（d,整除k)的N阶子群，G2是E（F）（d整除k）的N阶子群，则椭圆曲线双 线性对的值域GT是F的子群，因此椭圆曲线双线性对可将椭圆曲线离散对数问题转化为有限域F。 上离散对数问题。嵌入次数越大安全性越高，但双线性对的计算越困难，因而需要采用嵌入次数适中且 达到安全性标准的椭圆曲线。本部分规定Q>21536。 本部分规定选用如下的曲线： a）基域q为大于2191的素数、嵌人次数k=2'3的常曲线，其中i>0，j≥0； b）基域q为大于2768的素数、嵌人次数k=2的超奇异曲线。 对小于2360的N，建议： a）N一1含有大于2190的素因子； b）N+1含有大于212°的素因子

本部分规定的数据类型包括比特串、字节串、域元素、椭圆曲线上的点和整数。 比特串：有序的0和1的序列。 字节串：有序的字节序列，其中8比特为1个字节，最左边的比特为最高位。 域元素：有限域F（m≥1）中的元素。 椭圆曲线上的点：椭圆曲线E（F）（m≥1)上的点P或者是无穷远点O，或者是一对域元素（αp yp），其中域元素p和yp满足椭圆曲线方程。 点的字节串表示有多种形式，用一个字节PC加以标识。无穷远点O的字节串表示是单一的零字 节PC=00。非无穷远点P=（αp，yp）有以下三种字节串表示形式： a）压缩表示形式YBJ 277-1991 锚杆静压桩技术规程，PC=02或03； b）未压缩表示形式,PC=04

本部分规定的数据类型包括比特串、字节串、域元素、椭圆曲线上的点和整数 比特串：有序的0和1的序列。 字节串：有序的字节序列，其中8比特为1个字节，最左边的比特为最高位 域元素：有限域F（m≥1）中的元素。 椭圆曲线上的点：椭圆曲线E（F）（m≥1)上的点P或者是无穷远点O，或者是一对域元素（αp， Vp），其中域元素p和p满足椭圆曲线方程。 点的字节串表示有多种形式，用一个字节PC加以标识。无穷远点O的字节串表示是单一的零字 节PC=00。非无穷远点P=（p，p）有以下三种字节串表示形式： a）压缩表示形式，PC=02或03； b）未压缩表示形式,PC=04

c）混合表示形式，PC=06或07 注：混合表示形式既包含压缩表示形式又包含未压缩表示形式。在实现中，它允许转换到压缩表示形式或者 缩表示形式。对于椭圆曲线上点的压缩表示形式和混合表示形式，本部分定为可选形式。椭圆曲线上点 缩表示形式参见B.4。

c）混合表示形式，PC=06或07 注：混合表示形式既包含压缩表示形式文包含未压缩表示形式。在实现中，它充许转换到压缩表示形 缩表示形式。对于椭圆曲线上点的压缩表示形式和混合表示形式，本部分定为可选形式。椭圆曲 缩表示形式参见B.4

1.2.1数据类型转换关系

图1表示了各种数据类型之间的转换关系，线上的标志是相应数据转换方法所在的条号

7.2.2整数到字节串的转换

2.4比特串到字节串的车

输入：长度为n的比特串s

图1数据类型和转换约定示意图

GB/T38635.12020

7.2.5字节串到比特串的转换

7.2.6域元素到字节串的转换

7.2.7字节串到域元素的转换

7.2.8点到字节串的转换

点到字节串的转换分为两种情形：一种是在计算过程中，将椭圆曲线点转换为字节串后才能作为 数（如杂凑函数）的输人，这种情况下只需直接将点转换为字节串；一种是在传输或存储椭圆曲线

时，为了减少传输的量或存储空间，可采用点的压缩或混合压缩表示形式，这种情况下需要加入一个字 节的识别符PC来指示点的表示形式。下面分两种情况说明详细的转换过程。 情形1：直接转换 输入：椭圆曲线E(F）（m≥1)上的点P=（rp，yp），且P≠O。 输出：长度为2的字节串X，lY1。（当m=1时，l=[log2q/8l；当m>1时，1=[log2q/8xm。） 计算步骤为： a）按7.2.6中的细节把域元素p转换成长度为1的字节串X； b）按7.2.6中的细节把域元素yp转换成长度为l的字节串Y1； c）输出字节串X，Y1。 情形2：添加一字节识别符PC的转换 输入：椭圆曲线E（F）（m≥1)上的点P=（rp，yp）,且P≠O。 输出：字节串PO。若选用未压缩表示形式或混合表示形式，则输出字节串长度为21十1；若选用压 宿表示形式，则输出字节串长度为1十1。（当m=1时，l=「1og2q/81；当m>1时，l=「1og2q/8xm）。 计算步骤为： a）按7.2.6中的细节把域元素，转换成长度为1的字节串X1。 b）若选用压缩表示形式，则： 1）计算比特yp（参见B.4)； 2）若p=0,则令PC=02;若yp=1,则令PC=03; 3）字节串PO=PCIX, c）若选用未压缩表示形式，则： 1）按7.2.6的细节把域元素yp转换成长度为1的字节串Y1； 2)令 PC=04; 3）字节串 PO=PCX,Y1。 d） 若选用混合表示形式，则： 1）按7.2.6的细节把域元素p转换成长度为1的字节串Y1； 2）计算比特p（参见B.4)； 3）若p=0,则令PC=06;若yp=1,则令PC=07; 4)字节串 PO=PC IX, IYi

7.2.9字节串到点的转换

字节串到点的转换是7.2.8的逆过程。下面也分两种情况加以说明。 情形1：直接转换 输入：定义F。（m≥1)上椭圆曲线的域元素a、b，长度为21的字节串X，IY1，X1、Yi的长度均为l （当m=1时，l=[1og2q/81;当m>1时，l=[1og2q/8xm）。 输出：椭圆曲线上的点P=（p，yp），且P≠O。 计算步骤为： a）按7.2.7的细节把字节串X，转换成域元素p； b）按7.2.7的细节把字节串Y，转换成域元素yp° 情形2：包含一字节识别符PC的字节串的转换 输入：定义F,（m≥1)上椭圆曲线的域元素α、b，字节串PO。若选用未压缩表示形式或混合表示 形式，则字节串PO长度为21十1；若选用压缩表示形式，则字节串PO长度为1十1（当m=1时，l [log29/8];当 m>1 时,l=[log2q/8 xm)

字节串到点的转换是7.2.8的逆过程。下面也分两种情况加以说明。 情形1：直接转换 输入：定义F（m≥1)上椭圆曲线的域元素a、b，长度为2l的字节串X，IY1，X1、Yi的长度均为l （当m=1时，l=[1og2q/81;当m>1时，l=[1og2q/8xm）。 输出：椭圆曲线上的点P=（p，yp），且P≠O。 计算步骤为： a）按7.2.7的细节把字节串X，转换成域元素p； b）按7.2.7的细节把字节串Y，转换成域元素yp° 情形2：包含一字节识别符PC的字节串的转换 输入：定义F,（m≥1)上椭圆曲线的域元素α、b，字节串PO。若选用未压缩表示形式或混合表示 形式，则字节串PO长度为21十1；若选用压缩表示形式，则字节串PO长度为1十1（当m=1时，l [1og2q/8];当m>1 时,l=[1og2g/8xm)

GB/T38635.12020

输出：椭圆曲线上的点P=（α，，y，），且P≠C

a）若选用压缩表示形式，则PO=PCⅡX1；若选用未压缩表示形式或混合表示形式，则PO PCⅡIX，ⅡIYi，其中PC是单一字节，X，和Y,都是长度为I的字节串。 b） 按7.2.7的细节把字节串X，转换成域元素αp。 C 若选用压缩表示形式，则： 1）检验PC=02或者是PC=03，若不是这种情形，则报错； 2）若PC=02,则令3p=0；若PC=03,则令yp=1； 3）将（p，）转换为椭圆曲线上的一个点（αp*p）（参见B.4）。 d）若选用未压缩表示形式，则： 1）检验PC=04，若不是这种情形，则报错； e） 若选用混合表示形式，则： 1）检验PC=06或者PC=07，若不是这种情形，则报错； 2）执行以下步骤： ·按7.2.7的细节把字节串Y转换成域元素3p； ·若PC=06,则令yp=0，否则令p=1； 将（ap，yp）转换为椭圆曲线上的一个点（ap，yp）（参见B.4）。 f）验证（p，yp）是否满足曲线方程，若不满足，则报错。 g) P=(2p.V,)

GB/T 38635.1—2020

本部分使用256位的BN曲线。 椭圆曲线方程：32=3+b。 曲线参数： 参数t：600000000058F98A 迹tr(t)=6t²+1:D8000000019062ED0000B98B0CB27659 基域特征q（t)=36t*+36t"+24t²+6t+1 B640000002A3A6F1D603AB4FF58EC74521F2934B1A7AEEDBE56F9B27E351457D 方程参数6：05 群的阶Nt）=36t4+36t3+18t²+6t+1： B640000002A3A6F1D603AB4FF58EC74449F2934B18EA8BEEE56EE19CD69ECF25 余因子f：1 嵌人次数：12 扭曲线的参数β：V一2 k的因子d,=1,d2=2 曲线识别符cid0x12 群G的生成元P,=(αP,yp,）： 坐标p,:93DE051D62BF718FF5ED0704487D01D6E1E4086909DC3280E8C4E4817C66DDDD 坐标yp,:21FE8DDA4F21E607631065125C395BBC1C1C00CBFA6024350C464CD70A3EA616 群G2的生成元P2=（P2，yP2）： 3722755292130B08D2AAB97FD34EC120EE265948D19C17ABF9B7213BAF82D65B 坐标yp:(17509B092E845C1266BA0D262CBEE6ED0736A96FA347C8BD856DC76B84EBEB96 A7CF28D519BE3DA65F3170153D278FF247EFBA98A71A08116215BBA5C999A7C7 双线性对的识别符eid：0x04

,bc用F，中元素表示：

GB/T38635.12020

b=b1+b。=(b1,ba) c=CiU+C。=(cl,C) 其中:ai,ao,bi,bo,c1,coEFa2 b)F12中元素A用F中的元素表示： A=(ai,ao,bi,bo,c1,co) a1,ao,bi,ba,ci,c。用基域F中的元素表示： a=ao.1u+ao.=(ao.1,ao.) a=a1.1u+a1.0=(a1.1,a1.0) b,=bo.1u十bo.o=(bo.1,bo.0) b,=b1.1u+b1.0=(b1.1,b1.o) Co=Co.1u+Co.o=(co,1,Co.o) C, =C1.1 u +C1.0 =(c1.1,C1.0)

C =CU+C= (C , Co ) 其中:ai,ao,bi,bo,ci.coEF.2o b)F12中元素A用F中的元素表示： A=(ai,ao,bi,boc1,co) a1,ao,b1,bo,c1,c。用基域F中的元素表示： a。=ao.1u+ao.=(ao.1,ao.) a,=a1,1u+a1.0=(a1.1,a1.o) b=bo.1u+bo.o=(bo.1,bo.o) b,=b1.1u+b1.0=(b1.1,b1.0) Co=Co.1u+Co.o=(co.1,Co.o) Ci =C1.1u+C1,0=(c1,1,C1.o) 其中:ao.1ao.o.ai.1a1.o,bo.1,bo.0bi.1,b1..co.1.co.o.c1.1.c1.EF.o c)F。12中元素A用基域F。中的元素表示： A=(ao.1,ao.o.al.1,a1.0,bo.1,bo.o,b.1,bi.o.co.1+co.o,1.l,C1.o) 其中:ao.1.ao.o,a1.1.a1.o,bo.1,bo.o,b.1,b1.0.co.1.co.oc1.1.c1.oEF.o F2中单位元的表示为（0，1）。 F中单位元的表示为（0，0，0，1）。 F。12中单位元的表示为（0,0,0,0,0,0,0,0,0,0,0,1)。 各种扩域中分量序为：左边是高维，右边是低维。 示例数据中，扩域中的元素均用基域中的元素表示

c)F。2中元素A用基域F。中的元素表示

GB/T 38635.1—2020

附录B （资料性附录） 关于椭圆曲线的背景知识

B.1.3有限域上的椭圆曲线

有限域上椭圆曲线常用的表示形式有两种：仿射坐标表示和射影坐标表示

B.1.3.2仿射坐标表示

GB/T 38635.1—2020

B.1.3.3射影坐标表示

B.1.3.4Jacobian加重射影坐标系

B.1.4有限域上椭圆曲线的阶

B.2椭圆曲线多倍点运算

椭圆曲线上同一个点的重复相加称为该点的多倍点运算。设u是一个正整数，P是椭圆曲线上的 点，其u倍点Q=[u]P=P+P++P 多倍点运算可以扩展到O倍点运算和负数倍点运算：LO|P=O，L一u|P=LuJ（一P） 椭圆曲线多倍点运算的实现有多种方法，这里只介绍最基本的三种方法，以下都假设1≤u

椭圆曲线上同一个点的重复相加称为该点的多倍点运算。设u是一个正整数，P是椭圆曲线上的 点,其u倍点Q=[uJP=P+P++P 多倍点运算可以扩展到O倍点运算和负数倍点运算：［O]P=O,［一u]P=［u]（一P）。 椭圆曲线多倍点运算的实现有多种方法，这里只介绍最基本的三种方法，以下都假设1≤u

B.3.1求解有限域上离散对数问题的方法

B.3.2求解椭圆曲线离散对数问题的方法

对于椭圆曲线E（F）上的任意非无穷远点P=（αp），该点能由坐标αp及由和p导出白 特定比特简洁地表示，称为点的压缩表示

GB/T38635.12020

B.4.2F，上椭圆曲线点的压缩与解压缩方法

GB/T38635.12020

附录C （资料性附录） 椭圆曲线上双线性对的计算

设有限域F。上随员曲线为E（F。），若并E（F Xr，产是系数且gcd（r，q）三I，c为余因于， 则使rlq*一1的最小正整数k称为椭圆曲线相对于r的嵌人次数。若G是E（F。）的r阶子群，则G 的嵌入次数也是尺。 设F，是有限域F的代数闭包，E[r表示E(F,)中所有r阶点的集合

C.2Miller算法

C.3Weil对的计算

设E是F。上的椭圆曲线，r是与q互素的正整数，设,是r次单位根集合，k是相对于r的嵌入次 数,即rI q*1,则μ,F。 令G=E[r],G2=E[r],G=μ,，则Weil对是从G,×G,到G的双线性映射，记为e, 设PEG，QEG2，若P=O或Q=O,则e,（P，Q）=1；如果P≠O且Q≠O,随机选取非无穷远点 TEG，UEG2.使得P+T和T均不等于U或U+Q,则Weil对为：

f p+T.,(Q+U)f r..(U)fu..(P+ T)f +U.(T) er(P,Q): f r., (Q +U)f p+T.,(U)f o+u..(P + T) fu. (T)

(T)均可用Miller算法计算。在计算过程中，若出现分母为0的情况，则更换点T或U重新计算

C.4Tate对的计算

fp.,（Q十U)和fp.（U)可通过Miller算法计算。在计算过程中，若出现分母为O的情况，则更换 点U重新计算。 在实际应用中，一般使用约化Tate对：

GB/T 28406-2012 农用地估价规程Jf p.r (Q)(qt=1/ Q≠O t,(P,Q) : 1. Q=0

约化Tate对比一般Tate对的计算量减少了一半。若相对于r的嵌人次数k是偶数时，约化Ta 计算方法可以进一步优化。算法1描述的是一般约化Tate对的计算方法，算法2、3、4均指k= 况。

输入：与Q互素的整数r,PEE（F。)[r,QEEF,)[r]。 输出：t,(P，Q)。 a）设r的二进制表示是r;riro，其最高位r,为1。 b) 置f=1,V=P。 c）对i=j一1降至0，执行： 1) 计算 f =f" · gv.v(Q)/g2v(Q),V=[2]V; 2) 若r;=1,则计算 f =f ·gv.p(Q)/gv+p(Q),V=V+P。

GB/T38635.12020

设元为Frobenius自同态，即元：E→E，（，y)→（"，y"）；［q为映射：E→E，Q→qQ；［1]为 单位映射；元，的对偶为元。，满足元。·元。=［q」；Ker（）表示映射的核；设椭圆曲线E（F。）的Frobenius 迹为t，令T=t一1。 下面给出不同结构下的Ate对的计算方法。

C.5.2定义在G,xGGB/T 32610-2016 日常防护型口罩技术规范，上Ate对的计算

义在G,XG，上Ate对自

Ate:G,XG2→F/(F）