【學習】第19講EIGamal體制

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

2、，只要p足夠的大，求解離散足夠的大，求解離散 對數(shù)就是相當困難的。對數(shù)就是相當困難的。.EIGamal公鑰密碼體制公鑰密碼體制n設(shè)計過程設(shè)計過程:nStep1 選取大素數(shù)p,再選取 的一個本原元a,并將p和a公開.nStep2 隨機選取整數(shù) ,并計算出 并將 作為公開的加密密鑰,將d作為保密的脫密密鑰.21:pdd*pZpdmod.加脫密變換n 加密變換加密變換: ,秘密選擇一個整數(shù), 則密文為其中n脫密變換脫密變換: 對任意密文明文為*pZm21:pkk*21),(ppZZcccpmcpckkmodmod21*21),(ppZZcccpccmdmod)(112.實例實例nP=2597,取a2

3、，秘密密鑰為765，可以計算出公開密鑰為y2765 mod 2597949。n取明文M1299，隨機數(shù)k853，則 C12853 mod 2597435， C21299949853 mod 25972396 所以密文為: （C1，C2）（435，2396） 解密時計算: M2396(435765)-1 mod 25971299.特點(1) 密文長度擴展1倍;(2) 只利用了有限域的乘法群的性質(zhì),即只使用了乘法運算和求乘法逆的運算 為何密文需要擴展1倍? 這涉及其設(shè)計思想問題.安全性分析安全性分析n因為該算法是基于離散對數(shù)問題的，所以因為該算法是基于離散對數(shù)問題的，所以p的選取必須足夠的大，為的

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

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

6、od:0minptwt1mod2p1modpq.安全素數(shù)條件下本原元的構(gòu)造方法 n在 ( p=2q+1)中隨機選擇一個 ,若 且 ,則判定 是安全素數(shù);否則再隨機選擇另一個進行檢驗.*pZ1mod2p1modpq.問題:容易找到本原元嗎容易找到本原元嗎?n答案答案:n容易容易,至少在安全素數(shù)條件下容易至少在安全素數(shù)條件下容易.橢圓曲線橢圓曲線(ECC)密碼體制密碼體制Elliptic Curve Cryptography.概述n獲得同樣的安全性，密鑰長度較獲得同樣的安全性，密鑰長度較RSARSA短得短得多多n被被IEEEIEEE公鑰密碼標準公鑰密碼標準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ù)。定義中包含一個稱為無窮遠點的元素，記為為無窮遠點的元素，記為OO.橢圓曲線加法的定義n如果其上的如果其上的3 3個點位于同一直線上，那么它個點位于同一直線上，那么它們的和為們的和為OO。nOO為加法單位元，即對為加法單位元，即對ECCECC上任一點上任一點P,P,有有P+O=PP+O=Pn設(shè)設(shè)P P1 1=(x,y)=(x,y)

8、是是ECCECC上一點，加法逆元定義為上一點，加法逆元定義為P P2 2=-P=-P1 1=(x,-y)=(x,-y)nP P1 1,P,P2 2連線延長到無窮遠，得到連線延長到無窮遠，得到ECCECC上另一點上另一點O,O,即即P P1 1,P,P2 2,O,O三點共線，所以三點共線，所以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坐標不同的兩點，坐標不同的兩點，Q+RQ+R定義為：定義為：畫一條通過畫一條通過Q,RQ,R的

9、直線與的直線與ECCECC交于交于P P1 1( (交點是交點是唯一的，除非做的唯一的，除非做的Q,RQ,R點的切線，此時分別點的切線，此時分別取取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點點QQ的倍數(shù)定義如下：在的倍數(shù)定義如下：在QQ點做點做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é)

10、合律等結(jié)合律等.有限域上的橢圓曲線n曲線方程中的所有系數(shù)都是某一有限域曲線方程中的所有系數(shù)都是某一有限域GF(p)GF(p)中的元素中的元素(p(p為一大素數(shù)為一大素數(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ù)點。設(shè)是在第一象限的整數(shù)點。設(shè)Ep(a,b)表示表示ECC上點集上點集(

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

12、x,y),則則(x,y)+(x,-y)(x,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)

13、1 , 1 ()20,17(23mod2016410)173(1123mood11222216339107323223323PyxPEQPyxll.ECC上的密碼nECCECC上的離散對數(shù)問題上的離散對數(shù)問題n在在ECCECC構(gòu)成的交換群構(gòu)成的交換群E Ep p(a,b)(a,b)上考慮方程上考慮方程QQkPkP，P,QEP,QEp p(a,b),kp.(a,b),kp.由由k k和和P P求求QQ容易，由容易，由P,QP,Q求求k k則是困難的。則是困難的。n由由ECCECC上離散對數(shù)問題可以構(gòu)造上離散對數(shù)問題可以構(gòu)造Diffie-Diffie-HellmanHel

14、lman密鑰交換和密鑰交換和ElgamalElgamal密碼體制密碼體制.ECC實現(xiàn)Elgamal密碼體制n選取一條橢圓曲線，得到選取一條橢圓曲線，得到E Ep p(a,b)(a,b)。將明文消息通。將明文消息通過編碼嵌入曲線上得到點過編碼嵌入曲線上得到點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加密：選隨機正整數(shù)加密：選隨機正整數(shù)k k，密文為，密文為C Cmm=(kG,P=(kG,Pmm+kP+

15、kPA A) )n解密：解密：P Pmm+kP+kPA A-n-nA AkG=PkG=Pmm.橢圓曲線密碼體制的優(yōu)點n安全性高安全性高n攻擊有限域上的離散對數(shù)可用指數(shù)積分法，運算復攻擊有限域上的離散對數(shù)可用指數(shù)積分法，運算復雜度為雜度為 。 對對ECCECC上離散對數(shù)上離散對數(shù)攻擊并不有效。攻擊并不有效。n攻擊攻擊ECCECC上離散對數(shù)問題的方法只有大步小步法，上離散對數(shù)問題的方法只有大步小步法，復雜度為復雜度為 。p pmaxmax是是ECCECC形成的交形成的交換群的階的最大素因子，因此換群的階的最大素因子，因此ECCECC上的密碼體制比上的密碼體制比基于有限域上離散對數(shù)問題的公鑰體制更安全基于有限域上離散對數(shù)問題的公鑰體制更安全32)log)(log(log(expppO)(exp(logmaxpO