基于C語(yǔ)言的RSA算法的實(shí)現(xiàn)

戚娜

（陜西工業(yè)職業(yè)技術(shù)學(xué)院 陜西 咸陽(yáng) 712000）

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

我們現(xiàn)在所說(shuō)的加密技術(shù)的起源，是Diffie和Hellman于1976年在“New Direction in Cryptography”（密碼學(xué)新方向）一文中首次提出了公開(kāi)密鑰密碼體制的思想。1978年，R.Rivest，A.Shamir和L.Adleman第一次實(shí)現(xiàn)了公開(kāi)密鑰密碼體制，現(xiàn)在稱(chēng)為RSA公開(kāi)密鑰體制[1]。迄今為止，該算法被認(rèn)為是最完善最成熟的公鑰密碼體制，被廣泛的應(yīng)用于各個(gè)領(lǐng)域。

1 密碼學(xué)基礎(chǔ)

密碼學(xué)有很長(zhǎng)的研究歷史，但一般人對(duì)它依然十分陌生，因?yàn)樗辉谌畿娛?、情?bào)、外交等這些敏感部門(mén)小范圍內(nèi)使用。計(jì)算機(jī)密碼學(xué)是研究計(jì)算機(jī)信息加密、解密及其變換的科學(xué)，是數(shù)學(xué)和計(jì)算機(jī)的交叉學(xué)科，也是一門(mén)新興的學(xué)科[2]。

密碼技術(shù)主要用于保證電子數(shù)據(jù)的保密性，完整性和真實(shí)性。保密性是對(duì)數(shù)據(jù)進(jìn)行加密，使非法用戶(hù)無(wú)法讀懂?dāng)?shù)據(jù)信息，而合法用戶(hù)可以用密鑰讀取信息.完整性是對(duì)數(shù)據(jù)完整性的鑒別，以確定數(shù)據(jù)是否被非法篡改，保證合法用戶(hù)得到正確、完整的信息。真實(shí)性是數(shù)據(jù)來(lái)源的真實(shí)性、數(shù)據(jù)本身真實(shí)性的鑒別，可以保證合法用戶(hù)不被欺騙[2]。簡(jiǎn)單的過(guò)程如圖1所示。

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

2 加密算法描述

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

圖2 對(duì)稱(chēng)密碼模型Fig.2 Symmetric cipher model

與對(duì)稱(chēng)加密算法不同，非對(duì)稱(chēng)加密算法RSA需要兩個(gè)密鑰，一個(gè)是公開(kāi)的密鑰，一個(gè)是保密的私鑰。它們兩個(gè)成對(duì)出現(xiàn)，如果用公開(kāi)密鑰對(duì)數(shù)據(jù)進(jìn)行加密，只有用對(duì)應(yīng)的私有密鑰才能解密；如果用私有密鑰對(duì)數(shù)據(jù)進(jìn)行加密，那么只有用對(duì)應(yīng)的公開(kāi)密鑰才能解密。因?yàn)榧用芎徒饷苁褂玫氖莾蓚€(gè)不同的密鑰，所以這種算法叫作非對(duì)稱(chēng)加密算法[3]。甲方生成一對(duì)密鑰并將其中的一把作為公用密鑰向其它方公開(kāi)；得到該公用密鑰的乙方使用該密鑰對(duì)機(jī)密信息進(jìn)行加密后再發(fā)送給甲方；甲方再用自己保存的另一把專(zhuān)用密鑰對(duì)加密后的信息進(jìn)行解密。甲方只能用其專(zhuān)用密鑰解密由其公用密鑰加密后的任何信息。簡(jiǎn)單流程如圖2所示。

3 RSA算法的原理及應(yīng)用

3.1 RSA算法的原理

RSA算法是非對(duì)稱(chēng)加密算法中的一種，出現(xiàn)于1978年。該算法是一個(gè)被廣泛接受并實(shí)現(xiàn)的通用公開(kāi)密鑰加密算法，既能用于數(shù)據(jù)加密又可用于數(shù)字簽名的算法之一。從提出到現(xiàn)在已近四十年，經(jīng)歷了各種攻擊和考驗(yàn)，逐漸為人們所接受，普遍認(rèn)為是目前最優(yōu)秀的公鑰方案之一。

圖3 非對(duì)稱(chēng)密碼模型Fig.3 Symmetric cipher model

該算法是建立在大數(shù)分解和素?cái)?shù)檢測(cè)的理論基礎(chǔ)上，它的數(shù)學(xué)基礎(chǔ)是初等數(shù)論中的歐拉（Euler）定理，其安全性建立在大整數(shù)因子分解的困難之上。

1）密鑰的產(chǎn)生。首先，隨機(jī)選取兩個(gè)長(zhǎng)度相同的大素?cái)?shù)：p 和 q，另：n=p*q，另：t=（p－1）*（q－1），隨機(jī)選取一個(gè)數(shù) e，要求 e的取值范圍為 （0＜e＜t）， 常用的 e值是 3，17和 65537（216+1），而且e要滿(mǎn)足d*e%t==1，繼而就可以得到d的值。這樣就得到 4個(gè)數(shù)：n，t，e，d，其中 e就是加密的密鑰，而 d是解密的密鑰，公開(kāi) n 和 d，保密 p，q，e。

雖說(shuō)加密和解密的變換是互逆的，但私鑰系統(tǒng)把數(shù)據(jù)作為比特來(lái)處理，而公鑰系統(tǒng)則把數(shù)據(jù)作為數(shù)字進(jìn)行函數(shù)運(yùn)算處理，并且這種數(shù)學(xué)函數(shù)是單向的。即在一個(gè)方向上是容易的，另一個(gè)方向上卻異常困難，那么簡(jiǎn)單地顛倒步驟是無(wú)法解密密文[4]。

2）加密算法實(shí)現(xiàn)。 已知明文 x（x＜n），并對(duì) x 進(jìn)行分組，將x劃分成字符塊，使得每個(gè)明文報(bào)文xi長(zhǎng)度m滿(mǎn)足0＜xi＜k（其中 k 為 n 的長(zhǎng)度），計(jì)算密文：C=xe（mod n）。

3）解密算法實(shí)現(xiàn)。已知密文C以及私鑰（n，d），可以計(jì)算出明文 x=Cd（mod n）。

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

3.2 RSA算法的應(yīng)用

3.2.1 用于交換對(duì)稱(chēng)加密算法的密鑰

因?yàn)榉菍?duì)稱(chēng)的加密和解密算法要比對(duì)稱(chēng)加密和解密算法慢的多，所以非對(duì)稱(chēng)加密算法在實(shí)際中通常被用來(lái)安全的交換對(duì)稱(chēng)加密算法的密鑰，而對(duì)稱(chēng)加密算法實(shí)際被用來(lái)作為通信過(guò)程的加密。也就是說(shuō)，非對(duì)稱(chēng)加密算法主要用于對(duì)對(duì)稱(chēng)加密算法中密鑰的加密。

交換對(duì)稱(chēng)密碼的會(huì)話密鑰過(guò)程如下：

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

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

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

圖4 交換對(duì)稱(chēng)加密算法的關(guān)鍵過(guò)程Fig.4 Exchange of symmetric encryption algorithm key processes

3.2.2 用于數(shù)字簽名

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

4 RSA算法在C環(huán)境中的實(shí)現(xiàn)

4.1 程序流程圖

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

圖5 RSA算法在數(shù)字簽名中的應(yīng)用Fig.5 RSA algorithms in the digital signature

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

4.2 程序的相關(guān)說(shuō)明

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

該程序中，主函數(shù)主要用于根據(jù)用戶(hù)輸入的兩個(gè)素?cái)?shù)p和q，求n及它的歐拉數(shù)t，由用戶(hù)給定的公鑰e，調(diào)用子函數(shù)fun（）判斷e和t是否互素，求解出私鑰d。用戶(hù)選擇對(duì)輸入的信息是加密還是解密，調(diào)用子函數(shù)my encryption（），實(shí)現(xiàn)了求冪取余運(yùn)算，及輸入信息的加密或解密運(yùn)算。

寄生蟲(chóng)是豬常見(jiàn)疾病中的重要誘導(dǎo)因素，寄生蟲(chóng)能夠寄生在豬的皮膚表面以及體內(nèi)，進(jìn)而對(duì)正常的生長(zhǎng)產(chǎn)生影響，甚至在體內(nèi)大量繁殖，導(dǎo)致豬出現(xiàn)疾病。面對(duì)這一現(xiàn)象，在此過(guò)程中需要對(duì)寄生蟲(chóng)展開(kāi)有效防治，例如，定期組織殺蟲(chóng)處理，豬舍寄生蟲(chóng)疫苗，降低寄生蟲(chóng)出現(xiàn)的概率。另外，對(duì)豬糞便展開(kāi)定期檢查，如果發(fā)現(xiàn)糞便中含有寄生蟲(chóng)或者蟲(chóng)卵，則需要在豬飼料中添加一定的伊維菌素以及阿苯達(dá)唑粉劑，根據(jù)寄生蟲(chóng)的數(shù)量以及豬自身的生長(zhǎng)情況確定用量，這種方式能夠?qū)纳x(chóng)起到良好的控制作用，最終達(dá)到提升豬常見(jiàn)疾病控制質(zhì)量的目的。

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；//實(shí)現(xiàn)冪的取余運(yùn)算

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 程序運(yùn)行結(jié)果

當(dāng)p=57，q=23時(shí)，對(duì)4573進(jìn)行加密，運(yùn)行結(jié)果如圖7所示。

圖7 程序運(yùn)行結(jié)果Fig.7 The result of running

5 RSA算法的安全性

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

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

6 RSA算法的缺點(diǎn)

1）假冒公開(kāi)密鑰。用戶(hù)雖然不必?fù)?dān)心公開(kāi)鑰匙泄密，但卻需要考慮有人冒名頂替公布假的公開(kāi)鑰匙。所以應(yīng)當(dāng)盡可能地廣泛地公布正確的公開(kāi)鑰匙，以防假冒。

2）密鑰產(chǎn)生麻煩。由于RSA算法受到素?cái)?shù)產(chǎn)生的限制，生成素?cái)?shù)的效率比較低，因而難以做到一次一密。

3）安全性有待驗(yàn)證。RSA的安全性依賴(lài)于大數(shù)分解難度，但是否等同于大數(shù)分解一直未能得到理論上的證明，因?yàn)闆](méi)有證明破解RSA就一定需要作大數(shù)分解。如果存在一種算法，可以快速的分解大數(shù)，那么RSA算法的安全性就會(huì)受到威脅。另外，隨著計(jì)算機(jī)計(jì)算能力的不斷提高，計(jì)算機(jī)造價(jià)的降低及并行技術(shù)的發(fā)展，那么攻擊RSA算法能力將會(huì)得到巨大增長(zhǎng)。

4）速度慢。使用RSA算法加密解密，要進(jìn)行大量的計(jì)算，而且速度較慢，與對(duì)稱(chēng)密碼算法相比要慢幾千倍。而且隨著大數(shù)分解技術(shù)的不斷發(fā)展，為了保證安全，密鑰的長(zhǎng)度還要增加，計(jì)算量會(huì)更大。

7 RSA算法的發(fā)展前景

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

8 結(jié) 論

本文在對(duì)傳統(tǒng)的 RSA算法[8]的原理充分研究和深刻理解上，介紹了RSA算法的主要應(yīng)用，在C環(huán)境下 RSA算法的實(shí)現(xiàn)，并分析了RSA算法的安全性及存在的缺點(diǎn)?？傮w上來(lái)說(shuō)，RSA算法是一個(gè)比較優(yōu)秀的算法。但從RSA算法的應(yīng)用來(lái)看，還存在很多的問(wèn)題，比如公共密鑰的正確性、加密解密速度很慢以及密鑰產(chǎn)生很麻煩等。因此，在使用RSA算法時(shí)，要考慮到該算法的弱點(diǎn)，作好RSA算法攻擊的防范。

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

[2]張仕斌，萬(wàn)武南，張金全.應(yīng)用密碼學(xué)[M].西安:西安電子科技大學(xué)出版社，2009.

[3]何彩燕，吳紅.公鑰制RSA算法應(yīng)用中要注意的幾個(gè)問(wèn)題[J].現(xiàn)代計(jì)算機(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算法應(yīng)用及實(shí)現(xiàn)細(xì)節(jié)[J].計(jì)算機(jī)工程與科學(xué)，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]石志堅(jiān)，譚全權(quán)，段海龍.RSA算法實(shí)現(xiàn)數(shù)字簽名的研究與應(yīng)用[J].微型電腦應(yīng)用，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算法的加密應(yīng)用[J].科技咨詢(xún)（科技-管理），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]王紅勝，紀(jì)道剛，張陽(yáng)，等.針對(duì)RSA-CRT數(shù)字簽名的光故障攻擊研究[J].電子設(shè)計(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.