摘要：首先利用RSA加密算法對(duì)數(shù)據(jù)進(jìn)行加密和解密，實(shí)現(xiàn)了數(shù)據(jù)的安全傳輸;然后針對(duì)RSA加密算法時(shí)間開銷大和算法設(shè)計(jì)復(fù)雜的缺點(diǎn)，提出基于乘同余對(duì)稱特性的SNM算法。通過對(duì)該改進(jìn)RSA加密算法的實(shí)現(xiàn)發(fā)現(xiàn)加密運(yùn)算速度明顯提高且算法更簡單，從而證明了本文所提改進(jìn)算法的有效性。

0 引言

在當(dāng)今信息社會(huì)中，每天都有大量的加密信息在傳輸、交換、存儲(chǔ)和處理，一旦密碼遭到破解就可能造成信息的丟失、篡改、偽造、假冒以及系統(tǒng)遭受破壞等嚴(yán)重后果，因此，如何保證信息的安全傳輸成為當(dāng)前信息傳輸領(lǐng)域的熱點(diǎn)問題。W.Diffie和M.E.Hellmam在1976年發(fā)表了具有劃時(shí)代意義的“密碼學(xué)的新方向”一文，提出了公鑰密碼體制思想，克服了傳統(tǒng)對(duì)稱密碼體制的缺點(diǎn)，為近代密碼學(xué)的發(fā)展指明了方向。它的出現(xiàn)是密碼學(xué)研究領(lǐng)域中的一項(xiàng)重大突破，也是現(xiàn)代密碼學(xué)誕生的標(biāo)志之一。

本文首先對(duì)非對(duì)稱加密算法RSA的原理和優(yōu)點(diǎn)進(jìn)行研究，然后實(shí)現(xiàn)其加密、解密功能。RSA算法在公鑰密碼體制中占有重要的地位。但該算法所采用的冪乘計(jì)算耗時(shí)太多，一直是制約其廣泛應(yīng)用的瓶頸。因此，為了提高加密和解密速度，本文提出一種新型的加密算法即基于乘同余對(duì)稱特性的SMM算法。該算法采用簡單的迭代來實(shí)現(xiàn)，不需要冪乘和乘法逆運(yùn)算，從而在提高加密解密的速度同時(shí)也使得程序設(shè)計(jì)更簡潔緊湊。

1 RSA加密算法原理

RSA加密算法的理論基礎(chǔ)是一種特殊的可逆模指數(shù)運(yùn)算，其算法描述如下：

(1)選擇兩個(gè)互異的大質(zhì)數(shù)p和q(p和q必須保密，一般取1024位)。

(2)計(jì)算出n=p q，φ(n)=(p-1)(q-1)。

(3)選擇一個(gè)比n小且與φ(n)互質(zhì)(沒有公因子)的數(shù)e。

(4)找出一個(gè)d，使得ed-1能夠被φ(n)整除。其中，ed=1 mod(p-1)(q-1)。

(5)RSA是一種分組密碼系統(tǒng)，所以公開密鑰=(n，e)，私有密鑰=(n，d)。

其中，n為模數(shù)，通信雙方都必須知道，e為加密運(yùn)算的指數(shù)，發(fā)送方需要知道，d為解密運(yùn)算的指數(shù)，只有接受方才能知道。

將以上過程進(jìn)一步描述如下：

公開密鑰：n=pq(p，q分別為兩個(gè)互異的大素?cái)?shù))，e與(p-1)(q-1)互質(zhì)。

私有密鑰：d=e-1{mod(p-1)(q-1)}。

加密：C=Me mod n，其中M為明文，C為密文。

解密：M=Cd(mod n)。

若要破譯密碼必須知道p，q，即對(duì)n作素因子分解，這在數(shù)學(xué)上是非常困難的。

2 RSA加密算法的實(shí)現(xiàn)

2.1 算法設(shè)計(jì)流程

RSA算法設(shè)計(jì)流程如圖1所示，主要采用下述加密/解密變換。

(1)密鑰的產(chǎn)生

a.選擇兩個(gè)保密的大素?cái)?shù)p和q。

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

c.選擇一個(gè)整數(shù)e，滿足1

d.計(jì)算私鑰d，滿足d=l(modφ(n))/e，d是e在模φ(n)下的乘法逆元。

e.以(e，n)為公鑰，(d，n)為密鑰，銷毀P，q，φ(n)。

(2)加密

加密時(shí)首先將明文比特串進(jìn)行分組，使得每個(gè)分組對(duì)應(yīng)的串在數(shù)值上小于N，即分組的二進(jìn)制長度小于1 092 N。然后，對(duì)每個(gè)明文分組M，作加密運(yùn)算。

加密：C=Me(modn)，其中M為明文，C為密文。

(3)解密

對(duì)密文分組的解密運(yùn)算為：M=Cd(modn)。

2.2 RSA加密算法的實(shí)現(xiàn)

(1) 生成密鑰

隨機(jī)選擇兩個(gè)大素?cái)?shù)p和q，如果p和q足夠大，那么n=p q就會(huì)變的很大，在理論上因式分解一個(gè)大數(shù)并準(zhǔn)確地分解出p和q是很難實(shí)現(xiàn)的。本文隨機(jī)選擇P和q為61和67。根據(jù)φ(n)=(p-1)(q-1)可得n的歐拉函數(shù)值φ(n)為3960，如圖2所示。

隨機(jī)數(shù)e的選取要滿足隨機(jī)數(shù)和歐拉函數(shù)最大公約數(shù)gcd(eφ(n))=1這個(gè)條件。如果e比較大，加、解密速度變慢，也不便于存儲(chǔ)，但是太小的e會(huì)導(dǎo)致安全性問題。所以限定1

(2)加密

輸入明文，根據(jù)公鑰(e，n)和公式C=Me(modn)可得密文。本文選擇要加密的明文為1234，由公式可得密文為2793。根據(jù)計(jì)算結(jié)果可知此加密算法加密所用的時(shí)間為2.667 ms。

(3)解密

輸入3調(diào)用第三個(gè)模塊來實(shí)現(xiàn)解密功能。RSA加密算法解密所需要的條件是知道密文和私鑰，根據(jù)M=Cd(modn)可得到明文。由計(jì)算得到密文為2793，私鑰為233，所以可解的密文為1234，從而實(shí)現(xiàn)了解密功能。

RSA加密算法的實(shí)現(xiàn)過程如圖2所示。

大整數(shù)因子分解問題向來被數(shù)學(xué)界視為世界性難題。正是基于這一點(diǎn)，RSA公鑰密碼體制才能夠以其較高的安全性為人們廣泛接受。但是RSA公鑰密碼體制也存在諸多不足之處：加解密算法中涉及大量的數(shù)值計(jì)算問題導(dǎo)致計(jì)算時(shí)間開銷較大，在一定程度上限制了其應(yīng)用范圍。且密鑰的產(chǎn)生受到素?cái)?shù)產(chǎn)生技術(shù)的限制，因而很難做到一次一密。為保證安全性必須選取1024 bits或以上，但這就使得運(yùn)算速度較慢，而且隨著大數(shù)分解技術(shù)的發(fā)展，這個(gè)長度還在增加，不利于數(shù)據(jù)格式的標(biāo)準(zhǔn)化，致使其實(shí)現(xiàn)的難度增大，實(shí)用性降低。

因此，如何提高密鑰產(chǎn)生技術(shù)，發(fā)展更快速、更精確的大素?cái)?shù)生成方法，完善RSA加密算法的大整數(shù)模冪乘運(yùn)算，設(shè)計(jì)運(yùn)算速度更快的求模和求冪算法，是很有意義的—個(gè)探索方向。

3 RSA加密算法的改進(jìn)及實(shí)現(xiàn)

針對(duì)RSA加密算法加密速度慢的問題，經(jīng)過進(jìn)一步的研究，提出了SMM算法。SMM(Symmetry of Modulo Multiplication)算法是利用乘同余對(duì)稱特性來減少RSA加密計(jì)算中乘法和求模運(yùn)算量的一種快速算法。RSA加密是對(duì)明文求冪剩余的過程為：

y=n (1)

傳統(tǒng)RSA算法是將指數(shù)表示成二進(jìn)制數(shù)的形式，并將冪乘變成一系列乘同余的迭代。SMM算法是在每步迭代中對(duì)乘數(shù)進(jìn)行有條件的代換。乘同余和平方剩余的對(duì)稱性有：

(n-i)(n-j)≡ijmod n (2)

(n-i)2mod n≡i2mod n (3)

j(n-j)≡(n-j)i≡-ijmod n (4)

其代換情況如下：如果ai-1表示第i-1步迭代的結(jié)果，則在進(jìn)行第i步迭代時(shí)，若ai-1或g(n-1)/2，則保持原數(shù)不變;如果ai-1或g≥(n-1)/2則使用n-ai或n-g來代替ai-1或g[8,9]。

由于使用SMM方法，減少了乘法時(shí)間和求模運(yùn)算量，改進(jìn)后的RSA加密算法理論上可以使得算法速度得到一定程度的提高。

為了方便將改進(jìn)前后的算法做比較，本文隨機(jī)素?cái)?shù)p、q仍選擇61和67。根據(jù)f(n)=(p-1)(q-1)可得f(n)為3960 c，隨機(jī)數(shù)e選擇17，可得公鑰為(17，4087)，私鑰為233。改進(jìn)后的RSA加密算法運(yùn)行結(jié)果如圖3所示。與圖2對(duì)比可知，相同初始條件下原RSA算法所用的加密時(shí)間為2.667 ms，改進(jìn)后算法所用的加密時(shí)間為1.669 ms，加密速度提高了約37.4%，且程序的復(fù)雜度也有所降低。

改進(jìn)后的RSA加密算法可以通過簡單的循環(huán)迭代完成整個(gè)RSA加解密過程，減少了將十進(jìn)制數(shù)據(jù)轉(zhuǎn)化為二進(jìn)制數(shù)組和用擴(kuò)展的歐幾里得算法求乘法逆元這兩步，不僅降低了程序的復(fù)雜性，而且提高了運(yùn)算的效率。

4 結(jié)論

本文針對(duì)RSA加密算法時(shí)間開銷高和程序復(fù)雜的缺點(diǎn)，提出一種基于乘同余特性的SMM加密改進(jìn)算法，該改進(jìn)算法可減少RSA模冪乘運(yùn)算過程耗時(shí)以及提高RSA加解密速度。最后通過改進(jìn)前后算法的實(shí)例對(duì)比證明了本文所提改進(jìn)RSA加密算法的有效性。