基于C語言的RSA算法的實現

戚娜

（陜西工業職業技術學院 陜西 咸陽 712000）

加密技術并不是現在才有的，它起源于公元前2000年（幾個世紀了），雖然和我們現在所說的加密技術不同，但作為一種加密的概念，確實早在幾個世紀前就誕生了，其目的是相同的。其都是為了保障信息在傳遞的過程中，防止有用或私有化信息被攔截和竊取。即使被第三方獲取，沒有相應的解密方法，該信息就沒有任何利用價值，也就不會造成任何損失。

我們現在所說的加密技術的起源，是Diffie和Hellman于1976年在“New Direction in Cryptography”（密碼學新方向）一文中首次提出了公開密鑰密碼體制的思想。1978年，R.Rivest，A.Shamir和L.Adleman第一次實現了公開密鑰密碼體制，現在稱為RSA公開密鑰體制[1]。迄今為止，該算法被認為是最完善最成熟的公鑰密碼體制，被廣泛的應用于各個領域。

1 密碼學基礎

密碼學有很長的研究歷史，但一般人對它依然十分陌生，因為它只在如軍事、情報、外交等這些敏感部門小范圍內使用。計算機密碼學是研究計算機信息加密、解密及其變換的科學，是數學和計算機的交叉學科，也是一門新興的學科[2]。

密碼技術主要用于保證電子數據的保密性，完整性和真實性。保密性是對數據進行加密，使非法用戶無法讀懂數據信息，而合法用戶可以用密鑰讀取信息.完整性是對數據完整性的鑒別，以確定數據是否被非法篡改，保證合法用戶得到正確、完整的信息。真實性是數據來源的真實性、數據本身真實性的鑒別，可以保證合法用戶不被欺騙[2]。簡單的過程如圖1所示。

圖1 RSA算法加密解密的過程Fig.1 Encrypt and decrypt process of the RSA algorithm

2 加密算法描述

加密算法分為兩種，對稱加密和非對稱加密。采用對稱加密時，通信的雙方采用共同密鑰，只需要一個密鑰。不論發送方對信息的加密還是接收方對信息的解密都使用該密鑰，如果該密鑰在傳送的過程中被第三方獲取，我們給信息上所加的密鑰就沒有意義了。而且對稱密鑰如何把密鑰送到對方手里，也成為了該算法的缺憾。該算法的模型如圖2所示。

圖2 對稱密碼模型Fig.2 Symmetric cipher model

與對稱加密算法不同，非對稱加密算法RSA需要兩個密鑰，一個是公開的密鑰，一個是保密的私鑰。它們兩個成對出現，如果用公開密鑰對數據進行加密，只有用對應的私有密鑰才能解密；如果用私有密鑰對數據進行加密，那么只有用對應的公開密鑰才能解密。因為加密和解密使用的是兩個不同的密鑰，所以這種算法叫作非對稱加密算法[3]。甲方生成一對密鑰并將其中的一把作為公用密鑰向其它方公開；得到該公用密鑰的乙方使用該密鑰對機密信息進行加密后再發送給甲方；甲方再用自己保存的另一把專用密鑰對加密后的信息進行解密。甲方只能用其專用密鑰解密由其公用密鑰加密后的任何信息。簡單流程如圖2所示。

3 RSA算法的原理及應用

3.1 RSA算法的原理

RSA算法是非對稱加密算法中的一種，出現于1978年。該算法是一個被廣泛接受并實現的通用公開密鑰加密算法，既能用于數據加密又可用于數字簽名的算法之一。從提出到現在已近四十年，經歷了各種攻擊和考驗，逐漸為人們所接受，普遍認為是目前最優秀的公鑰方案之一。

圖3 非對稱密碼模型Fig.3 Symmetric cipher model

該算法是建立在大數分解和素數檢測的理論基礎上，它的數學基礎是初等數論中的歐拉（Euler）定理，其安全性建立在大整數因子分解的困難之上。

1）密鑰的產生。首先，隨機選取兩個長度相同的大素數：p 和 q，另：n=p*q，另：t=（p－1）*（q－1），隨機選取一個數 e，要求 e的取值范圍為 （0＜e＜t）， 常用的 e值是 3，17和 65537（216+1），而且e要滿足d*e%t==1，繼而就可以得到d的值。這樣就得到 4個數：n，t，e，d，其中 e就是加密的密鑰，而 d是解密的密鑰，公開 n 和 d，保密 p，q，e。

雖說加密和解密的變換是互逆的，但私鑰系統把數據作為比特來處理，而公鑰系統則把數據作為數字進行函數運算處理，并且這種數學函數是單向的。即在一個方向上是容易的，另一個方向上卻異常困難，那么簡單地顛倒步驟是無法解密密文[4]。

2）加密算法實現。 已知明文 x（x＜n），并對 x 進行分組，將x劃分成字符塊，使得每個明文報文xi長度m滿足0＜xi＜k（其中 k 為 n 的長度），計算密文：C=xe（mod n）。

3）解密算法實現。已知密文C以及私鑰（n，d），可以計算出明文 x=Cd（mod n）。

4）RSA 算法舉例。 已知 p=11，q=19，得 n=209，t=180，隨機選取一個數 e=7，滿足 0＜e＜t，根據公式 d*e%t==1可得出d=103，d 是私有密鑰。 其中公開（n，e），保密（n，d）。 假設想需要發送信息 x=65，利用（n，e）=（209，7）計算出加密值：C=xe（mod n）=657mod 209=4902227890625 mod 209=余 56， 當收到密文 C=56 后，利用（n，d）=（209，103）計算明文：x=Cd（ mod n）=56103mod 209=1.1570890445040892822428130017059…10180mod 209=65。

3.2 RSA算法的應用

3.2.1 用于交換對稱加密算法的密鑰

因為非對稱的加密和解密算法要比對稱加密和解密算法慢的多，所以非對稱加密算法在實際中通常被用來安全的交換對稱加密算法的密鑰，而對稱加密算法實際被用來作為通信過程的加密。也就是說，非對稱加密算法主要用于對對稱加密算法中密鑰的加密。

交換對稱密碼的會話密鑰過程如下：

1）A 用 RSA 算法生成自己的公鑰（n，e）和私鑰（n，d），并發送一信息給B，信息包含A的公鑰（n，d）和A的標識ID。

2）B生成會話密鑰K，并用 A的公鑰加密后傳送給A，即Kemod n。

3）A用自己的私鑰解密Kemod n，即可得到K。這樣，A和B就可以完全用對稱加密算法和密鑰K進行通信了，如圖4所示。

圖4 交換對稱加密算法的關鍵過程Fig.4 Exchange of symmetric encryption algorithm key processes

3.2.2 用于數字簽名

RSA算法在加密/解密過程中使用公鑰加密，私鑰解密。而在數字簽名中則是私鑰加密，公鑰解密。即發送方先用HASH算法對文件M求散列值，然后利用自己的密鑰對數字摘要進行加密生成數字簽名C，然后將M和C一起發送給接收方。接收方接收到文件M1和數字簽名C1，需要驗證M和M1是否完全相同。驗證過程是利用HASH函數對M1求散列值H1，利用發送方公開的公鑰對數字簽名C1進行解密得到H2，比較H1和H2是否相同[6]。如果相同說明信息發送安全。其具體的流程如圖5所示。

4 RSA算法在C環境中的實現

4.1 程序流程圖

該程序的流程圖如圖6所示。

圖5 RSA算法在數字簽名中的應用Fig.5 RSA algorithms in the digital signature

圖6 程序流程圖Fig.6 Flow chart

4.2 程序的相關說明

在該程序中，用戶可以加密解密數字、漢字、字母等信息。在加密解密數字信息時，用戶根據程序的提示，直接輸入要加密解密的數字信息，即可得到該數字信息的加密或解密后的信息。對于該數字信息不需要做任何的處理，如果用戶輸入的是由漢字組成的信息，把漢字變成URL編碼，再將URL編碼轉化成ASCII碼進行加密解密操作.如果該信息是一個很長的字符串，就需要對加密的信息先進行分組；如果用戶輸入的是由字符串組成的信息，把該字符串轉化成ASCII碼進行加密解密操作。

該程序中，主函數主要用于根據用戶輸入的兩個素數p和q，求n及它的歐拉數t，由用戶給定的公鑰e，調用子函數fun（）判斷e和t是否互素，求解出私鑰d。用戶選擇對輸入的信息是加密還是解密，調用子函數my encryption（），實現了求冪取余運算，及輸入信息的加密或解密運算。

寄生蟲是豬常見疾病中的重要誘導因素，寄生蟲能夠寄生在豬的皮膚表面以及體內，進而對正常的生長產生影響，甚至在體內大量繁殖，導致豬出現疾病。面對這一現象，在此過程中需要對寄生蟲展開有效防治，例如，定期組織殺蟲處理，豬舍寄生蟲疫苗，降低寄生蟲出現的概率。另外，對豬糞便展開定期檢查，如果發現糞便中含有寄生蟲或者蟲卵，則需要在豬飼料中添加一定的伊維菌素以及阿苯達唑粉劑，根據寄生蟲的數量以及豬自身的生長情況確定用量，這種方式能夠對寄生蟲起到良好的控制作用，最終達到提升豬常見疾病控制質量的目的。

4.3 程序部分代碼

unsigned long my encryption （unsigned long x， unsigned long y， unsigned long z）

{unsigned long r=1；

y=y+1；

while（y!=1）

{

r=r*x；

r=r%z；

y--；

}

printf（"%d "，r）；

return r；//實現冪的取余運算

unsigned long fun（unsigned long a， unsigned long b）

{

unsigned long t；

while（b）

{

t=a；

a=b；

b=t%b；

}

if（a==1）

return 0；

else

return 1；

}//判斷公鑰e與t是否互素

4.4 程序運行結果

當p=57，q=23時，對4573進行加密，運行結果如圖7所示。

圖7 程序運行結果Fig.7 The result of running

5 RSA算法的安全性

RSA算法的體制構造是基于數論的歐拉定理，它是密鑰系統最安全的一種體制，其算法的安全性依賴于大數的分解。該算法利用了數論領域的一個事實，那就是雖然將兩個大質數相乘生成一個合數非常容易，但要把一個合數分解成兩個質數卻十分困難[7]。要想對其破解需要分解一個大數，即從一個公鑰中通過因數分解得到私鑰就十分的困難。比如，1994年4月，為了分解RSA密鑰RSA-129即分解一個129位十進制425比特的大數，600余名志愿者參加了這項破譯活動，分解時啟用了1 600多臺工作站、大型機和超級計算機，花費了8個月的時間，終于分解了RSA－129問題中的公開鑰匙。

但研究表明，自從1994年的破譯工作完成之后，又有更快的因數分解計算方法提出來。因此，近年來位數較低的大數（512 bit二進制數）已被成功分解，這就告訴人們，在使用RSA算法加密時，在密鑰生成時，盡量要求n很大，這樣攻擊者要成功的分解t=（p-1）*（q-1），就非常困難。 要使 RSA使用安全，就必須選擇足夠大的p和q，使用更長密鑰是有益而無害的。一般選擇在100位以上的十進制數字，這樣攻擊者沒有辦法在有效的多項式時間內分解出n。

6 RSA算法的缺點

1）假冒公開密鑰。用戶雖然不必擔心公開鑰匙泄密，但卻需要考慮有人冒名頂替公布假的公開鑰匙。所以應當盡可能地廣泛地公布正確的公開鑰匙，以防假冒。

2）密鑰產生麻煩。由于RSA算法受到素數產生的限制，生成素數的效率比較低，因而難以做到一次一密。

3）安全性有待驗證。RSA的安全性依賴于大數分解難度，但是否等同于大數分解一直未能得到理論上的證明，因為沒有證明破解RSA就一定需要作大數分解。如果存在一種算法，可以快速的分解大數，那么RSA算法的安全性就會受到威脅。另外，隨著計算機計算能力的不斷提高，計算機造價的降低及并行技術的發展，那么攻擊RSA算法能力將會得到巨大增長。

4）速度慢。使用RSA算法加密解密，要進行大量的計算，而且速度較慢，與對稱密碼算法相比要慢幾千倍。而且隨著大數分解技術的不斷發展，為了保證安全，密鑰的長度還要增加，計算量會更大。

7 RSA算法的發展前景

從20世紀70年代提出以來，經歷了20多年的實踐檢驗，已得到廣泛的應用，成為最流行的一種加密標準。隨著計算機網絡和電子商務技術的不斷發展，為RSA技術的應用提供了更為廣闊的空間。在許多硬件，軟件產品的內核中都有RSA的軟件和類庫，方便人們使用。比如，硬件上主要用于各類電子產品中的IC技術；軟件上主要用于Internet上的加密連接、數字簽名和數字認證等。另外，IE瀏覽器中也集成和使用了RSA技術的加密功能，結合MD5和SHA1，主要用于數字證書和數字簽名，對于使用經常網購的用戶來說，幾乎每天都在與RSA技術打交道。但是，隨著數據量的逐年增加和人們需求的不斷提高，RSA面臨各個方面的挑戰，應用程序安全、數據安全與隱私、云安全、拒絕服務攻擊、高級持續性威脅（APTs）、移動安全等，都是RSA未來幾年的發展前景。

8 結 論

本文在對傳統的 RSA算法[8]的原理充分研究和深刻理解上，介紹了RSA算法的主要應用，在C環境下 RSA算法的實現，并分析了RSA算法的安全性及存在的缺點?？傮w上來說，RSA算法是一個比較優秀的算法。但從RSA算法的應用來看，還存在很多的問題，比如公共密鑰的正確性、加密解密速度很慢以及密鑰產生很麻煩等。因此，在使用RSA算法時，要考慮到該算法的弱點，作好RSA算法攻擊的防范。

[1]Atul Kahata.Cryptography And Network Secutrity[M].北京:清華大學出版社，2005.

[2]張仕斌，萬武南，張金全.應用密碼學[M].西安:西安電子科技大學出版社，2009.

[3]何彩燕，吳紅.公鑰制RSA算法應用中要注意的幾個問題[J].現代計算機，2004，178（5）:72-74.HE Cai-yan，WU Hong.2004.Public key RSA algorithm is applied to several problems[J].Modern Computer，Volume，2004，178（5）:72-74.

[4]BUCHMANN J.A.Introduction to cryptography[M].New York:Springer-Verlage，2001.

[5]陳傳波，祝中濤.RSA算法應用及實現細節[J].計算機工程與科學，2006（9）:13-14.CHEN Chuan-bo，ZHU Zhong-tao.Application of RSA algorithm and implementation details[J].Computer Engineering and Science，2009（6）:13-14.

[6]石志堅，譚全權，段海龍.RSA算法實現數字簽名的研究與應用[J].微型電腦應用，2008（6）:50-51.SHI Zhi-jian，TAN Quan-quan，DUAN Hai-long.The research and application of the RSAalgorithmin thedigital signature[J].Microcomputer Applications，2008（6）:50-51.

[7]張穎，曹天人.基于RSA算法的加密應用[J].科技咨詢（科技-管理），2011（25）:79-80.ZHANG Yin，CAO Tian-ren.Application of encryption based on RSA algorithm[J].Science and Technology Advisory（Technology， Administration），2011（25）:79-80.

[8]王紅勝，紀道剛，張陽，等.針對RSA-CRT數字簽名的光故障攻擊研究[J].電子設計工程，2015（6）：12-15.WANG Hong-sheng，JI Dao-gang，ZHANG Yang，et al.Optical fault attack on RSA-CRT signatures[J].Electronic Design Engineering，2015（6）:12-15.