資源描述:
《應(yīng)用密碼學(xué)第21講--EIGamal體制與公鑰密碼體制小結(jié)》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、EIGamal體制與公鑰密碼體制小結(jié)數(shù)學(xué)基礎(chǔ)本原元:設(shè)p為素?cái)?shù),若存在一個(gè)整數(shù)a,使得a,a2,a3,……,ap-1,,關(guān)于模p互不同余,則稱模p的本原元。離散對(duì)數(shù)問(wèn)題:Y=logaXX計(jì)算Y是容易的,至多需要2×log2p次運(yùn)算就可以。但是根據(jù)Y計(jì)算X就是困難的,利用目前最好的算法,對(duì)于小心選擇的p將至少需要p1/2次以上的運(yùn)算,只要p足夠的大,求解離散對(duì)數(shù)就是相當(dāng)困難的。EIGamal公鑰密碼體制設(shè)計(jì)過(guò)程:Step1選取大素?cái)?shù)p,再選取的一個(gè)本原元a,并將p和a公開(kāi).Step2隨機(jī)選取整數(shù),并計(jì)算出并將作為
2、公開(kāi)的加密密鑰,將d作為保密的脫密密鑰.加脫密變換加密變換:,秘密選擇一個(gè)整數(shù),則密文為其中脫密變換:對(duì)任意密文明文為實(shí)例P=2597,取a=2,秘密密鑰為765,可以計(jì)算出公開(kāi)密鑰為y=2765mod2597=949。取明文M=1299,隨機(jī)數(shù)k=853,則C1=2853mod2597=435,C2=1299×949853mod2597=2396所以密文為:(C1,C2)=(435,2396)解密時(shí)計(jì)算:M=2396×(435765)-1mod2597=1299特點(diǎn)(1)密文長(zhǎng)度擴(kuò)展1倍;(2)只利用了有限域的
3、乘法群的性質(zhì),即只使用了乘法運(yùn)算和求乘法逆的運(yùn)算為何密文需要擴(kuò)展1倍?這涉及其設(shè)計(jì)思想問(wèn)題.安全性分析因?yàn)樵撍惴ㄊ腔陔x散對(duì)數(shù)問(wèn)題的,所以p的選取必須足夠的大,為150位以上的十進(jìn)制數(shù),且p-1有大素因子為了加密和簽名的安全k必須是一次性的設(shè)計(jì)思想(1)利用Diffie-Hellman密鑰交換協(xié)議生成雙方加密用的密鑰.此時(shí)不同之處在于已將作為公開(kāi)密鑰公布,不需每次發(fā)送.(2)采取了一次一密的加密思想.將作為雙方交換的密鑰,利用它對(duì)明文進(jìn)行加脫密.問(wèn)題為什么要求?答案:因?yàn)榈闹芷跒閜-1,即備注:(1)參數(shù)可以全網(wǎng)
4、公用,也可一人一套;(2)加密不同的明文分組時(shí)選用獨(dú)立的隨機(jī)數(shù),但秘密的脫密密鑰需和其版本號(hào)一起長(zhǎng)期不變.實(shí)現(xiàn)方法(1)大素?cái)?shù)的選擇與構(gòu)造將大素?cái)?shù)p選為安全素?cái)?shù),即使p=2q+1且q為素?cái)?shù).實(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ù)條件下本原元的判斷方法由Fermat定理知,即因而如果則有w整除p-1=2q,因而由q是素?cái)?shù)知,w只能是2或q.此時(shí)是 本原元等價(jià)于且安全素?cái)?shù)條件下本原元的構(gòu)造方法在(p=2q+1)中隨機(jī)選擇一個(gè),若且,則判定是安全素?cái)?shù);否則再隨
5、機(jī)選擇另一個(gè)進(jìn)行檢驗(yàn).問(wèn)題:容易找到本原元嗎?答案:容易,至少在安全素?cái)?shù)條件下容易.習(xí)題在用戶a對(duì)用戶b利用RSA公鑰密碼體制進(jìn)行消息的加密+簽名時(shí),若二者使用的模數(shù)na>nb,為了使脫密正常進(jìn)行,應(yīng)該先加密還是先簽名?