【正文】 對n不互素的數x就等價于破譯了算法。這是因為：x和r的gcd可能等于P或者q，而其值可以用歐幾里德算法計算出來。實際上，若r足夠大，則沒必要擔心由x這個數來破譯算法。在的區(qū)間中有個與r互素的數，且有個與r非互素的數。所以偶然出現含有p或q作為因子的一個數的概率等于:對于數值很大的p和q，這個概率是非常小的。以目前的常規(guī)個人計算機為工具來進行因子分解，其工作量是非線性增長的，分析見表4l: N的位數所需時間5075104天10074年200109年3001015年5001025年因此，在安全性要求不是特別高的系統(tǒng)中，可以認為RSA是安全的。 RSA時間復雜度分析RSA運算過程涉及到大量的計算，所需時間相對于DES等加密算法來說，運算時間較長。但由于其良好的安全性和成熟的密鑰管理機制，RSA在實際工作中，被廣泛采用。RSA從20世紀80年代產生至今，始終以其成熟的工作體制和良好的安全性而被廣泛的應用于實際項目之中。RSA的安全性雖然沒有通過數學上的論證，因此，其安全性主要體現在大素數的分解這一復雜問題上。通過實踐證明，RSA在目前的計算機運行能力下，還是相對安全的。RSA在未來的很長一段時間中，必將保持旺盛的生命力。近年來，隨著電子商務、電子政務等網上行為的增加，對于加密技術的研究日趨活躍。而對于RSA的研究，同樣處于活躍的狀態(tài)。由于RSA本身框架的成熟，因此，對于RSA的研究主要體現在，對其子步驟算法的改進和研究，比如對于模n求逆算法的改進、最大公因子算法的改進。將RSA和其他算法、體制結合應用，比如目前在各計算機科技期刊上經常見到的關于門限RSA體制的研究成果。本章主要討論了RSA內部各步驟的算法實現。第5章 RSA算法的實現基于前面的分析，本章給出了一種實現RSA的快速高效算法，并介紹了利用組合算法實現大整數快速模冪乘運算的具體實現過程，以及在實現過程中所遇到的關鍵問題及解決方法。一個算法必須滿足它自身是正確的，即可以得到想要的計算結果。算法必須是有效的，即是高效的算法。簡單性原則不僅要使算法要盡量的容易實現，而且要盡量使程序容易被用戶使用。要求算法確實可行，不僅是在理論上是正確的，還要求在實際上也能達到預期的效果。本文前面介紹了一系列大數模冪運算及其改進算法，具體的實現方法步驟如下：（1）任意選取兩個不同的大質數p和q，計算乘積；（2）任意選取一個大整數d，d與互質，整數d用做加密密鑰。注重d的選取是很輕易的，例如所有大于p和q的質數都可用.；（3）確定解密密鑰n，由，根據d，p和q可以輕易地計算出n，即為逆元；（4）公開整數r和d，但是不公開n；（5）規(guī)定明文動態(tài)分布空間L，輸入明文，通過計算成為密文；（6）將密文C解密為明文；具體程序見附錄。開發(fā)環(huán)境：，512M內存，80G硬盤，17寸顯示器操作系統(tǒng)：Windows XP開發(fā)工具：Visusl C++仿真結果：其中p,q為2位素數，計算p與q的乘積，輸入整數d，d可以取大于p,q的素數小于p,q乘積，要求與(p－1)*(q－1)互質，計算d的逆元，輸入明文動態(tài)空間L，要求明文字節(jié)數不得超過L，否則任務終止。系統(tǒng)計算密文，然后計算明文舉例如圖：輸入2個素數：p=11,q=311,當輸入不是素數時會提示如下計算出p與q的乘積r為3421，（p1）于(q1)乘積為3100，輸入隨機大整數例如353，與3100僅有公約數1，如輸入錯誤時會有如下提示計算353的逆元,由n*d=1mod((p－1)*(q－1))可得逆元為2617，規(guī)定明文動態(tài)分配空間，此時我規(guī)定的是64個字節(jié)，輸入明文12345678，通過C = Pe modulo r計算將會轉化為密文：1268 2307 116 838 323 692 440 2366，再通過將其轉換回來就為12345678在實際生活中，取素數p=11,q=311,公開乘積r,保密d與逆元n，當小A發(fā)出明文12345678時，對其加密，得到密文1268 2307 116 838 323 692 440 2366，發(fā)給小C，他通過認證可得到明文12345678總結在當今的信息社會中，每天都有大量的信息在傳輸、交換存儲和處理，而這些處理過程幾乎都要依賴強大的計算機系統(tǒng)來完成。一旦計算機系統(tǒng)發(fā)生安全問題，就可造成信息的丟失、篡改、偽造、假冒、失密，以及系統(tǒng)遭受搗亂、破壞等嚴重后果，輕者造成計算機系統(tǒng)運行效率低下，重者造成計算機系統(tǒng)的徹底癱瘓。因此，如何保證計算機系統(tǒng)的安全是當前一個需要立即解決的十分嚴峻的問題。密碼學的基本目的是使在不安全信道中通信的兩方以一種使他們的對手不能明白和理解的通信內容的方式進行通信。本文對密碼學與信息安全方面做了簡要的概述，具體論述了RSA公鑰密碼體制，RSA已經成為一種國際公認的公鑰密碼體制，在實際應用中也最為廣泛。文章對RSA公鑰密碼體制的數學基礎，加密算法，簽名算法，安全性及參數的選擇做了詳細的討論。在當今還沒有一個較RSA公鑰密碼系統(tǒng)更為優(yōu)秀的密碼系統(tǒng)出現之前，能夠有效地改進RSA密碼算法的運行速度也是當今密碼學主要的一個研究方向。此外，在實踐中還可能發(fā)現本文研究未涉及的新問題，還需不斷的歸納、總結，并提出相應的解決方法。參考文獻[1]盧開澄，郭保安，:重慶出版社，1999[2]李海泉，:人民郵電出版社，2001[3]黃元飛，陳麟，:浦東電子出版社，2001[4]李紅軍，2002(10):3133[5]Steve Practical Guide to Managing Information :Artech House Books,2004[6]王育民，劉建偉．通信網的安全．西安：西安電子科技大學出版社，1999，50213[7]王宇潔，張曉丹，徐占文等．一種新的組合快速RSA算法．沈陽工業(yè)大學學報，2001，27(2)：224227[8]D Lou，C Chang．An adaptive exponentiation method．The Journal ofsystems and software，1998，42：5969[9]Phillips B J，Burgess N．Implementing 1024bits RSA exponentiation on a 32bits processor core．IEEE International conference on Application SpecificSystems，Architecture and processor(A SAP’00)，2000[10]胡建軍，李愛武．中國剩余定理提高RSA解密速度的分析．現代計算機，2003，2(21)：1011[11]馮登國等，《密碼學導引》，科學出版社，,412[12]曹珍富，《公鑰密碼學》，黑龍江教育出版社，,1528[13]談嫻茹，基于DES和RSA的網絡數據安全系統(tǒng)，中國民航學院學報，(A02)，133136[14]Bruce 《，應用密碼學協(xié)議算法與c源程序》，機械工業(yè)出版社，2000,118132[15]顧冠群等，密鑰管理的設計與實現，電信科學，,4751[16]王立勝等，數據加密標準DES分析及其攻擊研究，計算機工程，2003,29(13)，130132[17]王克苑等，SSL安全性分析研究，合肥工業(yè)大學學報(自然科學版)2004,27(1)，8791[18]劉鐵民等，VPN網絡隧道技術的研究，電信工程技術與標準化，2003(12).5557[19]張燕，數字簽名技術的研究，計算機時代，1998(5),2022[20]賀衛(wèi)紅等，RSA公鑰密碼體制在數字簽名中的應用，微機發(fā)展，2003(9)，4951致謝本論文是在導師....老師的悉心指導下完成的。從論文選題、資料收集、數據整理到論文的撰寫，每個環(huán)節(jié)....老師都給予了我無微不至的關懷和毫無保留的指導，提出了許多寶貴的意見和建議。....老師淵博的學術知識、嚴謹的科研態(tài)度和誨人不倦的治學精神都在潛移默化的感染著我，使我受益匪淺，終生難忘。值此論文完成之際，請導師接受我最衷心的感謝和最誠摯的敬意。感謝..........等幾位同學在工作、學習中給予我的關心和支持，我們互相幫助，共同渡過了研究生階段學習的美好時光。感謝桂林理工大學的各位老師，特別是電子與計算機系的領導和老師們。他們在我的學習和論文撰寫、答辯過程中，均給予了我莫大的幫助。此致致謝