第19講 EIGamal體制

1、eigamaleigamal體制與體制與橢圓曲線橢圓曲線(ecc)(ecc)密碼體制密碼體制數(shù)學(xué)基礎(chǔ)數(shù)學(xué)基礎(chǔ)n本原元：本原元：設(shè)設(shè)p為素?cái)?shù)，若存在一個(gè)整數(shù)為素?cái)?shù)，若存在一個(gè)整數(shù)a，使得，使得a，a2，a3，ap1，關(guān)于模，關(guān)于模p互不同余，則互不同余，則稱模稱模p的本原元。的本原元。n離散對數(shù)問題：離散對數(shù)問題：y=logax x計(jì)算計(jì)算y是容易的，至多需要是容易的，至多需要2log2p次運(yùn)算次運(yùn)算就可以。但是根據(jù)就可以。但是根據(jù)y計(jì)算計(jì)算x就是困難的，利用目就是困難的，利用目前最好的算法，對于小心選擇的前最好的算法，對于小心選擇的p將至少需要將至少需要p1/2次以上的運(yùn)算，只要次以上的運(yùn)算，

2、只要p足夠的大，求解離散足夠的大，求解離散 對數(shù)就是相當(dāng)困難的。對數(shù)就是相當(dāng)困難的。eigamal公鑰密碼體制公鑰密碼體制n設(shè)計(jì)過程設(shè)計(jì)過程:nstep1 選取大素?cái)?shù)p,再選取 的一個(gè)本原元a,并將p和a公開.nstep2 隨機(jī)選取整數(shù) ,并計(jì)算出 并將 作為公開的加密密鑰,將d作為保密的脫密密鑰.21:pdd*pzpdmod加脫密變換n 加密變換加密變換: ,秘密選擇一個(gè)整數(shù), 則密文為其中n脫密變換脫密變換: 對任意密文明文為*pzm21:pkk*21),(ppzzcccpmcpckkmodmod21*21),(ppzzcccpccmdmod)(112實(shí)例實(shí)例np=2597,取a2，秘密密

3、鑰為765，可以計(jì)算出公開密鑰為y2765 mod 2597949。n取明文m1299，隨機(jī)數(shù)k853，則 c12853 mod 2597435， c21299949853 mod 25972396 所以密文為: （c1，c2）（435，2396） 解密時(shí)計(jì)算: m2396(435765)-1 mod 25971299特點(diǎn)(1) 密文長度擴(kuò)展1倍;(2) 只利用了有限域的乘法群的性質(zhì),即只使用了乘法運(yùn)算和求乘法逆的運(yùn)算 為何密文需要擴(kuò)展1倍? 這涉及其設(shè)計(jì)思想問題.安全性分析安全性分析n因?yàn)樵撍惴ㄊ腔陔x散對數(shù)問題的，所以因?yàn)樵撍惴ㄊ腔陔x散對數(shù)問題的，所以p的選取必須足夠的大，為的選取必須足

4、夠的大，為150位以上的十位以上的十進(jìn)制數(shù)，且進(jìn)制數(shù)，且p1有大素因子有大素因子n為了加密和簽名的安全為了加密和簽名的安全k必須是一次性的必須是一次性的設(shè)計(jì)思想n(1) 利用diffie-hellman密鑰交換協(xié)議生成雙方加密用的密鑰.此時(shí)n不同之處在于已將 作為公開密鑰公布,不需每次發(fā)送.n(2) 采取了一次一密的加密思想.n將 作為雙方交換的密鑰,利用它對明文進(jìn)行加脫密.pppdkkdkmodmod)(modpdmodpkmod問題n為什么要求 ?n答案答案: 因?yàn)?的周期為 p-1 ,即n備注備注:n(1) 參數(shù)可以全網(wǎng)公用參數(shù)可以全網(wǎng)公用,也可一人一套也可一人一套;n(2) 加密不同的

5、明文分組時(shí)選用獨(dú)立的隨機(jī)加密不同的明文分組時(shí)選用獨(dú)立的隨機(jī)數(shù)數(shù),但秘密的脫密密鑰需和其版本號一起長但秘密的脫密密鑰需和其版本號一起長期不變期不變.21:pdd1mod1pp實(shí)現(xiàn)方法n(1) 大素?cái)?shù)的選擇與構(gòu)造大素?cái)?shù)的選擇與構(gòu)造n將大素?cái)?shù)p選為安全素?cái)?shù),即使p=2q+1且q為素?cái)?shù).n實(shí)驗(yàn)表明,平均100個(gè)隨機(jī)數(shù)中可選出1個(gè)素?cái)?shù), 平均100素?cái)?shù)中可選出1個(gè)安全素?cái)?shù).(2)安全素?cái)?shù)條件下本原元的判斷方法安全素?cái)?shù)條件下本原元的判斷方法n由fermat定理知 ,即因而如果則有w 整除p-1=2q,因而由q是素?cái)?shù)知,w只能是2或q.此時(shí)是本原元等價(jià)于 且 1mod1pp1mod2pq1mod:0minp

6、twt1mod2p1modpq安全素?cái)?shù)條件下本原元的構(gòu)造方法 n在 ( p=2q+1)中隨機(jī)選擇一個(gè) ,若 且 ,則判定 是安全素?cái)?shù);否則再隨機(jī)選擇另一個(gè)進(jìn)行檢驗(yàn).*pz1mod2p1modpq問題:容易找到本原元嗎容易找到本原元嗎?n答案答案:n容易容易,至少在安全素?cái)?shù)條件下容易至少在安全素?cái)?shù)條件下容易.橢圓曲線橢圓曲線(ecc)密碼體制密碼體制elliptic curve cryptography概述n獲得同樣的安全性，密鑰長度較獲得同樣的安全性，密鑰長度較rsarsa短得短得多多n被被ieeeieee公鑰密碼標(biāo)準(zhǔn)公鑰密碼標(biāo)準(zhǔn)p1363p1363采用采用橢圓曲線n橢圓曲線的曲線方程是以下形

7、式的三次方程橢圓曲線的曲線方程是以下形式的三次方程y y2 2+axy+by=x+axy+by=x3 3+cx+cx2 2+dx+e+dx+ea,b,c,d,ea,b,c,d,e是滿足某些簡單條件的實(shí)數(shù)。定義中包含一個(gè)稱是滿足某些簡單條件的實(shí)數(shù)。定義中包含一個(gè)稱為無窮遠(yuǎn)點(diǎn)的元素，記為為無窮遠(yuǎn)點(diǎn)的元素，記為oo.橢圓曲線加法的定義n如果其上的如果其上的3 3個(gè)點(diǎn)位于同一直線上，那么它個(gè)點(diǎn)位于同一直線上，那么它們的和為們的和為oo。noo為加法單位元，即對為加法單位元，即對eccecc上任一點(diǎn)上任一點(diǎn)p,p,有有p+o=pp+o=pn設(shè)設(shè)p p1 1=(=(x,yx,y) )是是eccecc上一點(diǎn)

8、，加法逆元定義為上一點(diǎn)，加法逆元定義為p p2 2=-p=-p1 1=(=(x,-yx,-y) )np p1 1,p,p2 2連線延長到無窮遠(yuǎn)，得到連線延長到無窮遠(yuǎn)，得到eccecc上另一點(diǎn)上另一點(diǎn)o,o,即即p p1 1,p,p2 2,o,o三點(diǎn)共線，所以三點(diǎn)共線，所以p p1 1+p+p2 2+o=o, p+o=o, p1 1+p+p2 2=o, =o, p p2 2=-p=-p1 1nooooo,o=-oo,o=-o橢圓曲線加法的定義nq,rq,r是是eccecc上上x x坐標(biāo)不同的兩點(diǎn)，坐標(biāo)不同的兩點(diǎn)，q+rq+r定義為：定義為：畫一條通過畫一條通過q,rq,r的直線與的直線與ecce

9、cc交于交于p p1 1( (交點(diǎn)是交點(diǎn)是唯一的，除非做的唯一的，除非做的q,rq,r點(diǎn)的切線，此時(shí)分別點(diǎn)的切線，此時(shí)分別取取p p1 1=q=q或或p p1 1=r)=r)。由。由q+r+pq+r+p1 1=o,=o,得得q+r=-q+r=-p p1 1n點(diǎn)點(diǎn)qq的倍數(shù)定義如下：在的倍數(shù)定義如下：在qq點(diǎn)做點(diǎn)做eccecc的一條切的一條切線，設(shè)切線與線，設(shè)切線與eccecc交于交于s, s,定義定義2q=q+q=-s2q=q+q=-s。類似可定義類似可定義3q=q+q+q,3q=q+q+q, ,n上述加法滿足加法的一般性質(zhì)，如交換律、上述加法滿足加法的一般性質(zhì)，如交換律、結(jié)合律等結(jié)合律等有限

10、域上的橢圓曲線n曲線方程中的所有系數(shù)都是某一有限域曲線方程中的所有系數(shù)都是某一有限域gf(pgf(p) )中的元素中的元素(p(p為一大素?cái)?shù)為一大素?cái)?shù)) )，最為常用的曲線方程為，最為常用的曲線方程為y2=x3+ax+b mod(p) (a,bgf(p),4a3+27b20 mod p)n例：例：p=23,a=b=1, 4a4a3 3+27b+27b2 2=8 =8 0 (mod23),方程為方程為y2=x3+x+1 mod(p)，圖形為連續(xù)圖形。我們感興趣的圖形為連續(xù)圖形。我們感興趣的是在第一象限的整數(shù)點(diǎn)。設(shè)是在第一象限的整數(shù)點(diǎn)。設(shè)ep(a,b)表示表示ecc上點(diǎn)集上點(diǎn)集(x,y)|0 xp

11、,0 yp,x,y)|0 xp,0 yp,且且x,yx,y均為整數(shù)均為整數(shù)并上并上o. 有限域上的橢圓曲線點(diǎn)集產(chǎn)生方法n對每一x(0 xp0 xp且且x x為整數(shù)），計(jì)算為整數(shù)），計(jì)算x x3 3+ax+b +ax+b mod pmod pn決定求出的值在模決定求出的值在模p p下是否有平方根，如果沒下是否有平方根，如果沒有則橢圓曲線上沒有與這一有則橢圓曲線上沒有與這一x x對應(yīng)的點(diǎn)；如果有，對應(yīng)的點(diǎn)；如果有，則求出兩個(gè)平方根。則求出兩個(gè)平方根。ep(a,b)上加法n如果如果p,q p,q e ep p(a,b(a,b) )np+o=pp+o=pn如果如果p p( (x,yx,y), ),則則

12、( (x,y)+(x,-yx,y)+(x,-y) )oonp p(x(x1 1,y,y1 1),q= (x),q= (x2 2,y,y2 2),p),p-q,p+q= (x(x3 3,y,y3 3) )x x3 3=l l2 2-x-x1 1-x-x2 2（mod pmod p）y y3 3=l l(x(x1 1-x-x3 3)-y)-y1 1 (mod p) (mod p)qpyaxqpxxyy121121223l例：例：e23(1,1)np=(3,10),q(=9,7)12, 7(223mod123410)73(623mod73033623mod641205102133:2) 1 , 1

13、()20,17(23mod2016410)173(1123mood11222216339107323223323pyxpeqpyxllecc上的密碼neccecc上的離散對數(shù)問題上的離散對數(shù)問題n在在eccecc構(gòu)成的交換群構(gòu)成的交換群e ep p(a,b(a,b) )上考慮方程上考慮方程qqkpkp，p,qep,qep p(a,b),k(a,b),kp.p.由由k k和和p p求求qq容易，由容易，由p,qp,q求求k k則是困難的。則是困難的。n由由eccecc上離散對數(shù)問題可以構(gòu)造上離散對數(shù)問題可以構(gòu)造diffiediffie- -hellmanhellman密

14、鑰交換和密鑰交換和elgamalelgamal密碼體制密碼體制ecc實(shí)現(xiàn)elgamal密碼體制n選取一條橢圓曲線，得到選取一條橢圓曲線，得到e ep p(a,b(a,b) )。將明文消息通。將明文消息通過編碼嵌入曲線上得到點(diǎn)過編碼嵌入曲線上得到點(diǎn)p pmmn取取e ep p(a,b(a,b) )的生成元的生成元g g， e ep p(a,b(a,b) )和和g g為公開參數(shù)為公開參數(shù)n用戶選取用戶選取n na a為秘密鑰，為秘密鑰，p pa a=n na ag g為公開鑰。為公開鑰。n加密：選隨機(jī)正整數(shù)加密：選隨機(jī)正整數(shù)k k，密文為，密文為c cmm=(=(kg,pkg,pmm+kp+kpa

15、 a) )n解密：解密：p pmm+kp+kpa a-n-na akgkg=p=pmm橢圓曲線密碼體制的優(yōu)點(diǎn)n安全性高安全性高n攻擊有限域上的離散對數(shù)可用指數(shù)積分法，運(yùn)算復(fù)攻擊有限域上的離散對數(shù)可用指數(shù)積分法，運(yùn)算復(fù)雜度為雜度為 。 對對eccecc上離散對數(shù)上離散對數(shù)攻擊并不有效。攻擊并不有效。n攻擊攻擊eccecc上離散對數(shù)問題的方法只有大步小步法，上離散對數(shù)問題的方法只有大步小步法，復(fù)雜度為復(fù)雜度為 。p pmaxmax是是eccecc形成的交形成的交換群的階的最大素因子，因此換群的階的最大素因子，因此eccecc上的密碼體制比上的密碼體制比基于有限域上離散對數(shù)問題的公鑰體制更安全基于有限域上離散對數(shù)問題的公鑰體制更安全32)log)(log(log(expppo)(exp(logmax