椭圆曲线数字签名算法文档格式.docx
- 文档编号:7989571
- 上传时间:2023-05-09
- 格式:DOCX
- 页数:30
- 大小:44.18KB
椭圆曲线数字签名算法文档格式.docx
《椭圆曲线数字签名算法文档格式.docx》由会员分享,可在线阅读,更多相关《椭圆曲线数字签名算法文档格式.docx(30页珍藏版)》请在冰点文库上搜索。
签名必须是可验证的,即如果对签名的真实性存在疑问,必须由一个中立的第三方作出公正的裁决,并且无需知道签名者的私钥。
对签名的抵赖以及伪造签名应该能被发现。
本文论述的是非对称摘要数字签名。
"
非对称"
即用户的密钥对各不相同。
用户的私钥用于签名,其他用户用他的公钥来检验签名的真实性。
摘要是指对一段消息先用哈希函数进行摘要计算,尔后再对消息摘要进行签名。
安全性。
从理论上讲,在选择消息攻击下,数字签名应该是不可伪造的。
这一概念由GoldwasserMicali和Rivest提出。
更一般的讲就是攻击者获得用户A的摘要和签名,但他无法用其他的摘要来伪造这样一个签名。
应用。
数字签名方案用于以下一些用途:
数据完整性(确保数据没有被未知或未授权的中间人改变),数据源认证(确保数据的来源是可信的),不可否认性(确保用户不能对自己的行为进行抵赖)。
数字签名是密码学协议的基本组成部分,并且可以提供其他一些服务如:
身份认证(FIPS196,ISO/IEC9798-3),密钥传递前的认证(ANSIX9.63,ISO/IEC11770-3),经验证的密钥协商(ISO/IEC11770-3)。
分类。
数字签名方案可以根据所基于的数学难题进行分类:
1、基于大整数分解(IF)的方案,安全性基于大整数分解的难度。
实例有RSA方案和Rabin方案。
2、基于离散对数(DL)的方案,安全性基于有限域上普通的离散对数问题。
实例包括ElGamal,Schnorr,DSA和Nyberg-Rueppel方案。
3、基于椭圆曲线(EC)的方案,安全性基于椭圆曲线离散对数问题。
2.2数字签名算法
DSA于1991年由NIST提出,并在FIPS186中得到确认。
DSA可以看作是ElGamal签名方案的一个变形。
其安全性建立在素域上的离散对数问题的困难性之上。
DSA参数的产生。
每个用户的安全参数产生如下:
1、选择160比特的素数q和1024比特的素数p,满足q|p-1。
2、在有限域Zp*中寻找q阶循环子群的生成元g,具体方法是在Zp*选取元素h计算g=h(p-1)/qmodp,当g≠1时即找到满足要求的g。
3、域参数就是p,q和g。
DSA密钥对的产生。
每个拥有域参数p,q和g进行如下操作:
1、选择伪随机数x满足1<
x<
p-1。
2、计算y=gxmodp。
3、用户的私钥是x,公钥是y。
DSA签名过程:
1、选择伪随机数k满足1<
k<
2、计算X=gkmodp,r=Xmodq,若r=0则返回第一步。
3、计算k-1modq。
4、计算e=SHA-1(m)。
5、计算s=k-1(e+xr)modq,若s=0则返回第一步。
6、对消息m的签名就是(r,s)。
DSA签名的验证。
为了验证(r,s)是对m的签名,需要使用签名者的域参数(p,q,g)和公钥y进行如下运算:
1、验证r,s在区间[1,q-1]中。
2、计算e=SHA-1(m)。
3、计算ω=s-1modq。
4、计算u1=ωemodq和u2=rωmodq
5、计算X=gu1yu2modp及v=Xmodq。
6、如果v=r则认可此签名。
安全性分析。
由于r和s均小于q,故DSA签名长度小于320比特。
DSA的安全性依赖于两个方面,它们都基于离散对数问题的难解性,一个是Zp*上的离散对数问题,目前已有数域筛算法去加以解决,这是一种亚指数级的算法。
其平均运算时间为:
O(exp((c+o
(1))(lnp)1/3(lnlnp)2/3))
其中c约为1.923,若p是1024比特的素数,则上式的计算量是无法接受的。
因此目前1024比特的DSA可以应付现有攻击。
另一个是q阶子群上的离散对数问题,给定p,q,g和y,y=gxmodp,要寻找x,目前最好的算法是Pollard'
sRho算法,大约要做sqrt(пq/2)步。
若q是160比特的,则该算法在计算上不可行,因此DSA是很安全的。
DSA的安全性主要取决于p和q的尺寸。
增加其中一个的尺寸而不增加另一个的尺寸对安全性的提高并无益处。
此外,对两种离散对数问题解决算法的提高都会削弱DSA。
安全参数的产生。
DSA的早期版本受到了一些批评,因此FIPS186推出了一种新模式以产生素数以及"
可证明的随机性"
。
它可以防止用户故意构造一个利于破译的素数(例如可以由CA来产生域参数并发送给用户)。
FIPS指定了两个模式,分别使用SHA-1和DES,产生伪随机私钥x。
FIPS186指定使用这两种模式以及其他经过FIPS认可的安全模式。
3、有限域
我们将简要介绍有限域的知识。
更多详细内容请参看其他书籍。
有限域由一个有限集合F和F上的两个二元运算组成,这两个运算满足某种运算规则,分别称为加法和乘法。
有限域的阶即域中元素的个数。
当仅当q是素数时存在一个q阶有限域,这个有限域是唯一的,记作Fq。
有很多方法可以描述Fq的元素,有些描述方式可以使域上的软件及硬件运算更加高效。
若q=pm,其中p为素数,m为正整数,则p称为Fq的特征,m称为Fq的度。
至于椭圆曲线密码,一般基于素域或是多项式域。
在3.1和3.2中我们将分别介绍这两种有限域上的元素和运算以及多项式域的两种表示方法:
多项式表示方法和正规基表示方法。
3.1有限域Fp
P为素数,有限域Fp称为素域,由整数集{1,2,......,p-1}和其上的符合下列规则的运算组成:
1、加法。
a,b∈p,a+b=r,r为a与b的和模p所得的值。
2、乘法。
a,b∈p,a*b=s,s为a与b的积模p所得的值。
3、求逆运算。
a是Fp中的非零元素,a的逆是唯一的,记作a-1,有a*a-1=1modp
例1.F23,全部元素为{1,2,......,22},其上三种运算:
12+20=9,8*9=3,8-1=3。
3.2有限域F2m
F2m称之为特征为2的有限域,可以看做是F2上的m维向量空间。
F2m中存在m个不同的元素?
0,?
1......,?
m-1,任一个?
∈F2m均可写为以下形式:
?
=a0?
0+a1?
1+......+am-1?
m-1ai∈{0,1}
集合{?
m-1}称为F2m在F2上的基。
有这样一个基,域中所有元素就可以用一个比特串(a0,a1,......am-1)来表示。
这样,加法就可以用向量的逐比特异或运算来表示,乘法运算则依赖于基的选择。
基的选择方式是多种多样的。
一些基可以使运算变得高效。
ANSIX9.62给出了两种基,分别是多项式基和正规基。
多项式基
f(x)=xm+fm-1xm-1+......f2x2+f1x+f0(fi∈{0,1})是F2上的m次本原多项式。
域元素。
有限域F2m由F2上的所有不多于m次的多项式组成。
F2m={am-1xm-1+......+a1x+a0|ai∈{0,1}}
域元素am-1xm-1+......+a1x+a0可以写为比特串(am-1,......a1,a0)形式。
因此F2m的元素可以写为长度为m的比特串。
乘法单位元是(0,0,...,0,1),加法零元是全零串(0,0,......,0)。
域运算。
加法。
a=(am-1,......a1,a0),b=(bm-1,......,b1,b0),a+b=c=(cm-1,......,c1,c0),ci=aiXORbi。
乘法。
a=(am-1,......a1,a0),b=(bm-1,......,b1,b0),a*b=r=(rm-1,......,r1,r0),多项式rm-1xm-1+......+r1x+r0由(am-1xm-1+......+a1x+a0)*(bm-1xm-1+......+b1x+b0)模f(x)而来。
求逆运算。
a是F2m中的非零元素,a-1满足a-1*a=1
例2.有限域F24,模多项式为f(x)=x4+x+1,有限域中16个元素分别为:
0(0000)1(0001)x(0010)
x+1(0011)x2(0100)x2+1(0101)
x2+x(0110)x2+x+1(0111)x3(1000)
x3+1(1001)x3+x(1010)x3+x+1(1011)
x3+x2(1100)x3+x2+1(1101)x3+x2+x(1110)
x3+x2+x+1(1111)
F2^4上的运算举例:
(1101)+(1001)=(0100)
(1101)*(1001)=(1111)(x3+x2+1)*(x3+1)=x6+x5+x2+1(x6+x5+x2+1)mod(x4+x+1)=x3+x2+x+1
(1101)-1=(0100)
x=(0010)是F24的生成元
x1=(0010)x2=(0100)x3=(1000)x4=(0011)
x5=(0110)x6=(1100)x7=(1011)x8=(0101)
x9=(1010)x10=(0111)x11=(1110)x12=(1111)
x13=(1101)x14=(1001)x15=(0001)
模多项式的确定。
ANSIX9.62的两条标准如下:
1.如果在F2上有m次三项本原多项式xm+xk+1,则模多项式应在这些多项式中选取k最小的那个。
2.若不存在那样的多项式,则f(x)应为m次5项本原多项式xm+xk3+xk2+xk1+1。
这时有三条原则:
(1)k3应尽量小。
(2)k3确定时k2应尽量小。
(3)k3,k2确定时,k1应尽量小。
正规基(略)
4、有限域上的椭圆曲线
本节我们将给出椭圆曲线的简要介绍,更详细的内容请参见其他书目。
4.1Fp上的椭圆曲线
P为大于3的奇素数,定义在Fp上的椭圆曲线有如下形式:
y2=x3+ax+b,a,b∈Fp,4a3+27b2≠0modp。
集合E(Fp)包括所有满足方程的(x,y),x∈Fp,y∈Fp,另外还包括一个无穷远点O。
例4.F23上的椭圆曲线y2=x3+x+4,4a3+27b2=22mod23,下面是E(F23)上的除无穷远点之外的所有点:
(0,2)(0,21)(1,11)(1,12)(4,7)(4,16)(7,3)
(7,20)(8,8)(8,15)(9,11)(9,12)(10,5)(10,18)
(11,9)(11,14)(13,11)(13,12)(14,5)(14,18)(15,6)
(15,17)(17,9)(17,14)(18,9)(18,14)(22,5)(22,19)
加法公式。
椭圆曲线上点的加法遵循的规则称之为"
弦切规则"
椭圆曲线上的点及其运算规则即构成椭圆曲线密码系统的基本结构。
加法规则最好用几何方法来描述。
P=(x1,y1),Q=(x2,y2)是曲线E上两个不同的点,P与Q的和R(x3,y3)用以下方法求得:
作过P和Q的割线,这条线与曲线交于第三点,这个点的共轭即是R。
在进行倍点运算时,只需把割线改成切线即可。
由上面的几何描述,可以导出下面的点加和倍点公式。
1.任意P∈E(Fp),P+O=O+P=P。
2.P=(x,y)∈E(Fp),(x,y)+(x,-y)=O。
(点(x,-y)称为-P)
3.P=(x1,y1)∈E(Fp),Q=(x2,y2)∈E(Fp),P≠±
Q,P+Q=R=(x3,y3)。
x3=((y2-y1)/(x2-x1))2-x1-x2y3=((y2-y1)/(x2-x1))(x1-x3)-y1
4.P=(x1,y1)∈E(Fp),P≠-P,2P=(x3,y3)
x3=((3x12+a)/2y1)2-2x1y3=((3x12+a)/2y1)(x1-x3)-y1
想要完成这些计算,就需要定义在Fp上的一系列运算,包括加法、减法、乘法和求逆运算。
例5.例4中椭圆曲线上的点加和倍点。
P=(4,7),Q=(13,11)
P+Q=(15,6)2P=(10,18)
4.2F2m上的椭圆曲线
F2m上的椭圆曲线形式如下:
y2+xy=x3+ax2+b,a,b∈F2m,b≠0。
集合E(F2m)包括所有满足方程的(x,y),x∈F2m,y∈F2m,另外还包括一个无穷远点O。
例6.有限域F24,模多项式f(x)=x4+x+1。
曲线E:
:
y2+xy=x3+?
4x2+1。
下面是曲线上的除无穷远点之外的所有点:
(0,1)(1,?
6)(1,?
13)(?
3,?
8)(?
3,?
5,?
3)
(?
11)(?
6,?
14)(?
9,?
10)(?
10,?
)
12,0)(?
12,?
12)
几何描述与Fp上的椭圆曲线一致。
点加和倍点公式如下:
1.任意P∈E(F2m),P+O=O+P=P。
2.P=(x,y)∈E(F2m),(x,y)+(x,x+y)=O,(x,x+y)称为-P。
3.P=(x1,y1)∈E(F2m),Q=(x2,y2)∈E(F2m),P≠±
x3=((y2+y1)/(x2+x1))2+(y2+y1)/(x2+x1)+x1+x2+ay3=((y2+y1)/(x2+x1))(x1+x3)+x3+y1
4.P=(x1,y1)∈E(F2m),P≠-P,2P=(x3,y3)
x3=x12+b/x12y3=x12+(x1+y1/x1)x3+x3
例7.例6中椭圆曲线上的点加和倍点。
P=(?
8),Q=(?
13)
P+Q=(1,?
13)2P=(?
8)
4.3基本性质
群的阶。
E是Fq上的椭圆曲线。
Hasse定理指出椭圆曲线上的点(包括无穷远点)个数为#E(Fq)=q+1-t,|t|≤2sqrt(q),#E(Fq)就是E的阶,t称为E的迹。
也就是说曲线的阶大致等于基域的尺寸q。
群结构。
E(Fq)是一个秩为1或2的阿贝尔群。
E(Fq)同构于Zn1×
Zn2,n2整除n1。
Zn是n阶循环群。
另外n2整除q-1,若n2=1,则E(Fq)是循环群。
此时E(Fq)同构于Zn1,存在P∈E(Fq),使E(Fq)={kP|0≤k≤n1-1},这个点叫作E(Fq)的生成元。
例8.循环椭圆曲线。
例4中的椭圆曲线E(F23)。
#E(F23)=29,曲线的阶为素数,E(F23)是一个循环群并且除O外的其他点都是生成元。
选取P=(0,2)。
1=(0,2)2=(13,12)3=(11,9)4=(1,12)
5=(7,20)6=(9,11)7=(15,6)8=(14,5)
9=(4,7)10(22,5)11(10,5)12(17,9)
13(8,15)14(18,9)15(18,14)16(8,8)
17(17,14)18(10,18)19(22,18)20(4,16)
21(14,18)22(15,17)23(9,12)24(7,3)
25(1,11)26(11,14)27(13,11)28(0,21)
29O
5、ECDSA域参数
ECDSA的域参数包括一条合适的椭圆曲线和其上一个基点G。
域参数可以全局公开,也可以只对单个用户公开。
5.1部分讲述域参数应该满足的要求,5.2部分讲解如何产生随机曲线,5.3部分介绍了一种产生域参数的方法,5.4部分给出了验证域参数是否符合要求的方法。
5.1域参数
为了提高实现效率,基域尺寸和参数的选择都有限制:
另外,为了抵抗已知的攻击方式,曲线的选择和基点的阶都有一定的限制。
对域的要求。
基域的阶要么q等于p,要么等于2m。
前者模一个大素数p,后者模一个多项式或正规基。
对曲线的要求。
为了抵抗Pollard'
srho和PohligHellman攻击。
E上的点的个数应能被一个大素数n整除。
ANSIX9.62规定n应大于2160和4sqrt(q)。
定义辅因子h=#E(Fq)/n。
选择曲线时应注意的一些其他事项。
为了抵抗MOV和FR攻击,曲线应是非超奇异(即要求p不能整除q+1-#E(Fq))的。
更一般的,应当满足n不能整除qk-1,1≤k≤C,一般取C为20。
最后,为了抵抗SSSA对反常曲线的攻击,不得取反常曲线(即#E(Fq)不得等于q)。
为了抵御上面提到的和将来可能出现的对这些特殊曲线的攻击,应使用随机方式选取一条椭圆曲线满足#E(Fq)能被一个大素数整除,满足上述一系列条件的随机曲线不甚可能被这些攻击方式所攻破。
可以使用随机数发生器(如SHA-1一类的单向函数)来产生曲线的系数。
5.2中介绍了一种类似FIPS-186的模式以产生随机曲线。
概述。
域参数的概述。
1.域尺寸q,q=p或2m。
2.域的表示方法FR和其中元素的表示方法。
3.至少160比特长度的随机比特串。
4.两个域参数a和b。
5.基点G(xG,yG)。
6.点G的阶n>
160bit,n>
4sqrt(q)。
7.辅因子h=#E(Fq)/n。
5.2用随机方法产生椭圆曲线
本节讲述如何用随机方法产生椭圆曲线。
随机参数使用SHA-1来产生。
使用这种方法产生的椭圆曲线具有良好的随机性,可以避免性质较差的曲线的产生。
q=p的情况
下面要使用到这些参数:
t=┌㏒p┐,s=└(t-1)/160┘,v=t-160s
算法1.产生一条随机椭圆曲线。
输入:
域尺寸p。
输出:
至少160比特的比特串,参数a,b,它们确定了一条Fp上的椭圆曲线。
1.选择一个长度g大于160比特的随机比特串SeedE。
2.计算H=SHA-1(SeedE),c0表示H的右起v长比特串。
3.W0是H的左起v长比特串。
4.z是比特串SeedE所表示的整数。
5.forifrom1tosdo
(1)si是(z+i)mod2g的比特串。
(2)计算Wi=SHA-1(si)。
6.W是比特串W0||W1||......||Ws。
7.r是比特串W所表示的整数。
8.若r=0或4r+27=0modp则返回第一步。
9.选择随机整数a,b∈Fp,不能同时为0,要求rb2=a3modp(可以让a,b同时为r)。
10.选定的曲线为y2=x3+ax+b。
11.输出SeedE,a,b。
Fp上的椭圆曲线同构类。
两条定义在Fp上的椭圆曲线E1:
y2=x3+a1x+b1和E2:
y2=x3+a2x+b2在Fp上同构的充要条件是存在u∈Fp使得a1=u4a2,b1=u6b2(同构的椭圆曲线可以认为是相同的,若E1同构于E2,则E1(Fp)同构于E2(Fp))。
若E1同构于E2且b1不为0,则有a13/b12=a23/b22。
奇异椭圆曲线:
y2=x3+ax+b,4a3+27b2=0modp,要么是a,b同时为0,要么是a3/b2=-27/4。
若r∈Fp,r≠0,r≠-27/4,则存在两个曲线同构群E:
y2=x3+ax+b,a3/b2=rmodp。
算法1的第9步中(a,b)就只有两种选择。
第8步中的限制条件确保曲线不是异常曲线。
另外我们注意到算法1产生的曲线不会发生a,b有一个为0而另一个不为0的情况,这无关紧要因为这些曲线只是所有曲线中微不足道的一部分,任何算法都不可能完全随机地来产生曲线。
Fp上的扭曲线。
两条非同构曲线:
E1:
y2=x3+ax+b,E2:
y2=x3+ac2x+bc3,c∈Fp,是一个非模p二次剩余,则称E1,E2相互扭转。
它们的r是相等的。
它们的阶满足:
#E1(Fp)+#E2(Fp)=2p+2,若能计算出其中一条曲线的阶,另一条曲线的阶可轻易得出。
算法2.证明一条曲线是在Fp上随机产生的。
域尺寸p,长度g≥160bit的比特串SeedE,域参数a,b。
1.计算H=SHA-1(SeedE),c0是H的右起v长比特串。
2.W0是H的左起v长比特串。
3.z是比特串SeedE所表示的整数。
4.forifrom1tosdo
5.W是比特串W0||W1||......||Ws。
6.r是比特串W所表示的整数。
7.验证rb2=a3modp是否成立,成立则接受,反之则拒绝。
q=2m的情况
s=└(t-1)/160┘,v=m-160s
算法3:
产生F2m上的一条随机椭圆曲线。
域尺寸2m。
至少160比特的比特串,参数a,b,它们确定了一条F2m上的椭圆曲线。
1.选择一个长度g大于160比特的随机比特串SeedE。
2.计算H=SHA-1(SeedE),b0表示H的右起v长比特串。
4.forifr
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 椭圆 曲线 数字签名 算法
![提示](https://static.bingdoc.com/images/bang_tan.gif)