RSA算法課程設計報告

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

2、a 機密體制的一些基本概念及原理；第三，詳述了 rsa 加密的設計與實現(xiàn)，主要實現(xiàn)的模塊包括 rsa 密鑰的產(chǎn)生（一對公鑰和私鑰） ， rsa 加密算法和解密算法的實現(xiàn)；第五,對該系統(tǒng)進行了整體的測試和分析改進； 關鍵詞：rsa 算法；公鑰密碼體制；加密；解密；vc+ 目目 錄錄 1 課題綜述 .1 1.1 課題來源.1 1.2 課題意義.1 1.3 預期目標.1 2 系統(tǒng)分析 .1 2.1 基礎知識.2 2.2 總體方案.4 2.3 功能模塊.4 3 系統(tǒng)設計 .5 3.1 算法描述.5 3.2 流程圖.7 4 代碼編寫 .9 5 運行與測試 .14 5.1 產(chǎn)生公鑰和密鑰.14 5.2 加

3、密與解密.14 總 結 .16 致 謝 .17 參考文獻 .18 現(xiàn)代密碼學課程設計報告 1 1 課題綜述課題綜述 1.1 課題來源課題來源 隨著電子信息技術的迅速發(fā)展，人類已步入信息社會。但是由于整個社會形成了 一個巨大的計算機網(wǎng)絡，任何一個計算機網(wǎng)絡出現(xiàn)的安全問題，都會影響整個國家的 網(wǎng)絡安全，所以信息安全、計算機網(wǎng)絡安全問題已引起了人類的高度重視。無論是在 局域網(wǎng)還是在廣域網(wǎng)中，都存在著自然和人為等諸多因素的脆弱性和潛在威脅。故此， 網(wǎng)絡的安全措施應是能全方位地針對各種不同的威脅和脆弱性，這樣才能確保網(wǎng)絡信 息的保密性、完整性和可用性?，F(xiàn)代密碼學已成為信息安全技術的核心，密碼學是以 研究

4、通信安全保密的學科，即研究對傳輸信息采用何種秘密的變換以防止第三者對信 息的竊取。公鑰密碼體制的特點是：接收方 b 產(chǎn)生一對密鑰（pk 和） ；公開， 保密；從推出是很困難的；、雙方通信時，通過任何途徑取得 的公鑰，用的公鑰加密信息，加密后的信息可通過任何不安全信道發(fā)送。收到密 文信息后，用自己私鑰解密恢復出明文。公鑰密碼體制已成為確保信息的安全性的關 鍵技術。rsa 公鑰密碼體制到目前為止還是一種被認可為安全的體制。 1.2 課題意義課題意義 rsa 公鑰加密算法是第一個既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的算法。它易于 理解和操作，也十分流行。算法的名字以發(fā)明者的姓氏首字母命名：ron riv

5、est, adi shamir 和 leonard adleman。雖然自 1978 年提出以來，rsa 的安全性一直未能得到 理論上的證明，但它經(jīng)歷了各種攻擊，至今未被完全攻破。隨著越來越多的商業(yè)應用 和標準化工作，rsa 已經(jīng)成為最具代表性的公鑰加密技術。 visa、mastercard、ibm、microsoft 等公司協(xié)力制定的安全電子交易標準（secure electronic transactions，set）就采用了標準 rsa 算法，這使得 rsa 在我們的生活中 幾乎無處不在。網(wǎng)上交易加密連接、網(wǎng)上銀行身份驗證、各種信用卡使用的數(shù)字證書、 智能移動電話和存儲卡的驗證功能芯片等

6、，大多數(shù)使用 rsa 技術。應用了 rsa 加密 體制保證了秘密信息的安全。 1.3 預期目標預期目標 在充分理解 rsa 加密體制概念和原理的基礎上，用 microsoft visual c+ 6.0 實現(xiàn) rsa 加密與解密，演示公鑰與密鑰的生成及加密與解密的過程。 現(xiàn)代密碼學課程設計報告 2 2 系統(tǒng)分析系統(tǒng)分析 2.1 基礎知識基礎知識 2.1.1 素數(shù) 稱整數(shù) p(p1)是素數(shù)，如果 p 的因子只有1，p。 稱 c 是兩個整數(shù) a、b 的最大公因子，如果 c 是 a 的因子也是 b 的因子，即 c 是 a、b 的公因子。 a 和 b 的任一公因子，也是 c 的因子。 表示為 c=gc

7、d(a, b)。 由于要求最大公因子為正，所以 gcd(a,b)=gcd(a,-b)=gcd(-a,b)=gcd(-a,-b)。一般 gcd(a,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 模運算 設 n 是

8、一正整數(shù)，a 是整數(shù)，如果用 n 除 a，得商為 q，余數(shù)為 r，則 a=qn+r,0rn, 其中 x 為小于或等于 x 的最大整數(shù)。 用 a mod n 表示余數(shù) r 如果(a mod n)=(b mod n)，則稱兩整數(shù) a 和 b 模 n 同余，記為 ab mod n。稱與 a 模 n 同余的數(shù)的全體為 a 的同余類，記為a，稱 a 為這個同余類的表示元素。 2.2.3 歐拉函數(shù)和歐拉定理 歐拉函數(shù)：設 n 是一正整數(shù)，小于 n 且與 n 互素的正整數(shù)的個數(shù)稱為 n 的歐拉函 數(shù)，記為 (n)。 若 n 是素數(shù)，則顯然有 (n)=n-1。 若 n 是兩個素數(shù) p 和 q 的乘積，則 (n

9、)=(p)(q)=(p-1)(q-1)。 歐拉定理：若 a 和 n 互素，則 a(n)1 mod n。 2.1.4 歐幾里德算法 現(xiàn)代密碼學課程設計報告 3 歐幾里得（euclid）算法是數(shù)論中的一個基本技術，是求兩個正整數(shù)的最大公因子 的簡化過程。而推廣的 euclid 算法不僅可求兩個正整數(shù)的最大公因子，而且當兩個正 整數(shù)互素時，還可求出其中一個數(shù)關于另一個數(shù)的乘法逆元。 1. 求最大公因子： euclid 算法是基于下面一個基本結論： 對任意非負整數(shù) a 和正整數(shù) b，有 gcd(a, b)=gcd(b, a mod b)。 2. 求乘法逆元： 如果 gcd(a, b)=1 ，則 b 在

10、 mod a 下有乘法逆元（不妨設 ba） ，即存在一 x (xa)，使 得 bx1 mod a。 2.1.5 rsa 算法中的計算問題 1. rsa 的加密與解密過程 rsa 的加密、解密過程都為求一個整數(shù)的整數(shù)次冪，再取模。如果按其含義直接 計算，則中間結果非常大，有可能超出計算機所允許的整數(shù)取值范圍。如上例中解密 運算 6677 mod 119，先求 6677 再取模，則中間結果就已遠遠超出了計算機允許的整 數(shù)取值范圍。而用模運算的性質： (ab) mod n=(a mod n)(b mod n) mod n 就可減小中間結果再者，考慮如何提高加、解密運算中指數(shù)運算的有效性。例如求 x1

11、6，直接計算的話需做 15 次乘法。然而如果重復對每個部分結果做平方運算即求 x，x2，x4，x8，x16 則只需 4 次乘法。 2. rsa 密鑰的產(chǎn)生 產(chǎn)生密鑰時，需要考慮兩個大素數(shù) p、q 的選取，以及 e 的選取和 d 的計算。 因為 n=pq 在體制中是公開的，因此為了防止敵手通過窮搜索發(fā)現(xiàn) p、q，這兩個 素數(shù)應是在一個足夠大的整數(shù)集合中選取的大數(shù)。如果選取 p 和 q 為 10100 左右的大 素數(shù)，那么 n 的階為 10200，每個明文分組可以含有 664 位（102002664） ，即 83 個 8 比特字節(jié)，這比 des 的數(shù)據(jù)分組（8 個 8 比特字節(jié)）大得多，這時就能看

12、出 rsa 算 法的優(yōu)越性了。因此如何有效地尋找大素數(shù)是第一個需要解決的問題。尋找大素數(shù)時 一般是先隨機選取一個大的奇數(shù)（例如用偽隨機數(shù)產(chǎn)生器） ，然后用素性檢驗算法檢 驗這一奇數(shù)是否為素數(shù)，如果不是則選取另一大奇數(shù)，重復這一過程，直到找到素數(shù) 為止。素性檢驗算法通常都是概率性的，但如果算法被多次重復執(zhí)行，每次執(zhí)行時輸 入不同的參數(shù)，算法的檢驗結果都認為被檢驗的數(shù)是素數(shù)，那么就可以比較有把握地 認為被檢驗的數(shù)是素數(shù)。 現(xiàn)代密碼學課程設計報告 4 2.1.6 公鑰密碼體制的基本概念 在公鑰密碼體制以前的整個密碼學史中，所有的密碼算法，包括原始手工計算的、 由機械設備實現(xiàn)的以及由計算機實現(xiàn)的，都是

13、基于代換和置換這兩個基本工具。而公 鑰密碼體制則為密碼學的發(fā)展提供了新的理論和技術基礎，一方面公鑰密碼算法的基 本工具不再是代換和置換，而是數(shù)學函數(shù)；另一方面公鑰密碼算法是以非對稱的形式 使用兩個密鑰，兩個密鑰的使用對保密性、密鑰分配、認證等都有著深刻的意義?？?以說公鑰密碼體制的出現(xiàn)在密碼學史上是一個最大的而且是惟一真正的革命。公鑰密 碼體制的概念是在解決單鑰密碼體制中最難解決的兩個問題時提出的，這兩個問題是 密鑰分配和數(shù)字簽字。單鑰密碼體制在進行密鑰分配時（看第 5 章） ，要求通信雙方 或者已經(jīng)有一個共享的密鑰，或者可籍助于一個密鑰分配中心。對第一個要求，常常 可用人工方式傳送雙方最初共

14、享的密鑰，這種方法成本很高，而且還完全依賴信使的 可靠性。第二個要求則完全依賴于密鑰分配中心的可靠性。第二個問題數(shù)字簽字考慮 的是如何為數(shù)字化的消息或文件提供一種類似于為書面文件手書簽字的方法。1976 年 w.diffie 和 m.hellman 對解決上述兩個問題有了突破，從而提出了公鑰密碼體制。 2.2 總體方案總體方案 要實現(xiàn)生成公鑰和密鑰的功能，必須先生成兩個大素數(shù)。方法是先設定隨機種子 為系統(tǒng)當前時間，然后隨即生成兩個 100 以內的隨機數(shù)，并判斷其是否為素數(shù)，取出 這兩個素數(shù)。然后通過調用函數(shù)生成公鑰對和密鑰對，同時顯示出結果到屏幕上。隨 后可以用公鑰對明文進行加密，將加密后的秘

15、聞顯示出來。然后可以演示用密鑰對密 文進行解密，并將結果顯示到屏幕上。 2.3 功能模塊功能模塊 本系統(tǒng)含有兩個功能模塊： （1）公鑰和密鑰生成模塊：可以生成個 100 以內的素數(shù) p 和 q，以及 n、e、d； （2）加密和解密模塊：可以顯示加密后的數(shù)據(jù)，點擊解密可顯示解密后數(shù)據(jù)。 系統(tǒng)功能界面圖如下： 現(xiàn)代密碼學課程設計報告 5 圖 2-1 系統(tǒng)功能界面圖 3 系統(tǒng)設計系統(tǒng)設計 3.1 算法描述算法描述 rsa 算法描述： (1) 密鑰的產(chǎn)生 選兩個保密的大素數(shù) p 和 q。 計算 n=pq，(n)=(p-1)(q-1),其中 (n)是 n 的歐拉函數(shù)值。 選一整數(shù) e，滿足 1e n 的

16、開方 ） 返回 n 為宿舍； 求最大公因子的算法：euclid 算法就是用這種方法，因 gcd(a, b)=gcd(|a|, |b|)，因此 可假定算法的輸入是兩個正整數(shù)，設為 d，f，并設 f d。 euclid（f, d） xf; yd； if y=0 then return x=gcd(f,d)； r=x mod y； x=y； y=r； goto 。 求乘法逆元：推廣的 euclid 算法先求出 gcd(a, b)，當 gcd(a, b)=1 時，則返回 b 的 逆元。 extended euclid(f, d) （設 f d） (x1,x2,x3)(1,0,f);(y1,y2,y3)

17、(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)(x1-qy1,x2-qy2,x3-qy3); (x1,x2,x3)(y1,y2,y3); (y1,y2,y3)(t1,t2,t3); goto 。 處理明文：將明文的每個字符提取出來將其裝換為數(shù)字。進行加密處理，將處理 后的數(shù)字字符用“+”號相連。其中加密的算法為：求 am 可如下進行，其中 a，m 是正 整數(shù)： 將 m 表示為二進制形式 bk bk-1b

18、0，即 現(xiàn)代密碼學課程設計報告 7 m=bk2k+bk-12k-1+b12+b0 因此： 例如：19=124+023+022+121+120，所以 a19=(a1)2a0)2a0)2a1)2a1 從而可得以下快速指數(shù)算法： c=0; d=1； for i=k downto 0 d0 c=2c; d=(dd) mod n; if bi=1 then c=c+1; d=(da) mod n return d. 其中 d 是中間結果，d 的終值即為所求結果。c 在這里的作用是表示指數(shù)的部分結果， 其終值即為指數(shù) m，c 對計算結果無任何貢獻，算法中完全可將之去掉。 解密過程：將“+”連接的數(shù)字字符轉

19、換為數(shù)字并相加，用密鑰做與加密相同的算法， 即可得出明文。 3.2 流程圖流程圖 現(xiàn)代密碼學課程設計報告 8 開 始 產(chǎn)生素數(shù) p 和 q p,q100 且為素數(shù) n = (p - 1) * (q - 1) 找出 e e 為素數(shù)與 n 互素 求出 d 結 束 是 是 否 否 圖 3-1 生成公鑰和私鑰流程圖 現(xiàn)代密碼學課程設計報告 9 開 始 明文不為空 將明文轉換為數(shù)字加密 結 束 取得明文 是 否 圖 3-2 明文加密流程圖 開 始 密文不為空 將密文轉換為明文 結 束 取得密文 是 否 圖 3-3 密文解密流程圖 4 代碼編寫代碼編寫 現(xiàn)代密碼學課程設計報告 10 在 rsadlg.h

20、中聲明成員變量： 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 (isprime(m_p) m_n = m_p * m_q; int fin = (m_p - 1) * (m_q

21、 - 1); /int e; for (int i = 3; i fin; i+) if (isprime(i) break; 現(xiàn)代密碼學課程設計報告 11 euler(m_code, fin); updatedata(false); 代碼分析：首先設置系統(tǒng)的當前時間為隨機種子，循環(huán)找出 p 和 q 并且調用判斷 素數(shù)的函數(shù) isprime(int)使 p,q 都為小于 100 的素數(shù)，然后 fin = (m_p - 1) * (m_q - 1)產(chǎn) 生 fin，產(chǎn)生 m_n = m_p * m_q，通過調用 gcd(fin, i)找出與 fin 互素的數(shù) m_code，調 用 uler(m_c

22、ode, fin)找出 m_decode，最后 updatedata(false)刷新文本框顯示出結果。 2.加密明文： void crsadlg:oncode() /加密函數(shù) cstring temp; updatedata(true); cstring encst = ; cstring e2st = ; if (m_ptxt.isempty() return; for (int i = 0; i m_ptxt.getlength(); i+) temp = encst; encst.format(%s%d%s,temp,power(int)m_ptxt.getat(i), m_code,

23、 m_n),+); m_etxt = encst; updatedata(false); 代碼分析：首先判斷明文文本框是否為空，若為空則返回。取出明文的每個字符，將 其裝換為數(shù)字，通過加密函數(shù) power 轉換后，生成的數(shù)字字符用“+”號相連，即為密 文。調用 updatedata(false)刷新文本框，顯示加密后的結果。 3.解密密文 void crsadlg:ondecode() / 解密函數(shù) 現(xiàn)代密碼學課程設計報告 12 int ptr; int tok; cstring temp = ; updatedata(true); cstring decst = ; /int t = m_e

24、txt.getlength(); for (int i = 0; i 0; n=1) if (n%2=1) z=(z*t) % m; t=(t*t) % m; 現(xiàn)代密碼學課程設計報告 13 return(z); bool crsadlg:isprime(int x) /判斷整數(shù) i 是否為素數(shù) int i; for (i = 2; i (int)sqrt(x) return true; return false; int crsadlg:gcd(int a, int b) /求出 a 與 b 的公因子 if (a = 0) return b; else return gcd(b % a, a)

25、; void crsadlg:euler(int e, int fin) /求出 e 相對模 fin 的乘法逆元 int u1 = 1; int u2 = 0; int u3 = fin; int v1 = 0; 現(xiàn)代密碼學課程設計報告 14 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

26、= v1; u2 = v2; u3 = v3; v1 = t1; v2 = t2; v3 = t3; z = 1; uu = u1; vv = u2; if (vv 0) inverse = vv + fin; else inverse = vv; m_decode = inverse; 5 運行與測試運行與測試 現(xiàn)代密碼學課程設計報告 15 5.1 產(chǎn)生公鑰和密鑰產(chǎn)生公鑰和密鑰 點擊密鑰生成，運行效果如下圖： 圖 5-1 產(chǎn)生公鑰和密鑰效果圖 5.2 加密與解密加密與解密 1.點擊加密，運行效果如下圖： 圖 5-2 加密效果圖 2.點擊解密，運行效果如下圖： 現(xiàn)代密碼學課程設計報告 16 圖 5-3 解密效果圖 現(xiàn)代密碼學課程設計報告 17 總總 結結 通過這次課程設計，我對 rsa 加密體制有了更進一步的了解。遇到的主要問題 是如何將明文按照比特分組并對其實現(xiàn) rsa 加密，以及對大素數(shù)的處理。最終大素 數(shù)的處理得以實現(xiàn)，但明文分組并沒有找到合適的方法，這就要求我在課程設計后去 學習怎樣為明文分組機密。要想學好現(xiàn)代密碼學不僅要學習好密碼學相關知識，還要 有很好的數(shù)學基礎，還有很強的編程能力，這個課程設計是用 microsoft