ElGamal公钥密码体制及安全性

第五章公钥密码ElGamal体制5.4.1ElGamal密码体制5.4.2.ElGamal公钥密码体制的安全性5.4ELGamel公钥密码5.4.1ElGamal公钥密码体制ElGamal公钥密码体制是由T.ElGamal于1985年提出。它至今仍然是一个安全性能良好的公钥密码体制。ElGamal公钥密码体制描述如下：(1)选择大素数,α∈zp*是一个本原元.p和α公开(2)随机选取整数d，1≤d≤p–2，计算ß=αdmodp.ß是公开的加密密钥，d是保密的解秘密钥。(3)明文空间为zp*，密文空间为zp*×zp*.(4)加密变换：对任意明文m∈zp*，秘密随机选取整数k,1≤k≤p–2密文为c=(c1,c2),p其中c1=αkmodp,c2=mßkmodp.(5)解密变换：对任意密文c=(c1,c2)∈zp*×zp*，明文为m=c2(c1d)–1modp.现在我们来证明解密变换能正确的从密文恢复相应的明文。因为c1=αkmodp,c2=mßkmodp,ß=αdmodp,所以c2(c1d)–1≡mßk(αdk)–1(modp)≡mαdk(αdk)–1(modp)α∈zp*≡m(modp).因此，解密变换能正确的从密文恢复相应的明文。5.4.2.ElGamal公钥密码体制的安全性5.4.2.ElGamal公钥密码体制的安全性定义5.9设p是一个素数，是一个本原元，ß∈zp*.已知和ß，求满足的唯一整数n，0≤n≤p–2称为有限域上的离散对数问题。常将n记为.log)(modpn5.4.3有限域上的离散对数的计算方法1.Shanks算法设p是一个素数，α是zp*的生成元，ß∈zp*.令m=p–1.求logαβ的算法描述如下：(1)计算αmjmodp,0≤j≤m–1.(2)将m个有序对(j,αmjmodp)按第二个坐标排序,得到表L1.(3)计算ßα–imodp,0≤i≤m–1.(4)将m个有序对(j,ßα–imodp)按第二个坐标排序,得到表L2.(5)寻找(j,y)∈L1和(j,y)∈L2，它们的第二各坐标相同.(6)计算logaß=mj+imod(p–1).在Shanks算法中，如果(j,y)∈L1,(j,y)∈L2，则αmjmodp=y=ßα–imodp.因此αmj+i=ß,logß=mj+imod(p–1).反过来，因为m=p–1，0≤logß≤p–2,所以存在j和i使得logß=mj+I,其中0≤j,i≤m–1.因此，在算法的第(5)步中，一定可以在表L1和L2中找到第二个坐标相同的一对有序对。aaa由上面的讨论知，Shanks算法能够成功计算logαß.例5.6设p=809.计算log3525.因为α=3，ß=525,m=p–1=29,所以,α29mod809=99.计算有序对(j,99jmod809)，.我们得到下表：(0,1)(1,99)(2,93)(3,308)(4,559)(5,329)(6,221)(7,664)(8,207)(9,268)(10,644)(11,654)(12,26)(13,147)(14,800)(15,727)(16,781)(17,464)(18,632)(19,275)(20,528)(21,496)(22,564)(23,15)(24,676)(25,586)(26,575)(27,295)(28,81)将上表按第二个坐标排序就得到表L1.计算有序对(i,525×(3j)–imod809)，0≤j≤28.我们得到下表：(0,525)(1,175)(2,328)(3,379)(4,396)(5,132)(6,44)(7,554)(8,724)(9,551)(10,440)(11,686)(12,768)(13,256)(14,355)(15,388)(16,399)(17,133)(18,314)(19,644)(20,754)(21,521)(22,713)(23,777)(24,259)(25,356)(26,658)(27,489)(28,163)将上表按第二个坐标排序就得到表L2.查找表L1和L2，我们得到(10,644)∈L1和(19,644)∈L2，他们的第二个坐标相同.因此，log3525=29×10+19=309容易验证，3309≡525(mod809).2.指标计算法p是一个素数，α是zp*的生成元，ß∈zp*.设ß={p1,p2,···pB}是一个“小”素数的集合。指标计算法的基本思想是利用logαpi,1≤i≤B.来计算logαß.现在来考虑如何计算logαß.随机选取s，1≤s≤p–2,使的素因子都在ß中，则我们有即logαß+s≡c1logαp1+c2logαp1+···cBlogαpB(mod(p–1)).在上式中，除了logαß未知外，其它都是已知的.因此，我们可求出logαß.psmod)(mod2121ppppBcBccs例5.7设p=10007,α=5.设ß={2,3,5,7}.显然log55=1.只需计算log52,log53以及log57.选取，计算x=4063,5136,9865,计算54063mod10007=42=2×3×7,55136mod10007=54=2×33,59865mod10007=189=33×7.我们有log52+log53+log57≡4063(mod10006),log52+3log53≡5136(mod10006),3log53+log57≡9865(mod10006).由此可求得log52=6578,log53=6190,log57=1301.设ß=9451.我们来计算log59451.选取s=7736,计算9451×57736mod10007=8400=24×3×52×7.我们得到log59451=4log52+log53+2log55+log57－smod10006=4×6578+6190+2×1+1301－7736mod10006=6057.易验证,56057mod10007=9451.3.Pohlig-Hellman算法设p是一个素数，是zp*的生成元，ß∈zp*.下面我们来介绍求logß的算法。Pohlig-Hellman算法适应于p－1的素因子都是小素数的情况。设其中是素数，1≤i≤k.我们的目的是计算logß，即寻找，0≤≤p－2,使得如能求得i=1,2,···,k,则由中国剩余定理，可求得mod(p－1)，即求得logß。kekeeqqqp21211)(modpaieiqamod首先计算,其中i=1,2,···,k,s=0,1,2,···qi－1.将这些排成一个表L.下面利用表L求,i=1,2,···,k.设其中0≤aj＜qi,0≤j≤ei－1.因为并且由Fermat定理知,mod1110iiieieieiqaqaaqaieiqamod)(modpa)(mod11ppsiq,siq,siq,siq,pisiqpsqmod)1(,所以.因此在表L中一定存在，0≤s0≤qi－1,使得.于是，通过计算，然后与表L中的元s=0,1,2,···qi－1,进行比较，可得.进一步我们来确定.令.)(mod)(mod)1()1()1(0ppaaiiiqpaqpaqp)(mod)(mod)1()1()1(0ppiiiqpaqpaqp0,)(mod)1(iiqqpp0,iq0,sqipiqpmod)1(01asqi,00s1在表L中一定存在，0≤s1≤qi－1，使得于是，通过计算，然后与表L中的元素(s=0,1,2,···,qi－1)进行比较，可得.一般地，假设我们已求得,1≤j≤ei–1.1a1,sqi1,sqi1,sqi1,2mod)1(1sqqpiippiqpmod2)1(111s110,,j令在表L中一定存在，0≤sj≤qi－1，使得)(110jijiqaaqajjijisqqpjp,)1(mod1jisq,于是，通过计算,然后与表L中的元素(s=0,1,2,···qi－1)进行比较，可得αj=sj。由以上讨论，我们可确定，从而求得，由中国剩余定理可求得，即求得.根据目前的计算能力，只有当p-1的素因子是小素数时，才能有效分解p-1求得。因此，Pohlig-Hellman算法适用于p-1的素因子是小素数的情况。例5.8设p=29,则p-1=28=22×7.设α=2,ß=18.求。令.下面我们首先计算jijisqqpjp,)1(mod1sqi,11,0,ieaaaieiqamod)1mod(ploglogalogγ2,0=α0×(p-1)/2mod29=20mod29=1,γ2,1=α1×(p-1)/2mod29=228/2mod29=28.因为ßmod29=1828/2mod29=28=γ2,1,所以=1.令0aß1=ßα-1=18×2-1=9.因为ß1(p-1)/2mod29=928/4mod29=28=γ2,1,所以下面来计算。首先利用γ7，s=as（p-1）/7mod290≤s≤6求得γ7，0=1，γ7，1=16，γ7，2=24，γ7，3=7，γ7，4=25，γ7，5=23，γ7，6=20。因为322mod,11020aaaa07modaa，ß(p-1)/7mod29=1828/7mod29=25=γ7，4所以。因此,最后，由同余方程组根据中国剩余定理可求得。因此求得Z29中Log218=1140a47mod0aa)7(mod4),2(mod32aa)28(mod11a5．5椭圆曲线上的Menezes-Vanstone公钥密码5．5．1有限域上的椭圆曲线椭圆曲线是指由方程y2+a1xy+a3y=x3+a2x2+a4x+a6所确定的平面曲线。也可坐标变换后化为：y2=x3+ax+b定义5.10设p3是一个素数。有限域Zp上的椭圆曲线y2=x3+ax+b是由一个无群远点θ和满足同余方程y2≡x3+ax+b(modp)的点(x,y)∈Zp×Zp组成的集合，其中，a,b∈Zp,4a3+27b2≠0(modp)椭圆曲线E上定义加法如下：对任意P=(x1,y1)∈E,Q=(x2,y2,)∈E,P+Q=θ,如果x1=x2,y1=–y2,P+Q={(x1,y1)否则其中,x3=λ2–x1–x2,.y3=λ(x1–x3)–y1(y2–y1)/(x2–x1)如果P≠Qλ={(3x12+a)/2y1如果P=Q另外，对任意P=(x1,y1)∈E,P+θ=θ+P=P设P和Q是椭圆曲线E上的任意两点，L是连接P和Q的直线。如果P=Q，则L为P点的切线。设L与椭圆曲线E相交于另一点R。过R点做y轴的平行线L’，即L’是过点R和θ的直线。L’与椭圆曲线E相交于另一点，这一点就是P+Q.定理5.15(Hasse定理)设E是有限域Zp上的椭圆曲线，则例5．9设p=11，E是由y2≡x3+x+6(mod11)所确定的有限域Z11上的椭圆曲线。要确定E的点，可以对每个x∈Z11，先计算z≡x3+x+6(mod11)，然后再求同余方程y2≡z(mod11)的解来实现。.2121ppEpp要确定z是一个模P的平方剩余，可用Euler准则来实现，即如果p是一个奇素数，则z是模p的平方剩余当切仅当z(p-1)/2=1modp。当p=3(mod4)时，如果z是模p的平方剩余，则+z(p-1)/4modp=就是z的两个模p平方根，这是因为(+z(p-1)/4)2≡z(p-1)/2(modp)≡zz(p-1)/2(modp)≡z(modp)由上面的讨论，可却顶E中的所有点，结果如表5.1所示。设α=(2,7).我们来计算2α=α+α.先计算λ=(3×22+1)(2×7)-1mod11=2×3-1mod11=2×4mod11=8.于是,x3=82-