基于RSA算法的文件加密系統設計

姜 楠，金英善，崔曉鋒，劉 波，李 禾

(1.大連民族學院計算機科學與工程學院，遼寧大連116605;2.遼寧科技大學 理學院，遼寧鞍山114044)

隨著網絡和通信技術的飛速進步，網上銀行、網上合同、電子簽名、網上支付等電子商務應用越來越廣泛，基于互聯網的電子商務已經成為國際現代商業的最新形式。然而，互聯網是一個面向全球用戶開放的巨大網絡，這使得電子商務交易的風險性和不確定性加大，從而對網絡傳輸過程中數據的安全和保密提出了更高的要求。電子商務要發展壯大，進行電子商務交易的數據和傳輸的信息的機密性和完整性必須受到保護，交易者的身份必須得到認證，對未被授權的進入應該進行控制［1］，密碼學的主要任務就是從理論上和實踐上解決這些問題。通過采用密碼技術對信息進行編碼可以隱蔽和保護需要保密的信息，將數據變成不可讀的格式，防止未授權者在這些信息的存儲或傳輸過程中進行篡改、刪除、替換等，從而實現消息的機密性、完整性和不可抵賴性，并且使消息的接收者應該能夠對消息的來源進行鑒別。

密碼學中包括對稱密碼體制和公鑰密碼體制兩種密碼體制，而公鑰密碼體制在電子商務安全中應用更為廣泛。公鑰密碼體制于1976年由W.Diffie和 M.Hellman 提出［2］，這種密碼體制采用了一對密鑰，一個是公開的，稱之為公鑰，另一個是秘密的，稱之為私鑰。用戶要保障私鑰的安全，公共密鑰則可以發布出去。公鑰與私鑰是有緊密關系的，但從一個密鑰難以推出另一個密鑰，用公鑰加密的信息只能用私鑰解密，反之亦然。公鑰密碼系統可用于以下三個方面:通信保密、數字簽名和密鑰交換。具有代表性的公鑰體制是RSA體制［3］，其安全性就是基于分解大整數的安全性，是迄今為止理論上最為成熟完善的公鑰密碼體制，該體制已得到廣泛的應用。

RSA加密算法是信息安全課程的一個重要內容，為了使學生能夠更好的理解和掌握這個密碼體制，設計了一個綜合性實驗項目“RSA加密算法實驗”。該試驗既融合了數論和密碼學知識，也包括了算法分析和程序設計的知識，通過該實驗的設計與編程實現可以培養學生分析問題、解決問題的綜合能力，開拓學生的創新意識，提高學生的實踐能力和開放意識，使學生獲得終身受益的理論功底和科學素養。

1 實驗原理

1.1 素數測試算法原理

目前大多數公鑰密碼體制都基于數學上的難題，RSA密碼系統的安全性基于大數分解的困難性。求一對大素數的乘積很容易，但要對這個乘積進行因式分解則非常困難，因此，可以把一對大素數的乘積公開作為公鑰，通過擴展歐幾里得算法求出私鑰，這樣利用已知的公開密鑰和密文恢復出明文非常困難。

素數是大于1且除自身和1之外沒有其他因子的自然數。素數是構成整數的因子，每一個整數都是由一個或幾個素數的不同次冪相乘得來的。目前還沒有有效的方法可以產生任意大素數，素數的生成通常是隨機選擇一個奇數n，通過素性檢測算法進行素性測試，若n沒有通過測試，拋棄n，如果通過了足夠次數的測試，則認為n是素數。在自然數n附近，每ln(n)個整數中有一個素數。下面介紹兩種素性測試算法。

(1)Solovay-Strassen素性測試算法基本原理

Solovay-Strassen素性測試是一個判定奇整數是否為素數的多項式時間的概率算法，該算法是根據Euler準則進行判定的，并且使用了雅可比函數來測試p是否為素數［4］。

Euler準則:p是奇素數，x∈Qp當且僅當x(p-1)/2≡1modp

(2)Miller-Rabin素性測試算法原理

Miller-Rabin素性測試算法也是一個多項式時間概率算法，是素性檢測的常用方法。對待測的大整數n，首先計算k，k是2整除n-1的次數，然后計算m，使得n-1=2km，選擇一個隨機整數a，1≤a≤ n-1，計算 b=ammodn，然后對n 進行素性檢測。對a選取不同的隨機數，重復t次這樣的測試。如果n都能通過測試，則我們可以斷定n不是素數的概率不大于1/4t，如果t取值很大，基本上可以肯定n就是素數［5］。

Miller-Rabin素性測試算法與Solovay-Strassen素性測試算法相比，Miller-Rabin算法的有效性和標準性都要好一些，因而使用的比較廣泛。

1.2 RSA算法原理

在RSA算法中，運算都是在集合Z*n={x=x(modn)|x∈Z，n=p·q，gcd(x，n)=1}中進行的，共有φ(n)=φ(p·q)=(p-1)(q-1)個元素，Z*n在普通乘法和模運算下構成一個群［6］。RSA算法既可以用于加密，又可以用作數字簽名，并可構造其它的簽名方案，是目前最能被人們接受的算法，國際上一些標準化組織都已接受RSA體制作為標準。在電子郵件中廣泛采用的PGP(PrettyGoodPrivacy)加密技術就是用RSA算法作為傳送會話密鑰和數字簽名的標準算法來確保電子郵件安全的。RSA算法的安全性是基于數論和計算復雜性理論中的下述論斷，求兩個大素數的乘積在計算上是容易的，但要分解兩個大素數的積求出它的素因子在計算上是困難的。大整數因子分解問題是數學上的著名難題，至今沒有有效的方法予以解決，因此可以確保RSA算法的安全性。RSA算法是非常著名的公鑰密碼算法，是一種分組密碼，明文和密文是0到n-1之間的整數，通常n的大小為1024位二進制數。該算法首先要生成密鑰，即通過素性測試算法生成兩個大素數p，q，計算 n=p×q和歐拉函數 φ(n)，φ(n)是小于n且與n互素的正整數的個數，φ(n)=(p-1)(q-1)。選擇 e使得 e大于1與 φ(n)互素，即gcd(e，φ(n))=1 ，解方程 ed≡1modφ(n)，0≤d≤n，其中e和d互為模φ(n)的乘法逆元，已知e可以用擴展歐幾里得算法求出d。這樣可以把e和n作為公開密鑰，d作為私人密鑰，然后進行加密。加密時先將消息分成大小合適的數據分組，然后對分組分別進行加密，每個明文分組m的二進制值均小于n。

對RSA算法的攻擊主要包括以下幾個方法:窮舉攻擊，數學攻擊，公共模數攻擊，計時攻擊。最基本的攻擊是窮舉攻擊，也就是嘗試所有可能的私鑰，數學攻擊的實質是試圖對兩個素數乘積的分解，計時攻擊也可以用于對RSA算法的攻擊，計時攻擊是攻擊者通過監視系統解密消息所花費的時間來確定私鑰。公共模數攻擊就是如果同一個消息用兩個不同的指數(模數相同)加密，這兩個密鑰又互素，那么無需任何指數就可以恢復出明文［7］。

2 算法設計

2.1 大素數產生算法

素性檢驗算法通常都是概率性的，但如果算法被多次重復執行，每次執行時輸入不同的參數，算法的檢驗結果都認為被檢驗的數是素數，那么就可以比較有把握地認為被檢驗的數是素數。

2.1.1 Solovay-Strassen算法

Solovay-Strassen素性測試算法使用了雅可比函數來測試p是否為素數。

具體過程如下:

(1)Zn中隨機且均勻的產生一個小于p的數a;

(2)計算 gcd(a，p);

(3)如果gcd(a，p)≠1，那么p沒有通過素性測試，它是合數;

(4)計算j=a(p-1)/2modp;

(5)計算雅可比符號 J(a，p)，若 j≠J(a，p)，那么p肯定不是素數;若j=J(a，p)，則p不是素數的概率最多為50%［5］。

2.1.2 Miller-Rabin算法

具體過程如下:

(1)選擇一個小于p的隨機數a;

(2)設j=0且z=ammodp;

(3)如果z=1或z=p-1，則p通過素性檢測，可能是素數;

(4)如果j＞0且z=1，那么p不是素數;

(5)設j=j+1，如果j＜b(b是2整除 p-1的次數)且 z≠p-1，設 z=z2modp，然后轉(4)，如果z=p-1，則p通過素性檢測，可能是素數;

(6)如果 j=b且 z≠p-1，那么 p不是素數［5］。

2.2 RSA加密算法

(1)選兩個保密的大素數p和q;

(2)計算n=p×q，φ(n)=(p-1)(q-1)，其中φ(n)是n的歐拉函數值;

(3)選一整數e，滿足1＜e＜φ(n)，且 gcd(φ(n)，e)=1;

(4)計算 d，滿足 d·e≡1modφ(n)，即 d是 e在模φ(n)下的乘法逆元，因e與φ(n)互素，由模運算可知，它的乘法逆元一定存在;

(5)以{e，n}為公開密鑰，d為秘密密鑰;

(6)計算 c=memodn，求出明文m對應的密文c;

(7)計算m=cdmodn，求出密文c對應的明文m［5］。

2.3 系統實現框圖

在本系統中首先隨機選擇一個奇數，使用素性檢測算法判斷選擇的數是否為素數，如果是保存，如果不是繼續判斷。通過大素數算法生成兩個大的素數p和q，然后計算這兩個素數的乘積n，再計算n的歐拉函數值φ(n)。之后選取一個整數e作為RSA算法的公鑰，它必須滿足大于1且與φ(n)互素。計算RSA算法中的私鑰d，而d是e在模φ(n)下的乘法逆元，可以通過擴展歐幾里得算法求出。用RSA算法的公鑰e加密信息m得到密文c，用私鑰解密密文c得到明文m，然后結束。系統實現流程如圖1。

圖1 系統流程圖

3 結語

RSA公鑰加密算法是網絡安全技術的重要部分，在身份認證、數字簽名和密鑰分配等信息安全領域中有廣泛的應用。本文主要研究大素數的生成，使用生成的大素數求出RSA算法中的密鑰，并且利用該算法進行加密和解密的原理與算法，進而編程實現信息的加密和解密系統。該系統設計的目的不僅使學生掌握公鑰密碼體制中RSA算法的基本理論，而且能夠利用計算機語言編程實現信息加解密程序。通過該算法設計與實現的實驗，可以使學生進一步理解書本上學過的密碼學理論知識，把抽象知識轉化為具體的程序設計，既可以提高學生的學習興趣，又可以培養學生的算法分析和程序設計能力以及綜合分析問題解決問題的能力。

［1］代春艷，謝曉堯，辛明軍，等.電子商務信息安全技術［M］.武漢:武漢大學出版社，2007.

［2］DIFFIE W，HELLMAN M E.New directrions in cryptography［J］.IEEE Transaction on Information Theory，1976，22(6):644-654

［3］RIVEST R L，SHAMIR A，ADLEMAN L M.A method for obtaining digital signatures and public-key cryptosystems［J］.Communications of the ACM，1978，21(2):120-126.

［4］孫淑玲.應用密碼學［M］.北京:清華大學出版社，2004.

［5］SCHNEIER B.應用密碼學［M］.2版.吳世忠，譯.北京:機械工業出版社，2000.

［6］司光東，楊加喜，譚示崇，等.RSA算法中的代數結構［J］.電子學報，2011(1):242-246.

［7］SIMMONS G J.A weak privacy protocol using the RSA cryptosystem［J］.Cryptologia，1983，7(2):180-182.