現(xiàn)代密碼學(xué)第七講：公鑰密碼學(xué)2(必修)new

《現(xiàn)代密碼學(xué)第七講：公鑰密碼學(xué)2(必修)new》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、《現(xiàn)代密碼學(xué)》第七章公鑰密碼（二）1上節(jié)內(nèi)容回顧￠公鑰密碼體制的提出及分類￠公鑰密碼體制的基本概念￠單向陷門函數(shù)的概念￠設(shè)計(jì)公鑰加密算法--背包密碼體制本節(jié)主要內(nèi)容￠RSA算法及其分析￠ElGmal算法￠橢圓曲線密碼體制￠其它公鑰密碼算法3RSA算法RSA算法是1978年由R.Rivest,A.Shamir和L.Adleman提出的一種用數(shù)論構(gòu)造的、也是迄今為止理論上最為成熟完善的公鑰密碼體制，該體制已得到廣泛的應(yīng)用。它既可用于加密、又可用于數(shù)字簽字。RSA算法的安全性基于數(shù)論中大整數(shù)分解的困難性。RLRivest,AShamir,LAdleman,"OnDigitalSi

2、gnaturesandPublicKeyCryptosystems",CommunicationsoftheACM,vol21no2,pp120-126,Feb19784RSA算法1.密鑰的產(chǎn)生①選兩個(gè)安全的大素?cái)?shù)p和q。②計(jì)算n=p×q，φ(n)=(p-1)(q-1),其中φ(n)是n的歐拉函數(shù)值。③選一整數(shù)e，滿足1

3、特串分組，使得每個(gè)分組對(duì)應(yīng)的十進(jìn)制數(shù)小于n，即分組長(zhǎng)度小于logn。然后對(duì)每個(gè)明文分組m，作加密運(yùn)算：2c≡memodn6RSA算法3.解密對(duì)密文分組的解密運(yùn)算為：m≡cdmodn證明RSA算法中解密過程的正確性.證明：m與n互素，由加密過程知c≡memodn，所以cdmodn≡medmodn≡mkφ(n)+1modn則由Euler定理得mφ(n)≡1modn,mkφ(n)≡1modn,mkφ(n)+1≡mmodn即cdmodn≡m。7RSA算法例：選p=7，q=17.求得n=p×q=119，φ(n)=(p-1)(q-1)=96.取e=5，滿足1

4、(n),e)=1，計(jì)算滿足d·e=1mod96且小于96的d.因?yàn)?7×5=385=4×96+1，所以d為77，因此公開鑰為{5，119}，秘密鑰為{77，119}.設(shè)明文m=19，則加密過程為c≡195mod119≡2476099mod119≡66;解密過程為m≡6677mod119≡19.8RSA算法的安全性整數(shù)分解問題：已知n是兩個(gè)大素?cái)?shù)的乘積，求n的素分解RSA的安全性是基于分解大整數(shù)困難的假定如果RSA的模數(shù)n被成功地分解為p×q，則獲得φ(n)=(p-1)(q-1)，從而攻擊者能夠從公鑰e解出d，即d≡e-1modφ(n)，攻擊成功.9RSA算法的安全性?至今還

5、未能證明分解大整數(shù)就是NPC問題，也許有尚未發(fā)現(xiàn)的多項(xiàng)式時(shí)間分解算法.?隨著人類計(jì)算能力的不斷提高，原來被認(rèn)為是不可能分解的大數(shù)已被成功分解.例如RSA-129（即n為129位十進(jìn)制數(shù)，大約428個(gè)比特）已在網(wǎng)絡(luò)上通過分布式計(jì)算歷時(shí)8個(gè)月于1994年4月被成功分解，RSA-130已于1996年4月被成功分解.RSA-768has232decimaldigitsandwasfactoredonDecember12,2009byThorstenKleinjung,KazumaroAoki,JensFranke,ArjenK.Lenstra,EmmanuelThomé,Pierr

6、ickGaudry,AlexanderKruppa,PeterMontgomery,JoppeW.Bos,DagArneOsvik,HermanteRiele,AndreyTimofeev,andPaulZimmermann10RSA算法的安全性?分解算法的進(jìn)一步改進(jìn).過去分解算法都采用二次篩法,如對(duì)RSA-129的分解.而對(duì)RSA-130的分解則采用了一個(gè)新算法，稱為推廣的數(shù)域篩法，該算法在分解RSA-130時(shí)所做的計(jì)算僅比分解RSA-129多10%.1）在使用RSA算法時(shí)對(duì)其密鑰的選取要特別注意其大小。估計(jì)在未來一段比較長(zhǎng)的時(shí)期，密鑰長(zhǎng)度介于1024比特至2048比特之

7、間的RSA是安全的.11RSA算法的安全性2）

8、p-q

9、要大222()p++?qp()qp()q由，?=np?=q如果

10、p-q

11、小，444則(p-q)2/4也??；因此(p+q)2/4稍大于n,即(p+q)/2稍大于n1/2。那么①順序檢查大于n1/2的每一整數(shù)x，直到找到一個(gè)x使得x2-n是某一整數(shù)（記為y）的平方。②由x2-n=y2，得n=(x+y)(x-y)，可得n的分解.12RSA算法的安全性3）p-1和q-1都應(yīng)有大素因子設(shè)攻擊者截獲密文c，可如下進(jìn)行重復(fù)加密：e2eeecmm≡≡()()modn223ee