曲线1u等于多少厘米

目次前言Ⅱ引言Ⅲ1范围12规范性引用文件13术语和定义14符号和缩略语25有限域和椭圆曲线35.
1有限域35.
2有限域上的椭圆曲线45.
3椭圆曲线群45.
4椭圆曲线多倍点运算55.
5椭圆曲线子群上点的验证55.
6离散对数问题56双线性对及安全曲线56.
1双线性对56.
2安全性66.
3嵌入次数及安全曲线67数据类型及其转换67.
1数据类型67.
2数据类型转换78系统参数及其验证108.
1系统参数108.
2系统参数的验证11附录A(规范性附录)参数定义12附录B(资料性附录)关于椭圆曲线的背景知识14附录C(资料性附录)椭圆曲线上双线性对的计算21附录D(资料性附录)数论算法29参考文献34前言GB/TXXXXX《信息安全技术SM9标识密码算法》分为两个部分:——第1部分:总则——第2部分:算法本部分为GB/TXXXXX的第1部分.
本部分依据GB/T1.
1—2009《标准化工作导则第1部分:标准的结构和编写》给出的规则起草.
请注意本文件的某些内容可能涉及专利.
本文件的发布机构不承担识别这些专利的责任.
本部分的附录A为规范性附录,附录B、附录C、附录D为资料性附录.
本部分由国家密码管理局提出.
本部分由全国信息安全标准化技术委员会(SAC/TC260)归口.
本部分起草单位:国家信息安全工程技术研究中心、深圳奥联信息安全技术有限公司、北京国脉信安科技有限公司、武汉大学、上海交通大学、中科院信息工程研究所、北方信息技术研究所.
本部分主要起草人:陈晓、程朝辉、叶顶峰、胡磊、陈建华、路贝可、季庆光、曹珍富、袁文恭、刘平、马宁、袁峰、李增欣、王学进、杨恒亮、张青坡、马艳丽、浦雨三、唐英、孙移盛、安萱.
引言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、(-双线性逆DH和(-Gap-双线性逆DH等难题,当椭圆曲线离散对数问题和扩域离散对数问题的求解难度相当时,可用椭圆曲线对构造出安全性和实现效率兼顾的标识密码.

本部分描述必要的数学基础知识与相关密码技术,以帮助实现本标准其它各部分所规定的密码机制;同时,在附录A中给出了本标准定义的公开参数.
信息安全技术SM9标识密码算法第1部分:总则范围本部分规定了必要的数学基础知识与相关密码技术,以帮助实现本标准其它各部分所规定的密码机制.
本部分规定使用Fp(素数p>2191)上椭圆曲线.
本部分适用于商用密码算法中SM9标识密码的实现、应用和检测.
规范性引用文件下列文件对于本文件的应用是必不可少的.
凡是注日期的引用文件,仅所注日期的版本适用于本文件.
凡是不注日期的引用文件,其最新版本(包括所有的修改单)适用于本文件.
GB/T32905信息安全技术SM3密码杂凑算法GB/T32907信息安全技术SM4分组密码算法术语和定义下列术语和定义适用于本文件.
标识identity可唯一确定一个实体身份的信息.
标识应由实体无法否认的信息组成,如实体的可识别名称、电子邮箱、身份证号、电话号码等.
主密钥masterkey系统的根密钥,包括主私钥和主公钥,其中主公钥公开,主私钥由KGC秘密保存.
KGC用主私钥和用户的标识生成用户的私钥.
在标识密码中,主私钥一般由KGC通过随机数发生器产生,主公钥由主私钥结合系统参数产生.

本部分中,签名系统的主密钥与加密系统的主密钥不同.
数字签名算法属于签名系统,其主密钥为签名主密钥,密钥交换协议、密钥封装机制和公钥加密算法属于加密系统,其主密钥为加密主密钥.
密钥生成中心keygenerationcenter;KGC在SM9标识密码中,负责选择系统参数、生成主密钥并产生用户私钥的可信机构.
符号和缩略语下列符号和缩略语适用于本部分.
cf:椭圆曲线阶相对于N的余因子.
cid:用一个字节表示的曲线识别符,用以区分所用曲线的类型.
DLP:有限域上离散对数问题.
deg(f):多项式f(x)的次数.
d1、d2:k的两个因子.
E:定义在有限域上的椭圆曲线.
ECDLP:椭圆曲线离散对数问题.
E(Fq):有限域Fq上椭圆曲线E的所有有理点(包括无穷远点O)组成的集合.
E(Fq)[r]:E(Fq)上r-扭点的集合(即曲线E(Fq)上的r阶扭子群).
e:从G1*G2到GT的双线性对.
eid:用一个字节表示的双线性对e的识别符,用以区分所用双线性对的类型.
Fp:包含p个元素的素域.
Fq:包含q个元素的有限域.
Fq*:由Fq中所有非零元构成的乘法群.
Fqm:有限域Fq的m次扩域.
GT:阶为素数N的乘法循环群.
G1:阶为素数N的加法循环群.
G2:阶为素数N的加法循环群.
gcd(x,y):x和y的最大公因子.
k:曲线E(Fq)相对于N的嵌入次数,其中N是#E(Fq)的素因子.
m:有限域Fqm关于Fq的扩张次数.
modf(x):模多项式f(x)的运算.
modn:模n运算.
例如,23mod7=2.
N:循环群G1、G2和GT的阶,为大于2191的素数.
O:椭圆曲线上的一个特殊点,称为无穷远点或零点,是椭圆曲线加法群的单位元.
P:P=(xP,yP)是椭圆曲线上除O之外的一个点,其坐标xP,yP满足椭圆曲线方程.
P1:G1的生成元.
P2:G2的生成元.
P+Q:椭圆曲线E上两个点P与Q的和.
p:大于2191的素数.
q:有限域Fq中元素的数目.
xP:点P的x坐标.
x||y:x与y的拼接,其中x和y是比特串或字节串.
x(y(modq):x与y模q同余.
亦即,xmodq=ymodq.
yP:点P的y坐标.
#E(K):E(K)上点的数目,称为椭圆曲线群E(K)的阶,其中K为有限域(包括Fq和Fqk).
:由椭圆曲线上点P生成的循环群.
[u]P:椭圆曲线上点的u倍点.
[x,y]:不小于x且不大于y的整数的集合.
:顶函数,不小于x的最小整数.
例如,.
:底函数,不大于x的最大整数.
例如,.
(:扭曲线参数.
(:G2到G1的同态映射,满足P1=((P2).
:长度相等的两个比特串按比特的模2加运算.
有限域和椭圆曲线有限域概述域由一个非空集合F和两种运算共同组成,这两种运算分别为加法(用"+"表示)和乘法(用""表示),并且满足下列算术特性:a)(F,+)对于加法运算构成加法交换群,单位元用0表示.
b)(F\{0},)对于乘法运算构成乘法交换群,单位元用1表示.
c)分配律成立:对于所有的a,b,c(F,都有(a+b)c=ac+bc.
若集合F是有限集合,则称域为有限域.
有限域的元素个数称为有限域的阶.
素域Fp阶为素数的有限域是素域.
设p是一个素数,则整数模p的全体余数的集合{0,1,2,.
.
.
,p-1}关于模p的加法和乘法构成一个p阶素域,用符号Fp表示.
Fp具有如下性质:加法单位元是0;乘法单位元是1;域元素的加法是整数的模p加法,即若a,bFp,则a+b=(a+b)modp;域元素的乘法是整数的模p乘法,即若a,bFp,则ab=(ab)modp.
有限域Fq的m次扩域Fqm设q是一个素数或素数方幂,f(x)是多项式环Fq[x]上的一个m(m>1)次不可约多项式(称为约化多项式或域多项式),商环Fq[x]/(f(x))是含qm个元素的有限域(记为Fqm),称Fqm是有限域Fq的扩域,域Fq为域Fqm的子域,m为扩张次数.
Fqm可以看成Fq上的m维向量空间.
Fqm的每一个元可以唯一地写成a0(0+a1(1+…+am-1(m-1的形式,其中ai∈Fq,而(0,(1,,(m-1是向量空间Fqm在Fq上的一组基.
Fqm中的元素可以用多项式基或正规基表示.
在本部分中,如果不作特别说明,Fqm中元素均采用多项式基表示.
不可约多项式f(x)可取为首一的多项式f(x)=xm+fm-1xm-1+…+f2x2+f1x+f0(其中fi(Fq,i=0,1,.
.
.
,m1),Fqm中的元素由多项式环Fq[x]中所有次数低于m的多项式构成.
多项式集合{xm-1,xm-2,.
.
.
,x,1}是Fqm在Fq上的一组基,称为多项式基.
域Fqm上的任意一个元素a(x)=am-1xm-1+am-2xm-2+…+a1x+a0在Fq上的系数恰好构成了一个m维向量,用a=(am-1,am-2,.
.
.
,a1,a0)表示,其中分量ai∈Fq,i=0,1,.
.
.
,m1.
Fqm具有如下性质:零元0用m维向量(0,.
.
.
,0,0)表示;乘法单位元1用m维向量(0,.
.
.
,0,1)表示;两个域元素的加法为向量加法,各个分量用域Fq的加法;域元素a和b的乘法定义如下:设a和b对应的Fq上多项式为a(x)和b(x),则ab定义为多项式(a(x)b(x))modf(x)对应的向量.
逆元:设a对应的Fq上多项式为a(x),a的逆元a1对应的Fq上多项式为a-1(x),那么有a(x)a-1(x)≡1modf(x).
关于有限域的扩域Fqm更多细节,参见附录B.
1.
有限域上的椭圆曲线有限域Fqm(m≥1)上的椭圆曲线是由点组成的集合.
在仿射坐标系下,椭圆曲线上点(非无穷远点)用满足一定方程的两个域元素xP和yP表示,xP,yP分别称为点的x坐标和y坐标,并记P=(xP,yP).
本部分描述特征为大素数p的域上的曲线.
本部分如果不作特别说明,椭圆曲线上的点均采用仿射坐标表示.
定义在Fpm上的椭圆曲线方程为:y2=x3+ax+b,a,b(Fpm,且4a3+27b2(0.
1)椭圆曲线E(Fpm)定义为:E(Fpm)={(x,y)|x,y(Fpm,且满足公式(1)}∪{O},其中O是无穷远点.
椭圆曲线E(Fpm)上的点的数目用#E(Fpm)表示,称为椭圆曲线E(Fpm)的阶.
本标准规定素数p>2191.
设E和E'是定义在Fq上的椭圆曲线,如果存在一个同构映射φd:E'(Fqd)→E(Fqd),其中d是使映射存在的最小整数,则称E'为E的d次扭曲线.
当时,d的取值有三种情况:若a=0,b(0,那么d=6,E':y2=x3+(b,;若b=0,a(0,那么d=4,E':y2=x3+(ax,;若a(0,b(0,那么d=2,E':y2=x3+(2ax+(3b,.
椭圆曲线群椭圆曲线E(Fpm)(m≥1)上的点按照下面的加法运算规则,构成一个交换群:O+O=O;(P=(x,y)(E(Fpm)\{O},P+O=O+P=P;(P=(x,y)(E(Fpm)\{O},P的逆元素P=(x,y),P+(P)=O;两个非互逆的不同点相加的规则:设P1=(x1,y1)(E(Fpm)\{O},P2=(x2,y2)(E(Fpm)\{O},且x1(x2,设P3=(x3,y3)=P1+P2,则其中;倍点规则:设P1=(x1,y1)(E(Fpm)\{O},且y1≠0,P3=(x3,y3)=P1+P1,则其中.
椭圆曲线多倍点运算椭圆曲线上同一个点的重复相加称为该点的多倍点运算.
设u是一个正整数,P是椭圆曲线上的点,其u倍点.
多倍点运算可以扩展到0倍点运算和负数倍点运算:[0]P=O,[u]P=[u](P).
多倍点运算可以通过一些技巧有效地实现,参见附录B.
2.
椭圆曲线子群上点的验证输入:定义Fqm上(q为奇素数,m(1)椭圆曲线方程的参数a、b,椭圆曲线E(Fqm)上子群G的阶N,Fqm上的一对元素(x,y).
输出:若(x,y)是群G中的元素,则输出"有效";否则输出"无效".
在Fqm上验证(x,y)是否满足椭圆曲线方程y2=x3+ax+b;令Q=(x,y),验证[N]Q=O;若以上任何一项验证失败,则输出"无效";否则,输出"有效".
离散对数问题有限域上离散对数问题(DLP)有限域Fqm(q为奇素数,m≥1)的全体非零元素构成一个乘法循环群,记为Fqm*.
Fqm*中存在元素g,使得Fqm*={gi|0iqm2},称g为生成元.
Fqm*中元素a的阶是满足at=1的最小正整数t.
群Fqm*的阶为qm1,因此t|qm1.
设乘法循环群Fqm*的生成元为g,y(Fqm*,有限域上离散对数问题是指确定整数x([0,qm-2],使得y=gx在Fqm*上成立.
椭圆曲线离散对数问题(ECDLP)已知椭圆曲线E(Fqm)(m≥1),阶为n的点P(E(Fqm)及Q(,椭圆曲线离散对数问题是指确定整数l([0,n-1],使得Q=[l]P成立.
双线性对及安全曲线双线性对设(G1,+)、(G2,+)和(GT,·)是三个循环群,G1、G2和GT的阶均为素数N,P1是G1的生成元,P2是G2的生成元,存在G2到G1的同态映射(使得((P2)=P1;双线性对e是G1*G2→GT的映射,满足如下条件:双线性性:对任意的P(G1,Q(G2,a,b(ZN,有e([a]P,[b]Q)=e(P,Q)ab;非退化性:e(P1,P2)(1GT;可计算性:对任意的P(G1,Q(G2,存在有效的算法计算e(P,Q).
本部分所用的双线性对定义在椭圆曲线群上,主要有Weil对、Tate对、Ate对、R-ate对等,相关描述参见附录C.
安全性双线性对的安全性主要建立在以下几个问题的难解性基础之上:问题1(双线性逆DH(BIDH))对a,b([1,N1],给定([a]P1,[b]P2),计算e(P1,P2)b/a是困难的.
问题2(判定性双线性逆DH(DBIDH))对a,b,r([1,N1],区分(P1,P2,[a]P1,[b]P2,e(P1,P2)b/a)和(P1,P2,[a]P1,[b]P2,e(P1,P2)r)是困难的.
问题3((-双线性逆DH((-BDHI))对正整数(和x([1,N1],给定(P1,[x]P1,P2,[x]P2,[x2]P2,.
.
.
,[x(]P2),计算e(P1,P2)1/x是困难的.
问题4((-Gap-双线性逆DH((-Gap-BDHI))对正整数(和x([1,N1],给定(P1,[x]P1,P2,[x]P2,[x2]P2,…,[x(]P2)和DBIDH确定算法,计算e(P1,P2)1/x是困难的.
上述问题的难解性是SM9标识密码的安全性的重要基础,这些问题的难解性都意味着G1、G2和GT上的离散对数问题难解,选取的椭圆曲线应首先使得离散对数问题难解.
嵌入次数及安全曲线设G是椭圆曲线E(Fq)的N阶子群,使N|qk1成立的最小正整数k称为子群G相对于N的嵌入次数,也称为曲线E(Fq)相对于N的嵌入次数.
设G1是E(Fqd1)(d1整除k)的N阶子群,G2是E(Fqd2)(d2整除k)的N阶子群,则椭圆曲线双线性对的值域GT是Fqk*的子群,因此椭圆曲线双线性对可将椭圆曲线离散对数问题转化为有限域Fqk*上离散对数问题.
嵌入次数越大安全性越高,但双线性对的计算越困难,因而需要采用嵌入次数适中且达到安全性标准的椭圆曲线.
本部分规定qk21536.
本部分规定选用如下的曲线:基域q为大于2191的素数、嵌入次数k=2i3j的常曲线,其中i0,j(0;基域q为大于2768的素数、嵌入次数k=2的超奇异曲线;对小于2360的N,建议:N1含有大于2190的素因子;N1含有大于2120的素因子.
数据类型及其转换数据类型本部分规定的数据类型包括比特串、字节串、域元素、椭圆曲线上的点和整数.
比特串:有序的0和1的序列.
字节串:有序的字节序列,其中8比特为1个字节,最左边的比特为最高位.
域元素:有限域Fqm(m≥1)中的元素.
椭圆曲线上的点:椭圆曲线E(Fqm)(m(1)上的点P或者是无穷远点O,或者是一对域元素(xP,yP),其中域元素xP和yP满足椭圆曲线方程.
点的字节串表示有多种形式,用一个字节PC加以标识.
无穷远点O的字节串表示是单一的零字节PC=00.
非无穷远点P=(xP,yP)有如下三种字节串表示形式:压缩表示形式,PC=02或03;未压缩表示形式,PC=04;混合表示形式,PC=06或07.
混合表示形式既包含压缩表示形式又包含未压缩表示形式.
在实现中,它允许转换到压缩表示形式或者未压缩表示形式.
对于椭圆曲线上点的压缩表示形式和混合表示形式,本部分定为可选形式.
椭圆曲线上点的压缩表示形式参见附录B.
4.

数据类型转换数据类型转换关系图1表示了各种数据类型之间的转换关系,线上的标志是相应数据转换方法所在的条.
数据类型和转换约定整数到字节串的转换输入:非负整数x,以及字节串的目标长度l(其中l满足28l>x).
输出:长度为l的字节串M.
设Ml-1,Ml-2,(,M0是M的从最左边到最右边的字节;M的字节满足:.
字节串到整数的转换输入:长度为l的字节串M.
输出:整数x.
设Ml-1,Ml-2,(,M0是M的从最左边到最右边的字节;将M转换为整数x:.
比特串到字节串的转换输入:长度为n的比特串s.
输出:长度为l的字节串M,其中l=(n/8(.
设sn-1,sn-2,(,s0是s从最左边到最右边的比特;设Ml-1,Ml-2,(,M0是M从最左边到最右边的字节,则Mi=s8i+7s8i+6…s8i+1s8i,其中0≤i1,则(=(am-1,am-2,(,a1,a0)(q=p),其中ai∈Fq,i=0,1,(,m-1;1)置r=(log2q/8(;2)对i从m-1到0执行:按7.
2.
2的细节把ai(q=p)转换成长度为r的字节串si;3)S=sm-1||sm-2||…||s0.
字节串到域元素的转换情形1:转换为基域中元素输入:域Fq,q=p,长度为l的字节串S,l=(log2q/8(.
输出:Fq中的元素α.
若qp,则按7.
2.
3的细节将S转换为整数α,若α[0,q-1],则报错;情形2:转换为扩域中元素输入:域Fqm(m≥2),qp,长度为l的字节串S,其中l=(log2q/8((m.
输出:Fqm中的元素α.
a)将字节串S平均分成m段,每段长度为l/m,记作S=(Sm-1,Sm-2,(,S1,S0);b)对i从m1到0执行:按7.
2.
3的细节将Si转换为整数ai,若ai[0,q1],则报错;c)若q=p,输出(=(am-1,am-2,(,a1,a0).
点到字节串的转换点到字节串的转换分为两种情形:一种是在计算过程中,将椭圆曲线点转换为字节串后才能作为某个函数(如杂凑函数)的输入,这种情况下只需直接将点转换为字节串;一种是在传输或存储椭圆曲线点时,为了减少传输的量或存储空间,可采用点的压缩或混合压缩表示形式,这种情况下需要加入一个字节的识别符PC来指示点的表示形式.
下面分两种情况说明详细的转换过程.

情形1:直接转换输入:椭圆曲线E(Fqm)(m≥1)上的点P=(xP,yP),且P≠O.
输出:长度为2l的字节串X1||Y1.
(当m=1时,l=(log2q/8(;当m>1时,l=(log2q/8((m.
)按7.
2.
6中的细节把域元素xP转换成长度为l的字节串X1;按7.
2.
6中的细节把域元素yP转换成长度为l的字节串Y1;输出字节串X1||Y1.
情形2:添加一字节识别符PC的转换输入:椭圆曲线E(Fqm)(m≥1)上的点P=(xP,yP),且P≠O.
输出:字节串PO.
若选用未压缩表示形式或混合表示形式,则输出字节串长度为2l+1;若选用压缩表示形式,则输出字节串长度为l+1.
(当m=1时,l=(log2q/8(;当m>1时,l=(log2q/8((m.
)按7.
2.
6中的细节把域元素xP转换成长度为l的字节串X1;若选用压缩表示形式,则:计算比特;(参见附录B.
4.
)若=0,则令PC=02;若=1,则令PC=03;字节串PO=PC||X1;若选用未压缩表示形式,则:按7.
2.
6的细节把域元素yP转换成长度为l的字节串Y1;令PC=04;字节串PO=PC||X1||Y1;若选用混合表示形式,则:按7.
2.
6的细节把域元素yP转换成长度为l的字节串Y1;计算比特;(参见附录B.
4.
)若=0,则令PC=06;若=1,则令PC=07;字节串PO=PC||X1||Y1.
字节串到点的转换字节串到点的转换是7.
2.
8的逆过程.
下面也分两种情况加以说明.
情形1:直接转换输入:定义Fqm(m≥1)上椭圆曲线的域元素a、b,长度为2l的字节串X1||Y1,X1、Y1的长度均为l(当m=1时,l=(log2q/8(;当m>1时,l=(log2q/8((m).
输出:椭圆曲线上的点P=(xP,yP),且P≠O.
按7.
2.
7的细节把字节串X1转换成域元素xP;按7.
2.
7的细节把字节串Y1转换成域元素yP.
情形2:包含一字节识别符PC的字节串的转换输入:定义Fqm(m≥1)上椭圆曲线的域元素a、b,字节串PO.
若选用未压缩表示形式或混合表示形式,则字节串PO长度为2l+1;若选用压缩表示形式,则字节串PO长度为l+1(当m=1时,llog2q/8(;当m>1时,l=(log2q/8((m).
输出:椭圆曲线上的点P=(xP,yP),且P≠O.
若选用压缩表示形式,则PO=PC||X1;若选用未压缩表示形式或混合表示形式,则PO=PC||X1||Y1,其中PC是单一字节,X1和Y1都是长度为l的字节串;按7.
2.
7的细节把字节串X1转换成域元素xP;若选用压缩表示形式,则:检验PC=02或者是PC=03,若不是这种情形,则报错;若PC=02,则令=0;若PC=03,则令=1;将转换为椭圆曲线上的一个点;(参见附录B.
4.
)若选用未压缩表示形式,则:检验PC=04,若不是这种情形,则报错;按7.
2.
7的细节把字节串Y1转换成域元素yP;若选用混合表示形式,则:检验PC=06或者PC=07,若不是这种情形,则报错;执行步骤e.
2.
1)或者e.
2.
2):按7.
2.
7的细节把字节串Y1转换成域元素yP;若PC=06,则令=0,否则令=1;将转换为椭圆曲线上的一个点(xP,yP);(参见附录B.
4.
)验证(xP,yP)是否满足曲线方程,若不满足,则报错;P=(xP,yP).
系统参数及其验证系统参数系统参数包括:曲线的识别符cid,用一个字节表示:0x10表示Fq(素数q>3)上常曲线,0x11表示Fq上超奇异曲线,0x12表示Fq上常曲线及其扭曲线;椭圆曲线基域Fq的参数:基域参数为大于3的素数q;Fq中的两个元素a和b,它们定义椭圆曲线E的方程:y2=x3+ax+b;扭曲线参数((若cid的低4位为2);余因子cf和素数N,其中cf(N=#E(Fq),N>2191且N不整除cf,如果N小于2360,建议N1含有大于2190的素因子,N1含有大于2120的素因子;曲线E(Fq)相对于N的嵌入次数(N阶循环群(GT,·)(Fqk*),规定qk>21536;N阶循环群(G1,+)的生成元P1=(xP1,yP1),P1≠O;N阶循环群(G2,+)的生成元P2=(xP2,yP2),P2≠O;双线性对e:G1*G2→GT,用一个字节的识别符eid表示:0x01表示Tate对,0x02表示Weil对,0x03表示Ate对,0x04表示R-ate对;(选项)参数d1,d2,其中d1,d2整除k;(选项)G2到G1的同态映射(,使得P1=((P2).
(选项)BN曲线的基域特征q,曲线阶r,Frobenius映射的迹tr可通过参数t来确定,t至少达到63比特.
本规范规定的具体参数见附录A.
系统参数的验证下面的条件应由系统参数的生成者加以验证.
这些条件也能由系统参数的用户验证.
输入:系统参数集合.
输出:若所有参数有效,则输出"有效";否则输出"无效".
验证q是大于3的素数(参见附录D.
1.
5);验证a,b是区间[0,q-1]中的整数;验证在Fq上4a3+27b2(0;若cid的低4位为2,验证(是非平方元(参见附录D.
1.
4.
3.
1);验证N为大于2191的素数且N不整除cf,如果N小于2360,验证N1含有大于2190的素因子,N1含有大于2120的素因子;验证|q+1cf(N|21536,且k为使N|(qm1)成立的最小正整数m;验证(xP1,yP1)是群G1中的元素;验证(xP2,yP2)是群G2中的元素;验证e(P1,P2)(Fqk*\{1},且e(P1,P2)N=1;(选项)验证d1,d2整除k;(选项)验证P1=((P2);(选项)验证t至少达到63比特.
若以上任何一项验证失败,则输出"无效";否则,输出"有效".
(规范性附录)参数定义系统参数本部分使用256位的BN曲线.
椭圆曲线方程:y2=x3+b.
曲线参数:参数t:600000000058F98A迹tr(t)=6t2+1:D8000000019062ED0000B98B0CB27659基域特征q(t)=36t4+36t3+24t2+6t+1:B640000002A3A6F1D603AB4FF58EC74521F2934B1A7AEEDBE56F9B27E351457D方程参数b:05群的阶N(t)=36t4+36t3+18t2+6t+1:B640000002A3A6F1D603AB4FF58EC74449F2934B18EA8BEEE56EE19CD69ECF25余因子cf:1嵌入次数k:12扭曲线的参数:k的因子d1=1,d2=2曲线识别符cid:0x12群G1的生成元P1=(xP1,yP1):坐标xP1:93DE051D62BF718FF5ED0704487D01D6E1E4086909DC3280E8C4E4817C66DDDD坐标yP1:21FE8DDA4F21E607631065125C395BBC1C1C00CBFA6024350C464CD70A3EA616群G2的生成元P2=(xP2,yP2):坐标xP2:(85AEF3D078640C98597B6027B441A01FF1DD2C190F5E93C454806C11D8806141,3722755292130B08D2AAB97FD34EC120EE265948D19C17ABF9B7213BAF82D65B)坐标yP2:(17509B092E845C1266BA0D262CBEE6ED0736A96FA347C8BD856DC76B84EBEB96,A7CF28D519BE3DA65F3170153D278FF247EFBA98A71A08116215BBA5C999A7C7)双线性对的识别符eid:0x04扩域元素的表示Fq12的1-2-4-12塔式扩张:Fq2[u]=Fq[u]/(u2(2;Fq4[v]=Fq2[v]/(v2ξ),ξ=u;Fq12[w]=Fq4[w]/(w3v),v2=ξ;其中,第(1)进行二次扩张的约化多项式为:x2(,(=2;第(2)进行二次扩张的约化多项式为:x2u,u2=(,u=;第(3)进行三次扩张的约化多项式为:x3v,v2=u,v=;u属于Fq2,表示为(1,0),左边是第1维(高维),右边是第0维(低维).
v属于Fq4,表示为(0,1,0,0),其中左边(0,1)是Fq4中元素以Fq2表示的第1维(高维),右边(0,0)是Fq4中元素以Fq2表示的第0维(低维).
Fq12中元素有三种表示方法:Fq12中元素A用Fq4中元素表示:A=aw2+bw+c=(a,b,c),a,b,c用Fq2中元素表示:a=a1v+a0=(a1,a0);b=b1v+b0=(b1,b0);c=c1v+c0=(c1,c0);其中a1,a0,b1,b0,c1,c0(Fq2.
Fq12中元素A用Fq2中的元素表示:A=(a1,a0,b1,b0,c1,c0),a1,a0,b1,b0,c1,c0用基域Fq中的元素表示:a0=a0,1u+a0,0=(a0,1,a0,0);a1=a1,1u+a1,0=(a1,1,a1,0);b0=b0,1u+b0,0=(b0,1,b0,0);b1=b1,1u+b1,0=(b1,1,b1,0);c0=c0,1u+c0,0=(c0,1,c0,0);c1=c1,1u+c1,0=(c1,1,c1,0);其中a0,1,a0,0,a1,1,a1,0,b0,1,b0,0,b1,1,b1,0,c0,1,c0,0,c1,1,c1,0(Fq.
Fq12中元素A用基域Fq中的元素表示:A=(a0,1,a0,0,a1,1,a1,0,b0,1,b0,0,b1,1,b1,0,c0,1,c0,0,c1,1,c1,0),其中a0,1,a0,0,a1,1,a1,0,b0,1,b0,0,b1,1,b1,0,c0,1,c0,0,c1,1,c1,0(Fq.
Fq2中单位元的表示为(0,1);Fq4中单位元的表示为(0,0,0,1);Fq12中单位元的表示为(0,0,0,0,0,0,0,0,0,0,0,1).
各种扩域中分量序为:左边是高维,右边是低维.
示例数据中,扩域中的元素均用基域中的元素表示.
(资料性附录)关于椭圆曲线的背景知识有限域素域Fp设p是一个素数,整数模p的全体余数的集合{0,1,2,.
.
.
,p-1}关于模p的加法和乘法构成一个p阶素域,用符号Fp表示.
加法单位元是0,乘法单位元是1,Fp的元素满足如下运算法则:——加法:设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*是循环群,所以在Fp中至少存在一个元素g,使得Fp中任一非零元都可以由g的一个方幂表示,称g为Fp*的生成元(或本原元),即Fp*={gi|0ip-2}.
设a=gi(Fp*,其中0ip-2,则a的乘法逆元为:a-1=gp-1-i素域F19,F19={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,则7·8=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.
有限域Fqm设q是一个素数或素数方幂,f(x)是多项式环Fq[x]上的一个m(m>1)次不可约多项式(称为约化多项式或域多项式),商环Fq[x]/(f(x))是含qm个元素的有限域(记为Fqm),称Fqm是有限域Fq的扩域,域Fq为域Fqm的子域,m为扩张次数.
Fqm可以看成Fq上的m维向量空间,也就是说,在Fqm中存在m个元素α0,α1,(,αm-1,使得(a(Fqm,a可以唯一表示为:a=am-1(m-1+···+a1(1+a0(0,其中ai∈Fq,称{(m-1,(,(1,(0}为Fqm在Fq上的一组基.
给定这样一组基,就可以由向量(am-1,am-2,(,a1,a0)来表示域元素a.
Fqm在Fq上的基有多种选择:多项式基和正规基等.
不可约多项式f(x)可取为首一的多项式f(x)=xm+fm-1xm-1+···+f2x2+f1x+f0(其中fi(Fq,i=0,1,…,m1),Fqm中的元素由多项式环Fq[x]中所有次数低于m的多项式构成,即Fqm={am-1xm-1+am-2xm-2+···+a1x+a0|ai∈Fq,i=0,1,(,m-1}.
多项式集合{xm-1,xm-2,…,x,1}是Fqm作为向量空间在Fq上的一组基,称为多项式基.
当m含有因子d(11.
预计算P1=P,P2=[2]P;i从1到2r-1-1计算P2i+1=P2i-1+P2;置j=l-1,Q=O.
主循环d)当j≥0执行:若uj=0,则Q=[2]Q,j=j-1;否则令t是使j–t+1r且ut=1的最小整数;;Q=[2j-t+1]Q+Phj;置j=t-1;e)输出Q.
离散对数问题求解有限域上离散对数问题的方法有限域Fq的全体非零元素构成一个乘法循环群,记为Fq*.
Fq*中存在一个元素g,g称为生成元,使得Fq*={gi|0iq2}.
aFq的阶是满足at=1的最小正整数t.
循环群Fq*的阶为q1,因此t|q1.
设乘法循环群Fq*的生成元为g,y(Fq*,有限域上离散对数问题是指确定整数x([0,q2],使得y=gxmodq成立.
有限域上离散对数问题现有攻击方法有:Pohlig-Hellman方法:设l是q1的最大素因子,则时间复杂度为O(l1/2);BSGS方法:时间复杂度与空间复杂度均为(πq/2)1/2;Pollard方法:时间复杂度为(πq/2)1/2;并行Pollard方法:设s为并行处理器个数,时间复杂度为(πq/2)1/2/s;线性筛法(对素域Fq):时间复杂度为;Gauss整数法(对素域Fq):时间复杂度为;剩余列举筛法(对素域Fq):时间复杂度为;数域筛法(对素域Fq):时间复杂度为;函数域筛法(对小特征域):时间复杂度为和拟多项式时间.
从以上列举的求解离散对数问题的方法及其时间复杂度可知:对于一般的大特征域上的离散对数问题,存在亚指数级计算复杂度的攻击方法,对小特征域上的离散对数问题,目前已经有拟多项式时间的攻击方法.

求解椭圆曲线离散对数问题的方法已知椭圆曲线E(Fq),阶为n的点P(E(Fq)及Q(,椭圆曲线离散对数问题是指确定整数u([0,n-1],使得Q=[u]P成立.
ECDLP现有攻击方法有:Pohlig-Hellman方法:设l是n的最大素因子,则时间复杂度为O(l1/2);BSGS方法:时间复杂度与空间复杂度均为(πn/2)1/2;Pollard方法:时间复杂度为(πn/2)1/2;并行Pollard方法:设r为并行处理器个数,时间复杂度为(πn/2)1/2/r;MOV-方法:把超奇异椭圆曲线及具有相似性质的曲线的ECDLP降到Fq的小扩域上的离散对数问题(亚指数级计算复杂度算法);Anomalous方法:对Anomalous曲线(#E(Fq)=q的曲线)的有效攻击方法(多项式级计算复杂度算法);GHS-方法:利用Weil下降技术求解扩张次数为合数的二元扩域上椭圆曲线离散对数问题,将ECDLP转化为超椭圆曲线离散对数问题,而求解高亏格的超椭圆曲线离散对数存在亚指数级计算复杂度算法.

DGS-点分解方法:对低次扩域上的椭圆曲线离散对数利用的指标计算方法,在某些特殊情况下,其求解复杂度低于平方根时间复杂度.
从上述对椭圆曲线离散对数问题解法的描述与分析可知:对于一般曲线的离散对数问题,目前的求解方法都为指数级计算复杂度,未发现亚指数级计算复杂度的一般攻击方法;而对于某些特殊曲线的离散对数问题,存在多项式级或者亚指数级计算复杂度算法.

点的压缩概述对于椭圆曲线E(Fq)上的任意非无穷远点P=(xP,yP),该点能由坐标xP及由xP和yP导出的一个特定比特简洁地表示,称为点的压缩表示.
Fp上椭圆曲线点的压缩与解压缩方法设P=(xP,yP)是定义在Fp上椭圆曲线E:y2=x3+ax+b上的一个点,为yP的最右边的一个比特,则点P可由xP和比特表示.
由xP和恢复yP的方法如下:在Fp上计算域元素α=xP3+axP+b;计算α在Fp上的平方根β(参见附录D.
1.
4),若输出是"不存在平方根",则报错;若β的最右边比特等于,则置yP=β;否则置yP=pβ.
Fqm(q为奇素数,m(2)上椭圆曲线点的压缩与解压缩方法设P=(xP,yP)是定义在Fqm上椭圆曲线E:y2=x3+ax+b上的一个点,则yP可表示为(ym-1,ym-2,…,y1,y0),为y0的最右边的一个比特,则点P可由xP和比特表示.
由xP和恢复yP的方法如下:在Fqm上计算域元素(=xP3+axP+b;计算(在Fqm上的平方根β(参见附录D.
1.
4),若输出是"不存在平方根",则报错;若β的表示(βm-1,βm-2,…,β1,β0)中β0的最右边比特等于,则置yP=β;否则置yP=(βm-1,βm-2,…,β1,β0),其中βi=(q-βi)Fq,i=0,1,…,m-1.
(资料性附录)椭圆曲线上双线性对的计算概述设有限域Fq上椭圆曲线为E(Fq),若#E(Fq)=cf(r,r是素数且gcd(r,q)=1,cf为余因子,则使r|qk-1的最小正整数k称为椭圆曲线相对于r的嵌入次数.
若G是E(Fq)的r阶子群,则G的嵌入次数也是k.
设是有限域Fq的代数闭包,E[r]表示中所有r阶点的集合.
Miller算法设Fqk上椭圆曲线E(Fqk)的方程为y2=x3+ax+b,定义过E(Fqk)上点U和V的直线为gU,V:E(Fqk)→Fqk,若过U,V两点的直线方程为(x+(y+τ=0,则令函数gU,V(Q)=(xQ+(yQ+τ,其中Q=(xQ,yQ).
当U=V时,gU,V定义为过点U的切线;若U和V中有一个点为无穷远点O,gU,V就是过另一个点且垂直于x轴的直线.
一般用gU作为gU,U的简写.
记U=(xU,yU),V=(xV,yV),Q=(xQ,yQ),λ1=(3xV2+a)/(2yV),λ2=(yU–yV)/(xU–xV),则有以下性质:gU,V(O)=gU,O(Q)=gO,V(Q)=1;gV,V(Q)=λ1(xQ–xV)–yQ+yV,Q(O;gU,V(Q)=λ2(xQ–xV)–yQ+yV,Q(O,U(±V;gV,V(Q)=xQ–xV,Q≠O.
Miller算法是计算双线性对的有效算法.
Miller算法输入:曲线E,E上两点P和Q,整数c.
输出:fP,c(Q).
a)设c的二进制表示是cj…c1c0,其最高位cj为1;b)置f=1,V=P;c)对i从j1降至0,执行:c.
1)计算;c.
2)若ci=1,令.
d)输出f.
一般,称fP,c(Q)为Miller函数.
Weil对的计算设E是Fq上的椭圆曲线,r是与q互素的正整数,设μr是r次单位根集合,k是相对于r的嵌入次数,即r|qk1,则(r(Fqk.
令G1=E[r],G2=E[r],GT=μr,则Weil对是从G1*G2到GT的双线性映射,记为er.
设P(G1,Q(G2,若P=O或Q=O,则er(P,Q)=1;如果P(O且Q(O,随机选取非无穷远点T(G1,U(G2,使得P+T和T均不等于U或U+Q,则Weil对为:.
fP+T,r(Q+U),fT,r(Q+U),fP+T,r(U),fT,r(U),fQ+U,r(P+T),fQ+U,r(T),fU,r(P+T)和fU,r(T)均可用Miller算法计算.
在计算过程中,若出现分母为0的情况,则更换点T或U重新计算.

Tate对的计算设E是Fq上的椭圆曲线,r是与q互素的正整数,k是相对于r的嵌入次数.
设Q是E(Fqk)[r]上的r阶点,由Q生成的循环群记为.
(Fqk)r为Fqk中每一个元素的r次幂构成的集合,(Fqk)r是Fqk的子群,Fqk关于(Fqk)r的商群记为Fqk/(Fqk)r.

令G1=E(Fq)[r],G2=,GT=Fqk/(Fqk)r,则Tate对是从G1*G2到GT的双线性映射,记为tr.
设P(G1,Q(G2,若P=O或Q=O,则tr=1;若P(O且Q(O,随机选择非无穷远点U(E(Fqk),使得P(U,P(Q+U,U(Q,则Tate对为:.
fP,r(Q+U)和fP,,r(U)可通过Miller算法计算.
在计算过程中,若出现分母为0的情况,则更换点U重新计算.
在实际应用中,一般使用约化Tate对:约化Tate对比一般Tate对的计算量减少了一半.
若相对于r的嵌入次数k是偶数时,约化Tate对的计算方法可以进一步优化.
算法1描述的是一般约化Tate对的计算方法,算法2、3、4均指k=2d的情况.