【正文】 9 而：????????1,0,1)(22 iia amamiii 對于給定的 e ，只需根 據(jù)其二進制表示，取出 1?ia 的 im2 相乘即可，由于其中間結(jié)果均為小于 n 的整數(shù)，從而使運算量大大減小 . 例 ：計算 2173mod374 31 作預計算： 2173mod80413 98 76374 2 ?? 2 17 3m o d1 03 58 043 74 24 ?? 2173mod21091035374 28 ?? 217 3m od192 3210 9374 216 ?? 由于 16842131 ????? 所以 21 7 3m od44637480410 3 521 0 919 2 3374 31 ?????? 例 ： 一個簡單的 RSA 加密解密算法 取 43?p ， 59?q .則 25375943 ???n 24 365842)( ???n? ， 13?e . 設明文段 2106?m 則對于密文 253 7m od210 613?c . 做計算 84113 ??? 2 5 3 7m o d4312 1 0 6 ?? 2 5 3 7m o d5 6 0)4 3 1(2 1 0 6 22 ??? 253 7m od988560210 6 24 ??? 2537m o d601)988(2106 28 ???? 2 5 3 7m o d2 3 2 1)6 0 1()9 8 8()4 3 1(2 1 0 6 13 ??????? 得密文為 2321 現(xiàn)在將其恢復為明文：做計算 )(m od1 ned ??? .其中 13?e ， 2436)( ?n? 即： 1|)( ??edn? ， yx,? ，使得： 1)( ???? nyxe ? ， )( xd? .即： x 的值，因此，用輾轉(zhuǎn)相除法： 11 rqba ??? br??10 221 rqrb ??? 120 rr?? …… . nnnn rqrr ??? ?? 12 10 ??? nn rr 第 3 章 RSA 的數(shù)學原理及其算法設計 10 11 ?? ?? nnn qrr 其中： 2110 ,1,0 ?? ????? kkkk qQ ，得 nn Qx 1)1( ??? 代入數(shù)據(jù) 得： 937??xd 則明文 2537m od2321 9 3 7?m 又 5122561283281937 ??????? 計算： 2 5 3 7m o d2162 3 2 1 ?? 2 5 3 7m o d9 9 0)2 1 6(2 3 2 1 22 ??? 2537m od8189902321 24 ?? 2537m od6448182321 28 ??? 2 5 3 7m o d1 2 0 5)644(2 3 2 1 216 ??? 2537m od86112052321 232 ?? 253 7m od517861232 1 264 ?? 2537m od9045172321 21 2 8 ?? 2537m od3029042321 22 5 6 ?? 2 53 7m o d1 283 022 32 1 25 1 2 ??? 2 5 3 7m o d2 1 0 6)1 2 8(3 0 29 0 48 6 1)6 4 4()2 1 6(2 3 2 1 937 ??????????? 得明文為： 2106 RSA 的 MATLAB 實現(xiàn) 1. 模 n 求逆函數(shù) function [d]=moni(u,n) n1=n。 for i=0:1000 q=floor(n1/n2)。 n2=r。 else break end end if n2~=1 warning(‘所求的模逆不存在‘ )； end if n2= =1 if 0= =mod(i,2) b2=b2。 end n 的大數(shù)冪乘函數(shù) function [dashuchenmi]=dashuchenmi(x,r,n)。 for i=1:1000 if b= =0 dashuchenmi=c。 a=mod(a*a,n)。 fain=(p1)*(q1)。 end miwen mingwen 實驗結(jié)果： 輸入待加密的明文： 2106 輸入第一個大素數(shù)： 43 輸入第二個大素數(shù)： 59 四川理工學院畢業(yè)論文 13 輸入加密密鑰： 13 密文 = 2321 明文 = 2106 第 4 章 RSA 的安全性分析 14 第 4 章 RSA 的安全性分析 對 RSA常見的攻擊方法 RSA 的安全性依賴于對一種特殊形式的數(shù) pqn? （ qp, 為素數(shù)）進行分解的困難行 . 常見的攻擊方法有： （ 1） 分解 n 攻擊 RSA 體制最直接的方式就是試圖分解模數(shù) n ，得到 qp, ，求出 )(n? ，從而由 e和 )(n? 求出解密密鑰 d ，今天對大整數(shù)進行分解最有效的三種算法是二次篩法，橢圓曲線分解算法和數(shù)域篩法； 目前 1024bit 以上的 RSA 被認為是符合安全性要求的 . （ 2） 對 d 的值直接猜測 實踐證明這是一種窮搜索法 （ 3） 直接猜測 )(n? 事實上，這并不比分解 n 容易，因為若能猜出 )(n? ，則由 ??? ? ????pqn qppqn 1)(? 很容易求出 n 的分解， 但已證明這種算法等價于分解 n . （ 4） 小指數(shù)攻擊 當加密指數(shù) e 較小時，可以加快運算速度，但易受攻擊如果采用不同的模數(shù) n 及相同的 e 值，對 2/)1( ?ee 個線性相關的消息加密 ，則存在一種攻擊方法，如果消息相同，則用 e 個消息就夠了 . 如：三個用戶的加密密鑰 e 均為 3，而有不同的模數(shù) 321 , nnn ，這里要求 321 , nnn 兩兩互素 ，若要同時 向這三個用戶發(fā)送廣播消息 m ，先對 m 分別進行加密，計算 333232131 m o d,m o d,m o d nmmmc ??? 這里 ? ?321 ,min nnnm ? ，密碼分析者截獲到這三個密文后，由于 321 , nnn 兩兩互素，可用中國剩余定理 ，求出 3213 m od nnnmc ? 由于 ? ?321 ,min nnnm ? ，故 3213 nnnm ? ，因此有 3 cm? ，得到明文 m ， 防止這種攻擊的方法，對于短的消息，可用獨立的隨機值填充，使其足夠長，即消息 m滿足 3213 nnnm ? ，這樣就可以防止小指數(shù)攻擊 . （ 5） 定時攻擊 定時 攻擊通過觀察解密所需時間來確定解密密鑰，但如果 d 的二進制表示中 1 的數(shù)四川理工學院畢業(yè)論文 15 目較多時，則解密需要的運算時間也較長 。同時，也注重專業(yè)知識的應用，強調(diào)學以致用。困難能讓我們學到更多，更好的鍛煉自己。對本研究提供過幫助和做出過貢獻的個人或集體，均已在文中作了明確的說明并表示了謝意。對本文的研究做出重要貢獻的個人和集體，均已在文中以明確方式標明。 涉密論文按學校規(guī)定處理。圖表整潔，布局合理，文字注釋必須使用工程字書寫，不準用徒手畫 3）畢業(yè)論文須用 A4 單面打印，論文 50 頁以上的雙面打印 4）圖表應繪制于無格子的頁面上 5）軟件工程類課題應有程序清單，并提供電子文檔 1）設計（論文） 2）附件：按照任務書、開題報告、外文譯文、譯文原文（復印件）次序裝訂 3）其它