1、摘要：RSA 算法是基于數(shù)論的公鑰密碼體制， 是公鑰密碼體制中最優(yōu)秀的加密算法， 同時 也是第一個能同時用于加密和數(shù)字簽名的算法，也易于理解和操作。 RSA 是被研究得 最廣泛的公鑰算法，從提出到現(xiàn)在已近二十年，經(jīng)歷了各種攻擊的考驗，逐漸為人們 接受，普遍認(rèn)為是目前最優(yōu)秀的公鑰方案之一。RSA勺安全性依賴于大數(shù)的因子分解，但并沒有從理論上證明破譯 RSA的難度與大數(shù)分解難度等價。本文主要研究的內(nèi)容包 括：第一,對RSA算法進(jìn)行了全面系統(tǒng)的介紹，包括 RSA算法的應(yīng)用現(xiàn)狀和原理一大素 數(shù)的產(chǎn)生、密鑰對的產(chǎn)生、對明文的加密運算和密文的解密運算，為具體實現(xiàn)打下了 理論基礎(chǔ)；第二,介紹了 RSA機密體

2、制的一些基本概念及原理；第三，詳述了 RSA加密 的設(shè)計與實現(xiàn)，主要實現(xiàn)的模塊包括 RSA密鑰的產(chǎn)生（一對公鑰和私鑰），RSA加密算 法和解密算法的實現(xiàn)；第五 , 對該系統(tǒng)進(jìn)行了整體的測試和分析改進(jìn)； 關(guān)鍵詞： RSA 算法；公鑰密碼體制；加密；解密； VC+目錄1 課題綜述 . 11.1 課題來源 11.2 課題意義 11.3 預(yù)期目標(biāo) 12 系統(tǒng)分析 . 12.1 基礎(chǔ)知識 22.2 總體方案 42.3 功能模塊 43 系統(tǒng)設(shè)計 . 53.1 算法描述 53.2 流程圖 74 代碼編寫 . 95 運行與測試 . 145.1 產(chǎn)生公鑰和密鑰 145.2 加密與解密 14總 結(jié). 16致 謝.

3、 17參考文獻(xiàn) . 181 課題綜述1.1 課題來源隨著電子信息技術(shù)的迅速發(fā)展，人類已步入信息社會。但是由于整個社會形成了 一個巨大的計算機網(wǎng)絡(luò)，任何一個計算機網(wǎng)絡(luò)出現(xiàn)的安全問題，都會影響整個國家的 網(wǎng)絡(luò)安全，所以信息安全、計算機網(wǎng)絡(luò)安全問題已引起了人類的高度重視。無論是在 局域網(wǎng)還是在廣域網(wǎng)中，都存在著自然和人為等諸多因素的脆弱性和潛在威脅。故此， 網(wǎng)絡(luò)的安全措施應(yīng)是能全方位地針對各種不同的威脅和脆弱性，這樣才能確保網(wǎng)絡(luò)信 息的保密性、完整性和可用性。現(xiàn)代密碼學(xué)已成為信息安全技術(shù)的核心，密碼學(xué)是以 研究通信安全保密的學(xué)科，即研究對傳輸信息采用何種秘密的變換以防止第三者對信 息的竊取。公鑰密碼

4、體制的特點是：接收方 B產(chǎn)生一對密鑰(PK和SK) ; PK公開， SK保密；從PK推出SK是很困難的；A、E雙方通信時，A通過任何途徑取得E 的公鑰，用E的公鑰加密信息，加密后的信息可通過任何不安全信道發(fā)送。E收到密 文信息后，用自己私鑰解密恢復(fù)出明文。公鑰密碼體制已成為確保信息的安全性的關(guān) 鍵技術(shù)。 RSA 公鑰密碼體制到目前為止還是一種被認(rèn)可為安全的體制。1.2 課題意義RSA 公鑰加密算法是第一個既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的算法。它易于 理解和操作，也十分流行。算法的名字以發(fā)明者的姓氏首字母命名： Ron Rivest, Adi Shamir和Leonard Adleman。雖然

5、自1978年提出以來，RSA的安全性一直未能得到理 論上的證明，但它經(jīng)歷了各種攻擊，至今未被完全攻破。隨著越來越多的商業(yè)應(yīng)用和 標(biāo)準(zhǔn)化工作， RSA 已經(jīng)成為最具代表性的公鑰加密技術(shù)。 VISA、 MasterCard、 IBM、 Microsoft 等公司協(xié)力制定的安全電子交易標(biāo)準(zhǔn)( Secure Electronic Transaction，s SET) 就采用了標(biāo)準(zhǔn)RSA算法，這使得RSA在我們的生活中幾乎無處不在。網(wǎng)上交易加密連 接、網(wǎng)上銀行身份驗證、各種信用卡使用的數(shù)字證書、智能移動電話和存儲卡的驗證 功能芯片等，大多數(shù)使用 RSA技術(shù)。應(yīng)用了 RSA加密體制保證了秘密信息的安全。1

6、.3 預(yù)期目標(biāo)在充分理解RSA加密體制概念和原理的基礎(chǔ)上，用 Microsoft Visual C+ 6.0實現(xiàn)RSA 加密與解密，演示公鑰與密鑰的生成及加密與解密的過程。2 系統(tǒng)分析2.1 基礎(chǔ)知識2.1.1 素數(shù)稱整數(shù)p(p>1)是素數(shù)，如果p的因子只有±, ±>。稱 c 是兩個整數(shù) a、b 的最大公因子，如果 c是a的因子也是b的因子，即c是a b的公因子。 a和b的任一公因子，也是c的因子。表示為 c=gcd(a, b)。由于要求最大公因 子為正， 所以 gcd(a,b)=gcd(a,-b)=gcd(-a,b)=gcd(-a,-b)。 一般 gcd(a,

7、b)=gcd(|a|,|b|)由任一非0整數(shù)能整除0，可得gcd(a,0)=|a。如果將a，b都表示 為素數(shù)的乘積，則gcd( a, b)極易確定。一般由 c=gcd(a,b)可得：對每一素數(shù) p，cp=min(ap,bp)。由于確定大數(shù)的素因子不很容易，所以這種方法不能直接用于求兩個大數(shù)的最大公因 子，如何求兩個大數(shù)的最大公因子在下面介紹。如果gcd(a,b)=1，則稱a和b互素。2.1.2 模運算設(shè)n是一正整數(shù)，a是整數(shù)，如果用n除a,得商為q,余數(shù)為r，則a=qn+r,0 < r<n,其中 x 為小于或等于 x 的最大整數(shù)。用a mod n表示余數(shù)r如果(a mod n)=(

8、b mod n)，則稱兩整數(shù)a和b模n同余，記為a= bmod n。稱與a模n 同余的數(shù)的全體為a的同余類，記為a，稱a為這個同余類的表示元素。2.2.3 歐拉函數(shù)和歐拉定理歐拉函數(shù)：設(shè) n 是一正整數(shù)，小于 n 且與 n 互素的正整數(shù)的個數(shù)稱為 n 的歐拉函數(shù)， 記為© (n) 若n是素數(shù)，則顯然有© (n)=n1。若n是兩個素數(shù)p和q的乘積，貝U © (n)= © (p) x©(q)=(pq-i)。歐拉定理：若a和n互素，貝U a © (n) = 1 modn2.1.4 歐幾里德算法歐幾里得(Euclid )算法是數(shù)論中的一個基本

9、技術(shù)，是求兩個正整數(shù)的最大公因子 的簡化過程。而推廣的 Euclid 算法不僅可求兩個正整數(shù)的最大公因子，而且當(dāng)兩個正整數(shù)互素時，還可求出其中一個數(shù)關(guān)于另一個數(shù)的乘法逆元。1. 求最大公因子：Euclid 算法是基于下面一個基本結(jié)論：對任意非負(fù)整數(shù) a和正整數(shù)b,有g(shù)cd(a, b)=gcd(b, a mod b。2. 求乘法逆元：如果gcd(a, b)=1 ,則b在mod a下有乘法逆元(不妨設(shè)b<a),即存在一 x (x<a),使得bx = 1 mod a2.1.5 RSA算法中的計算問題1. RSA的加密與解密過程RSA 的加密、解密過程都為求一個整數(shù)的整數(shù)次冪，再取模。如果

10、按其含義直接 計算，則中間結(jié)果非常大，有可能超出計算機所允許的整數(shù)取值范圍。如上例中解密 運算 6677 mod 119，先求 6677再取模，則中間結(jié)果就已遠(yuǎn)遠(yuǎn)超出了計算機允許的整數(shù) 取值范圍。而用模運算的性質(zhì)：(a 為)mod n=(a mod n) (b mod n) mod n就可減小中間結(jié)果再者， 考慮如何提高加、 解密運算中指數(shù)運算的有效性。 例如求 x16， 直接計算的話需做 15次乘法。然而如果重復(fù)對每個部分結(jié)果做平方運算即求 x，x2， x4，x8，x16 則只需 4 次乘法。2. RSA密鑰的產(chǎn)生產(chǎn)生密鑰時，需要考慮兩個大素數(shù) p、q的選取，以及e的選取和d的計算。因為n=

11、pq在體制中是公開的，因此為了防止敵手通過窮搜索發(fā)現(xiàn)p、q,這兩個素數(shù)應(yīng)是在一個足夠大的整數(shù)集合中選取的大數(shù)。如果選取p和q為10100左右的大素數(shù)，那么n的階為10200,每個明文分組可以含有 664位(10200"2664，即83個8 比特字節(jié)，這比DES的數(shù)據(jù)分組(8個8比特字節(jié))大得多，這時就能看出 RSA算法 的優(yōu)越性了。因此如何有效地尋找大素數(shù)是第一個需要解決的問題。尋找大素數(shù)時一 般是先隨機選取一個大的奇數(shù)(例如用偽隨機數(shù)產(chǎn)生器) ，然后用素性檢驗算法檢驗這 一奇數(shù)是否為素數(shù)，如果不是則選取另一大奇數(shù)，重復(fù)這一過程，直到找到素數(shù)為止。 素性檢驗算法通常都是概率性的，但如

12、果算法被多次重復(fù)執(zhí)行，每次執(zhí)行時輸入不同 的參數(shù)，算法的檢驗結(jié)果都認(rèn)為被檢驗的數(shù)是素數(shù)，那么就可以比較有把握地認(rèn)為被 檢驗的數(shù)是素數(shù)。2.1.6公鑰密碼體制的基本概念在公鑰密碼體制以前的整個密碼學(xué)史中，所有的密碼算法，包括原始手工計算的、由機械設(shè)備實現(xiàn)的以及由計算機實現(xiàn)的，都是基于代換和置換這兩個基本工具。而公 鑰密碼體制則為密碼學(xué)的發(fā)展提供了新的理論和技術(shù)基礎(chǔ)，一方面公鑰密碼算法的基 本工具不再是代換和置換，而是數(shù)學(xué)函數(shù)；另一方面公鑰密碼算法是以非對稱的形式 使用兩個密鑰，兩個密鑰的使用對保密性、密鑰分配、認(rèn)證等都有著深刻的意義。可 以說公鑰密碼體制的出現(xiàn)在密碼學(xué)史上是一個最大的而且是惟一真

13、正的革命。公鑰密 碼體制的概念是在解決單鑰密碼體制中最難解決的兩個問題時提出的，這兩個問題是 密鑰分配和數(shù)字簽字。單鑰密碼體制在進(jìn)行密鑰分配時(看第5章)，要求通信雙方或者已經(jīng)有一個共享的密鑰，或者可籍助于一個密鑰分配中心。對第一個要求，常?？?用人工方式傳送雙方最初共享的密鑰，這種方法成本很高，而且還完全依賴信使的可 靠性。第二個要求則完全依賴于密鑰分配中心的可靠性。第二個問題數(shù)字簽字考慮的 是如何為數(shù)字化的消息或文件提供一種類似于為書面文件手書簽字的方法。1976年W.Diffie和M.Hellman對解決上述兩個問題有了突破，從而提出了公鑰密碼體制。2.2總體方案要實現(xiàn)生成公鑰和密鑰的功

14、能，必須先生成兩個大素數(shù)。方法是先設(shè)定隨機種子為 系統(tǒng)當(dāng)前時間，然后隨即生成兩個 100以內(nèi)的隨機數(shù)，并判斷其是否為素數(shù)，取出這 兩個素數(shù)。然后通過調(diào)用函數(shù)生成公鑰對和密鑰對，同時顯示出結(jié)果到屏幕上。隨后 可以用公鑰對明文進(jìn)行加密，將加密后的秘聞顯示出來。然后可以演示用密鑰對密文 進(jìn)行解密，并將結(jié)果顯示到屏幕上。2.3功能模塊本系統(tǒng)含有兩個功能模塊:(1) 公鑰和密鑰生成模塊：可以生成個 100以內(nèi)的素數(shù)p和q,以及n、e、d；(2) 加密和解密模塊：可以顯示加密后的數(shù)據(jù)，點擊解密可顯示解密后數(shù)據(jù)。系統(tǒng)功能界面圖如下:月生咸圖2-1系統(tǒng)功能界面圖3 系統(tǒng)設(shè)計3.1 算法描述RSA 算法描述：(

15、1) 密鑰的產(chǎn)生 選兩個保密的大素數(shù) p 和 q 。 計算n=pXq, © (n)=(p1)(q-1),其中© (n是 n的歐拉函數(shù)值。 選一整數(shù) e,滿足 1<e<© (n,且 gcd( © (n),e)=1 計算d,滿足d e=mod © (n)即 d是e在模© (n下的乘法逆元，因e與© (r互素， 由模運算可知，它的乘法逆元一定存在。 以e,n為公開鑰，d,n為秘密鑰。加密加密時首先將明文比特串分組，使得每個分組對應(yīng)的十進(jìn)制數(shù)小于 n,即分組長度小于Iog2 n。然后對每個明文分組 m,作加密運算：c =

16、 me mod n(3) 解密對密文分組的解密運算為：m cd mod n下面證明 RSA 算法中解密過程的正確性。證明：由加密過程知c= me mod n所以cd mod n = med mod n = ml mod © (n) mod n = mk© (n)+1 mod n要獲得兩個隨機的小于 100的素數(shù)，可以首先將系統(tǒng)當(dāng)前時間設(shè)置為隨機數(shù)種子， 然后對生成的隨機數(shù)取 100模，然后調(diào)用判斷素數(shù)的函數(shù)。要判斷一個屬實否為素數(shù)， 可以判斷數(shù)n從2到n的開方，是否能整除n。偽代碼如下：for(i 從 2 到 n 的開方 ; i+)if(n 被 i 整除 )則n不是素數(shù)終止

17、循環(huán)；if(i > n 的開方 )返回 n 為宿舍；求最大公因子的算法：Euclid算法就是用這種方法，因 gcd(a, b)=gcd(|a|, |b|)因此可假定算法的輸入是兩個正整數(shù)，設(shè)為d, f，并設(shè)f >d。Euclid (f, d) X f; Y d; if Y=0 then return X=gcd(f,d) ； R=X mod Y； X=Y ； Y=R ； goto 。求乘法逆元：推廣的Euclid算法先求出gcd(a, b)，當(dāng)gcd(a, b)=1時，則返回b的逆 元。Extended Euclid(f, d) (設(shè) f >d) (X1,X2,X3) (1,

18、0,f);(Y1,Y2,Y3)(0,1,d); if Y3=0 then return X3=gcd(f, d)； no inverse; if Y3=1 then return Y3=gcd(f, d)； Y2=d-1 mod f; Q=X3Y3 ； (T1,T2,T3) (X-1QY 1 ,X2-QY2 ,X3-QY3) ; (X1,X2,X3) (Y1,Y2,Y3); (Y1,Y2,Y3) (T1,T2,T3); goto 。處理明文： 將明文的每個字符提取出來將其裝換為數(shù)字。進(jìn)行加密處理，將處理后 的數(shù)字字符用“ +”相連。其中加密的算法為：求am可如下進(jìn)行，其中a,m是正整數(shù)： 將m

19、表示為二進(jìn)制形式bk bk-1bO，即m=bk2k+bk-12k-1+b12+b0因此：例如：19=1X24+0X23+0X22+1X21+1X20,所以a19=(a1)2a0)2a0)2a1)2a1從而可得以下快速指數(shù)算法：c=0; d=1 ；For i=k downto 0 d0 c=2 Xc;d=(d Xd) mod n;c=c+1;d=(d >a)mod nreturn d.其中d是中間結(jié)果，d的終值即為所求結(jié)果。c在這里的作用是表示指數(shù)的部分結(jié)果， 其終值即為指數(shù)m，c對計算結(jié)果無任何貢獻(xiàn)，算法中完全可將之去掉。解密過程：將“ +連接的數(shù)字字符轉(zhuǎn)換為數(shù)字并相加，用密鑰做與加密相

20、同的算法,即可得出明文。3.2流程圖圖3-1生成公鑰和私鑰流程圖圖3-2明文加密流程圖圖3-3密文解密流程圖4 代碼編寫在 RSADlg.h 中聲明成員變量：intm_p;intm_q;intm_n;intm_code;intm_decode;CStringm_dtxt;CStringm_etxt;CStringm_ptxt;1. 產(chǎn)生公鑰和密鑰：void CRSADlg:OnButtonProduce() /產(chǎn)生公鑰和密鑰函數(shù) UpdateData(true);while(true)srand(time(0);m_p = rand() % 100;m_q = rand() % 100;if

21、(isPrime(m_p) && isPrime(m_q)break;m_n = m_p * m_q;int fiN = (m_p - 1) * (m_q - 1);/int e;for (int i = 3; i < fiN; i+)if (isPrime(i) && gcd(fiN, i) = 1)m_code = i;Euler(m_code, fiN);UpdateData(false);代碼分析：首先設(shè)置系統(tǒng)的當(dāng)前時間為隨機種子，循環(huán)找出 p 和 q 并且調(diào)用判斷 素數(shù)的函數(shù)isPrime(int)使p,q都為小于100的素數(shù)，然后fiN = (

22、m_p - 1) * (m_q - 1)產(chǎn) 生fiN，產(chǎn)生m_n = m_p * m_q，通過調(diào)用gcd(fiN, i)找出與fiN互素的數(shù) m_code,調(diào) 用uler(m_code, fiN)找出m_decode,最后UpdateData(false刷新文本框顯示出結(jié)果。2. 加密明文：void CRSADlg:OnCode() / 加密函數(shù)CString temp;UpdateData(true);CString encSt = ""CString e2st = ""if (m_ptxt.IsEmpty()return;for (int i = 0

23、; i < m_ptxt.GetLength(); i+)temp = encSt;encSt.Format("%s%d%s",temp,power(int)m_ptxt.GetAt(i), m_code, m_n),"+");m_etxt = encSt;UpdateData(false); 代碼分析：首先判斷明文文本框是否為空,若為空則返回。取出明文的每個字符,將 其裝換為數(shù)字，通過加密函數(shù)power轉(zhuǎn)換后，生成的數(shù)字字符用“ + 號相連，即為密文。 調(diào)用UpdateData(false刷新文本框，顯示加密后的結(jié)果。3. 解密密文void CR

24、SADlg:OnDecode() / 解密函數(shù)int ptr;int tok;CString temp = ""UpdateData(true);CString DecSt = ""/int t = m_etxt.GetLength();for (int i = 0; i < m_etxt.GetLength();)ptr = m_etxt.Find("+", i);tok = atoi(m_etxt.Mid(i, ptr - i);temp = DecSt;DecSt.Format("%s%c", temp

25、, char(power(tok, m_decode, m_n);i = i + num(tok) + 1;m_dtxt = DecSt;UpdateData(false);代碼分析：計算出密文字符串的長度，循環(huán)尋找以字符“+”分隔得數(shù)字字符串，并將其轉(zhuǎn)換問數(shù)字，然后調(diào)用 power 函數(shù)處理，將得出的數(shù)字轉(zhuǎn)換為字符，將得出的字符連 接起來就解密出了明文，最后調(diào)用UpdateData(false刷新文本框，顯示出解密出的結(jié)果。4. 其他函數(shù)：int CRSADlg:power(int a, int n, int m) / 求出 a 的 n 次方模 m 的值int z=1, t;for(t=a;

26、 n>0; n>>=1)if (n%2=1) z=(z*t) % m;t=(t*t) % m;return(z);BOOL CRSADlg:isPrime(int x)/ 判斷整數(shù) i 是否為素數(shù)int i;for (i = 2; i <= (int)sqrt(x); i+)if (x % i = 0)break;if (i > (int)sqrt(x)return true;return false;int CRSADlg:gcd(int a, int b) / 求出 a 與 b 的公因子if (a = 0)return b;elsereturn gcd(b %

27、 a, a);void CRSADlg:Euler(int e, int fin)/求出 e 相對模 fin 的乘法逆元int u1 = 1;int u2 = 0;int u3 = fin;int v1 = 0;int v2 = 1;int v3 = e;int v = 1;int t1, t2, t3;int q;int uu, vv;int inverse, z;while (v3 != 0)q = (int)(u3 /v3);t1 = u1 - q * v1;t2 = u2 - q * v2;t3 = u3 - q * v3;u1 = v1;u2 = v2;u3 = v3;v1 = t1

28、;v2 = t2;v3 = t3;z = 1;uu = u1;vv = u2;if (vv < 0)inverse = vv + fin; elseinverse = vv;m_decode = inverse;5運行與測試5.1產(chǎn)生公鑰和密鑰點擊密鑰生成，運行效果如下圖:圖5-1產(chǎn)生公鑰和密鑰效果圖5.2加密與解密1點擊加密，運行效果如下圖:RSA密鑰生成醫(yī)8】即窖密鑰解密密鑰ff N = p * Q明丈Tbi; i eM mm a叵已35+2S5+105+1 陽襖 i oFHFnFs5解密后明文為矚解密追出 I圖5-2加密效果圖2點擊解密，運行效果如下圖:圖5-3解密效果圖總結(jié)通過這次課程設(shè)計，我對 RSA 加密體制有了更進(jìn)一步的了解。遇到的主要問題是 如何將明文按照比特分組并對其實現(xiàn) RSA 加密，以及對大素數(shù)的處理。最終大素數(shù)的 處理得以實現(xiàn)，但明文分組并沒有找到合適的方法，這就