PAGE河南科技大學畢業(yè)論文設計PAGEPAGE5畢業(yè)設計（論文）題目:＿＿RSA加密算法的分析與實現(xiàn)＿＿

畢業(yè)設計（論文）原創(chuàng)性聲明和使用授權說明原創(chuàng)性聲明本人鄭重承諾：所呈交的畢業(yè)設計（論文），是我個人在指導教師的指導下進行的研究工作及取得的成果。盡我所知，除文中特別加以標注和致謝的地方外，不包含其他人或組織已經(jīng)發(fā)表或公布過的研究成果，也不包含我為獲得及其它教育機構的學位或學歷而使用過的材料。對本研究提供過幫助和做出過貢獻的個人或集體，均已在文中作了明確的說明并表示了謝意。作者簽名：日期：指導教師簽名：日期：使用授權說明本人完全了解大學關于收集、保存、使用畢業(yè)設計（論文）的規(guī)定，即：按照學校要求提交畢業(yè)設計（論文）的印刷本和電子版本；學校有權保存畢業(yè)設計（論文）的印刷本和電子版，并提供目錄檢索與閱覽服務；學?？梢圆捎糜坝?、縮印、數(shù)字化或其它復制手段保存論文；在不以贏利為目的前提下，學?？梢怨颊撐牡牟糠只蛉績热?。作者簽名：日期：

學位論文原創(chuàng)性聲明本人鄭重聲明：所呈交的論文是本人在導師的指導下獨立進行研究所取得的研究成果。除了文中特別加以標注引用的內容外，本論文不包含任何其他個人或集體已經(jīng)發(fā)表或撰寫的成果作品。對本文的研究做出重要貢獻的個人和集體，均已在文中以明確方式標明。本人完全意識到本聲明的法律后果由本人承擔。作者簽名： 日期：年月日學位論文版權使用授權書本學位論文作者完全了解學校有關保留、使用學位論文的規(guī)定，同意學校保留并向國家有關部門或機構送交論文的復印件和電子版，允許論文被查閱和借閱。本人授權大學可以將本學位論文的全部或部分內容編入有關數(shù)據(jù)庫進行檢索，可以采用影印、縮印或掃描等復制手段保存和匯編本學位論文。涉密論文按學校規(guī)定處理。作者簽名： 日期：年月日導師簽名：日期：年月日

注意事項1.設計（論文）的內容包括：1）封面（按教務處制定的標準封面格式制作）2）原創(chuàng)性聲明3）中文摘要（300字左右）、關鍵詞4）外文摘要、關鍵詞5）目次頁（附件不統(tǒng)一編入）6）論文主體部分：引言（或緒論）、正文、結論7）參考文獻8）致謝9）附錄（對論文支持必要時）2.論文字數(shù)要求：理工類設計（論文）正文字數(shù)不少于1萬字（不包括圖紙、程序清單等），文科類論文正文字數(shù)不少于1.2萬字。3.附件包括：任務書、開題報告、外文譯文、譯文原文（復印件）。4.文字、圖表要求：1）文字通順，語言流暢，書寫字跡工整，打印字體及大小符合要求，無錯別字，不準請他人代寫2）工程設計類題目的圖紙，要求部分用尺規(guī)繪制，部分用計算機繪制，所有圖紙應符合國家技術標準規(guī)范。圖表整潔，布局合理，文字注釋必須使用工程字書寫，不準用徒手畫3）畢業(yè)論文須用A4單面打印，論文50頁以上的雙面打印4）圖表應繪制于無格子的頁面上5）軟件工程類課題應有程序清單，并提供電子文檔5.裝訂順序1）設計（論文）2）附件：按照任務書、開題報告、外文譯文、譯文原文（復印件）次序裝訂3）其它

摘要隨著信息產(chǎn)業(yè)的迅速發(fā)展，人們對信息和信息技術的需要不斷增加，信息安全也顯得越來越重要?；趯W(wǎng)絡傳輸數(shù)據(jù)安全性的考慮，保障網(wǎng)絡信息安全的加密產(chǎn)品具有廣泛的應用前景，密碼技術則是保障信息安全的一個重要手段。密碼學是信息安全技術的核心，現(xiàn)代密碼體制分為公鑰體制和私鑰體制兩大類:私鑰體制又稱單鑰體制，其加密密鑰和解密密鑰相同;公鑰體制又稱為雙鑰體制，其加、解密密鑰不同，可以公開加密密鑰，而僅需保密解密密鑰，從而具有數(shù)字簽名、鑒別等新功能，被廣泛應用于金融、商業(yè)等社會生活各領域。RSA是目前公認的在理論和實際應用中最為成熟和完善的一種公鑰密碼體制，不僅可以進行加密，還可以用來進行數(shù)字簽名和身份驗證，是公鑰密碼體制的代表。大數(shù)模冪乘運算是實現(xiàn)RSA等公鑰密碼的基本運算，該算法存在的問題是在實現(xiàn)時耗時太多，這也是制約其廣泛應用的瓶頸。本論文的第一章介紹了國內外密碼學和RSA的有關動態(tài)以及本論文的意義，第二章介紹密碼學的有關知識，第三章對RSA算法進行分析、介紹，第四章是RSA加密與解密的實現(xiàn)的代碼和測試，第五章對本課題的結論。最后是致謝和參考文獻。關鍵詞:密碼學，RSA公鑰密碼體制，信息安全ABSTRACTWiththerapiddevelopmentofITtechnology,peopledependonitincreasingly,Asaresult,informationsecurityisgettingmoreandmoreimportant.Meanwhile,Productsthatensurenetworkinformationshowagreatprospectduetotheimportance.Oftransmittingdatabynetworksafely,andasanimportantmeansofinformationSecurity,cryptographymustbelifted.Cryptographyisthecoreoftheinformationsecurity.Moderncryptographis,Dividedintothepublickeysystemandtheprivatekeysystem.Theprivatekeysystem,Isalsocalledthesinglekeysystem,inwhichtheencryptionprocessisthesameasthe.Decryptionprocess.Thepublickeysystemisalsocalledthedoublekeysystem,Wheretheencryptionprocessisdifferentwiththedecryptionprocess.SincethePublickeysystemcanpublishitspublickeyandkeepitsprivatekeysecret,ithas,Manynewapplicationssuchasthedigitalsignatureandauthentication,whichis.ideallyusedineveryfieldofthesociety.Amongthevariouspublickeycryptosystem,RSAalgorithmisthebestchoicein,Boththeoryandapplication,anditisopenusedindigitalsignatureandidentificationSystem.Modularexponentiationandmodularmultiplicationarethebasicalgorithms.ForimplementingthepublickeyalgorithmssuchasRSA,etc.Howeverthe,Time-consumingmoduloexponentiationcomputation,whichhasalwaysbeenthe,Bottle-neckofRSArestrictsitswiderapplication.Thefirstchapterintroducesthedomesticandforeignprogressofcryptograph;TheRSArelatedtendencyaswellasthemeaningoftheresearch.ThesecondchapterExplainscryptograph.ThethirdchapterdescribesandanalyzestheRSAalgorithm.ThefourthchapterdiscussestheimprovementoftheRSAalgorithmincludingthebig,Numberrestoreandoperation,andtheimprovementalgorithmofthe”Squaremultiply"algorithm.ThefifthchapterreprintsanimprovedalgorithmandComparisons.KEYWORDS:cryptography,RSA,publickeycryptosystem,informationsecurity目錄摘要 1ABSTRACT 2第一章引言 61.1研究背景 61.2信息加密技術 61.3密碼技術研究現(xiàn)狀 81.4研究本課題的意義 9第二章密碼學概論 112.1密碼學的基本概念 112.2古典密碼體制 142.3對稱密碼體制 142.3.1DES(DataEncryptionStandard) 162.3.2AES(AdvancedEncryptionStandard) 182.4公鑰密碼體制 192.5密碼分析技術 21第三章RSA公鑰密碼體制 243.1RSA的數(shù)學基礎知識 243.1.1因子的概念 243.1.2素數(shù)與合數(shù) 253.1.3公約數(shù)與最大公約數(shù) 263.1．4互質數(shù) 273.2RSA算法 283.2.1RSA體制描述 283.2.2RSA工作原理 29第四章RAS的加密與解密技術的實現(xiàn) 324.1RSA加密與解密代碼 324.2測試的環(huán)境與工具 344.3測試的結果 35第五章結論 365.1結論 36致謝 37參考文獻 38第一章引言1.1研究背景自20世紀90年代以來，計算機網(wǎng)絡技術得到了空前飛速的發(fā)展和廣泛的應用，但網(wǎng)絡在帶給我們方便快捷的同時，也存在著種種安全危機，隨著計算機應用的日益廣泛和深入，信息交流和資源共享的范圍不斷擴大，計算機應用環(huán)境日趨復雜，計算機的數(shù)據(jù)安全問題也越來越重要。在計算機網(wǎng)絡日益擴大和普及的今天，計算機對安全的要求更高、涉及面更廣。其內容主要包括:(1)實體安全。實體安全是指對場地、環(huán)境、設施、設備、載體、人員采取的各種安全對策和措施;(2)數(shù)據(jù)傳輸網(wǎng)絡安全。是指信息、在數(shù)據(jù)傳輸網(wǎng)絡中傳輸時，如何保證其安全性的問題，避免在傳輸途中遭受非法竊取、篡改等;(3)軟件安全。它涉及信息在存儲和處理狀態(tài)下的保護問題;(4)信息安全。即數(shù)據(jù)安全，是指系統(tǒng)有能力抵抗外來非法入侵者對信息的惡意訪問、泄漏、修改和破壞等，即:機密性、完整性、可用性。所以，如何實現(xiàn)計算機網(wǎng)絡中數(shù)據(jù)安全傳輸近年來一直是人們研究的課題之一。1.2信息加密技術信息加密技術是信息安全技術l2]的核心技術，其主要目的是防止惡意攻擊者非法破譯系統(tǒng)中的機密信息。數(shù)據(jù)加密技術可以提高信息系統(tǒng)及數(shù)據(jù)的安全性和保密性，防止秘密數(shù)據(jù)被外部破譯所采用的主要技術手段之一。而密碼學是研究通信安全保密的科學，其目的是保護信息在信道上傳輸過程中不被他人竊取、解讀和利用，它主要包括密碼編碼學和密碼分析學兩個相互獨立又相互促進的分支。前者研究將發(fā)送的信息(明文)變換成沒有密鑰不能解或很難解的密文的方法;而后者則研究分析破譯密碼的方法。其發(fā)展經(jīng)歷了相當長的時期。第一次世界大戰(zhàn)之前，密碼學的重要進展根本是不為人知的，很少有文獻披露這方面的信息。直到1918年由WF.Friendlunn論述了重合指數(shù)及其在密碼學中的應用以及轉輪機專利的發(fā)表才引起了人們的重視，但僅僅由軍事和秘密部門所控制。第一次世界大戰(zhàn)之后到20世紀40年代末期，密碼學家們將信息理論、密碼學和數(shù)學結合起來研究，使信息論成為了研究密碼編碼學和密碼分析學的重要理論基礎。完全處于秘密工作狀態(tài)的研究機構開始在密碼學方面取得根本性的進展，最具代表性的有Shannon(香農(nóng))的論文—《保密系統(tǒng)的通信理論》和《通信的數(shù)學理論》，他將安全保密的研究引入了科學的軌道，從而創(chuàng)立了信息論的一個新學科。從20世紀50年代初期到60年代末期的20年中，在密碼學的研究方面公開發(fā)表的論文極少，但DavidKahn于1967年出版的著作—《破譯者》使密碼學的研究涉及到了相當廣泛的領域，使不知道密碼學的人了解了密碼學，因此密碼學的研究有了新的進展。自20世紀70年代初期到現(xiàn)在，隨著計算機科學與技術的發(fā)展，促進了密碼學研究的興起和發(fā)展，人們使用密碼學技術來保護計算機系統(tǒng)中信息的安全。因此，在密碼學的研究和應用等方面取得了許多驚人的成果和理論。具有代表性的有:(l)由Daffier和Hellman于1976年發(fā)表的“密碼學的新方向”一文提出了公開密鑰密碼學(即公開密鑰或雙密鑰體制)，打破了長期沿用單密鑰體制的束縛，提出了一種新的密碼體制。公開密鑰體制可使收、發(fā)信息的雙方無須事先交換密鑰就可秘密通信。(2)由HorstFestal研究小組于20世紀70年代初著手研究美國數(shù)據(jù)加密標準(DataEncryptionstandard，DES)，并于1973年發(fā)表了“密碼學與計算機保密”等有價值的論文，該文論述了他們的研究成果并被美國標準局伽BS)采納，于1977年正式公布實施為美因數(shù)據(jù)加密標準并被簡稱為Desk標準。上述密碼學的發(fā)展可粗略的劃分為三個階段:第一階段(194·9年之前)的密碼學可以說不是什么學科，僅為一門藝術;第二階段(1949年到1975年)可以說是密碼學研究的“冬天”，成果和論文少且為單密鑰體制，但在這一階段有如Shaman的理論和Dave記Kahn的著作并為密碼學奠定了堅實的理論基礎;第三階段(1976年到現(xiàn)在)可以說是密碼學研究的“春天”，密碼學的各種理論和觀點百花齊放，應用成果累累。1.3密碼技術研究現(xiàn)狀密碼技術是信息安全技術的核心，它主要由密碼編碼技術和密碼分析技術兩大分支組成。密碼編碼技術的主要任務是尋求產(chǎn)生安全性高的有效密碼算法和協(xié)議，以滿足對消息進行加密或認證的要求。密碼分析技術的主要任務是破譯密碼或偽造認證信息，實現(xiàn)竊取機密信息或進行詐騙破壞話動。這兩個分支既相互對立又相互依存，正是由于這種對立統(tǒng)一關系，才‘推動了密碼學自身的發(fā)展。目前人們將密碼理論與技術分成兩大類，一類是基于數(shù)學的密碼理論與技術，包括公鑰密碼、分組密碼、序列密碼、認證碼、數(shù)字簽名、Hash函數(shù)、身份識別、密鑰管理、PKI技術、VPN技術等;另一類是非數(shù)學的密碼理論與技術，包括信息隱藏、量子密碼、基于生物特征的識別理論與技術等。現(xiàn)在世界上的一些大國都非常重視密碼學研究I3jI4]。在美國國家安全局(Nast)和國家標準技術研究所(Mist)的共同推動下，20世紀70年代以來陸續(xù)建立了國家數(shù)據(jù)加密標準(DES)和數(shù)字簽名標準(D55)，2001年又確定了高級加密標準算法(AES)以作為21世紀的應用基礎。美國政府為了適應信息社會發(fā)展的需要，加強政府司法機構的社會管理執(zhí)法的高技術支撐能力和情報部門的對抗信息戰(zhàn)的能力，正通過Nast提出并推動著密鑰托管、密鑰恢復、證書授權認證、公開密鑰基礎設施、公開密鑰管理基礎設施等一系列技術手段、技術標準和相關理論基礎的研究。國際上對在分組密碼和序列密碼設計和分析的理論和技術已經(jīng)比較成熟。除了算法的設計之外，美國、歐洲、日本發(fā)達國家在加密算法的標準化方面做了大量的工作。我們國內的學者也設計了很多對稱加密算法，但是目前的問題是，國內還沒有一個統(tǒng)一的加密標準?？上驳氖?，目前有關部門正在組織對加密標準的討論和征集。1.4研究本課題的意義加密技術按照密碼使用方法不同可以分為對稱密鑰算法和非對稱密鑰算法。對稱密鑰算法中，加密、解密都使用相同的密鑰。非對稱密鑰算法又稱公鑰密碼算法，即加密、解密使用兩個不同的密鑰。由于公鑰密碼算法在保證數(shù)據(jù)的機密性、完整性以及簽名和認可等方面的突出優(yōu)點，它已經(jīng)成為當今網(wǎng)絡安全中最重要的解決方法。在眾多的公鑰密碼體制中，1978年由Rivets，Shamir和Adelman在美國MIT提出的Rosa算法15][6]被公認為是目前理論和實際應用中最為成熱和完善的一種公鑰密碼體制，可以用來進行數(shù)字簽名和身份驗證。該算法的安全性依賴于大整數(shù)的素數(shù)因子分解的困難性，其最基本最核心的算術操作是模乘運算，再由一系列的模乘來完成模冪運算。RSA體制算法完善(既可用于數(shù)據(jù)加密，又可用于數(shù)字簽名)，安全性良好，易于實現(xiàn)和理解。使用RSA體制作為課題算法和方案的實現(xiàn)基礎，我們可以有效地利用RSA體制的優(yōu)點。同時，關于RSA體制的大量的研究工作的文獻和成果為本文研究工作的開展提供了良好的基礎。RSA體制是最具代表性的公鑰密碼體制。RSA體制的特點使得它成為公鑰密碼體制研究的一個標準模板。同時，由于RSA算法發(fā)展至今，在實現(xiàn)技術上己經(jīng)相當成熟，因此本文算法的實現(xiàn)在許多方面都可以利用己有的技術，這對增強算法的實用性是非常有益的。RSA算法計算復雜，實現(xiàn)的難度大。軟件實現(xiàn)主要問題是加密、解密操作要計算位數(shù)達十進制百位以上的模冪乘函數(shù)。執(zhí)行的時間長，難以滿足實際使用要求。在實際應用中，其加密和解密的速度是主要的問題，所以研究RSA的快速算法具有非常重要的現(xiàn)實意義。本論文主要研究了密碼學尤其是RSA的發(fā)展歷程，及目前RSA在應用中面臨的問題。在大量閱讀國內外重要文獻資料的基礎上，深入剖析了RSA算法的精要。第二章密碼學概論密碼學[7]的歷史極為久遠，其起源可以追溯到遠古時代，人類有記載的通信密碼始于公元前400年。雖然密碼是一門古老的技術，但自密碼誕生直至第二次世界大戰(zhàn)結束，對于公眾而言，密碼始終處于一種未知的黑暗當中，常常與軍事、機要、間諜等工作聯(lián)系在一起，讓人在感到神秘之余，又有幾分畏懼。信息技術的發(fā)展迅速改變了這一切。隨著計算機和通信技術的迅猛發(fā)展，大量的敏感信息常常通過公共通信設施或計算機網(wǎng)絡進行交換，特別是intermit的廣泛應用、電子商務和電子政務的迅速發(fā)展，越來越多的個人信息需要嚴格保密，如:銀行賬號、個人隱私等。正是這種對信息的秘密性與真實性的需求，密碼學才逐漸揭去了神秘的面紗，走進公眾的日常生活當中。本章回顧了密碼學的基礎知識，包括密碼學的基本概念、密碼理論與技術基礎、認證理論與技術基礎以及密碼分析學基礎。這些基礎概念和知識是本課題研究工作的理論與技術基礎。2.1密碼學的基本概念首先我們明確一下本文所使用的密碼學的一些基本概念。它們將貫穿本文的由始至終。定義1密碼學(Cryptology)是研究信息系統(tǒng)安全保密的科學。它包括兩個分支，即密碼編碼學和密碼分析學。定義2密碼編碼學(Cryptography)是對信息進行編碼實現(xiàn)信息隱蔽的技術和科學。定義3密碼分析學(Cryptanalysis)是研究分析破譯密碼的技術與科學。定義4明文(Plaintext)是指發(fā)送方想要發(fā)送給接受方的消息。定義5密文(Ciphertext)是指明文被加密后的消息。定義6加密(Encryption)將明文變換為密文的過程。定義7解密(Decryptions)將密文恢復為明文的過程。定義1.8一個密碼體制是滿足以下條件的五元組(P，C，K，E，D):1.P表示所有可能的明文組成的有限集。2.C表示所有可能的密文組成的有限集。3.K代表密鑰空間，是由所有可能的密鑰組成的有限集。4.對任意的，都存在一個加密法則和相應的解密法則。并且對每一:和:對任意的明文，均有。通常人們用香農(nóng)(Salmon)的密碼模型來說明密碼體制。Shalom提出的保密系統(tǒng)的模型[8}如圖2-1所示:它由以下幾部分組成:明文空間P，密文空間C，密鑰空間K1和k2單鑰體制下K1=k2=k3密鑰K需通過安全的密鑰通道由發(fā)送方傳給接密變換EK1:，由加密器完成，其中;解密變換DK2:密器完成，其中。稱五元組(P，c，K，E，D)為一保密系統(tǒng)。如果一個密碼體制的，或由其中一個很容易推出另一個，鑰密碼體制或對稱密碼體制或傳統(tǒng)密碼體制(one-keyCryptosystem，其是美國的數(shù)據(jù)加密標準Desk(DataEncryptionStandard):其中（3.2）否則，稱為雙體制或非對稱密碼體制。進而，如果在計算上K2不能由K1推出，這公開也不會損害K2的安全，于是便可以將K1公開。這種密碼體制稱碼體制(public一keyCryptosystem)，其典型代表是Rosa密碼體制。根據(jù)對明文的劃分與密鑰的使用方法的不同可將密碼體制分為分序列密碼體制。①分組密碼是將明文M劃分為一系列明文塊M1，M2，…，Mn，通常若干字符，并且對每一塊Mi都用同一個密鑰Kill進行加密，即C=(C1,C2…,Cn)。②序列密碼將M劃分為一系列的字符或位m1，m2，…，mn，并且對于這每一個mi用密鑰序列KI=(Kl1，Kl2，…，Kln)的第I個分量Kli來加密，即C=(C1，C2，…，Cn)，其中Ci=E(mi，kli)，i=l，2，…，n分組密碼一次加密一個明文塊，而序列密碼一次加密一個字符或一個位。兩種密碼在計算機系統(tǒng)中都有廣泛應用。為了實現(xiàn)信息的保密性，抗擊密碼分析，保密系統(tǒng)應當滿足下述要求:①即使達不到理論上是不可破解的，也應當是實際上是不可破解的。也就是說，從截獲的密文或某些己知明文密文對，要確定密鑰或任意明文在計算上是不可行的;②保密系統(tǒng)的安全性應依賴于密鑰，而不是依賴于密碼體制或算法本身的細節(jié)的安全性;③加密解密算法實用于所有密鑰空間中的元素;④系統(tǒng)應該易于實現(xiàn)和使用方便。2.2古典密碼體制古典密碼是密碼學的淵源，這些密碼都是由基于字符的密碼算法構成的，可用手工或機械操作實現(xiàn)加解密。不同的密碼算法是字符之間互相代換或者是互相置換，好的密碼算法是結合這兩種方法，每次進行多次運算。雖然現(xiàn)在己經(jīng)很少采用了，但原理還是沒變。重要的變化是算法對位而不是對字符進行變換，實質上這只是字母表長度的改變。古典密碼的基本運算有兩種代替(substitution)和換位(Transposition)。代替是指每一個或一組字符被另一個或另一個或一組字符所取代;換位是不改變明文字符，而按一定規(guī)則重新安排字符次序。實際的密碼算法是執(zhí)行一系列這兩種基本運算的不同組合，即得到所謂的乘積密碼。比較有名的古典密碼包括J愷撒(Kaiser)密碼、維吉利亞(viewers)密碼、維爾南(Velma)、普萊費厄(pl即fair)密碼和希爾(Hill)密碼等。2.3對稱密碼體制對稱密碼體制[10]又叫私鑰密碼算法，是指能夠從解密密鑰中推算出加密密鑰，反過來也成立。在大多數(shù)的對稱密碼體制中，加密密鑰和解密密鑰的，它要求發(fā)送者和接收者在通信之前協(xié)商一個安全的密鑰，因此有時碼也稱為單鑰密碼。單鑰密碼體制的安全性主要取決于算法和密鑰的長漏密鑰就意味著任何人都能對消息進行加、解密。對稱密碼體制不僅可以用于數(shù)據(jù)加密，也可以用于消息認、證。但是碼體制存在著嚴重的缺陷:在進行安全通信之前，通信的雙方必須通過道商定和傳送密鑰，而在實際的通訊網(wǎng)中，通信雙方很難確定一條合理通道;另外一個問題就是密鑰的管理。在擁有大量用戶的計算機通信網(wǎng)個相互進行保密通信的用戶需要N(N一1)/2個密鑰;當N值比較大的鑰管理的開銷極大，密鑰只能記錄在計算機內存或外存上，這.本身就是全的。分組密碼一般的設計原則包括:①分組長度n要足夠大，使分組代替字母表中的元素個數(shù)2n足夠大明文窮舉攻擊法奏效。②密鑰量要足夠大(即置換子集中的元素足夠多)，盡可能消除弱密鑰有密鑰無特殊性可分析，以防止密鑰窮舉攻擊奏效。但密鑰又不能過長于密鑰的管理。③由密鑰確定代替的算法要足夠復雜，充分實現(xiàn)明文和密文的擴散沒有簡單的關系可循，要能抗擊各種己知的攻擊，如差分攻擊和線性攻④加密和解密運算簡單，易于軟件和硬件的快速實現(xiàn)。⑤數(shù)據(jù)擴展。一般無數(shù)據(jù)擴散，在采用同態(tài)置換和隨機化加密技術入數(shù)據(jù)擴展。⑥差錯傳播盡可能地小。為了抗擊統(tǒng)計分析破譯法，需要實現(xiàn)三條要求，Shannon曾建議采用擴散(Diffusion)和混淆(confusedly)法。所謂擴散，就是將明文及密鑰的每一位數(shù)字的影響盡可能迅速地擴散到輸出密文的較多個數(shù)字中，以便隱蔽明文數(shù)字的統(tǒng)計特性。在理想情況下，明文的每一位bit和密鑰的每一bit應影響密文的每一bit即實現(xiàn)所謂的“完備性”。Sharman提出的“混淆”概念目的在于使作用于文明的密鑰和密文之間的關系復雜化，使明文和密文之間、密文和密鑰之間的統(tǒng)計相關性極小化，從而使統(tǒng)計分析攻擊法不能奏效。擴散和混淆原則是設計分組密碼的基本準則，到達良好的擴散和混淆效果是分組密碼設計的核心問題Shannon還提出了“乘積”的方法，所謂“乘積密碼”，是將若干個密碼復合。例如，設有兩個子密碼T和S，我們先以T對明文進行加密，然后再以S對所得的結果進行加密，則乘積密碼可表示為F二ST。利用這種方法?？蓪⒑唵我子趯崿F(xiàn)的密碼組合成復雜的更為安全的密碼。分組密碼的特點是將明文消息編碼后的數(shù)字序列在密鑰的控制下變換成等長的數(shù)字序列。分組密碼的輸入輸出序列長度預先己確定(一般二者相等)，故從本質上看，這種密碼可看作是字長為分組長度的數(shù)字序列的代換密碼。著名的數(shù)據(jù)加密標準(DataEncryptionStandard，DES)是分組密碼家族的一個成員，它作為世界范圍的標準己經(jīng)有20多年的歷史了。其他比較有名的分組密碼算法還有國際數(shù)據(jù)加密算法(IDEA)Ghost算法等。2.3.1DES(DataEncryptionStandard)數(shù)據(jù)加密標準DES(DataEncryptionstandard)算法由IBM公司開發(fā)，并被美國國家標準局困（NIST)于1977年2月采納作為“非密級”應用的一個標準，此后，DES成為全世界使用最廣泛的加密標準。DES是迄今為止最為廣泛應用的一種加密算法，也是最具代表性的一種分組密碼體制。DES對于推動密碼理論的發(fā)展和應用起了重大作用，掌握和了解這一算法的基本原理、設計思想、安全性分析等問題，對于研究分組密碼理論和其實際應用具有重要意義。DES是一種對二元數(shù)據(jù)進行加密的方法，數(shù)據(jù)分組長度為64位，密文分組長度也是64位，沒有數(shù)據(jù)擴展。其算法的基本思想是:通過循環(huán)或迭代，將簡單的基本運算(例如左移、右移、模2加法等)和變換(選擇函數(shù)、置換函數(shù))構造成數(shù)據(jù)流的非線性變換(加密變換或解密變換)。DES算法的數(shù)據(jù)流程的基本框架是固定的，通過密鑰分解將一個實際上是56位(二進制)(64位密鑰去掉奇偶校驗位，剛好是56位)的密鑰分解成16個48位(二進制)的子密鑰，每個子密鑰控制一次循環(huán)或迭代。加密與解密的密鑰和流程是完全相同的，區(qū)別僅僅是加密與解密使用子密鑰序列的操作順序剛好相反。DES算法在歷史上曾發(fā)揮重要作用，但也存在以下問題:①DES密鑰空間的規(guī)模256對實際安全而言太小。②DES的密鑰存在弱密鑰、半弱密鑰和互補密鑰。③DES里的所有計算，除去S盒，全是線性的。S盒的設計對密碼算法的安全性至關重要。然而，美國國家安全局并沒有公布S盒的設計原則，因此，有人懷疑S盒里隱藏了“陷門(trapdoors)”，如果是這樣，美國國家安全局就能輕易地解密消息。由于DES的密鑰空間小，針對DES算法進行窮舉攻擊就可以取得成1998年7月，電子前沿基金會(EFF)使用一臺25萬美元的電腦在56小時了DES密鑰。1999年1月RSA數(shù)據(jù)安全會議期間，EFF通過遍布全世萬臺計算機的協(xié)同工作，用22小時巧分鐘就宣告破解了一個DES的密外，關于DES的攻擊還有差分密碼分析方法和線性密碼分析方法。2.3.2AES(AdvancedEncryptionStandard)從各方面來看，DES已走到了它生命的盡頭，為了替代己經(jīng)超齡服役DES算法，Nils于1997年1月開始了公開篩選DES替代者—高級加密標準（AES）的工作。其目的是為了確定一個非保密的、全球免費使用的分組密碼算法，用于保護下一世紀政府的敏感信息，并希望成為秘密和公開部門的數(shù)據(jù)加密標準.最終，2000年10月2日，NIST宣布比利時的密碼學家JoanDiemen和VincentRijmen設計的“Roundel算法”最終獲勝。Roundel之所為能當選AES，主要是因為:①運算速度快。在無論有無反饋模式的計算環(huán)境下的軟硬件中，Rijndael表現(xiàn)出非常好的性能。②對內存的需求非常低，使它很適合用于受限制的環(huán)境。③算法可靠。使用非線性結構的S一盒，表現(xiàn)出有足夠的安全余地。④Irondale算法的設計策略是寬軌跡策略(WideTrailStrategy)，這種策略會有效抵抗差分分析和線性分析攻擊。⑤Irondale是一個分組迭代密碼，被設計成128/192/256比特三種密匙標準可用于加密長度為128/192/256比特的分組，相應的輪數(shù)為10/12/14，分組長度和密鑰長度設計靈活。⑥密鑰安裝的時間很好，也具有很高的靈活性。⑦操作簡單，并可抵御時間和能量攻擊，此外，它還有許多未被特的防御性能。由上可見，助deal匯聚了安全性能、效率、可實現(xiàn)性和靈活性等。2.4公鑰密碼體制對稱密碼體制的特點是解密密鑰與加密密鑰相同或者很容易從加密密鑰導出解密密鑰。在對稱密碼體制中，加密密鑰的暴露會使系統(tǒng)變得不安全。對稱密碼系統(tǒng)的一個嚴重缺陷是在任何密文傳輸之前，發(fā)送者和接收者必須使用一個安全信道預先商定和傳送密鑰。在實際的通訊網(wǎng)中，通信雙方則很難確定一條合理的安全通道。由Dime和Hellman首先引入的公鑰密碼體制克服了對稱密碼體制的缺點。它的出現(xiàn)是密碼學研究中的一項重大突破，也是現(xiàn)代密碼學誕生的標志之一。在公鑰密碼體制中，解密密鑰和加密密鑰不同，從一個難以計算出另一個，解密運算和加密運算可以分離。通信雙方無須事先交換密鑰就可建立起保密通信。公鑰密碼體制克服了對稱密碼體制的缺點，特別適用于計算機網(wǎng)絡中的多用戶通信，它大大減少了多用戶通信所需的密鑰量，節(jié)省了系統(tǒng)資源，也便于密鑰管理。1978年Rivets，Shamir:和Adelman提出了第一個比較完善的公鑰密碼算法，這就是著名的RSA算法。自從那時起，人們基于不同的計算問題，提出了大量的公鑰密碼算法。比較重要的有RSA算法、Mermen-Hellman背包算法、Mealier算法、Enigmas算法和橢圓曲線密碼算法等。設計公鑰密碼體制的關鍵是先要尋找一個合適的單向函數(shù)，大多數(shù)的公鑰密碼體制都是基于計算單向函數(shù)的逆的困難性建立的。例如，RSA體制就是典型的基于單向函數(shù)模型的實現(xiàn)。這類密碼的強度取決于它所依據(jù)的問題的計算復雜性。值得注意的是，公鑰密碼體制的安全性是指計算安全性，而絕不是無條件安全性，這是由它的安全性理論基礎即復雜性理論決定的。單向函數(shù)在密碼學中起一個中心作用。它對公鑰密碼體制的構造的研究是非常重要的。雖然目前許多函數(shù)(包括RSA算法的加密函數(shù))的被認為或被相信是單向26的，但目前還沒有一個函數(shù)能被證明是單向的。目前己經(jīng)問世的公鑰密碼算法主要有三大類:第一類是基于有限域范圍內計算離散對數(shù)的難度而提出的算法。比如，世界上第一個公鑰算法Defile一Hellman算法就屬此類，但是，它只可用于密鑰發(fā)，不能用于加密解密信息。此外，比較著名的還有Enigma算法和1991年NIST提出的數(shù)字簽名算法-DigitalsignatureAlgorithm(DSA)。第二類是20世紀90年代后期才得到重視的橢圓曲線密碼體制。1985年，美國Washington大學的NealKoblenz和IBMWatson認研究中心的VictorMiller各自獨立的提出:一個稱為橢圈曲線的不引人注目的數(shù)學分支可以用于實現(xiàn)密碼學。他們沒有設計出用橢圓曲線的新的密碼算法，但他們在有限域上用橢圓曲線實現(xiàn)了己有的公鑰算法，如Dine-Henlman.lGamal和Schonn一算法等。第三類就是本課題研究要涉及的RSA公鑰密碼算法。1977年，MIT的RonaldL.Rivest.AdiShamirLeonard和Madmen教授對Defies和Hellman的公約密碼學的思想進行了深入的研究，開發(fā)出了一個能夠真正加密數(shù)據(jù)的算法。眾所周知的用他們三個名字首字母命名的RSA算法問世。由于Whiff和MartinHellman提供的ME背包算法于1984年被破譯，失去了實際意義，因而RSA算法是真正有生命力的公開密鑰加密系統(tǒng)算法，也是第一個既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的算法，在過去數(shù)年中提出的所有公鑰算法是最易于理解和實現(xiàn)的，也是最流行的，自提出后已經(jīng)經(jīng)過了多密碼分析，至今還沒有發(fā)現(xiàn)其中的嚴重缺陷，仍然在發(fā)揮的及其重要的作用。本文將在下一章對該算法作比較詳細的介紹。另外，還有由Remark。和Elhanan設計出的第一個廣義的公鑰加密算法--背包算法，Rabin算法，細胞自動機算法等許許多多的算法。1988年，daffier總結了己經(jīng)出現(xiàn)的所有公鑰密碼算法，提出大多數(shù)公鑰算法都基于三個難問題之一:背包問題、離散對數(shù)和因子分解。所以說，公鑰密碼學的數(shù)學基礎是很狹窄的，設計出全新的公鑰密碼算法的難度相當大，而且無論是數(shù)學上對因子分解還是計一算離散對數(shù)問題的突破都會使現(xiàn)在看起來安全的所有么:鑰算法變得不安全。2.5密碼分析技術密碼分析學是密碼學的一個重要分支，同密碼編碼學并列。一般說來密碼分析學是研究是在不掌握密鑰的情況下，利用密碼體制的弱點來恢復明文的一門學科。對一個密碼系統(tǒng)采取截獲密文進行分析的這類攻擊稱作被動攻擊(passiveattack)。密碼系統(tǒng)可能遭受的另一種攻擊是主動攻擊口、evilest。既非法入侵者主動向系統(tǒng)竄擾，采用刪除、更改、增添、重放、偽造等手段向系統(tǒng)插入假消息，以達到竊取非法信息的目的。如果能夠根據(jù)密文確定出明文或密鑰，或者能夠根據(jù)明文一密文對確定出密鑰，則我們說這個密碼是可破譯的。否則，我們說這個密碼是不可破譯的。密碼分析者攻擊密碼的方法主要有以下三種:窮舉攻擊:是指密碼分析者用試遍所有密鑰的方法來破譯密碼。窮舉攻擊所花費的時間等于嘗試次數(shù)乘以一次解密(加密)所需的時間。顯然可以通過增大密鑰量或加大解密(加密)算法的復雜性來對抗窮舉攻擊。當密鑰量增大時，嘗試的次數(shù)必然增大。當解密(加密)算法的復雜性增大時，完成一次解密(加密)所需的時間增大。從而使窮舉攻擊在實際上不能實現(xiàn)。②統(tǒng)計分析攻擊:是指密碼分析者通過分析密文和明文的統(tǒng)計規(guī)律來破譯密碼。統(tǒng)計分析攻擊在歷史上為破譯密碼做出過極大的貢獻。許多古典密碼都可以通過分析明文字母和字母組的頻率而破譯。對抗統(tǒng)計分析攻擊的方法是設法使明文的統(tǒng)計特性不帶入密文。這樣，密文不帶有明文的痕跡，從而使統(tǒng)計分析成為不可能。③數(shù)學分析攻擊:是指密碼分析者針對加密算法的數(shù)學依據(jù)通過數(shù)學求解的方法來破譯密碼。為了對抗這種數(shù)學分析攻擊，應選用具有堅實數(shù)學基礎和足夠復雜的加密算法。此外，攻擊密碼分析者可利用的數(shù)據(jù)來分類，可將破譯密碼的類型分為下三種:①僅知密文攻擊:即密碼分析者僅根據(jù)截獲的密文來破譯密碼;②己知明文攻擊:即密碼分析者根據(jù)己經(jīng)知道的某些明文一密文對來破譯密碼。例如，密碼分析者可能知道從用戶終端送到計算機的密文數(shù)據(jù)以一個標準詞“Login”開頭。又例如，加密成密文的計算機源程序特別容易受到這種攻擊，這是因為諸如“begin”、“。nd”、“if”、“then”、“else”等詞有規(guī)律的在密文中出現(xiàn)，密碼分析者可以合理的猜測它們。近代密碼學認為，一個密碼僅當它能夠經(jīng)得起己知明文攻擊時才是可取的。③選擇明文攻擊:即密碼分析者能夠選擇明文并獲得相應的密文。這是對密碼分析者最有利的情況。計算機文件系統(tǒng)和數(shù)據(jù)庫特別容易受到這種攻擊，因為用戶可隨意選擇明文，并得到相應的密文文件和密文數(shù)據(jù)庫。密碼編制學的任務是尋求生成高強度密碼的有效算法，滿足對消息進行加密或認證的要求。密碼分析學的任務是破譯密碼或偽造認證密碼，竊取機密信息或進行詐騙破壞活動。對一個保密系統(tǒng)采取截獲密文進行分析的方法進行進攻，稱為被動進攻;非法入侵者采用刪除、更改、添加、重放、偽造等手段向系統(tǒng)注入假消息的進攻是主動進攻。進攻與反進攻、破譯與反破譯是永無止境的矛與盾的競技。一個密碼，如果無論密碼分析者截獲了多少密文和用什么方法進行不能被攻破，則稱為是絕對不可破譯的。絕對不可破譯的密碼在理論上的。但是，如果能夠利用足夠的資源，那么任何實際的密碼都是可破譯此，對我們更有實際意義的是在計算上不可破譯的密碼，如果一個密碼僅當它能夠密碼分析者根據(jù)可利用的資源所破譯，則稱為在計算上是不可破譯的。通常假定密碼分析者或攻擊者知道所使用的密碼系統(tǒng)或算法，這種攻擊作Kirchhoff假設。當然，如果密碼分析者或攻擊者不知道所使用的密碼算法，那么破譯密碼會更困難，但是密碼系統(tǒng)的安全性應依賴于密鑰，依賴于加密體制或算法本身的細節(jié)的安全性。因此，在設計一個密碼體我們的目標是在Kirchhoff假設下達到安全性。第三章RSA公鑰密碼體制著名的Rosa公鑰密碼體制是在1975年由R.L.Rivest，A.Shamir和L.Adlemen三人共同提出。Rash是最具代表性的公鑰密碼體制。由于算法完善(既可用于數(shù)據(jù)加密，又可用于數(shù)字簽名)，安全性良好，易于實現(xiàn)和理解，Rosa己成為一種應用極廣的公鑰密碼體制，也是目前世界上唯一被廣泛使用的公鑰密碼。在廣泛的應用中，不僅它的實現(xiàn)技術日趨成熟，而且安全性逐漸得到證明。由此人們越發(fā)對RSA偏愛有加，并提出了許多基于RSA的加強或變形公鑰密碼體制根據(jù)不同的應用需要，人們基于RSA算法開發(fā)了大量的加密方案與產(chǎn)品。例如Intermit所采用的電子郵件安全協(xié)議pap(prettyGoodprivacy)將RSA作為傳送會話密鑰和數(shù)字簽名的標準算法。本章我們將詳細地闡述Rosa公鑰密碼體制的數(shù)學基礎、基本思想、參數(shù)的確定及其素數(shù)的檢測等問題。3.1RSA的數(shù)學基礎知識3.1.1因子的概念一個整數(shù)能被另一個整數(shù)整除的概念是數(shù)論中的一個中心概念，記號d|a（讀作“d除a”)，意味著對某個整數(shù)k，有a一k*d。0可被每個整數(shù)整除。如果a>0且d>a則d<=}a}。如果dale，則我們也可以說a是d的倍數(shù)。如果dale并且d>0，則我們說d是a的約數(shù)。注意，d∣a當且僅當(d)|a,因此定義約數(shù)為非負整數(shù)不會失去一般性，只要明白a的任何約數(shù)的相應負數(shù)同樣能整除a。一個整數(shù)a的約數(shù)最小為l，最大為∣a∣。例如，24的約數(shù)有1，2，3，4,6，8，12和24。每個整數(shù)a都可以被其平凡約數(shù)1和a整除。a的非平凡約數(shù)也稱為a的因子。例如:20的因子有2，4，5和10。3.1.2素數(shù)與合數(shù)對于某個整數(shù)p>l，并且因子僅為1和p，則我們稱p為素數(shù)(或質數(shù))。素數(shù)具有許多特殊性質，在數(shù)論中舉足輕重。按順序，下列為一個小素數(shù)序列：2，3，5，6，11，13，17，19，23，29，31，37，41，43，47，53，59，…不是素數(shù)的整數(shù)a>l稱為合數(shù)。例如，因為有3139，所以39是合數(shù)。整數(shù)1被稱為基數(shù)，它既不是質數(shù)也不是合數(shù)。類似地，整數(shù)0和所有負整數(shù)既不是素數(shù)也不是合數(shù)。亞里士多德和歐拉己經(jīng)用反證法非常漂亮的證明了“素數(shù)有無窮多個”。若不計素數(shù)的排列次序，任何大于1的整數(shù)a都能被因式分解為如下的唯一形式，我們稱為標準分解式:其中p:為自然數(shù)中的第I個素數(shù)，p，印2<.二印r，且e;為非負整數(shù)(注意e，可以為O)。例如:11011=7xllZxl3另外，如果P表示所有素數(shù)集合，則任一正整數(shù)均可唯一的表示為如下形式:（3.2）上式右邊是所有素數(shù)p的乘積;對于任一特定的值a，大多數(shù)分量娜均為0.例如:3600==24x32xs常用的素數(shù)表通常只有幾千個素數(shù)，這顯然無法滿足密碼學的要求，因為密碼體制往往建立在極大的素數(shù)基礎上。所以我們要為特定的密碼體制臨時計算符合要求的素數(shù)。這就牽涉到素性檢測的問題。判斷一個整數(shù)是不是素數(shù)的過程叫素性檢測。目前還沒有一個簡單有效的辦法來確定一個大數(shù)是否是素數(shù)。理論上常用的方法有:(1)Wilson定理:若(n-l)!=-l(modn)，則n為素數(shù);(2)窮舉檢測:若而不為整數(shù)，且n不能被任何小于石的正整數(shù)整除，則為素數(shù)。但是這些理論上的方法在n很大時，計算量太大，不適合密碼學中使用。現(xiàn)在常用的素性檢測的方法是數(shù)學家Solvay和Stassen提出的概率算法。即在某個區(qū)間上能經(jīng)受住某個概率檢測的整數(shù)，就認為它是素數(shù)。因子分解問題是NP困難問題。如果n為200位十進制數(shù)，那么對n進行素數(shù)的因式完全分解大概要花費幾十億年。所以，密碼體大制都是建立在大數(shù)的因式分解的基礎上。3.1.3公約數(shù)與最大公約數(shù)如果d是a的約數(shù)并且也是b的約數(shù)，則d是a與b的公約數(shù)。例如，24與30的公約數(shù)為l，2，3和6。注意，1是任意兩個整數(shù)的公約數(shù)。兩個不同時為0的整數(shù)a與b的最大公約數(shù)表示成gcd(a，b)。例如，例如，gcd（24，30)=6，gad(5，7)=l，gcd(0，9)=9。如果a與b不同時為0，則gcd(a，b)是,一個在l與min({a}，)之間的整數(shù)。我們定義geld(0,0)=0。下列相:質就是geld函數(shù)的基本性質:geld(a，b)=geld(b，a)geld(a，b)=geld(-a，b)geld(a，b)=geld({a{，{b1)geld(a，0)=}a{geld(a，ka)=…a…k02如果a和b是不都為0的任意整數(shù)，則god(a，b)是a與b的線性組合集合{ax+by:x,y∈z}中的最小正元素。對任意整數(shù)a與b，如果并且，則d|gcd(a，b)。對j沂有整數(shù)a和b以及任意非負整數(shù)n，gcd(a*n，b*n)=n*gcd(a，b)。對所有正整數(shù)n，a和b，如果n∣a*b并且gcd(a，n)=l，則n∣b。3.1．4互質數(shù)如果兩個整數(shù)a與b僅有公因數(shù)1，即如果gad(a，b)=l，則a與b稱為互質數(shù)。例如，8和25是互質數(shù)，因為8的約數(shù)為l，2，4，8，而15的約數(shù)為1，3，5，15。對任意整數(shù)a，b和p，如果gcd(a，p)=l且gcd(b，p)=l，則gcd(ab，p)=1這說明如果兩個整數(shù)中每一個數(shù)都與一個整數(shù)p互為質數(shù)，則它們的積與p互為質數(shù)。如果兩個正整數(shù)都分別表示為素數(shù)的乘積，則很容易確定它們的最大公約數(shù)。例如:300=2∧2*3*5∧;15=2*3∧2;gcd(18,300)==2*3*5∧0=6。確定一個大數(shù)的素數(shù)因子是不容易的，實踐中通常采用Euclidean和擴展的Echidna算法來尋找最大公約數(shù)和各自的乘法逆元。對于整數(shù)nl，n2，…nk，如果對任何I護j都有gad(nj，ni)=1則說整數(shù)n1，n2，…nk兩兩互質。3.2RSA算法RSA的理論基礎是一種特殊的可逆模指數(shù)運算。它的安全性是基于數(shù)論和計算復雜性理論中的下述論斷:求兩個大素數(shù)的乘積是計算上容易的，但要分解兩個大素數(shù)的積求出它的素因子是計算上困難的。大整數(shù)因子分解問題是數(shù)學上的著名難題，至今沒有有效的方法予以解決，因此可以確保RSA算法的安全性。下面給出RSA的算法描述:3.2.1RSA體制描述設n=pq，p和q是兩個奇素數(shù)，設，對定義:加密算法:解密算法:。其中，n，e公開，p，q，d保密。3.2.2RSA工作原理RSA算法的工作原理是選擇兩個大素數(shù)p，q，計算n=pq，其中(n)為歐拉函數(shù):選擇一個整數(shù)e，它滿足1<e<中(n)，再求出滿足e，1<d<的整數(shù)d。根據(jù)歐幾里法用(n)次運算就可求出d。這樣得到RSA系統(tǒng)的公共密鑰為k=(n，私有密鑰為k’=d。對于明文信息為m，滿足O=<m<n，對其加密和解密過別為:如果第三者進行竊聽時，他會得到幾個數(shù):m，e，n(=pq)，c……他如果碼的話，必須想辦法得到d.所以，他必須先知道p，q，即對n作素因子分而分解1024位的素數(shù)n卻是非常困難的。RSA算法實現(xiàn)過程如圖3.1在RSA算法中使用了這樣一個基本事實：到目前為止，無法找到一個有效的算法來解決兩個大質數(shù)之積。RSA的原理RSA公開密鑰算法的原理如下。選擇兩個互異的大質數(shù)p和q(p和q必須保密，一般取1024位)。計算出n=pq,z=(p-1)(q-1)。選擇一個比n小且與z互質（沒有公因子）的數(shù)e。找出一個d，使得ed-1能夠被z整除。其中，ed=1mod(p-1)(q-1).因為RSA是一種分組密碼系統(tǒng)，所以公開密鑰=（n,e）,私有密鑰=（n,d）。在以上的關系式中，n稱為模數(shù)，通信雙方都必須知道；e為加密運算的指數(shù)，發(fā)送方需要知道；而d為解密運算的指數(shù)，只有接受方才能知道。將以上的過程進一步描述如下。公開密鑰：n=pq(p、q分別為兩個互異的大素數(shù)，p、q必須保密)，e與(p-1)(q-1)互質。私有密鑰：d=e-1{mod(p-1)(q-1)}。加密：,其中M為明文，C為密文。解密：。RSA應用舉例為了對字母表中的第M個字母加密，加密算法為,第C個字母即為加密后的字母。對應的解密算法為。下面以一個簡單的例子進行計算。1、設p=5,q=7。2、所以n=pq=35,z=(5-1)(7-1)=24。3、選擇e=5(因為5與24互質)。4、選擇d=29(ed-1=144,可以被24整除)。5、所以公開密鑰為（35,5），私有密鑰為（35,29）。如果被加密的是26個字母中的第12個字母（L）,則它的密文為：C=125(mod35)=17第17個字母為Q，解密得到的明文為：M1729(mod35)=12通過以上的計算可以看出，當兩個互質數(shù)p和q取的值足夠大時，RSA的加密是非常安全的。第四章RAS的加密與解密技術的實現(xiàn)4.1RSA加密與解密代碼//構造函數(shù)///<summary>///generateprivatekeyandpublickeyarr[0]forprivatekeyarr[1]forpublickey///</summary>///<returns></returns>publicstaticstring[]GenerateKeys(){string[]sKeys=newString[2];RSACryptoServiceProviderrsa=newRSACryptoServiceProvider();sKeys[0]=rsa.ToXmlString(true);sKeys[1]=rsa.ToXmlString(false);returnsKeys;}///<summary>///RSAEncrypt///</summary>///<paramname="sSource">Sourcestring</param>///<paramname="sPublicKey">publickey</param>///<returns></returns>publicstaticstringEncryptString(stringsSource,stringsPublicKey){RSACryptoServiceProviderrsa=newRSACryptoServiceProvider();stringplaintext=sSource;byte[]cipherbytes;byte[]byteEn=rsa.Encrypt(Encoding.UTF8.GetBytes("a"),false);cipherbytes=rsa.Encrypt(Encoding.UTF8.GetBytes(plaintext),false);StringBuildersbString=newStringBuilder();for(inti=0;i<cipherbytes.Length;i++){sbString.Append(cipherbytes[i]+",");}returnsbString.ToString();}///<summary>///RSADecrypt