基于RSA算法的文件加密系統(tǒng)設(shè)計(jì)

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

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

隨著網(wǎng)絡(luò)和通信技術(shù)的飛速進(jìn)步，網(wǎng)上銀行、網(wǎng)上合同、電子簽名、網(wǎng)上支付等電子商務(wù)應(yīng)用越來越廣泛，基于互聯(lián)網(wǎng)的電子商務(wù)已經(jīng)成為國(guó)際現(xiàn)代商業(yè)的最新形式。然而，互聯(lián)網(wǎng)是一個(gè)面向全球用戶開放的巨大網(wǎng)絡(luò)，這使得電子商務(wù)交易的風(fēng)險(xiǎn)性和不確定性加大，從而對(duì)網(wǎng)絡(luò)傳輸過程中數(shù)據(jù)的安全和保密提出了更高的要求。電子商務(wù)要發(fā)展壯大，進(jìn)行電子商務(wù)交易的數(shù)據(jù)和傳輸?shù)男畔⒌臋C(jī)密性和完整性必須受到保護(hù)，交易者的身份必須得到認(rèn)證，對(duì)未被授權(quán)的進(jìn)入應(yīng)該進(jìn)行控制［1］，密碼學(xué)的主要任務(wù)就是從理論上和實(shí)踐上解決這些問題。通過采用密碼技術(shù)對(duì)信息進(jìn)行編碼可以隱蔽和保護(hù)需要保密的信息，將數(shù)據(jù)變成不可讀的格式，防止未授權(quán)者在這些信息的存儲(chǔ)或傳輸過程中進(jìn)行篡改、刪除、替換等，從而實(shí)現(xiàn)消息的機(jī)密性、完整性和不可抵賴性，并且使消息的接收者應(yīng)該能夠?qū)ο⒌膩碓催M(jìn)行鑒別。

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

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

1 實(shí)驗(yàn)原理

1.1 素?cái)?shù)測(cè)試算法原理

目前大多數(shù)公鑰密碼體制都基于數(shù)學(xué)上的難題，RSA密碼系統(tǒng)的安全性基于大數(shù)分解的困難性。求一對(duì)大素?cái)?shù)的乘積很容易，但要對(duì)這個(gè)乘積進(jìn)行因式分解則非常困難，因此，可以把一對(duì)大素?cái)?shù)的乘積公開作為公鑰，通過擴(kuò)展歐幾里得算法求出私鑰，這樣利用已知的公開密鑰和密文恢復(fù)出明文非常困難。

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

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

Solovay-Strassen素性測(cè)試是一個(gè)判定奇整數(shù)是否為素?cái)?shù)的多項(xiàng)式時(shí)間的概率算法，該算法是根據(jù)Euler準(zhǔn)則進(jìn)行判定的，并且使用了雅可比函數(shù)來測(cè)試p是否為素?cái)?shù)［4］。

Euler準(zhǔn)則:p是奇素?cái)?shù)，x∈Qp當(dāng)且僅當(dāng)x(p-1)/2≡1modp

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

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

Miller-Rabin素性測(cè)試算法與Solovay-Strassen素性測(cè)試算法相比，Miller-Rabin算法的有效性和標(biāo)準(zhǔn)性都要好一些，因而使用的比較廣泛。

1.2 RSA算法原理

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

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

2 算法設(shè)計(jì)

2.1 大素?cái)?shù)產(chǎn)生算法

素性檢驗(yàn)算法通常都是概率性的，但如果算法被多次重復(fù)執(zhí)行，每次執(zhí)行時(shí)輸入不同的參數(shù)，算法的檢驗(yàn)結(jié)果都認(rèn)為被檢驗(yàn)的數(shù)是素?cái)?shù)，那么就可以比較有把握地認(rèn)為被檢驗(yàn)的數(shù)是素?cái)?shù)。

2.1.1 Solovay-Strassen算法

Solovay-Strassen素性測(cè)試算法使用了雅可比函數(shù)來測(cè)試p是否為素?cái)?shù)。

具體過程如下:

(1)Zn中隨機(jī)且均勻的產(chǎn)生一個(gè)小于p的數(shù)a;

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

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

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

(5)計(jì)算雅可比符號(hào) J(a，p)，若 j≠J(a，p)，那么p肯定不是素?cái)?shù);若j=J(a，p)，則p不是素?cái)?shù)的概率最多為50%［5］。

2.1.2 Miller-Rabin算法

具體過程如下:

(1)選擇一個(gè)小于p的隨機(jī)數(shù)a;

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

(3)如果z=1或z=p-1，則p通過素性檢測(cè)，可能是素?cái)?shù);

(4)如果j＞0且z=1，那么p不是素?cái)?shù);

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

(6)如果 j=b且 z≠p-1，那么 p不是素?cái)?shù)［5］。

2.2 RSA加密算法

(1)選兩個(gè)保密的大素?cái)?shù)p和q;

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

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

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

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

(6)計(jì)算 c=memodn，求出明文m對(duì)應(yīng)的密文c;

(7)計(jì)算m=cdmodn，求出密文c對(duì)應(yīng)的明文m［5］。

2.3 系統(tǒng)實(shí)現(xiàn)框圖

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

圖1 系統(tǒng)流程圖

3 結(jié)語

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

［1］代春艷，謝曉堯，辛明軍，等.電子商務(wù)信息安全技術(shù)［M］.武漢:武漢大學(xué)出版社，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］孫淑玲.應(yīng)用密碼學(xué)［M］.北京:清華大學(xué)出版社，2004.

［5］SCHNEIER B.應(yīng)用密碼學(xué)［M］.2版.吳世忠，譯.北京:機(jī)械工業(yè)出版社，2000.

［6］司光東，楊加喜，譚示崇，等.RSA算法中的代數(shù)結(jié)構(gòu)［J］.電子學(xué)報(bào)，2011(1):242-246.

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