1、 課程設計報告-RSA算法實現(xiàn)院 （系）： 專 業(yè)：班 級： 學 生：學 號： 指導教師：2012年10月10日 目 錄1. RSA算法介紹與應用現(xiàn).32. 算法原理.33. RSA算法數(shù)論基礎.43.1.單向和陷門單向函數(shù).43.2.同余及模運算.43.3.歐拉函數(shù)、歐拉定理和費爾馬定理.53.4.乘法逆元及其求法.5.4. RSA算法的各環(huán)節(jié).64.1.RSA公鑰加密解密概述.64.2. RSA簽名算法64.3.大數(shù)運算處理.74.4.大素數(shù)的產(chǎn)生.85. RSA的安全性.86. 代碼實現(xiàn)：.107. RSA算法結(jié)果分析.157.1.主界面初始化157.2.設置密鑰.157.3.對明文加密

2、167.4.對密文解密178. 總結(jié)與展望.179. 參考文獻181.RSA算法介紹與應用現(xiàn)狀RSA公開密鑰加密算法自20世紀70年代提出以來，已經(jīng)得到了廣泛認可和應用。發(fā)展至今，電子安全領(lǐng)域的各方面已經(jīng)形成了較為完備的國際規(guī)范。RSA作為最重要的公開密鑰算法，在各領(lǐng)域的應用數(shù)不勝數(shù)。RSA在硬件方面，以技術(shù)成熟的IC應用于各種消費類電子產(chǎn)品。RSA在軟件方面的應用，主要集中在Internet上。加密連接、數(shù)字簽名和數(shù)字證書的核心算法廣泛使用RSA。日常應用中，有比較著名的工具包Open SSL(SSL，Security Socket Layer,是一個安全傳輸協(xié)議，在Internet上進行數(shù)

3、據(jù)保護和身份確認。Open SSL是一個開放源代碼的實現(xiàn)了SSL及相關(guān)加密技術(shù)的軟件包，由加拿大的Eric Yang等發(fā)起編寫的。Open SSL應用RSA實現(xiàn)簽名和密鑰交換，已經(jīng)在各種操作系統(tǒng)得到非常廣泛的應用。另外，家喻戶曉的IE瀏覽器，自然也實現(xiàn)了SSL協(xié)議，集成了使用RSA技術(shù)的加密功能，結(jié)合MD5和SHA1，主要用于數(shù)字證書和數(shù)字簽名，對于習慣于使用網(wǎng)上購物和網(wǎng)上銀行的用戶來說，幾乎天天都在使用RSA技術(shù)。RSA更出現(xiàn)在要求高度安全穩(wěn)定的企業(yè)級商務應用中。在當今的企業(yè)級商務應用中，不得不提及使用最廣泛的平臺j2ee。事實上，在j2se的標準庫中，就為安全和加密服務提供了兩組API：J

4、CA和JCE。 JCA (Java Cryptography Architecture)提供基本的加密框架，如證書、數(shù)字簽名、報文摘要和密鑰對產(chǎn)生器； JCA由幾個實現(xiàn)了基本的加密技術(shù)功能的類和接口組成，其中最主要的是java.security包，此軟件包包含的是一組核心的類和接口，Java中數(shù)字簽名的方法就集中在此軟件包中。JCE(Java Cryptography Extension) 在JCA的基礎上作了擴展，JCE也是由幾個軟件包組成，其中最主要的是javax.crypto包，此軟件包提供了JCE加密技術(shù)操作API。javax.crypto中的Cipher類用于具體的加密和解密。在上述

5、軟件包的實現(xiàn)中，集成了應用RSA算法的各種數(shù)據(jù)加密規(guī)范(RSA算法應用規(guī)范介紹參見： /rsalabs/node.asp?id=2146 ，這些API內(nèi)部支持的算法不僅僅只有RSA，但是RSA是數(shù)字簽名和證書中最常用的)，用戶程序可以直接使用java標準庫中提供的API進行數(shù)字簽名和證書的各種操作。單機應用程序使用RSA加密尚比較少見，例如使用RSA加密任意一個文件。RSA算法可以簡單敘述如下：取素數(shù)p，q，令n=pq.取與(p-1)(q-1)互素的整數(shù)e，由方程de=1 (mod (p-1)(q-1)解出d，二元組(e,n)作為公開密鑰，二元

6、組(d,n)作為私有密鑰b=ae mod n，c=bd mod n.2.算法原理1選擇兩個不同的大素數(shù)p、q (目前兩個數(shù)的長度都接近512bit是安全的）；2. 計算n = p*q。 3. 計算n的歐拉函數(shù) t=(p-1)(q-1)。4. 選擇整數(shù)e作為公鑰，使e與t互素，且1e t。5. 用歐幾里得算法計算d作為私鑰,使d*e=1 mod t。6. 加密：C=Me mod n7. 解密：MCd mod n=(Me)d mod n= Med mod n。3.RSA算法數(shù)論基礎RSA算法的數(shù)學理論基礎在密碼學中需要使用到許多數(shù)學理論，例如數(shù)論、信息論、復雜度理論等， 它們是設計密碼系統(tǒng)及協(xié)議不

7、可或缺的工具，其中數(shù)論是密碼學中(尤其是公開密鑰密碼系統(tǒng)中)最重要的數(shù)學基礎，因此有必要對有關(guān)數(shù)論理論做一介紹。下面介紹RSA算法的數(shù)學基礎知識。3.1單向和陷門單向函數(shù)RSA的安全性主要取決于構(gòu)造其加密算法的數(shù)學函數(shù)的求逆困難性，這同大多數(shù)公鑰密碼系統(tǒng)一樣(譬如EIGamal算法就是基于離散對數(shù)問題的困難性)，我們稱這樣的函數(shù)為單向函數(shù)。單向函數(shù)不能直接用作密碼體制，因為如果用單向函數(shù)對明文進行加密，即使是合法的接收者也不能還原出明文，因為單向函數(shù)的逆運算是困難的。與密碼體制關(guān)系更為密切的陷門單向函數(shù)，即函數(shù)及其逆函數(shù)的計算都存在有效的算法，而且可以將計算函數(shù)的方法公開。單向和陷門單向函數(shù)的

8、概念是公鑰密碼學的核心，它對公鑰密碼系統(tǒng)的構(gòu)造非常重要，甚至可以說公鑰密碼體制的設計就是陷門單向函數(shù)的設計。定義2. 1：令函數(shù)f是集合A到集合B的映射，以f：AB表示。若對任意x1x2，x1,x2A，有f(x1)f(x2)，則稱f為1一l映射，或可逆函數(shù)。定義2. 2：一個可逆函數(shù)廠，若它滿足： 1對所有XA，易于計算f(x)； 2對“幾乎所有xA，由f(x)求x“極為困難”，以至于實際上不可能做到。則稱f為單向函數(shù) (One-way function) 上述定義中的“極為困難”是對現(xiàn)有計算機能力和算法而言的，Massey稱此為視在困難性，相應的函數(shù)稱之為視在單向函數(shù)。以此來和本質(zhì)上的困難性

9、相區(qū)分。目前，還沒有人能夠從理論上證明單向函數(shù)是存在的。3.2同余及模運算同余：假定有三個整數(shù)a，b，n(n0)，當我們稱a在模n時與b同余，是指當且僅當a與b的差為n的整數(shù)倍，即a-b=kn，其中k為任一整數(shù)。若a與b在模n中同余， 我們可寫為a b(mod n)或n l(a-b)。剩余類(Residue Class)：很明顯地，利用同余概念，所有整數(shù)在模n中被分成n個不同的剩余類；為n所整除的數(shù)(即余數(shù)為0)為一剩余類，被n所除余數(shù)為1的數(shù)為另一剩余類，余2的數(shù)又為一剩余類，以此類推。完全剩余系(Complete Set of Residues)：若將每一剩余類中取一數(shù)為代表，形成一個集合

10、，則此集合稱為模n的完全剩余系，以Zn表示。很明顯地，集合(0，l， 2，n-1為模n的一完全剩余系。從0到n-1的整數(shù)組成的集合構(gòu)成了模n的“完全剩余系”。這意味著，對每一個整數(shù)a，它的模n剩余是從0到n-1之間的某個整數(shù)。所謂運算a mod n表示求a被n除的余數(shù)，成為模運算。既約剩余系(Reduced Set of Residues)：在模n的完全剩余系中，若將所有與n 互素的剩余類形成一個集合，則稱此集合為模n的既約剩余系，以Zn表示。例如n=10時，0，1，2，3，4，5，6，7，8，9)為模10的完全剩余系；而1，3，7，9)為模10的既約剩余系。3.3歐拉函數(shù)、歐拉定理和費爾馬定

11、理歐拉函數(shù)(n)：是一個定義在正整數(shù)上的函數(shù)，其值等于序列0，1，2，3， n-1 中與n互素的數(shù)的個數(shù)。即fn為模n既約剩余系中所有元素的個數(shù)。由定義知，當P是素數(shù)時， (p)=P-1。定理21歐拉定理：若m，a為正整數(shù)，有g(shù) c d(a，m)=l(g c d，Greatest Common Divisor，最大公約數(shù))，則a(m) (mod m)。其中m稱為歐拉函數(shù)，它是比m小但與m互素的正整數(shù)個數(shù)。歐拉定理也有一種等價形式：a(m)+1 =a(mod m)。 定理22設P和q是兩個不同的素數(shù)，n=pq，則(n)=(p-1)(q-1)，對任意的xZn及任意的非負整數(shù)k，有x k(n)+1x

12、 (mod n)。定理3費爾馬定理：如果P是素數(shù)，且g c d(m ,p)=l(可表示為(m , p)=1)， 則mp-1l(mod p)，費爾馬定理還存在另一種等價形式：如果P是素數(shù)，m是任意正整數(shù)，則mpm(mod p)。對于素數(shù)P來說， (p)=p-1，所以費爾馬定理實際是歐拉定理的一個推論。費爾馬定理和歐拉定理及其推論在構(gòu)成了RSA算法的主要理論基礎。3.4乘法逆元及其求法乘法逆元的定義：若a bl(mod n)，則稱b為a在模n的乘法逆元，b可表示為a-1。利用Euclid(歐幾里德)算法(輾轉(zhuǎn)相除法)求乘法逆元：己知a及n且(a ,n) =1，求a a l=1(mod n)。歐幾里

13、德算法是古希臘數(shù)學家歐幾里德給出的求兩個自然數(shù)的最大公約數(shù)的方法，如果(a，n)=1，則b一定存在。首先介紹利用歐幾里德算法求g c d(a，n)的方法，再介紹求乘法逆元的方法。令r0=n，r l=a，an，利用輾轉(zhuǎn)相除法可得r0=r1+g1+r2 0r2 r l r1=r2g2+r3 0r3r 2 : :rj-2=r j-l g j-1+rj 0r jr j-1 rm-3=rm-2 gm-2+rm-1 0rm-1rm-2 rm-2=rm-1 gm-1+rm 0r mrm-1 rm-1= r m gm 則r m為a及n的最大公因子。(歐幾里德算法求g c d的主要概念在于：若c=d g + r

14、， 則(c，d)=(d，r)。因此在上述算法中，(a，n)=(r0，r1) =(r l，r2)= (r(m-1)，r m)=(r m，o)=r m。可以通過舉例說明利用歐幾里德算法求逆元的方法，如：求1001b=lmod 3837， b是1001關(guān)于模3837的乘法逆元。因為(1001，3837)=l，而3837=31001+834 1001=1834+1 67 834=4167+166 167=1 166+1所以l=167166=167-(834-4167)=5167834 =5(1001834)一834 =51001-6834 =51001-6(383731001) =23 1001-63

15、837 因此231001l(mod 3837)，故1001關(guān)于模3837的乘法逆元為23。一般求乘法逆元以歐幾里德算法為佳。4.RSA算法的各環(huán)節(jié)RSA算法是1978年由R.L.Rivest，A.Shamir和L.Adleman提出的一種用數(shù)論構(gòu)造的、也是迄今為止理論上最為成熟完善的公鑰密碼體制。RSA的理論基礎是數(shù)論中的歐拉定理,它的的安全性依賴于大數(shù)的因子分解，但并沒有從理論上證明破譯RSA的難度與大數(shù)分解難度等價。4.1 RSA公鑰加密解密概述RSA算法采用下述加密/解密變換。1密鑰的產(chǎn)生選擇兩個保密的大素數(shù)P和q。計算N=p q，(N) =(p-1)(g-1)，其中(N)是N的歐拉函數(shù)

16、值。選擇一個整數(shù)e，滿足le(N)，且g c d(N)，e)1。計算私鑰d(解密密鑰)，滿足e dl(mod(N)，d是e在模(N)下的乘法逆元。 以(e, n)為公鑰，(d ,N)為密鑰，銷毀p，q，(N)。2加密加密時首先將明文比特串進行分組，使得每個分組對應得串在數(shù)值上小于N， 即分組的二進制長度小于l092N。然后，對每個明文分組M，作加密運算： C=E k(M)=M e mod N 3解密對密文分組的解密運算為：M=D k (C) =C d mod N 由定理1和定理2可以證明解密運算能恢復明文M 4.2 RSA簽名算法并非所有的公開密鑰系統(tǒng)，均可同時達到秘密性與數(shù)字簽名功能。一般而

17、言， 一公開密鑰系統(tǒng)若作為密碼系統(tǒng)，則無法作為數(shù)字簽名，反之亦然。只有很少數(shù)的系統(tǒng)可同時作為密碼系統(tǒng)和數(shù)字簽名，如本文討論的RSA系統(tǒng)。RSA簽名算法如下： 設N=p q，且p和q是兩個大素數(shù)，e和d滿足e dl(mod (N)。公開密鑰：N，e 私有密鑰：d 簽名過程：發(fā)送方使用自己的私鑰d對明文m進行數(shù)字簽名變換： y=x d mod N：并將加密后的消息和簽名y發(fā)送給接收方； 驗證過程：接收方使用發(fā)送方的公鑰e對收到的消息y進行數(shù)字簽名驗證變換x=ye mod N，并使用發(fā)送方的密鑰解密恢復消息x，比較x與x，如果x=x則證實發(fā)送方的身份合法。這樣，用戶A若想用RSA簽名方案對消息x簽名

18、，他只需公開他的公鑰N和e，由于簽名算法是保密的，因此A是唯一能產(chǎn)生簽名的人，任何要驗證用戶A 簽名的用戶只需查到A的公鑰即可驗證簽名。對于實現(xiàn)簽名和公鑰加密的組合，常用方法是：假定通信雙方為A和B。對于明文x，A計算他的簽名y=x d mod N，然后利用B的公開加密函數(shù)EB對信息對(x, y)加密得到Z，將密文Z傳送給B，當B收到密文Z后，他首先用他的解密函數(shù)DB來解密得到(x，y)=DB (Z)= DB (EB(x，y)，然后利用A的驗證算法來檢查x=x=y e mod N是否成立。4.3 大數(shù)運算處理 RSA依賴大數(shù)運算，目前主流RSA算法都建立在1024位的大數(shù)運算之上。而大多數(shù)的編

19、譯器只能支持到64位的整數(shù)運算，即我們在運算中所使用的整數(shù)必須小于等于64位，即：0xffffffffffffffff也就是，這遠遠達不到RSA的需要，于是需要專門建立大數(shù)運算庫來解決這一問題。最簡單的辦法是將大數(shù)當作數(shù)組進行處理，數(shù)組的各元素也就是大數(shù)每一位上的數(shù)字，通常采用最容易理解的十進制數(shù)字09。然后對“數(shù)字數(shù)組”編寫加減乘除函數(shù)。但是這樣做效率很低，因為二進制為1024位的大數(shù)在十進制下也有三百多位，對于任何一種運算，都需要在兩個有數(shù)百個元素的數(shù)組空間上多次重循環(huán)，還需要許多額外的空間存放計算的進退位標志及中間結(jié)果。另外，對于某些特殊的運算而言， 采用二進制會使計算過程大大簡化，而這

20、種大數(shù)表示方法轉(zhuǎn)化成二進制顯然非常麻煩，所以在某些實例中則干脆采用了二進制數(shù)組的方法來記錄大數(shù)，當然這樣效率就更低了。一個有效的改進方法是將大數(shù)表示為一個n進制數(shù)組，對于目前的32位系統(tǒng)而言n可以取值為2的32次方，即0x，假如將一個二進制為1024位的大數(shù)轉(zhuǎn)化成0x進制，就變成了32位，而每一位的取值范圍不再是二進制的0 1或十進制的09，而是00xffffffff我們正好可以用一個32位的DWORD(如：無符號長整數(shù)，unsigned long)類型來表示該值。所以1024位的大數(shù)就變成一個含有32個元素的DWORD數(shù)組，而針對DWORD 數(shù)組進行各種運算所需的循環(huán)規(guī)模至多32次而已。例如

21、大數(shù)1 09551 61 5，等于0Xffffffff ffffffff其表示方式就相當于十進制的99：有兩位，只是每位上的元素不是9而都是0xffffffff。而等于0x ，就相當于十進制的100：有三位，第一位是l，其它兩位都是0，如此等等。在實際應用中，“數(shù)字數(shù)組的排列順序采用低位在前高位在后的方式，這樣，大數(shù)A就可以方便地用數(shù)學表達式來表示其值： X=Xi r i (r=0x，0Xi r) 任何整數(shù)運算最終都能分解成數(shù)字與數(shù)字之間的運算，在Oxl進制下其“數(shù)字最大達到Ox靦筒，其數(shù)字與數(shù)字之間的運算，結(jié)果也必然超出了目前32位系統(tǒng)的字長。在VC+中，存在一個int64類型可以處理64位

22、的整數(shù)，所以不用擔心這一問題，而在其它編譯系統(tǒng)中如果不存在64位整形，就需要采用更小的進制方式來存儲大數(shù)，例如16位的WORD類型可以用來表示0x10000進制。但效率更高的辦法還是采用32位的DWORD類型。4.4 大素數(shù)的產(chǎn)生根據(jù)RSA算法的加解密變換，需要產(chǎn)生兩個保密的大素數(shù)作為基礎運算。在2000年前歐幾里德證明了素數(shù)有無窮多個，這自然的就引出一個問題：既然素數(shù)有無窮個，那么是否有一個計算素數(shù)的通項公式?兩千年來，數(shù)論學的一個重要任務，就是尋找一個可以表示全體素數(shù)的素數(shù)普遍公式。為此，人類耗費了巨大的心血。希爾伯特認為，如果有了素數(shù)統(tǒng)一的素數(shù)普遍公式，那么這些哥德巴赫猜想和孿生素數(shù)猜想

23、都可以得到解決。“研究各種各樣的素數(shù)分布狀況，一直是數(shù)論中最重要和最有吸引力的中心問題之一。關(guān)于素數(shù)分布性質(zhì)的許多著名猜想是通過數(shù)值觀察計算和初步研究提出的，大多數(shù)至今仍未解決”。因此，欲得到素數(shù)，必須另尋出路。大素數(shù)的產(chǎn)生應是現(xiàn)代密碼學應用中最重要的步驟。幾乎所有的公開密鑰系統(tǒng)均需要用到大的素數(shù)，若此素數(shù)選用不當，則此公開密鑰系統(tǒng)的安全性就岌岌可危。一般而言，素數(shù)的產(chǎn)生通常有兩種方法，一為確定性素數(shù)產(chǎn)生方法，一為概率性素數(shù)產(chǎn)生方法，目前后者是當今生成素數(shù)的主要方法。所謂概率性素數(shù)產(chǎn)生法，是指一種算法，其輸入為一奇數(shù)，輸出為兩種狀態(tài)YES或NO之一。若輸入一奇數(shù)n，輸出為NO，則表示11為合數(shù)

24、，若輸出為YES，則表示n為素數(shù)的概率為1-r，其中r為此素數(shù)產(chǎn)生法中可控制的任意小數(shù)，但不能為0。此類方法中較著名的有Solovay-Strassen算法、Lehmann算法、Miller-Rabin算法等。在實際應用中，一般做法是先生成大的隨機整數(shù)，然后通過素性檢測來測試其是否為素數(shù)。數(shù)論學家利用費爾馬定理研究出了多種素數(shù)測試方法，目前最快的算法是Miller-Rabin(拉賓米勒)測試算法(也稱為偽素數(shù)檢測)，其過程如下：首先選擇一個待測的隨機數(shù)N計算r，2r是能夠整除N-1的2的最大冪數(shù)。1計算M，使得N=2rM+1。2選擇隨機數(shù)AN。3若AM mod N =l，則N通過隨機數(shù)A的測試

25、。4讓A取不同的值對N進行5次測試，若全部通過則判定N為素數(shù)。若N通過一次測試，則N為合數(shù)(非素數(shù))的概率為25，若N通過t次測試，則為合數(shù)(非素數(shù))的概率為14t。事實上取t為5時，N為合數(shù)的概率為1128，N為素數(shù)的概率已經(jīng)大于9999。5. RSA的安全性密碼學所討論的系統(tǒng)，其安全性是最高的評價準則。再好的密碼系統(tǒng)，若安全性不足則一文不值，同時，密碼系統(tǒng)的安全性很難用理論證明(事實上證明一個安全系統(tǒng)是安全的很難，但若該系統(tǒng)不安全，證明它是不安全的則很容易). RSA從提出到現(xiàn)在已近二十年，經(jīng)歷了各種攻擊的考驗，逐漸為人們接受，普遍認為是目前最優(yōu)秀的公鑰方案之一。但是在特定的條件下，RSA

26、實現(xiàn)細節(jié)的疏忽會導致對RSA算法的有效攻擊。因此，對RSA體制實現(xiàn)的各個環(huán)節(jié)進行充分考慮，避免安全性缺陷是非常有必要的。RSA的安全性分析:理論上，RSA的安全性取決于因式分解模數(shù)N的困難性。從嚴格的技術(shù)角度上來說這是不正確的，在數(shù)學上至今還未證明分解模數(shù)就是攻擊RSA的最佳方法， 也未證明分解大整數(shù)就是NP問題(表示那些能在多項式時間內(nèi)利用“不確定性 圖靈機可以求解的問題)。事實情況是，大整數(shù)因子分解問題過去數(shù)百年來一直是令數(shù)學家頭疼而未能有效解決的世界性難題。人們設想了一些非因子分解的途徑來攻擊RSA體制，但這些方法都不比分解n來得容易。因此，嚴格地說，RSA的安全性基于求解其單向函數(shù)的逆

27、的困難性。RSA單向函數(shù)求逆的安全性沒有真正因式分解模數(shù)的安全性高，而且目前人們也無法證明這兩者等價。許多研究人員都試圖改進RSA體制使它的安全性等價于因式分解模數(shù)。對RSA算法的攻擊主要有以下幾種： 1對分解模數(shù)N的攻擊分解模數(shù)N是最直接也是最顯然的攻擊目標，同時也是最困難的。攻擊者可以合法的獲得公開密鑰e和模數(shù)N；如果N=p q被因式分解，則攻擊者通過p、q便可計算出(N)=(p-1)(q-1)，進而e dl(mod (N)而得到解密密鑰d，大整數(shù)分解研究一直是數(shù)論與密碼理論研究的重要課題。2對RSA的選擇密文攻擊選擇密文攻擊是攻擊者對RSA等公鑰算法最常用的攻擊，也是最有效的攻擊手段之一

28、。選擇密文攻擊通常是由RSA加密變換的性質(zhì)誘發(fā)的，常見的對RSA的選擇密文攻擊有三種： 明文破譯。攻擊者獲得某用戶A使用公鑰e加密的密文y=x e (mod n)，并試圖恢復出消息x。隨機選取rn，計算y1=r e (mod n )，這意味，r=y1d(mod n)。計算y2=(yy1)(mod n)。令t=r-1 (mod n )，則t=y1d(mod n )，現(xiàn)在攻擊者請A對消息y2，進行簽名，得到S=y2d (mod n)。攻擊者計算t l=t s=(y1-d y2d)(mod n)=(y1-dy1dyd)(mod n)= yd (mod n)=x，得到明文。騙取仲裁簽名。在有仲裁情況下

29、，若某用戶A有一個文件要求仲裁，可先將其送給仲裁T，T使用RSA的解密密鑰進行簽名后送給A。攻擊者有一個消息想要T簽名，因為由于可能有偽造的時戳或來自非法使用者的消息，T并不簽名。但攻擊者可用下述方法獲得T的簽名。令攻擊者的消息為X，他首先任選一個數(shù)N， 計算y=Ne (mod n)(e是T的公鑰)，然后計算M=y x，送給T，T將簽名結(jié)果M d mod n送給攻擊方，則有： M d N一1(y x)d N-1(x d y d N-1)x d NN-1x d(mod n)攻擊者成功騙取T對x的簽名。偽造合法簽名。攻擊者利用自己偽造的兩個消息x1和x2，來拼湊所需要的x3=(x1x2)(mod

30、n)。攻擊者如果得到用戶A對而和x2的簽名x1d(mod n)和x2d(mod n)，就可以計算屯的簽名，x3d=(x1d(mod n)(x2d(mod n)(mod n)。3對RSA小指數(shù)攻擊這類攻擊專門針對RSA算法實現(xiàn)的細節(jié)。采用小的e、d可以加快加密和驗證簽名的速度，而且所需的存儲空間小，但是如果e、d太小，則容易受到小指數(shù)攻擊，包括低加密指數(shù)攻擊和低解密指數(shù)攻擊。通過獨立隨機數(shù)字對明文消息x進行填充，這樣使得x e(mod n)xe，可以有效地抗擊小指數(shù)攻擊。4對RSA共模攻擊在RSA公鑰密碼的實現(xiàn)中，為簡化問題，可能會采用給每個人相同的n值， 但不同的指數(shù)值e和d。這樣做的問題是，

31、如果同一信息用兩個不同的指數(shù)加密， 這兩個指數(shù)是互素的，則不需要任何解密密鑰就能恢復明文。設m是明文，兩個加密密鑰分別為e1，e2，共同的模數(shù)為n，兩個密文為： c1=m e1 mod n c2=me2 mod n 由于el，e2是互素的，由擴展的歐幾里德算法可以找到r和s，使之滿足 Re1+se2=1假設r是負數(shù)(其中必有一個為負數(shù))，再次使用歐幾里德算法可以求得Ct對模數(shù)N的逆元c1-1，故可以得到(c1-1)-r c2r(mod n)mre1mse2(mod n)三m(mod n) 即密碼分析者知道n，e1，e2，c1和c2，則可以恢復出明文m。5關(guān)于RSA算法的明文部分信息安全性同RS

32、A算法一樣，大多數(shù)的公鑰密碼體制的安全性是建立在單向函數(shù)之上的， 即所謂的單向函數(shù)模型密碼體制。RSA算法使用的單向函數(shù)的安全性是基于大數(shù)分解的困難性，即攻擊者在多項式時間內(nèi)不能分解模數(shù)n。但這并不能保證攻擊者很難使用概率方法來推算明文的某些特征或用二進制表示某個或某些比特的值(即明文的部分信息)。攻擊者通過獲取明文消息的部分信息，進而可以破譯或恢復整個明文信息。這就是RSA安全性的另一個重要方面，可以稱之為比特安全性， 即RSA算法中密文所泄漏的有關(guān)明文二進制表示的某些有效位的部分安全性。關(guān)于RSA體制部分信息安全性的最好結(jié)果是由W.Aiexi等人得出的。他們證明了任何由密文E(x)(E為加

33、密函數(shù))以不小于12+1ploy(N)的正確概率猜對最末有效位的算法F，都可誘導出一種由密文E(x)破譯出x的相對于算法F的非確定多項式算法，即所謂的最末有效位12+lploy(N)安全性。6. 代碼實現(xiàn)：#include#include#includetypedef int Elemtype;Elemtype p,q,e;Elemtype fn;Elemtype m,c;int flag=0;typedef void(*Msghandler)(void);struct MsgMapchar ch;Msghandler handler;/*公鑰*/struct PUElemtype e;Ele

34、mtype n;pu;/*私鑰*/struct PRElemtype d;Elemtype n;pr;/*判定一個數(shù)是否為素數(shù)*/bool test_prime(Elemtype m)if(m=1)return false;else if(m=2)return true;elsefor(int i=2;i0)binn=b%2;n+;b/=2;/*初始化主界面*/void Init()cout*endl;cout* Welcome to use RSA encoder *endl;cout* 1.setkey *endl;cout* 2.加密 *endl;cout* 3.解密 *endl;cou

35、t* 4.退出 *endl;cout*endl;coutpress a key:in2?in1:in2);Elemtype b=(in1in2?in1:in2);in1=a;in2=b;/*求最大公約數(shù)*/Elemtype gcd(Elemtype a,Elemtype b)order(a,b);int r;if(b=0)return a;elsewhile(true)r=a%b;a=b;b=r;if(b=0)return a;break;/*用擴展的歐幾里得算法求乘法逆元*/Elemtype extend_euclid(Elemtype m,Elemtype bin)order(m,bin)

36、;Elemtype a3,b3,t3;a0=1,a1=0,a2=m;b0=0,b1=1,b2=bin;if(b2=0)return a2=gcd(m,bin);if(b2=1)return b2=gcd(m,bin);while(true)if(b2=1)return b1;break;int q=a2/b2;for(int i=0;i=0;i-)f=(f*f)%n;if(bini=1)f=(f*a)%n;return f;/*產(chǎn)生密鑰*/void produce_key()coutpq;while(!(test_prime(p)&test_prime(q)cout輸入錯誤，請重新輸入!endl;coutpq;pr.n=p*q;pu.n=p*q;fn=(p-1)*(q-1);coutfn為：fnendl;coute;while(gcd(fn,e)!=1)coute輸入錯誤，請重新輸入!endl;coute;pr.d=(extend_euclid(fn,e)+fn)%fn;pu.e=e;flag=1;cout公鑰(e,n）:pu.e,pu.nendl;cout