对公银行账号/支付宝 中国标准英文版 技术翻译  数据库收录: 159759 更新: 2020-12-31  
现货的,9秒内发货  

GB/T 32918.1-2016

标准搜索结果: 'GB/T 32918.1-2016'
标准号码内文价格美元第2步交付天数标准名称状态
GB/T 32918.1-2016 英文版 400 购买 3分钟内自动发货[PDF],有增值税发票。 信息安全技术 SM2椭圆曲线公钥密码算法 第1部分:总则 有效

   
基本信息
标准编号 GB/T 32918.1-2016 (GB/T32918.1-2016)
中文名称 信息安全技术 SM2椭圆曲线公钥密码算法 第1部分:总则
英文名称 Information security technology -- Public key cryptographic algorithm SM2 based on elliptic curves -- Part 1: General
行业 国家标准 (推荐)
中标分类 L80
字数估计 46,424
发布日期 2016-08-29
实施日期 2017-03-01
起草单位 北京华大信安科技有限公司、中国人民解放军信息工程大学、中国科学院数据与通信保护研究教育中心
归口单位 全国信息安全标准化技术委员会(SAC/TC 260)
标准依据 National Standard Announcement 2016 No.14
提出机构 国家密码管理局
发布机构 中华人民共和国国家质量监督检验检疫总局、中国国家标准化管理委员会
范围 GB/T 32918的本部分规定了SM2椭圆曲线公钥密码算法涉及的必要数学基础知识与相关密码技术,以帮助实现其他各部分所规定的密码机制。本部分适用于基域为素域和二元扩域的椭圆曲线公钥密码算法的设计、开发、使用。

GB/T 32918.1-2016
Information security technology--Public key cryptographic algorithm SM2 based on elliptic curves--Part 1: General
ICS 35.040
L80
中华人民共和国国家标准
信息安全技术
SM2椭圆曲线公钥密码算法
第1部分:总则
2016-08-29发布
2017-03-01实施
中华人民共和国国家质量监督检验检疫总局
中国国家标准化管理委员会发布
目次
前言 Ⅰ
引言 Ⅱ
1 范围 1
2 符号和缩略语 1
3 域和椭圆曲线 2
3.1 有限域 2
3.2 有限域上的椭圆曲线 3
4 数据类型及其转换 5
4.1 数据类型 5
4.2 数据类型转换 5
5 椭圆曲线系统参数及其验证 8
5.1 一般要求 8
5.2 Fp 上椭圆曲线系统参数及其验证 8
5.3 F2m上椭圆曲线系统参数及其验证 9
6 密钥对的生成与公钥的验证 9
6.1 密钥对的生成 9
6.2 公钥的验证 10
附录A(资料性附录) 关于椭圆曲线的背景知识 11
A.1 素域Fp 11
A.2 二元扩域F2m 13
A.3 椭圆曲线多倍点运算 23
A.4 求解椭圆曲线离散对数问题的方法 26
A.5 椭圆曲线上点的压缩 27
附录B(资料性附录) 数论算法 29
B.1 有限域和模运算 29
B.2 有限域上的多项式 33
B.3 椭圆曲线算法 35
附录C(资料性附录) 曲线示例 37
C.1 一般要求 37
C.2 Fp 上椭圆曲线 37
C.3 F2m上椭圆曲线 37
附录D(资料性附录) 椭圆曲线方程参数的拟随机生成及验证 39
D.1 椭圆曲线方程参数的拟随机生成 39
D.2 椭圆曲线方程参数的验证 40
参考文献 41
前言
GB/T 32918《信息安全技术 SM2椭圆曲线公钥密码算法》分为以下5个部分:
---第1部分:总则;
---第2部分:数字签名算法;
---第3部分:密钥交换协议;
---第4部分:公钥加密算法;
---第5部分:参数定义。
本部分为GB/T 32918的第1部分。
本部分按照GB/T 1.1-2009给出的规则起草。
本部分由国家密码管理局提出。
本部分由全国信息安全标准化技术委员会(SAC/TC260)归口。
本部分起草单位:北京华大信安科技有限公司、中国人民解放军信息工程大学、中国科学院数据与
通信保护研究教育中心。
本部分主要起草人:陈建华、祝跃飞、叶顶峰、胡磊、裴定一、彭国华、张亚娟、张振峰。
引 言
N.Koblitz和V.Miler在1985年各自独立地提出将椭圆曲线应用于公钥密码系统。椭圆曲线公
钥密码所基于的曲线性质如下:
---有限域上椭圆曲线在点加运算下构成有限交换群,且其阶与基域规模相近;
---类似于有限域乘法群中的乘幂运算,椭圆曲线多倍点运算构成一个单向函数。
在多倍点运算中,已知多倍点与基点,求解倍数的问题称为椭圆曲线离散对数问题。对于一般椭圆
曲线的离散对数问题,目前只存在指数级计算复杂度的求解方法。与大数分解问题及有限域上离散对
数问题相比,椭圆曲线离散对数问题的求解难度要大得多。因此,在相同安全程度要求下,椭圆曲线密
码较其他公钥密码所需的密钥规模要小得多。
SM2是国家密码管理局组织制定并提出的椭圆曲线密码算法标准。GB/T 32918的主要目标如下:
---GB/T 32918.1定义和描述了SM2椭圆曲线密码算法的相关概念及数学基础知识,并概述了
该部分同其他部分的关系。
---GB/T 32918.2描述了一种基于椭圆曲线的签名算法,即SM2签名算法。
---GB/T 32918.3描述了一种基于椭圆曲线的密钥交换协议,即SM2密钥交换协议。
---GB/T 32918.4描述了一种基于椭圆曲线的公钥加密算法,即SM2加密算法,该算法需使用
GB/T 32905-2016定义的SM3密码杂凑算法。
---GB/T 32918.5给出了SM2算法使用的椭圆曲线参数,以及使用椭圆曲线参数进行SM2运算
的示例结果。
本部分为GB/T 32918的第1部分,描述了必要的数学基础知识与一般技术,以帮助实现其他各部
分所规定的密码机制。
信息安全技术
SM2椭圆曲线公钥密码算法
第1部分:总则
1 范围
GB/T 32918的本部分规定了SM2椭圆曲线公钥密码算法涉及的必要数学基础知识与相关密码
技术,以帮助实现其他各部分所规定的密码机制。
本部分适用于基域为素域和二元扩域的椭圆曲线公钥密码算法的设计、开发、使用。
2 符号和缩略语
下列符号和缩略语适用于本文件。
B MOV阈。正数B,使得求取FqB上的离散对数至少与求取Fq 上的椭圆曲线离
散对数一样困难。
deg(f) 多项式f(x)的次数。
E 有限域上由a和b定义的一条椭圆曲线。
E(Fq) Fq 上椭圆曲线E 的所有有理点(包括无穷远点O)组成的集合。
ECDLP 椭圆曲线离散对数问题。
Fp 包含p个元素的素域。
Fq 包含q个元素的有限域。
Fq* 由Fq中所有非零元构成的乘法群。
F2m 包含2m 个元素的二元扩域。
G 椭圆曲线的一个基点,其阶为素数。
gcd(x,y) x和y的最大公因子。
h 余因子,h=#E(Fq)/n,其中n是基点G 的阶。
LeftRotate() 循环左移运算。
lmax 余因子h的最大素因子的上界。
m 二元扩域F2m关于F2的扩张次数。
modf(x) 模多项式f(x)的运算。若f(x)是二元域上的多项式,则所有系数执行模2
运算。
modn 模n运算。例如,23mod7=2。
n 基点G 的阶[n是#E(Fq)的素因子]。
O 椭圆曲线上的一个特殊点,称为无穷远点或零点,是椭圆曲线加法群的单位元。
P P=(xP,yP)是椭圆曲线上除O 之外的一个点,其坐标xP,yP满足椭圆曲线
方程。
P1+P2 椭圆曲线E 上两个点P1与P2的和。
p 大于3的素数。
q 有限域Fq中元素的数目。
a,b Fq 中的元素,它们定义Fq 上的一条椭圆曲线E。
rmin 基点G 的阶n的下界。
Tr() 迹函数。
xP 点P 的x坐标。
x-1modn 使得x·y≡1(modn)成立的唯一整数y,1≤y≤n-1,gcd(x,n)=1。
x‖y x与y的拼接,其中x和y是比特串或字节串。
x≡y(modn) x与y模n同余。亦即,x modn=ymodn。
yP 点P 的y坐标。
y~P yP的点压缩表示。
Zp 整数模p的剩余类环。
基点G 生成的循环群。
[k]P 椭圆曲线上点P 的k倍点,即:[k]P=P+P++P
,其中k是正整数。
[x,y] 大于或等于x且小于或等于y的整数的集合。
x 顶函数,大于或等于x的最小整数。例如,7 =7,8.3 =9。
x 底函数,小于或等于x的最大整数。例如,7 =7,8.3 =8。
#E(Fq) E(Fq)上点的数目,称为椭圆曲线E(Fq)的阶。
⊕ 长度相等的两个比特串按比特的异或运算。
3 域和椭圆曲线
3.1 有限域
3.1.1 概述
本条给出有限域Fq的描述及其元素的表示,q是一个奇素数或者是2的方幂。当q是奇素数p
时,要求p>2191;当q是2的方幂2m时,要求m>192且为素数。
3.1.2 素域Fp
当q是奇素数p时,素域Fp中的元素用整数0,1,2,,p-1表示。素域特性如下:
a) 加法单位元是整数0;
b) 乘法单位元是整数1;
c) 域元素的加法是整数的模p加法,即若a,b∈Fp,则a+b=(a+b)modp;
d) 域元素的乘法是整数的模p乘法,即若a,b∈Fp,则a·b=(a·b)modp。
3.1.3 二元扩域F2m
当q是2的方幂2m时,二元扩域F2m可以看成F2上的m 维向量空间,其元素可用长度为m 的比特
串表示。
F2m中的元素有多种表示方法,其中最常用的两种方法是多项式基(PB)表示(参见A.2.1.1)和正规
基(NB)表示(参见A.2.1.3)。基的选择原则是使得F2m中的运算效率尽可能高。本部分并不规定基的
选择。下面以多项式基表示为例说明二元扩域F2m。
设F2上m 次不可约多项式f(x)=xm+fm-1xm-1++f2x2+f1x+f0(其中fi∈F2,i=0,1,
,m-1)是二元扩域F2m 的约化多项式。F2m 由F2上所有次数低于m 的多项式构成。多项式集合
{xm-1,xm-2,,x,1}是F2m 在F2上的一组基,称为多项式基。F2m 中的任意一个元素a(x)=
am-1xm-1+am-2xm-2++a1x+a0在F2上的系数恰好构成了长度为m 的比特串,用a=(am-1,
am-2,,a1,a0)表示。多项式域特性如下:
a) 零元0用全0比特串表示;
b) 乘法单位元1用比特串00001表示;
c) 两个域元素的加法为比特串的按比特异或运算;
d) 域元素a和b的乘法定义如下:设a和b对应的F2上多项式为a(x)和b(x),则a·b定义为
多项式(a(x)b(x))modf(x)对应的比特串。
3.2 有限域上的椭圆曲线
有限域Fq上的椭圆曲线是由点组成的集合。在仿射坐标系下,椭圆曲线上点P(非无穷远点)的坐
标表示为P=(xP,yP),其中xP,yP为满足一定方程的域元素,分别称为点P 的x坐标和y坐标。在
本部分中,称Fq为基域。
关于椭圆曲线更多的背景知识,参见附录A中A.1和A.2。
在本部分中,如果不做特别说明,椭圆曲线上的点均采用仿射坐标表示。
3.2.1 Fp 上的椭圆曲线
定义在Fp(p是大于3的素数)上的椭圆曲线方程为:
y2=x3+ax+b,a,b∈Fp,且(4a3+27b2)modp≠0。(1)
椭圆曲线E(Fp)定义为,参见C.2:
E(Fp)={(x,y)|x,y∈Fp,且满足方程(1)}∪{O},其中O 是无穷远点。
椭圆曲线E(Fp)上的点的数目用#E(Fp)表示,称为椭圆曲线E(Fp)的阶。
3.2.2 F2m上的椭圆曲线
定义在F2m上的椭圆曲线方程为:
y2+xy=x3+ax2+b,a,b∈F2m,且b≠0。 (2)
椭圆曲线E(F2m)定义为,参见C.3:
E(F2m)={(x,y)|x,y∈F2m,且满足方程(2)}∪{O},其中O 是无穷远点。
椭圆曲线E(F2m)上的点的数目用#E(F2m)表示,称为椭圆曲线E(F2m)的阶。
3.2.3 椭圆曲线群
3.2.3.1 Fp 上的椭圆曲线群
椭圆曲线E(Fp)上的点按照下面的加法运算规则,构成一个交换群:
a) O+O=O;
b) ∀P=(x,y)∈E(Fp)\{O},P+O=O+P=P;
c) ∀P=(x,y)∈E(Fp)\{O},P 的逆元素-P=(x,-y),P+(-P)=O;
d) 两个非互逆的不同点相加的规则:
设P1=(x1,y1)∈E(Fp)\{O},P2=(x2,y2)∈E(Fp)\{O},且x1≠x2,
设P3=(x3,y3)=P1+P2,则
x3=λ2-x1-x2,
y3=λ(x1-x3)-y1,{
式中:
λ=
y2-y1
x2-x1
e) 倍点规则:
设P1=(x1,y1)∈E(Fp)\{O},且y1≠0,P3=(x3,y3)=P1+P1,
x3=λ2-2x1,
y3=λ(x1-x3)-y1,{
式中:
λ=
3x21+a
2y1
3.2.3.2 F2m上的椭圆曲线群
椭圆曲线E(F2m)上的点按照下面的加法运算规则,构成一个交换群:
a) O+O=O;
b) ∀P=(x,y)∈E(F2m)\{O},P+O=O+P=P;
c) ∀P=(x,y)∈E(F2m)\{O},P 的逆元素-P=(x,x+y),P+(-P)=O;
d) 两个非互逆的不同点相加的规则:
设P1=(x1,y1)∈E(F2m)\{O},P2=(x2,y2)∈E(F2m)\{O},且x1≠x2,
设P3=(x3,y3)=P1+P2,则
x3=λ2+λ+x1+x2+a,
y3=λ(x1+x3)+x3+y1,{
式中:
λ=
y1+y2
x1+x2
e) 倍点规则:
设P1=(x1,y1)∈E(F2m)\{O},且x1≠0,P3=(x3,y3)=P1+P1,则
x3=λ2+λ+a,
y3=x21+(λ+1)x3,{
式中:
λ=x1+
y1
x1
3.2.4 椭圆曲线多倍点运算
椭圆曲线上同一个点的多次加称为该点的多倍点运算。设k是一个正整数,P 是椭圆曲线上的
点,称点P 的k次加为点P 的k倍点运算,记为Q=[k]P=P+P++P
􀮩 􀮫􀮪􀪁􀪁􀪁 􀪁􀪁􀪁
。因为[k]P=[k-1]P+
P,所以k倍点可以递归求得。
多倍点运算的输出有可能是无穷远点O。
多倍点运算也可以通过一些技巧更有效地实现,参见附录A中A.3。
3.2.5 椭圆曲线离散对数问题(ECDLP)
已知椭圆曲线E(Fq)、阶为n的点G∈E(Fq)及Q∈,椭圆曲线离散对数问题是指确定整数
l∈[0,n-1],使得Q=[l]G 成立。
椭圆曲线离散对数问题关系到椭圆曲线密码系统的安全,因此应选择安全的椭圆曲线。关于如何
选择安全椭圆曲线,参见附录A中A.4。
3.2.6 弱椭圆曲线
若某椭圆曲线存在优于n1/2级(n是基点的阶)计算复杂度的攻击方法,则称此曲线为弱椭圆曲线。
在本部分中禁止使用弱椭圆曲线。
Fq上的超奇异曲线[有限域Fq的特征整除q+1-#E(Fq)]和Fp上的异常(Anomalous)曲线
[#E(Fp)=p]都是弱椭圆曲线。
4 数据类型及其转换
4.1 数据类型
在本部分中,数据类型包括比特串、字节串、域元素、椭圆曲线上的点和整数。
比特串:有序的0和1的序列。
字节串:有序的字节序列,其中8比特为1个字节。
域元素:有限域Fq中的元素。
椭圆曲线上的点:椭圆曲线上的点P∈E(Fq),或者是一对域元素(xP,yP),其中域元素xP和yP
满足椭圆曲线方程,或者是无穷远点O。
点的字节串表示有多种形式,用一个字节PC 加以标识。无穷远点O 的字节串表示是单一的零字
节PC=00。非无穷远点P=(xP,yP)有如下三种字节串表示形式:
a) 压缩表示形式,PC=02或03;
b) 未压缩表示形式,PC=04;
c) 混合表示形式,PC=06或07。
注:混合表示形式既包含压缩表示形式又包含未压缩表示形式。在实现中,它允许转换到压缩表示形式或者未压
缩表示形式。
对于椭圆曲线上点的压缩表示形式和混合表示形式,本部分中定为可选形式。椭圆曲线上点的压
缩表示形式参见附录A中A.5。
4.2 数据类型转换
4.2.1 数据类型转换关系
图1提供了各种数据类型之间的转换关系,线上的标志是相应数据转换方法所在的条。
图1 数据类型和转换约定
4.2.2 整数到字节串的转换
输入:非负整数x,以及字节串的目标长度k(其中k满足28k>x)。
输出:长度为k的字节串M。
a) 设Mk-1,Mk-2,,M0是M 的从最左边到最右边的字节;
b) M 的字节满足:
4.2.3 字节串到整数的转换
输入:长度为k的字节串M。
输出:整数x。
a) 设Mk-1,Mk-2,,M0是M 的从最左边到最右边的字节;
b) 将M 转换为整数x:
4.2.4 比特串到字节串的转换
输入:长度为m 的比特串s。
输出:长度为k的字节串M,其中k= m/8 。
a) 设sm-1,sm-2,,s0是s从最左边到最右边的比特;
b) 设Mk-1,Mk-2,,M0是M 从最左边到最右边的字节,则
Mi=s8i+7s8i+6s8i+1s8i,其中0≤i4.2.5 字节串到比特串的转换
输入:长度为k的字节串M。
输出:长度为m 的比特串s,其中m=8k。
a) 设Mk-1,Mk-2,,M0是M 从最左边到最右边的字节;
b) 设sm-1,sm-2,,s0是s从最左边到最右边的比特,则si是Mj右起第i-8j+1比特,其中j=
i/8 。
4.2.6 域元素到字节串的转换
输入:Fq中的元素α。
输出:长度l= t/8 的字节串S,其中t= log2q 。
a) 若q为奇素数,则α必为区间[0,q-1]中的整数,按4.2.2的方法把α转换成长度为l的字节
串S;
b) 若q=2m,则α必为长度为m 的比特串,按4.2.4的方法把α转换成长度为l的字节串S。
4.2.7 字节串到域元素的转换
输入:基域Fq的类型,长度为l= t/8 的字节串S,其中t= log2q 。
输出:Fq中的元素α。
a) 若q是奇素数,则按4.2.3的方法将S转换为整数α,若α∉[0,q-1],则报错;
b) 若q=2m,则按4.2.5的方法将S转换为长度为m 的比特串α。
4.2.8 域元素到整数的转换
输入:域Fq中的元素α。
输出:整数x。
a) 若q为奇素数,则x=α(不需要转换);
b) 若q=2m,则α必为长度为m 的比特串,设sm-1,sm-2,,s0是α的从最左边到最右边的比特,
将α转化为整数x:
4.2.9 点到字节串的转换
输入:椭圆曲线上的点P=(xP,yP),且P≠O。
输出:字节串S。若选用未压缩表示形式或混合表示形式,则输出字节串长度为2l+1;若选用压
缩表示形式,则输出字节串长度为l+1(l= (log2q)/8)。
a) 按4.2.6中的方法把域元素xP转换成长度为l的字节串X1;
b) 若选用压缩表示形式,则:
1) 计算比特y~P(参见附录A中A.5);
2) 若y~P=0,则令PC=02;若y~P=1,则令PC=03;
3) 字节串S=PC‖X1;
c) 若选用未压缩表示形式,则:
1) 按4.2.6的方法把域元素yP转换成长度为l的字节串Y1;
2) 令PC=04;
3) 字节串S=PC‖X1‖Y1;
d) 若选用混合表示形式,则:
1) 按4.2.6的方法把域元素yP转换成长度为l的字节串Y1;
2) 计算比特y~P(参见附录A中A.5);
3) 若y~P=0,则令PC=06;若y~P=1,则令PC=07;
4) 字节串S=PC‖X1‖Y1。
4.2.10 字节串到点的转换
输入:定义Fq上椭圆曲线的域元素a、b,字节串S。若选用未压缩表示形式或混合表示形式,则字
节串S长度为2l+1;若选用压缩表示形式,则字节串PO 长度为l+1(l= (log2q)/8)。
输出:椭圆曲线上的点P=(xP,yP),且P≠O。
a) 若选用压缩表示形式,则S=PC‖X1;若选用未压缩表示形式或混合表示形式,则S=
PC‖X1‖Y1,其中PC 是单一字节,X1和Y1都是长度为l的字节串;
b) 按4.2.7的方法把字节串X1转换成域元素xP;
c) 若选用压缩表示形式,则:
1) 检验PC=02或者是PC=03,若不是这种情形,则报错;
2) 若PC=02,则令y~P=0;若PC=03,则令y~P=1;
3) 将(xP,y~P)转换为椭圆曲线上的一个点(xP,yP)(参见附录A中A.5);
d) 若选用未压缩表示形式,则:
1) 检验PC=04,若不是这种情形,则报错;
2) 按4.2.7的方法把字节串Y1转换成域元素yP;
e) 若选用混合表示形式,则:
1) 检验PC=06或者PC=07,若不是这种情形,则报错;
2) 执行步骤如下:
---按4.2.7的细节把字节串Y1转换成域元素yP;
---若PC=06,则令y~P=0,否则令y~P=1;
3) 将(xP,y~P)转换为椭圆曲线上的一个点(xP,yP)(参见附录A中A.5);
f) 若q为奇素数,则验证y2P≡y3P+axP+b(modq),若不是这种情形,则报错;
若q=2m,则在F2m中验证y2P+xPyP=x3P+ax2P+b,若不是这种情形,则报错;
g) P=(xP,yP)。
5 椭圆曲线系统参数及其验证
5.1 一般要求
椭圆曲线系统参数是可以公开的,系统的安全性不依赖于对这些参数的保密。本部分不规定椭圆
曲线系统参数的生成方法,但规定了系统参数的验证方法。椭圆曲线阶的计算和基点的选取方法可参
见附录B中B.3,曲线参数的生成方法可参见附录D。
椭圆曲线系统参数按照基域的不同可以分为两种情形:
---当基域是Fp(p为大于3的素数)时,Fp上的椭圆曲线系统参数;
---当基域是F2m时,F2m上的椭圆曲线系统参数。
5.2 Fp 上椭圆曲线系统参数及其验证
5.2.1 Fp 上椭圆曲线系统参数
Fp 上椭圆曲线系统参数包括:
a) 域的规模q=p,p是大于3的素数;
b) (选项)一个长度至少为192的比特串SEED(若按照附录D描述的方法产生椭圆曲线);
c) Fp中的两个元素a和b,它们定义椭圆曲线E 的方程:y2=x3+ax+b;
d) 基点G=(xG,yG)∈E(Fp),G≠O;
e) 基点G 的阶n(要求:n>2191且n>4p1/2);
f) (选项)余因子h=#E(Fp)/n。
5.2.2 Fp 上椭圆曲线系统参数的验证
椭圆曲线系统参数的生成者应验证下面的条件。椭圆曲线系统参数的用户可选择验证这些条件。
输入:Fp上椭圆曲线系统参数的集合。
输出:若椭圆曲线系统参数是有效的,则输出“有效”;否则输出“无效”。
a) 验证q=p是奇素数(参见附录B中B.1.10);
b) 验证a,b,xG 和yG 是区间[0,p-1]中的整数;
c) 若按照附录D描述的方法拟随机产生椭圆曲线,验证SEED 是长度至少为192的比特串,且
a,b由SEED 派生得到;
d) 验证(4a3+27b2)modp≠0;
e) 验证yG2≡xG3+axG+b(modp);
f) 验证n是素数,n>2191且n>4p1/2(参见附录B中B.1.10);
g) 验证[n]G=O(参见附录A中A.3);
h) (选项)计算h'= (p1/2+1)2/n,并验证h=h';
i) 验证抗 MOV攻击条件和抗异常曲线攻击条件成立(参见附录A中A.4.2.1和A.4.2.2);
j) 若以上任何一个验证失败,则输出“无效”;否则,输出“有效”。
5.3 F2m上椭圆曲线系统参数及其验证
5.3.1 F2m上椭圆曲线系统参数
F2m上的椭圆曲线系统参数包括:
a) 域的规模q=2m,对F2m中元素表示法(三项式基TPB、五项式基PPB或高斯正规基GNB)的
标识,一个F2上的m 次约化多项式(若所用的基是TPB或PPB);
b) (选项)一个长度至少为192的比特串SEED(若按照附录 D描述的方法拟随机产生椭圆
曲线);
c) F2m中的两个元素a和b,它们定义椭圆曲线E 的方程:y2+xy=x3+ax2+b;
d) 基点G=(xG,yG)∈E(F2m),G≠O;
e) 基点G 的阶n(要求:n>2191且n>22+m/2);
f) (选项)余因子h=#E(F2m)/n。
5.3.2 F2m上椭圆曲线系统参数的验证
下面的条件椭圆曲线系统参数的生成者应加以验证。这些条件椭圆曲线系统参数的用户可选择
验证。
输入:F2m上椭圆曲线系统参数的集合。
输出:若椭圆曲线系统参数是有效的,则输出“有效”;否则输出“无效”。
a) 对某个m,验证q=2m;若所用的是TPB,则验证约化多项式是F2上的不可约三项式(参见
表A.3);若所用的是PPB,则验证不存在m 次不可约三项式,且约化多项式是F2上的不可约
五项式(参见表A.4);若所用的是GNB,则验证m 不能被8整除;
b) 验证a,b,xG 和yG 是长度为m 的比特串;
c) 若按照附录D描述的方法拟随机产生椭圆曲线,验证SEED 是长度至少为192的比特串,且
a,b由SEED 派生得到;
d) 验证b≠0;
e) 在F2m中验证yG2+xGyG=xG3+axG2+b;
f) 验证n是一个素数,n>2191且n>22+m/2(参见附录B中B.1.10);
g) 验证[n]G=O(参见附录A.3.2);
h) (选项)计算h'= (2m/2+1)2/n,验证h=h';
i) 验证抗 MOV攻击条件成立(参见附录A中A.4.2.1);
j) 若以上任何一个验证失败,则输出“无效”;否则输出“有效”。
6 密钥对的生成与公钥的验证
6.1 密钥对的生成
输入:一个有效的Fq(q=p且p为大于3的素数,或q=2m)上椭圆曲线系统参数的集合。
输出:与椭圆曲线系统参数相关的一个密钥对(d,P)。
a) 用随机数发生器产生整数d∈[1,n-2];
b) G 为基点,计算点P=(xP,yP)=[d]G(参见附录A中A.3.2);
c) 密钥对是(d,P),其中d为私钥,P 为公钥。
6.2 公钥的验证
6.2.1 Fp 上椭圆曲线公钥的验证
输入:一个有效的Fp(p>3且p为素数)上椭圆曲线系统参数集合及一个相关的公钥P。
输出:对于给定的椭圆曲线系统参数,若公钥P 是有效的,则输出“有效”;否则输出“无效”。
a) 验证P 不是无穷远点O;
b) 验证公钥P 的坐标xP和yP是域Fp中的元素(即验证xP和yP是区间[0,p-1]中的整数);
c) 验证yP2≡xP3+axP+b(modp);
d) 验证[n]P=O;
e) 若通过了所有验证,则输出“有效”;否则输出“无效”。
6.2.2 F2m上椭圆曲线公钥的验证
输入:一个有效的F2m上椭圆曲线系统参数集合及一个相关的公钥P。
输出:对于给定的椭圆曲线系统参数,若公钥P 是有效的,则输出“有效”;否则输出“无效”。
a) 验证P 不是无穷远点O;
b) 验证公钥P 的坐标xP和yP是域F2m中的元素(即验证xP和yP是长度为m 的比特串);
c) 在F2m中验证y2P+xPyP=x3P+ax2P+b;
d) 验证[n]P=O;
e) 若通过了所有验证,则输出“有效”;否则输出“无效”。
注:公钥的验证是可选项。
附 录 A
(资料性附录)
关于椭圆曲线的背景知识
A.1 素域Fp
A.1.1 素域Fp 的定义
设p是一个素数,Fp由{0,1,2,,p-1}中p个元素构成,称Fp为素域。加法单位元是整数0,乘
法单位元是整数1,Fp的元素满足如下运算法则:
---加法:设a,b∈Fp,则a+b=r,其中r=(a+b)modp,r∈[0,p-1]。
---乘法:设a,b∈Fp,则a·b=s,其中s=(a·b)modp,s∈[0,p-1]。
记F*p 是由Fp中所有非零元构成的乘法群,由于F*p 是循环群,所以在Fp中至少存在一个元素g,
使得Fp中任一非零元都可以由g的一个方幂表示,称g为F*p 的生成元(或本原元),即F*p ={gi|0≤
i≤p-2}。设a=gi∈F*p,其中0≤i≤p-2,则a的乘法逆元为:a-1=gp-1-i。
示例1:素域F2,F2={0,1}
F2的加法表如表A.1,乘法表如表A.2:
示例2:素域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。
A.1.2 Fp 上椭圆曲线的定义
A.1.2.1 概述
Fp上椭圆曲线常用的表示形式有两种:仿射坐标表示和射影坐标表示。
A.1.2.2 仿射坐标表示
当p是大于3的素数时,Fp上椭圆曲线方程在仿射坐标系下可以简化为y2=x3+ax+b,其中a,
b∈Fp,且使得(4a3+27b2)modp≠0。椭圆曲线上的点集记为E(Fp)={(x,y)|x,y∈Fp且满足曲线
方程y2=x3+ax+b}∪{O},其中O 是椭圆曲线的无穷远点。
E(Fp)上的点按照下面的加法运算规则,构成一个阿贝尔群:
a) O+O=O;
b) "P=(x,y)∈E(Fp)\{O},P+O=O+P=P;
c) "P=(x,y)∈E(Fp)\{O},P 的逆元素-P=(x,-y),P+(-P)=O;
d) 点P1=(x1,y1)∈E(Fp)\{O},P2=(x2,y2)∈E(Fp)\{O},P3=(x3,y3)=P1+P2≠
O,则
x3=λ2-x1-x2,
y3=λ(x1-x3)-y1,{
其中
λ=
y2-y1
x2-x1
, 若x1≠x2,
3x12+a
2y1
, 若x1=x2 且P2≠-P1。
示例3:有限域F19上一条椭圆曲线
F19上方程:y2=x3+x+1,其中a=1,b=1。则F19上曲线的点为:
(0,1),(0,18),(2,7),(2,12),(5,6),(5,13),(7,3),(7,16),(9,6),(9,13),(10,2),(10,17),(13,8),(13,11),
(14,2),(14,17),(15,3),(15,16),(16,3),(16,16),
则E(F19)有21个点(包括无穷远点O)。
a) 取P1=(10,2),P2=(9,6),计算P3=P1+P2:
λ=
y2-y1
x2-x1=
6-2
9-10=
-1=-4≡15
(mod19),
x3=152-10-9=225-10-9≡16-10-9=-3≡16(mod19),
y3=15×(10-16)-2=15×(-6)-2≡3(mod19),
所以P3=(16,3)。
b) 取P1=(10,2),计算[2]P1:
λ=
3x1 2+a
2y1
3×102+1
2×2 =
3×5+1
4 =
4=4
(mod19),
x3=42-10-10=-4≡15(mod19),
y3=4×(10-15)-2=-22≡16(mod19),
所以[2]P1=(15,16)。
A.1.2.3 射影坐标表示
A.1.2.3.1 标准射影坐标系
当p是大于3的素数时,Fp上椭圆曲线方程在标准射影坐标系下可以简化为y2z=x3+axz2+
bz3,其中a,b∈Fp,且4a3+27b2≠0modp。椭圆曲线上的点集记为E(Fp)={(x,y,z)|x,y,z∈Fp
且满足曲线方程y2z=x3+axz2+bz3}。对于(x1,y1,z1)和(x2,y2,z2),若存在某个u∈Fp且u≠0,
使得:x1=ux2,y1=uy2,z1=uz2,则称这两个三元组等价,表示同一个点。
若z≠0,记X=x/z,Y=y/z,则可从标准射影坐标表示转化为仿射坐标表示:Y2=X3+aX+b;
若z=0,(0,1,0)对应的仿射坐标系下的点即无穷远点O。
标准射影坐标系下,E(Fp)上点的加法运算定义如下:
a) O+O=O;
b) "P=(x,y,z)∈E(Fp)\{O},P+O=O+P=P;
c) "P=(x,y,z)∈E(Fp)\{O},P的逆元素-P=(ux,-uy,uz),u∈Fp且u≠0,P+(-P)=O;
d) 设点P1=(x1,y1,z1)∈E(Fp)\{O},P2=(x2,y2,z2)∈E(Fp)\{O},P3=P1+P2=
(x3,y3,z3)≠O,
若P1≠P2,则:
λ1=x1z2,λ2=x2z1,λ3=λ1-λ2,λ4=y1z2,λ5=y2z1,λ6=λ4-λ5,λ7=λ1+λ2,λ8=z1z2,
λ9=λ32,λ10=λ3λ9,λ11=λ8λ62-λ7λ9,x3=λ3λ11,y3=λ6(λ9λ1-λ11)-λ4λ10,z3=λ10λ8;
若P1=P2,则:
λ1=3x12+az12,λ2=2y1z1,λ3=y12,λ4=λ3x1z1,λ5=λ22,λ6=λ12-8λ4,
x3=λ2λ6,y3=λ1(4λ4-λ6)-2λ5λ3,z3=λ2λ5。
A.1.2.3.2 Jacobian加重射影坐标系
Fp上椭圆曲线方程在Jacobian加重射影坐标系下可以简化为y2=x3+axz4+bz6。其中a,b∈
Fp,且4a3+27b2≠0modp。椭圆曲线上的点集记为E(Fp)={(x,y,z)|x,y,z∈Fp且满足曲线方程
y2=x3+axz4+bz6}。对于(x1,y1,z1)和(x2,y2,z2),若存在某个u∈Fp且u≠0,使得:x1=u2x2,
y1=u3y2,z1=uz2,则称这两个三元组等价,表示同一个点。
若z≠0,记X=x/z2,Y=y/z3,则可从Jacobian加重射影坐标表示转化为仿射坐标表示:Y2=
X3+aX+b;
若z=0,(1,1,0)对应的仿射坐标系下的点即无穷远点O。
Jacobian加重射影坐标系下,E(Fp)上点的加法运算定义如下:
a) O+O=O;
b) "P=(x,y,z)∈E(Fp)\{O},P+O=O+P=P;
c) "P=(x,y,z)∈E(Fp)\{O},P的逆元素-P=(u2x,-u3y,uz),u∈Fp且u≠0,P+(-P)=O;
d) 设点P1=(x1,y1,z1)∈E(Fp)\{O},P2=(x2,y2,z2)∈E(Fp)\{O},P3=P1+P2=
(x3,y3,z3)≠O,
若P1≠P2,则:
λ1=x1z22,λ2=x2z12,λ3=λ1-λ2,λ4=y1z23,λ5=y2z13,λ6=λ4-λ5,λ7=λ1+λ2,
λ8=λ4+λ5,x3=λ62-λ7λ32,y3=λ6(λ1λ32-x3)-λ4λ33,z3=z1z2λ3;
若P1=P2,则:
λ1=3x12+az14,λ2=4x1y12,λ3=8y14,x3=λ12-2λ2,y3=λ1(λ2-x3)-λ3,z3=2y1z1。
A.1.3 Fp 上椭圆曲线的阶
Fp(p为大于3的素数)上一条椭圆曲线的阶是指点集E(Fp)中元素的个数,记为#E(Fp)。由
Hasse定理知:p+1-2p1/2≤#E(Fp)≤p+1+2p1/2。
若一条曲线的阶#E(Fp)=p+1,则称此曲线为超奇异的,否则为非超奇异的。
A.2 二元扩域F2m
A.2.1 二元扩域F2m的定义
由2m个元素构成的有限域F2m是F2的m 次扩张,称为m 次二元扩域。F2m可以看成F2上维数为
m 的向量空间,也就是说,在F2m中存在m 个元素α0,α1,,αm-1,使得∀α∈F2m,α可以唯一表示为:
α=a0α0+a1α1++am-1αm-1,其中ai∈F2,称{α0,α1,,αm-1}为F2m在F2 上的一组基。给定这样
一组基,就可以由向量(a0,a1,,am-1)来表示域元素α。F2m在F2 上的基有多种选择,域元素的加法
在不同的基下的运算规则是一致的,都可以通过向量按分量异或运算得到;域元素的乘法在不同的基下
有不同的运算规则(如用多项式基表示和用正规基表示时其运算规则就不一致)。
A.2.1.1 多项式基
设F2上m 次不可约多项式f(x)=xm+fm-1xm-1++f2x2+f1x+f0(其中fi∈F2,i=0,1,
,m-1)是二元扩域F2m的约化多项式。F2m由F2上所有次数低于m 的多项式构成,即:
F2m={am-1xm-1+am-2xm-2++a1x+a0|ai∈F2,i=0,1,,m-1}。
多项式集合{xm-1,xm -2,,x,1}是F2m作为向量空间在F2上的一组基,称为多项式基。
域元素am-1xm-1+am-2xm-2++a1x+a0相对多项式基可以由长度为m 的比特串(am-1am-2
a1a0)来表示,所以
F2m={(am-1am-2a1a0)|ai∈F2,i=0,1,,m-1}。
乘法单位元1由(0001)表示,零元由(0000)表示。域元素的加法和乘法定义如下:
---加法运算
"(am-1am-2a1a0),(bm-1bm-2b1b0)∈F2m,则(am-1am-2a1a0)+(bm-1bm-2b1b0)=
(cm-1cm-2c1c0),其中ci=ai⊕bi,i=0,1,,m-1,亦即,加法运算按分位异或运算执行。
---乘法运算
"(am-1am-2a1a0),(bm-1bm-2b1b0)∈F2m,则(am-1am-2a1a0)·(bm-1bm-2b1b0)=
(rm-1rm-2r1r0),其中多项式(rm-1xm-1+rm-2xm -2++r1x+r0)是(am-1xm-1+am-2xm-2++
a1x+a0)·(bm-1xm-1+bm-2xm -2++b1x+b0)在F2上 modf(x)的余式。
注意,F2m恰包含2m 个元素。记F2m *是由F2m 中所有非零元构成的乘法群,F2m *是循环群,在
F2m中至少存在一个元素g,使得F2m中任一非零元都可以由g的一个方幂表示,称g为F2m *的生成元
(或本原元),即:F2m *={gi|0≤i≤2m-2}。设a=gi∈F2m *,其中0≤i≤2m-2,则a的乘法逆元为:
a-1=g2m-1-i。
示例4:二元扩域F25的多项式基表示
取F2上的一个不可约多项式f(x)=x5+x2+1,则F25中的元素是:
(00000),(00001),(00010),(00011),(00100),(00101),(00110),
(00111),(01000),(01001),(01010),(01011),(01100),(01101),
(01110),(01111),(10000),(10001),(10010),(10011),(10100),
(10101),(10110),(10111),(11000),(11001),(11010),(11011),
(11100),(11101),(11110),(11111)。
加法:(11011)+(10011)=(01000)
乘法:(11011)·(10011)=(00100)
(x4+x3+x+1)·(x4+x+1)=x8+x7+x4+x3+x2+1
=(x5+x2+1)·(x3+x2+1)+x2
≡x2(modf(x))
即x2是(x4+x3+x+1)·(x4+x+1)除以f(x)的余式。
乘法单位元是(00001),α=x是F25*的一个生成元,则α的方幂为:
α0=(00001),α1=(00010),α2=(00100),α3=(01000),α4=(10000),α5=(00101),
α6=(01010),α7=(10100),α8=(01101),α9=(11010),α10=(10001),α11=(00111),
α12=(01110),α13=(11100),α14=(11101),α15=(11111),α16=(11011),α17=(10011),
α18=(00011),α19=(00110),α20=(01100),α21=(11000),α22=(10101),α23=(01111),
α24=(11110),α25=(11001),α26=(10111),α27=(01011),α28=(10110),α29=(01001),
α30=(10010),α31=(00001)。
A.2.1.2 三项式和五项式基
A.2.1.2.1 概述
三项式基(TPB)和五项式基(PPB)是特殊的多项式基。
A.2.1.2.2 三项式基
F2上的三项式是形如xm+xk+1的多项式,其中1≤k≤m-1。
F2m的一个三项式基表示是由F2上一个m 次不可约三项式决定的,只有某些特定的m 值存在这
样的三项式。上述示例4即为F25的三项式基表示。
对192≤m≤512,表A.3给出了存在m 次不可约三项式的每一个m 值;并对每个这样的m,给出
了最小的k,使得三项式xm+xk+1在F2上是不可约的。
表A.3
m,k m,k m,k m,k m,k m,k
193,15 194,87 196,3 198,9 199,34 201,14
202,55 204,27 207,43 209,6 210,7 212,105
214,73 215,23 217,45 218,11 220,7 223,33
225,32 228,113 231,26 233,74 234,31 236,5
238,73 239,36 241,70 242,95 244,111 247,82
249,35 250,103 252,15 253,46 255,52 257,12
258,71 260,15 263,93 265,42 266,47 268,25
270,53 271,58 273,23 274,67 276,63 278,5
279,5 281,93 282,35 284,53 286,69 287,71
289,21 292,37 294,33 295,48 297,5 300,5
302,41 303,1 305,102 308,15 310,93 313,79
314,15 316,63 318,45 319,36 321,31 322,67
324,51 327,34 329,50 330,99 332,89 333,2
337,55 340,45 342,125 343,75 345,22 346,63
348,103 350,53 351,34 353,69 354,99 358,57
359,68 362,63 364,9 366,29 367,21 369,91
370,139 372,111 375,16 377,41 378,43 380,47
382,81 383,90 385,6 386,83 388,159 390,9
391,28 393,7 394,135 396,25 399,26 401,152
402,171 404,65 406,141 407,71 409,87 412,147
414,13 415,102 417,107 418,199 420,7 422,149
423,25 425,12 426,63 428,105 431,120 433,33
表A.3(续)
m,k m,k m,k m,k m,k m,k
436,165 438,65 439,49 441,7 444,81 446,105
447,73 449,134 450,47 455,38 457,16 458,203
460,19 462,73 463,93 465,31 468,27 470,9
471,1 473,200 474,191 476,9 478,121 479,104
481,138 484,105 486,81 487,94 489,83 490,219
492,7 494,17 495,76 497,78 498,155 500,27
503,3 505,156 506,23 508,9 510,69 511,10
A.2.1.2.3 五项式基
F2上的五项式是形如xm+xk3+xk2+xk1+1的多项式,其中1≤k1式基表示是由F2上一个m 次不可约五项式决定的。对4≤m≤512,均存在这样的五项式。
对192≤m≤512且不存在不可约三项式的m,表A.4列出了其不可约五项式的m 值;并对每一个
这样的m,列出三元组(k1,k2,k3),满足:
a) xm+xk3+xk2+xk1+1在F2上不可约;
b)k1尽可能地小;
c) 对这个选定的k1,k2尽可能地小;
d) 对选定的k1和k2,k3尽可能地小。
表A.4
m(k1,k2,k3) m(k1,k2,k3) m(k1,k2,k3) m(k1,k2,k3)
192 (1,2,7) 195 (1,2,37) 197 (1,2,21) 200 (1,2,81)
203 (1,2,45) 205 (1,2,21) 206 (1,2,63) 208 (1,2,83)
211 (1,2,165) 213 (1,2,62) 216 (1,2,107) 219 (1,2,65)
221 (1,2,18) 222 (1,2,73) 224 (1,2,159) 226 (1,2,30)
227 (1,2,21) 229 (1,2,21) 230 (1,2,13) 232 (1,2,23)
235 (1,2,45) 237 (1,2,104) 240 (1,3,49) 243 (1,2,17)
245 (1,2,37) 246 (1,2,11) 248 (1,2,243) 251 (1,2,45)
254 (1,2,7) 256 (1,2,155) 259 (1,2,254) 261 (1,2,74)
262 (1,2,207) 264 (1,2,169) 267 (1,2,29) 269 (1,2,117)
272 (1,3,56) 275 (1,2,28) 277 (1,2,33) 280 (1,2,113)
283 (1,2,200) 285 (1,2,77) 288 (1,2,191) 290 (1,2,70)
291 (1,2,76) 293 (1,3,154) 296 (1,2,123) 298 (1,2,78)
299 (1,2,21) 301 (1,2,26) 304 (1,2,11) 306 (1,2,106)
307 (1,2,93) 309 (1,2,26) 311 (1,3,155) 312 (1,2,83)
315 (1,2,142) 317 (1,3,68) 320 (1,2,7) 323 (1,2,21)
表A.4(续)
m(k1,k2,k3) m(k1,k2,k3) m(k1,k2,k3) m(k1,k2,k3)
325 (1,2,53) 326 (1,2,67) 328 (1,2,51) 331 (1,2,134)
334 (1,2,5) 335 (1,2,250) 336 (1,2,77) 338 (1,2,112)
339 (1,2,26) 341 (1,2,57) 344 (1,2,7) 347 (1,2,96)
349 (1,2,186) 352 (1,2,263) 355 (1,2,138) 356 (1,2,69)
357 (1,2,28) 360 (1,2,49) 361 (1,2,44) 363 (1,2,38)
365 (1,2,109) 368 (1,2,85) 371 (1,2,156) 373 (1,3,172)
374 (1,2,109) 376 (1,2,77) 379 (1,2,222) 381 (1,2,5)
384 (1,2,299) 387 (1,2,146) 389 (1,2,159) 392 (1,2,145)
395 (1,2,333) 397 (1,2,125) 398 (1,3,23) 400 (1,2,245)
403 (1,2,80) 405 (1,2,38) 408 (1,2,323) 410 (1,2,16)
411 (1,2,50) 413 (1,2,33) 416 (1,3,76) 419 (1,2,129)
421 (1,2,81) 424 (1,2,177) 427 (1,2,245) 429 (1,2,14)
430 (1,2,263) 432 (1,2,103) 434 (1,2,64) 435 (1,2,166)
437 (1,2,6) 440 (1,2,37) 442 (1,2,32) 443 (1,2,57)
445 (1,2,225) 448 (1,3,83) 451 (1,2,33) 452 (1,2,10)
453 (1,2,88) 454 (1,2,195) 456 (1,2,275) 459 (1,2,332)
461 (1,2,247) 464 (1,2,310) 466 (1,2,78) 467 (1,2,210)
469 (1,2,149) 472 (1,2,33) 475 (1,2,68) 477 (1,2,121)
480 (1,2,149) 482 (1,2,13) 483 (1,2,352) 485 (1,2,70)
488 (1,2,123) 491 (1,2,270) 493 (1,2,171) 496 (1,3,52)
499 (1,2,174) 501 (1,2,332) 502 (1,2,99) 504 (1,3,148)
507 (1,2,26) 509 (1,2,94) 512 (1,2,51)
A.2.1.2.4 选择多项式基的规则
F2m的不同多项式基表示取决于约化多项式的选择:
a) 若存在F2上的m 次不可约三项式,则约化多项式f(x)选用不可约三项式xm+xk+1,为了
使实现的效果更好,k的取值应尽可能小(这样的多项式在表A.3给出);
b) 若不存在F2上的m 次不可约三项式,则约化多项式f(x)选用不可约五项式xm+xk3+
xk2+xk1+1,为了使实现的效果更好:
1) k1应尽可能小;
2) 对这个选定的k1,k2应尽可能小;
3) 对选定的k1和k2,k3应尽可能小(这样的多项式在表A.4给出)。
A.2.1.3 正规基
形如{β,β2,β2
2,,β2
m-1}的基是F2m在F2上的一组正规基,其中β∈F2m。这样的基总是存在的。
"α∈F2m,则α=a0β2
0+a1β2
1++am-1β2
m-1,其中ai∈F2,(i=0,1,,m-1),并记为α=(a0a1a2
am-2am-1),域元素α由长度为m 的比特串表示。所以F2m={(a0a1a2am-2am-1)|ai∈F2,0≤i≤
m-1},乘法单位元1由m 个1的比特串(111)表示,零元由m 个0的比特串(000)表示。
注:通过约定,正规基表示的比特排序同多项式基表示的比特排序是不一样的(参见A.2.1.1)。
在正规基表示下,F2m中求平方运算是循环右移位运算:
∀α∈F2m,α=a0β2
0+a1β2
1++am-1β2
m-1=(a0a1a2am-2am-1),
α2= ∑
m-1
i=0
aiβ2
i() 2=∑
m-1
i=0
a2iβ2
i+1=∑
m-1
i=0
ai-1β2
i=(am-1a0am-2)。
在这种情况下,求平方运算只是长度为m 的比特串的循环移位,便于在硬件上实现。
A.2.1.4 高斯正规基
由A.2.1.3可知,F2m在F2上的正规基是形式为N={β,β2,β2
2,,β2
m-1}的一组基,其中β∈F2m。
正规基表示在求取元素的平方时有计算优势,但对于一般意义下的不同元素的乘法运算不太方便。因
此,通常专用一种称为高斯正规基的基,对这样的基,乘法既简单又有效。
当m 不能被8整除时F2m存在高斯正规基。高斯正规基的类型T 是指在此基下度量乘法运算复
杂度的一个正整数。一般情况下,类型T 愈小,乘法效率愈高。对于给定的m 和T,域F2m至多有一个
类型T 的高斯正规基。在所有正规基中,类型1和类型2的高斯正规基有最有效的乘法运算,因而也
称它们为最优正规基。类型1的高斯正规基称为Ⅰ型最优正规基,类型2的高斯正规基称为Ⅱ型最优
正规基。
有限域F2m中的元素a在高斯正规基下可以由长度为m 的比特串(am-1am-2a1a0)来表示。
a) 乘法单位元1由m 个1的比特串表示;
b) 零元0由m 个0的比特串表示;
c) 两个域元素的加法由比特串对位异或运算完成;
d) 域元素的乘法在A.2.1.4.3中描述。
A.2.1.4.1 选择正规基的规则
选择F2m存在的最小类型的高斯正规基。
表A.5列出[192,512]中素数m 的F2m上高斯正规基的类型。
表A.5
m 类型 m 类型 m 类型 m 类型 m 类型 m 类型
193 4 19718 199 4 21110 22312 22724
22912 233 2 239 2 241 6 251 2 257 6
263 6 269 8 271 6 277 4 281 2 283 6
293 2 307 4 311 6 313 6 31726 331 6
33710 347 6 34910 35314 359 2 367 6
373 4 37912 38312 38924 397 6 401 8
409 4 419 2 42110 431 2 433 4 43910
443 2 449 8 45730 461 6 46312 467 6
479 8 487 4 491 2 499 4 503 6 509 2
A.2.1.4.2 高斯正规基的检验
给定类型T,利用下述算法可以检验F2m(m 大于1且不能被8整除)中类型T 的高斯正规基的存
在性。
输入:大于1且不被8整除的整数m,正整数T。
输出:若F2m存在一个类型T 的高斯正规基,输出“正确”;否则输出“错误”。
a) 计算p=T·m+1;
b) 若p不是素数,则输出“错误”并停止;
c) 计算2模p的阶k(参见B.1.8);
d) 计算u=T·m/k;
e) 计算d=gcd(u,m);
f) 若d=1,则输出“正确”;否则输出“错误”。
A.2.1.4.3 高斯正规基下的乘法算法
对于任意给定的高斯正规基,其乘法运算包含三部分:乘法预运算;给定两个元素后,其乘积的第一
项c0的公式;利用两个元素乘积的第一项c0的公式,计算两个元素的乘积。下面对这三部分进行详细
描述:
---乘法预运算:
输入:大于1的整数m,正整数T,其中在F2m上存在类型T 的高斯正规基B。
输出:相对于B的序列f(1),f(2),,f(p-1)。
a) 计算p=T·m+1;
b) 产生模p阶为T 的整数u(参见B.1.9);
c) 计算序列f(1),f(2),,f(p-1):
1) 置w=1;
2) 从j=0到T-1执行:
---置n=w;
---从i=0到m-1执行:
● 置f(n)=i;
● 置n=2nmodp;
● 置w=u·wmodp;
d) 输出序列f(1),f(2),,f(p-1)。
---给定在高斯正规基B表示下的两个域元素a和b,其乘积的第一项c0的公式:
记c0=F(a,b)。
输入:大于1的整数m,正整数T(其中在F2m上存在类型T 的高斯正规基B)及在高斯正规基
B表示下的两个域元素a、b。
输出:在高斯正规基B表示下的两个域元素a、b乘积的第一项c0的公式。
a) 利用乘法预运算得到输出序列f(1),f(2),,f(p-1);
b) T 为偶数,则J=0,否则
J=∑
k=1
(ak-1bm/2+k-1+am/2+k-1bk-1);
c) 输出公式
c0=J+∑
p-2
k=1
af(k+1)bf(p-k)。
---利用域元素a和b乘积的第一项c0的公式,计算域元素a和b的乘积:
对u=(u0u1um-1),v=(v0v1vm-1),设F(u,v)是以c0=F(a,b)导出的表达式。
输入:大于1的整数m,正整数T(其中在F2m上存在类型T 的高斯正规基B)及在高斯正规基
B表示下的两个域元素a、b。
输出:积(c0c1cm-1)=(a0a1am-1)×(b0b1bm-1)。
a) 置(u0u1um-1)=(a0a1am-1);
b) 置(v0v1vm-1)=(b0b1bm-1);
c) 对k从0到m-1执行:
1) 计算ck=F(u,v);
2) 置u=LeftRotate(u),并置v=LeftRotate(v),其中LeftRotate()表示循环左移1位
运算,即LeftRotate(u)=LeftRotate(u0u1um-2um-1)=(u1u2um-1u0);
d) 输出c=(c0c1cm-1)。
在示例4中,用多项式乘法和带余除法描述了F25,下面的示例5用高斯正规基表示F25。
示例5:二元扩域F25的高斯正规基表示
F25域元素为比特五位组:
(00000),(00001),(00010),(00011),(00100),(00101),(00110),(00111),
(01000),(01001),(01010),(01011),(01100),(01101),(01110),(01111),
(10000),(10001),(10010),(10011),(10100),(10101),(10110),(10111),
(11000),(11001),(11010),(11011),(11100),(11101),(11110),(11111)。
域加法:(a0a1a2a3a4)+(b0b1b2b3b4)=(c0c1c2c3c4),其中ci=ai⊕bi,0≤i<5,也就是域加法通过向量表示按分
量异或运算来实现。
域乘法:
因为2×5+1=11,11是一素数,则T=2,2模11的阶为10,且gcd(5,(11-1)/10)=1,所以F25有第2类高斯正规
基。10模11的阶为2,取u=10,则可计算出f的值如下:
f(1)=0, f(2)=1, f(4)=2, f(8)=3, f(5)=4,
f(10)=0, f(9)=1, f(7)=2, f(3)=3, f(6)=4。
a=(10000),b=(11001),由T=2为偶数,则有J=0。
则有F(a,b)=∑
11-2
k=1
af(k+1)bf(11-k)
=a0b1+a1(b0+b3)+a2(b3+b4)+a3(b1+b2)+a4(b2+b4)。
c0=a0b1+a1(b0+b3)+a2(b3+b4)+a3(b1+b2)+a4(b2+b4),
c1=a1b2+a2(b1+b4)+a3(b4+b0)+a4(b2+b3)+a0(b3+b0),
c2=a2b3+a3(b2+b0)+a4(b0+b1)+a0(b3+b4)+a1(b4+b1),
c3=a3b4+a4(b3+b1)+a0(b1+b2)+a1(b4+b0)+a2(b0+b2),
c4=a4b0+a0(b4+b2)+a1(b2+b3)+a2(b0+b1)+a3(b1+b3)。
可以得出: <
   
       隐私   ·  优质产品   ·  退款政策   ·  公平交易   ·  关于我们
宁德梧三商贸有限公司 (营业执照期限:2019-2049年. 纳税人识别号:91350900MA32WE2Q2X)
对公账号开户银行:中国建设银行 | 账户名称:宁德梧三商贸有限公司 | 账户号码:35050168730700000955
本公司专职于中国国家标准行业标准英文版