曾準(zhǔn)橋工程作業(yè)大

班級08311101 姓名曾準(zhǔn) 學(xué)號1120112060在目前應(yīng)用于實際生活比較廣泛的公鑰加密算法包含有RSA密碼體制和橢圓曲線密碼n=1004995n=5000時，密鑰量是增加到超過1200萬個。DKRB(c)=DKRB(EKUB(m))=mKRB，那么即使知道公鑰KUB、具體的加密與解密算法以及密文，的種類并不多。大整數(shù)分解問[2]和循環(huán)群上的離散對數(shù)問題是設(shè)計公鑰密碼體制常用的兩類數(shù)學(xué)困難問題[3]。比如，RSA的安全性就是基于大整數(shù)的分解問題，E1Gamal的安全性就93年,M.AnshelI.Anhel提出了利用不可解的共軛問題對信息進(jìn)行加密的算法,這也是公鑰密碼算法,其基本思想和第一個基本相似.更進(jìn)一步,在99年I.Anshel,M.Anshel和D.Goldfeld利用辮群的共軛問題實現(xiàn)了一個新的密鑰交換協(xié)議.密碼學(xué)在組合群論中的最新Hyoung.Ko,SangJinLeeJungHeeCheon提出的密鑰交換協(xié)議和加密協(xié)議,他們同樣是利用了辮群的不可解共軛問題,但是主要思想和具體的實現(xiàn)上和I.Anshel等提出的密鑰交RSARSA加密算法是第一個較為完善的公開密鑰算法，它的安全性主要依賴于大數(shù)分解的稱為互為模nb≡a-1modn二．下面介紹RSA選擇一個隨機(jī)數(shù)e,1<e<φ(n)gcd(e,φ(n))=1，并計算d=e-1modφ(n)c=memodnm=cdmodnRSA密碼體制中用到兩個群：群(Zφ(n),·)和群(Zn,（1）群(Zφ(n),ed=1mod),（2）群(Zn,c=memodn與解密運(yùn)算m=cdmodn中的乘法運(yùn)算是在群(Zn,·)中，n=pq。（1）1<e<φ(n)e1≡e2modφ(n)x，有xe1≡xe2modn，因此公鑰e的只需在范圍(1<e<φ(n))中選擇。(m-tn)emodn=memodn，t∈Zm-tn與m的加密結(jié)果相同，這樣使得解密結(jié)果唯一。m必是p和q的倍數(shù)，故也是n的倍數(shù)，這與m<n矛盾。 de=1modφ(n)故存在整數(shù)k滿足 數(shù)a使得m=aq，由歐拉定理： （2）mpq都互素，那么mn證畢。故有：cd≡med=mk·φ(n)+1mmod軟件實現(xiàn)的速度只有DES1/100，512bitRSA軟件實現(xiàn)大約為20KB/s。進(jìn)制表示中只有兩個1，通過設(shè)計優(yōu)良的算法可極大減小運(yùn)算量。如何快速計算ammodc=0;fori=kdownto0 ifbi=1then{c=c+1;d=(d×a)mod則 Miller-Rabin(米勒-拉賓)fori=kdownto0 d←(d×d)modif(d=1)and(x≠1)and(x≠n-1)thenreturnTRUE;ifbi=1thend←(d×a)modn;}ifd≠1thenreturnReturn以(1-2-s)的概率確信n是素數(shù)。RSA算法中兩個用戶的qp相同？素數(shù)定理：不超過p的素數(shù)的個數(shù)大約有p/lnp個。10n3.84×10287方法求得φ(n)d=e-1modφ(n)。一種方法是如果能夠成功將模數(shù)n分解為pq，則根據(jù)公式可得φ(n)=(p-1)(q-1)，從而求得d。針對RSA但是也沒有證明“分解n”的破解方法最容易。算，歷時8個月于19944月分解RSA-130，19964RSA-155，199983.2G中央內(nèi)存的CrayC916計算機(jī)上完成。建議個人用戶使用768bit的n。q-p=k，則(p+q)2-(p-q)2=4pq=4n(p+q)2=4n+k2q-p=kk較小，便可窮舉k解方程得出p,q。（根據(jù)公式：xymodn=x(ymodφ(nmodn）若p-1及q-1的最大公因子很大，ei=1modφ(n)ei=1modφ(n)ci=mmodn速度（c=memodn），降低存儲公鑰的空間。m送給KK>e(e+1)/2m。選型e為163種攻擊，e應(yīng)選擇在其模φ(n)時的階最大，即ei=1modφ(n)中最小的ii=(p-1)(q-1)/2。在智能卡的應(yīng)用中，因其CPU的處理能力低。dd的空間變小。1990Wiener提出一種針對d長度較小的攻擊方法，證明了若dn1/4d?？紤]實際使用和安全性，一般盡量降低e的長度而不應(yīng)降低d的長度。RSAn有很多優(yōu)點(diǎn)：密鑰管理簡單，節(jié)省公鑰的存儲空間，但存在風(fēng)險。modn由擴(kuò)展歐幾里得算法可求得兩個整數(shù)r及s使得rei+sej=1r和s一定有一個負(fù)數(shù)。假設(shè)r為負(fù)，若ci與n互素，則ci乘法逆元存在，并輕易求得ci-1，因此易得明文進(jìn)而分解n。p+qp-q，進(jìn)而可以求出p、q每個RSAm<nc=memodn=m。如0、1、n-1都是不動點(diǎn)。一般來說RSA有(1+gcd(e-1,p-1))(1+gcd(e-1,q-1))個不動點(diǎn)。當(dāng)n較大，e相對較小時，不動點(diǎn)所占比例相當(dāng)?shù)汀７酱螖?shù)。這樣如果能夠監(jiān)視到RSA的解密過程，并對其精確計時，就能算出d來。明文。故在使用RSA進(jìn)行加密前，需要對明文做某種預(yù)處理，一般是進(jìn)行隨機(jī)化的填充，如最優(yōu)非對稱加密填充（OAEP，具體描述可參見標(biāo)準(zhǔn)PKCS#1V2.0。p為素數(shù)，ap的本原根，則在模pamodp,a2modp,a3modp,…,ap-1modp≡logaymodp。上式稱xp下以ay的對數(shù)。Zp*上，所以稱為離散對數(shù)運(yùn)算。a,b為實數(shù)，計算ca,bna=bn，則是一logaymodp非常困難。選取一個大素數(shù)p，a∈Zp*p的一個本原根。隨機(jī)生成一個整數(shù)x，2≤x≤p-2，并計算：y=axmodp。以（p,a,y）作為公鑰，x作為私鑰。c1=akmodpc2=m·ykmod(c1x)-1c1x模pc1=akmodp,c2=m·ykmodp,y=axmodp，所以c2·(c1x)-1=m·yk·(akx)-1=m·akx·(akx)-1=mmodp。次剩余（平方剩余a是模p的二次非剩余（平方非剩余。隨著計算處理能力的不斷提高，對RSA的破解能力不斷增強(qiáng)，使得已得到廣泛應(yīng)用的ECCHealKablitzVictorMiller1985年提出，以高效性著稱，實現(xiàn)了密鑰長度與 ，其中N是 NTRU[10]公鑰密碼體制就是構(gòu)造了截斷多因子分解困難問題的RSA體制和Rabin體制，基于有限域上的離散對數(shù)困難問題的Diffie-Hellman公鑰體制和ElGamalDiffie-Hellman公鑰體制和ElGamalMerkle-Hellman體制和Chor-RivestMeEliece體制，以及基于有限自動機(jī)理論的公鑰體其中最典型的代表是RSA體制(2)ElGamal公鑰密碼體制和影響比較大的橢圓曲線公鑰密碼體制。由于分解大整數(shù)的能力日益增強(qiáng)因此為保證RSA體制的安全202048bits的模長，增大模長所導(dǎo)致的巨大的計算復(fù)雜度帶來了實現(xiàn)上的難度。而基于離散對數(shù)問題的公鑰密碼在目前技術(shù)下512bits模長就能夠160bits的廣泛關(guān)注，國際上已制定了橢圓曲線公鑰密碼標(biāo)準(zhǔn)IEEEP1363[11]。NESSIE(NewEuropeanSchemesforSignatures,Integrity,andEncryption)4次國)10個對稱算法(4個分組密碼，4MAC2Hash函數(shù))3個公鑰密碼算法、3117NESSIE5個是性能良好的正在使用中的標(biāo)準(zhǔn)(1個公鑰密碼算法RSA-KEM)。下面分別概括了NESSIE中涉及一．NESSIEPSEC-KEMNESSIEPSEC(ProvablySecureEllipticCurveEncryption)是日NTT實驗室提出的一個基于橢圓曲線的公鑰加密方案，它的加密消息不需要EC-DDHHashh選用隨機(jī)預(yù)言模型，則PSEC對于自適應(yīng)選擇密文攻擊是可證明安全的。RSA-KEMNESSIE的第2推薦是由RSA算法與最優(yōu)非對稱加密模式(OAEP)組合在RSAJ.JonssonB.Kaliski提ACEEncryptACEAdvancedCryptogra-phicEngineIBM蘇黎士研究室的VictorShoupDiffie-Hellman問題(DDH)、強(qiáng)RSA假設(shè)、Hash函數(shù)等假定下對適應(yīng)選擇密文攻擊是安全的。具有可證明的安全性。EPOCEPOCEfficientProbabilisticPublicKeyEncryption的簡稱，本算法由日本NTT實驗室的TatsuakiOkamoto3個版本：EPOC-1EPOC-2EPOC-3一個概率加密體制，使用了單向陷門函數(shù)(HASH函數(shù))也可使用對稱加密算法。ECIESCerticom公司提交，安全性是基于橢圓曲線上離散對數(shù)問題。1.2.2NESSIE數(shù)字簽名方案(基于公鑰密碼)。RSA-PSS:NESSIE的首選推薦方案。是由RSA歐洲實驗室的JakobJonsson提交，(HFE)HFEV算法和多變量的公特點(diǎn)是簽名長度短只有128bits。CRYPTREC(CryptographyResearchandEvaluationCommittees)[日本]是專為日本構(gòu)筑電子政府推薦密碼技術(shù)而成立的機(jī)構(gòu).評估活動也歷時3年(2001-2003)，活動主要參考了AES的NESSIEISO/IEC國際標(biāo)準(zhǔn)化組織進(jìn)行了協(xié)作。該機(jī)構(gòu)委員由日本著名1CRYPTREC91[15]可以看出其中有部分算法同時也是NESSIE的推薦算法。1CRYPTREC用戶AA的賬戶上給用戶B5000元。銀M是消息的集合，S是簽名的集合，K是密鑰的集合：數(shù)字簽名算法是一個映射sig：M×K→S，s=sigk(m)ANSIX9.30-199x以及美國聯(lián)邦信息處理標(biāo)準(zhǔn)FIPS186-2RSA作為推薦的數(shù)字簽名標(biāo)準(zhǔn)算法1.用戶AM∈Znd假設(shè)用戶B要驗證用戶AMM’=SAemodn其中e為公鑰，通MM’是否相等來確認(rèn)簽名是否確是A所產(chǎn)生，如果不是，拒絕該簽名消息。歐洲NESSIE計劃及日本CRYPTREC計劃的相繼進(jìn)行，以及韓國等一些發(fā)達(dá)國家也不甘同時美國為適應(yīng)技術(shù)發(fā)展的需求也加快了其它密碼標(biāo)準(zhǔn)的更新(SHA-1FIPS140-1)。我國在國家863計劃中也將制定密碼的標(biāo)準(zhǔn)化問題列入了議程。今后，公鑰密碼的重點(diǎn)研究..盧開澄.組合數(shù)學(xué)［M］.2版.盧開澄.計算機(jī)密碼學(xué)［M］.2版.MerkleRC，HellmanM．HidingInformationandSignaturesinTrapdoorKnapsacks[J-]．IEEETransonInformationT