【正文】 — 834 =5 (1001— 834)一 834 =5 10016 834 =5 10016 (3837— 3 1001) =23 10016 3837 因此 23 1001≡ l(mod3837)，故 1001關(guān)于模 3837的乘法逆元為 23。 0( , )mrr=mr 。 (歐幾里德算法求 gcd的主要概念在于：若 c=dg+r，則 (c，d)=(d， r)。首先介紹利用歐幾里德算法求 gcd(a， n)的方法，再介紹求乘法逆元的方法。 利用 Euclid(歐幾里德 )算法 (輾轉(zhuǎn)相除法 )求乘法逆元：己知 a及 n且 (a,n) =1，求 1 1(mod )aa n? ? 。費(fèi)爾馬定理和歐拉定理及其推論在構(gòu)成了 RSA算法的主要理論基礎(chǔ)。 定理 ：如果 P是素?cái)?shù)，且 gcd(m， P)=l(可表示為 (m， P)=1)，則1 1 modpmp? ? ，費(fèi)爾馬定理還存在另一種等價(jià)形式：如果 P是素?cái)?shù)， m是任意正整數(shù)，則 (mod )pm m p? 。 定理 P和 q是兩個不同的素?cái)?shù)， n=p q，則 ()n? =(P— 1) (q1)，對 任意的 X∈ nz 。其中 ()m? 為歐拉函數(shù)，它是比 m小但與 m互素的正整數(shù)個數(shù)。 由定義知，當(dāng) P是素?cái)?shù)時(shí)， ()n? =P1。 歐拉函數(shù)、歐拉定理和費(fèi)爾馬定理 歐拉函數(shù) ()n? ：是一個定義在正整數(shù)上的函數(shù)，其值等于 0， 1， 2， 3， ...n1中與 n互素的數(shù)的個數(shù)。 既約剩余系 (Reduced Set of Residues)：在模 n的完全剩余系中，若將所有與 n互素的剩余類形成一個集合，則稱此集合為模 n的既約剩余系，以 *nz 表示。這 意味著，對每一個整數(shù)a，它的模 n剩余是從 0到 n1之間的某個整數(shù)。很明顯地，集合 {0， l， 2，．．．，n1}為模 n的一完全剩余系。 RSA加解密系統(tǒng)的研究與實(shí)現(xiàn) 第 14 頁 共 53 頁 剩余類 (Residue Class)：很明顯地，利用同余概念，所有整數(shù)在模 n中被分成 n個不同的剩余類；為 n所整除的數(shù) (即余數(shù)為 O)為一剩余類，被 n所除余數(shù)為 1的數(shù)為另一剩余類，余 2的數(shù)又為一剩余類，以此類推。 同余及模運(yùn)算 同余：假定有三個整數(shù) a， b， n(n≠ O)，當(dāng)我們稱 a在模 n時(shí)與 b同余，是指當(dāng)且僅當(dāng)a與 b的差為 n的整數(shù)倍，即 ab=Kn，其中 k為任一整數(shù)。以此來和本質(zhì)上的困難性相區(qū) 分。 定義 b： 一個可逆函數(shù) f，若它滿足： X∈ A，易于計(jì)算 f(x)； 2．對“幾乎所有 x∈ A，由 f(X)求 x“極為困難’’，以至于實(shí)際上不可能做到。 定義 a：令函數(shù) f是集合 A到集合 B的映射，以 f： A→ B表示。與密碼體制關(guān)系更為密切的陷門單向函數(shù)，即函數(shù)及其逆函數(shù)的計(jì)算都 存在有效的算法，而且可以將計(jì)算函數(shù)的方法公開。 單向和陷門單向函數(shù) RSA的安全性主要取決于構(gòu)造其加密算法的數(shù)學(xué)函數(shù)的求逆困難性，這同大多數(shù)公鑰密碼系統(tǒng)一樣 (譬如 EIGamal算法就是基于離散對數(shù)問題的困難性），我們稱這樣的函數(shù)為單向函數(shù)。 華北科技學(xué)院畢業(yè)設(shè)計(jì)（論文） 第 13 頁 共 53 頁 3 RSA 算法的數(shù)學(xué)理論基礎(chǔ) 在密碼學(xué)中需要使用到許多數(shù)學(xué)理論，例如數(shù)論、信息論、復(fù)雜度理論等，它們是設(shè)計(jì)密碼系統(tǒng)及協(xié)議不可或缺的工具，其中數(shù)論 是密碼學(xué)中 (尤其是公開密鑰密碼系統(tǒng)中 )最重要的數(shù)學(xué)基礎(chǔ)，因此有必要對有關(guān)數(shù)論理論做一介紹。 由于公鑰密碼體制在保證數(shù)據(jù)的機(jī)密性、完整性以及簽名和認(rèn)可等方面的突出優(yōu)點(diǎn)，它已經(jīng)成為當(dāng)今網(wǎng)絡(luò)安全中最重要的解決方法。對稱密鑰體制中，加密、解密都使用相同的密鑰。密碼學(xué)通過對稱加密或非對稱加密，以及數(shù)字簽名等技術(shù)，并借助可信機(jī)構(gòu)或證書機(jī)構(gòu)的輔助來提供這種服務(wù)。密碼學(xué)可通過密碼數(shù)據(jù)，數(shù)字簽名和鑒別協(xié)議等技術(shù)來提供這種真實(shí)性服務(wù)。 鑒別 這是一種與數(shù)據(jù)來源和身份鑒別有關(guān)的安全服務(wù)。非授權(quán)修改包括 數(shù)據(jù)的篡改，刪除，插入和重放等。 數(shù)據(jù)完整性 數(shù)據(jù)完整性即用于確保數(shù)據(jù)在存儲和傳輸過程中不被非授權(quán)修改的安全屬性。 機(jī)密性 是一種允許特定用戶訪問和閱讀信息，而非授權(quán)用戶對信息內(nèi)容不可理解的安全屬性。但今天，密碼學(xué)已得到了更加神術(shù)廣泛的發(fā)展。密碼系統(tǒng)只要滿足以下兩條重則之一就稱為計(jì)算上不可破譯： （ 1） 破譯密文的代價(jià)超過被加密信息的價(jià)值； （ 2） 破譯密文的時(shí)間超過信息的有用期。但是，只要有足夠的資源，那么任何實(shí)際的密碼體制都是可以破譯的。對于一個密碼體制，如果密碼分析者無論獲得多少密文以及用什么方法進(jìn)行攻擊都不能破譯，則稱絕對不可破譯的密碼體制。 以上四種方法中，唯密文攻擊的強(qiáng)度最弱，其他情況的攻擊強(qiáng)度依次增加。 (Chosenplaintext Attack)：密碼攻擊者可以選擇一些明文， 并得到相應(yīng)的密文。 根據(jù)密碼攻擊者在密碼系統(tǒng)中獲得信息的不同，通?？梢栽谙率鏊姆N情況下對密碼體制進(jìn)行攻擊： (ciphtextonly attack)：密碼攻擊者僅知道一些密文。 攻擊：密碼攻擊者針對加密變換的數(shù)學(xué)基礎(chǔ)，通過數(shù)學(xué)求解的方法來設(shè)法找到相應(yīng)的解密變換。 ：密碼攻擊者通過分析密文和明文的統(tǒng)計(jì)規(guī)律來破譯密碼。 密碼攻擊者攻擊密碼體制的方法主要有以下三種： ：密碼攻 擊者通過試遍所有的密鑰來進(jìn)行破譯。 密碼分析技術(shù) 密碼分析學(xué)是密碼學(xué)的一個重要分支，是研究在不知道密鑰的情況下，利用密鑰體制的弱點(diǎn)恢復(fù)明文的一門學(xué)科。 （ 6）密鑰 (key)：包括加密密鑰和解密密鑰。 （ 5）解密 (decryption)：把密文轉(zhuǎn)變?yōu)槊魑牡倪^程。 （ 4）加密 (encryption)：用某種方法偽裝信息以隱藏它的內(nèi)容的過程。 （ 2）密文 (ciphertext)：就是加密后的消息，一般用 c表示。 密碼學(xué)基本概念 （ 1）明文 (plaintext)：也就是消息 (message)。凡是用特種符號按照通訊雙方約定的方法把電文的原形隱蔽起來，不為第三者所識別的通訊方式稱為密碼通訊。密碼學(xué)是研究信息系統(tǒng)安全保密的科學(xué)，它包括兩個分支， 密碼編碼學(xué)和密碼分析學(xué)；密碼編碼學(xué)是對信息進(jìn)行編碼實(shí)現(xiàn)信息隱蔽的技術(shù)和科學(xué)；密碼分析學(xué)是研究分析破譯密碼的技術(shù)和科學(xué)?？偨Y(jié)了全文的研究工作，指明了下一步的研究方向。并研究了密鑰對的生成實(shí)現(xiàn)以及加解密過程的整體實(shí)現(xiàn)。這一章是本文的重點(diǎn)。 對 RSA公鑰密碼系統(tǒng)進(jìn)行了詳細(xì)的研究，包括安全性的討論，常用攻擊方法及其對策的介紹， RSA算法的典型應(yīng)用及舉例。介紹了公鑰密碼系統(tǒng)中應(yīng)用到的基本數(shù)論知識，為后面相關(guān)章節(jié)奠定理論基礎(chǔ)。介紹了密碼學(xué)的一些基本概念以及密碼分析技術(shù)，討論了密碼學(xué)中的安全性定義，引出了公鑰密碼體制與私鑰密碼體制。闡述了課題的研究背景和意義，國內(nèi)外的研究現(xiàn)狀和發(fā)展趨勢，并介紹了本文研究的主要內(nèi)容。 本文的工作和內(nèi)容安排 在閱讀大量國內(nèi)外研究成果的基礎(chǔ)上，討論了針對 RSA 的各種攻擊方法，以及如何作出處理以抵制這些攻擊；討論了 RSA 的安全性和 RSA 的參數(shù)選擇詳細(xì)討論了大素?cái)?shù)的生成和檢測；研究了 RSA 公鑰密碼系統(tǒng)中用到的算法；以同余理論為基礎(chǔ)，推廣了整除性的兩個性質(zhì)；實(shí)現(xiàn)了 RSA 公鑰密碼體制大部分算法模塊；提出了一種快速模運(yùn)算算法。 華北科技學(xué)院畢業(yè)設(shè)計(jì)（論文） 第 9 頁 共 53 頁 總之，上述各個實(shí)現(xiàn)算法分別從不同方面改進(jìn)了 RSA加密算法，使得加密速度有了一定的提高。是將 RSA傳統(tǒng)算法中的求模運(yùn)算變成一系列 2的乘冪的余數(shù)和運(yùn)算，可以在一定程度上提高計(jì)算速度，但是由于在實(shí)際實(shí)現(xiàn)時(shí)， RSR算法要進(jìn)行對大整數(shù)進(jìn)行字節(jié)、比特的不斷轉(zhuǎn)換，不 適合與其他算法聯(lián)合使用。但是，在求冪運(yùn)算的過程中，基數(shù)的大小也是影響運(yùn)算速度的重要因素，而該算法只是減小了指數(shù)的長度。 指數(shù) 2k進(jìn)制化算法。是利用“乘同余對稱 特性”來減少加密和解密運(yùn)算中乘法和求模運(yùn)算量的一種改進(jìn)算法。該算法在一定程度上改善了 RSA的效率。但在實(shí)現(xiàn)過程中，由于算法中包含有大數(shù)的乘方運(yùn)算，在計(jì)算機(jī)上運(yùn)算時(shí)，會耗費(fèi)大量的時(shí)間，嚴(yán)重影響了 RSA的加密效率，制約了它的應(yīng)用，因此人們對其從不同方面進(jìn)行了改進(jìn)，并形成了以下實(shí)現(xiàn)算法： 傳統(tǒng)實(shí)現(xiàn)算法。由于算法完善 (既可用于數(shù)據(jù)加密，又可用于數(shù)字簽名 )，安全性良好 (據(jù)傳山東大學(xué)信息科學(xué)與工程學(xué)院的季凱和他的破解團(tuán)隊(duì)成員劉強(qiáng)等人宣布己找到可有效破解RSA的方法，并公布了算法，但未經(jīng)證實(shí) )，易于實(shí)現(xiàn)和理解， RSA已成為一種應(yīng)用極廣的公鑰密碼體制，它的提出真正使得互不相識的通信雙方在一個不安全的信道上進(jìn)行安全通信最終成 為可能。因而，對 RSA 公鑰密碼系統(tǒng)算法中的大整數(shù)運(yùn)算進(jìn)行研究具有顯著的現(xiàn)實(shí)價(jià)值。 RSA加解密系統(tǒng)的研究與實(shí)現(xiàn) 第 8 頁 共 53 頁 RSA 加解密可歸結(jié)為對 Mx (modN)的運(yùn)算。 RSA 是公鑰密碼體制中最成熟、最典型的代表，已成為數(shù)據(jù)加密事實(shí)上的標(biāo)準(zhǔn)。因此，目前密碼系統(tǒng)大多采用混和密碼體系，即用公鑰密碼體制實(shí)現(xiàn)密鑰管理和數(shù)字簽名，用傳統(tǒng)密碼體制實(shí)現(xiàn)大量信息的加解密。公鑰密鑰體制證實(shí)了從發(fā)送端到接收端無密鑰傳輸?shù)谋Ｃ芡ㄐ攀强尚械?，從而非常適合于計(jì)算機(jī)網(wǎng)絡(luò)的保密通信。公鑰密碼體制中加密算法和解密算法是公開的，加密、解密使用兩個不同的密鑰。 密碼體制按密鑰可以劃分為傳統(tǒng)密碼體制和公鑰密碼體制兩種。信息安全涉及法律、管理和技術(shù)等方面，在此僅討論技術(shù)方面。若把在網(wǎng)絡(luò)上傳送的保密信息以密文的方式傳輸，使竊聽者難以獲得有用信息，則可達(dá)到安全通信的目的。然 而，人與人之間存在著隱私，企業(yè)間存在著技術(shù)和商業(yè)利益的競爭，但網(wǎng)絡(luò)特有的開放性，使得在網(wǎng)絡(luò)上傳輸?shù)男畔⒑苋菀妆粩r截。人們可以足不出戶，通過網(wǎng)絡(luò)學(xué)習(xí)、購物、匯款等活動。 研究背景和意義 在計(jì)算機(jī)網(wǎng)絡(luò)蓬勃發(fā)展的今天，信息的交流與傳輸變得更為便捷與快速。特別是隨著計(jì)算機(jī)網(wǎng)絡(luò)和通信技術(shù)的發(fā)展，數(shù)據(jù)的保護(hù)、安全與隱私變得越來越重要。Large prime Numbers。s work security solutions. The security and performance of RSA public key cryptosystem which is proposal by R． L． ． Shamir and L． Adleman in 1 977 has been accepted， and it has bee the most famous cryptosystem． However,inefficiency is still a problem in theencryption and decryption process． This disadvantage has bee a bottleneck problem of RSA． Hence,how to implement RSA algorithm faster is a research content of modem cryptography． A secure and robust information system needs all kinds of information security technology． A lot of central security technology which is widely used in puter work derives from modern cryptography． The research and development of this technology is an important safeguard of the puter technology． In this paper we mainly study multiple— precision modular exponentiation algorithm in the implementation of RSA algorithm． This algorithm can be transformed as multiplication，modular multiplication and modular exponentiation algorithm． We can use the software Visual C++to implement them． RSA is mature publickey cryptography at present,it can encrypt， make a scratch of RSA加解密系統(tǒng)的研究與實(shí)現(xiàn) 第 6 頁 共 53 頁 digital and validate degree． It has been used in many security and identification system， such as we can and explorer security mail,remote loginand smart cards and function as the core of the security system． RSA algorithms canoperate with faster speed and has more ability to resist physical a