什么是RSA算法

　　RSA公鑰加密算法是1977年由羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）一起提出的。1987年7月首次在美國公布，當(dāng)時他們?nèi)硕荚诼槭±砉W(xué)院工作實習(xí)。RSA就是他們?nèi)诵帐祥_頭字母拼在一起組成的。

　　RSA是目前最有影響力和最常用的公鑰加密算法，它能夠抵抗到目前為止已知的絕大多數(shù)密碼攻擊，已被ISO推薦為公鑰數(shù)據(jù)加密標(biāo)準(zhǔn)。

　　今天只有短的RSA鑰匙才可能被強(qiáng)力方式解破。到2008年為止，世界上還沒有任何可靠的攻擊RSA算法的方式。只要其鑰匙的長度足夠長，用RSA加密的信息實際上是不能被解破的。但在分布式計算和量子計算機(jī)理論日趨成熟的今天，RSA加密安全性受到了挑戰(zhàn)和質(zhì)疑。

　　RSA算法基于一個十分簡單的數(shù)論事實：將兩個大質(zhì)數(shù)相乘十分容易，但是想要對其乘積進(jìn)行因式分解卻極其困難，因此可以將乘積公開作為加密密鑰。

　　基本含義

　　RSA公開密鑰密碼體制。所謂的公開密鑰密碼體制就是使用不同的加密密鑰與解密密鑰，是一種“由已知加密密鑰推導(dǎo)出解密密鑰在計算上是不可行的”密碼體制。

　　在公開密鑰密碼體制中，加密密鑰（即公開密鑰）PK是公開信息，而解密密鑰（即秘密密鑰）SK是需要保密的。加密算法E和解密算法D也都是公開的。雖然解密密鑰SK是由公開密鑰PK決定的，但卻不能根據(jù)PK計算出SK。

　　正是基于這種理論，1978年出現(xiàn)了著名的RSA算法，它通常是先生成一對RSA 密鑰，其中之一是保密密鑰，由用戶保存；另一個為公開密鑰，可對外公開，甚至可在網(wǎng)絡(luò)服務(wù)器中注冊。為提高保密強(qiáng)度，RSA密鑰至少為500位長，一般推薦使用1024位。這就使加密的計算量很大。為減少計算量，在傳送信息時，常采用傳統(tǒng)加密方法與公開密鑰加密方法相結(jié)合的方式，即信息采用改進(jìn)的DES或IDEA對話密鑰加密，然后使用RSA密鑰加密對話密鑰和信息摘要。對方收到信息后，用不同的密鑰解密并可核對信息摘要。

　　RSA算法是第一個能同時用于加密和數(shù)字簽名的算法，也易于理解和操作。RSA是被研究得最廣泛的公鑰算法，從提出到現(xiàn)今的三十多年里，經(jīng)歷了各種攻擊的考驗，逐漸為人們接受，截止2017年被普遍認(rèn)為是最優(yōu)秀的公鑰方案之一。

　　RSA加密算法原理

　　RSA加密算法中，只用到素數(shù)、互質(zhì)數(shù)、指數(shù)運算、模運算等幾個簡單的數(shù)學(xué)知識。所以，我們也需要了解這幾個概念即可。

　　素數(shù)

　　素數(shù)又稱質(zhì)數(shù)，指在一個大于1的自然數(shù)中，除了1和此整數(shù)自身外，不能被其他自然數(shù)整除的數(shù)。這個概念，我們在上初中，甚至小學(xué)的時候都學(xué)過了，這里就不再過多解釋了。

　　互質(zhì)數(shù)

　　百度百科上的解釋是：公因數(shù)只有1的兩個數(shù)，叫做互質(zhì)數(shù)。；維基百科上的解釋是：互質(zhì)，又稱互素。若N個整數(shù)的最大公因子是1，則稱這N個整數(shù)互質(zhì)。

　　常見的互質(zhì)數(shù)判斷方法主要有以下幾種：

　　兩個不同的質(zhì)數(shù)一定是互質(zhì)數(shù)。例如，2與7、13與19。

　　一個質(zhì)數(shù)，另一個不為它的倍數(shù)，這兩個數(shù)為互質(zhì)數(shù)。例如，3與10、5與 26。

　　相鄰的兩個自然數(shù)是互質(zhì)數(shù)。如 15與 16。

　　相鄰的兩個奇數(shù)是互質(zhì)數(shù)。如 49與 51。

　　較大數(shù)是質(zhì)數(shù)的兩個數(shù)是互質(zhì)數(shù)。如97與88。

　　小數(shù)是質(zhì)數(shù)，大數(shù)不是小數(shù)的倍數(shù)的兩個數(shù)是互質(zhì)數(shù)。例如 7和 16。

　　2和任何奇數(shù)是互質(zhì)數(shù)。例如2和87。

　　1不是質(zhì)數(shù)也不是合數(shù)，它和任何一個自然數(shù)在一起都是互質(zhì)數(shù)。如1和9908。

　　輾轉(zhuǎn)相除法。

　　指數(shù)運算

　　指數(shù)運算又稱乘方計算，計算結(jié)果稱為冪。nm指將n自乘m次。把nm看作乘方的結(jié)果，叫做”n的m次冪”或”n的m次方”。其中，n稱為“底數(shù)”，m稱為“指數(shù)”。

　　模運算

　　模運算即求余運算。“模”是“Mod”的音譯。和模運算緊密相關(guān)的一個概念是“同余”。數(shù)學(xué)上，當(dāng)兩個整數(shù)除以同一個正整數(shù)，若得相同余數(shù)，則二整數(shù)同余。

　　兩個整數(shù)a，b，若它們除以正整數(shù)m所得的余數(shù)相等，則稱a，b對于模m同余，記作： a ≡ b （mod m）；讀作：a同余于b模m，或者，a與b關(guān)于模m同余。例如：26 ≡ 14 （mod 12）。

　　RSA加密算法

　　RSA加密算法簡史

　　RSA是1977年由羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）一起提出的。當(dāng)時他們?nèi)硕荚诼槭±砉W(xué)院工作。RSA就是他們?nèi)诵帐祥_頭字母拼在一起組成的。

　　公鑰與密鑰的產(chǎn)生

　　假設(shè)Alice想要通過一個不可靠的媒體接收Bob的一條私人訊息。她可以用以下的方式來產(chǎn)生一個公鑰和一個私鑰：

　　隨意選擇兩個大的質(zhì)數(shù)p和q，p不等于q，計算N=pq。

　　根據(jù)歐拉函數(shù)，求得r = （p-1）（q-1）

　　選擇一個小于 r 的整數(shù) e，求得 e 關(guān)于模 r 的模反元素，命名為d。（模反元素存在，當(dāng)且僅當(dāng)e與r互質(zhì)）

　　將 p 和 q 的記錄銷毀。

　　（N，e）是公鑰，（N，d）是私鑰。Alice將她的公鑰（N，e）傳給Bob，而將她的私鑰（N，d）藏起來。

　　加密消息

　　假設(shè)Bob想給Alice送一個消息m，他知道Alice產(chǎn)生的N和e。他使用起先與Alice約好的格式將m轉(zhuǎn)換為一個小于N的整數(shù)n，比如他可以將每一個字轉(zhuǎn)換為這個字的Unicode碼，然后將這些數(shù)字連在一起組成一個數(shù)字。假如他的信息非常長的話，他可以將這個信息分為幾段，然后將每一段轉(zhuǎn)換為n。用下面這個公式他可以將n加密為c：

　　ne ≡ c （mod N）

　　計算c并不復(fù)雜。Bob算出c后就可以將它傳遞給Alice。

　　解密消息

　　Alice得到Bob的消息c后就可以利用她的密鑰d來解碼。她可以用以下這個公式來將c轉(zhuǎn)換為n：

　　cd ≡ n （mod N）

　　得到n后，她可以將原來的信息m重新復(fù)原。

　　解碼的原理是：

　　cd ≡ n e·d（mod N）

　　以及ed ≡ 1 （mod p-1）和ed ≡ 1 （mod q-1）。由費馬小定理可證明（因為p和q是質(zhì)數(shù)）

　　n e·d ≡ n （mod p） 　　和 　n e·d ≡ n （mod q）

　　這說明（因為p和q是不同的質(zhì)數(shù)，所以p和q互質(zhì)）

　　n e·d ≡ n （mod pq）

　　簽名消息

　　RSA也可以用來為一個消息署名。假如甲想給乙傳遞一個署名的消息的話，那么她可以為她的消息計算一個散列值（Message digest），然后用她的密鑰（private key）加密這個散列值并將這個“署名”加在消息的后面。這個消息只有用她的公鑰才能被解密。乙獲得這個消息后可以用甲的公鑰解密這個散列值，然后將這個數(shù)據(jù)與他自己為這個消息計算的散列值相比較。假如兩者相符的話，那么他就可以知道發(fā)信人持有甲的密鑰，以及這個消息在傳播路徑上沒有被篡改過。

　　編程實踐

　　下面，開始我們的重點環(huán)節(jié)：編程實踐。在開始編程前，我們通過計算，來確定公鑰和密鑰。

　　計算公鑰和密鑰

　　假設(shè)p = 3、q = 11（p，q都是素數(shù)即可。），則N = pq = 33；

　　r = （p-1）（q-1） = （3-1）（11-1） = 20；

　　根據(jù)模反元素的計算公式，我們可以得出，e·d ≡ 1 （mod 20），即e·d = 20n+1 （n為正整數(shù)）；我們假設(shè)n=1，則e·d = 21。e、d為正整數(shù)，并且e與r互質(zhì)，則e = 3，d = 7。（兩個數(shù)交換一下也可以。）

　　到這里，公鑰和密鑰已經(jīng)確定。公鑰為（N， e） = （33， 3），密鑰為（N， d） = （33， 7）。

　　編程實現(xiàn)

　　下面我們使用Java來實現(xiàn)一下加密和解密的過程。具體代碼如下：

　　RSA算法實現(xiàn)：

　　［java］ view plaincopy《span style=“font-size:14px;”》package security.rsa;

　　public class RSA {

　　/**

　　* 加密、解密算法

　　* @param key 公鑰或密鑰

　　* @param message 數(shù)據(jù)

　　* @return

　　*/

　　public static long rsa（int baseNum， int key， long message）{

　　if（baseNum 《 1 || key 《 1）{

　　return 0L;

　　}

　　//加密或者解密之后的數(shù)據(jù)

　　long rsaMessage = 0L;

　　//加密核心算法

　　rsaMessage = Math.round（Math.pow（message， key）） % baseNum;

　　return rsaMessage;

　　}

　　public static void main（String［］ args）{

　　//基數(shù)

　　int baseNum = 3 * 11;

　　//公鑰

　　int keyE = 3;

　　//密鑰

　　int keyD = 7;

　　//未加密的數(shù)據(jù)

　　long msg = 24L;

　　//加密后的數(shù)據(jù)

　　long encodeMsg = rsa（baseNum， keyE， msg）;

　　//解密后的數(shù)據(jù)

　　long decodeMsg = rsa（baseNum， keyD， encodeMsg）;

　　System.out.println（“加密前：” + msg）;

　　System.out.println（“加密后：” + encodeMsg）;

　　System.out.println（“解密后：” + decodeMsg）;

　　}

　　《/span》

　　}

　　RSA算法結(jié)果：

　　加密前：24

　　加密后：30

　　解密后：24

　　（看程序最清楚了，對于要加密的數(shù)字m， m^e%N=c， c就是加密之后的密文。c^d%N=m， 就能解密得到m）

　　RSA加密算法的安全性

　　當(dāng)p和q是一個大素數(shù)的時候，從它們的積pq去分解因子p和q，這是一個公認(rèn)的數(shù)學(xué)難題。然而，雖然RSA的安全性依賴于大數(shù)的因子分解，但并沒有從理論上證明破譯RSA的難度與大數(shù)分解難度等價。

　　1994年彼得·秀爾（Peter Shor）證明一臺量子計算機(jī)可以在多項式時間內(nèi)進(jìn)行因數(shù)分解。假如量子計算機(jī)有朝一日可以成為一種可行的技術(shù)的話，那么秀爾的算法可以淘汰RSA和相關(guān)的衍生算法。（即依賴于分解大整數(shù)困難性的加密算法）

　　另外，假如N的長度小于或等于256位，那么用一臺個人電腦在幾個小時內(nèi)就可以分解它的因子了。1999年，數(shù)百臺電腦合作分解了一個512位長的N。1997年后開發(fā)的系統(tǒng)，用戶應(yīng)使用1024位密鑰，證書認(rèn)證機(jī)構(gòu)應(yīng)用2048位或以上。

　　RSA加密算法的缺點

　　雖然RSA加密算法作為目前最優(yōu)秀的公鑰方案之一，在發(fā)表三十多年的時間里，經(jīng)歷了各種攻擊的考驗，逐漸為人們接受。但是，也不是說RSA沒有任何缺點。由于沒有從理論上證明破譯RSA的難度與大數(shù)分解難度的等價性。所以，RSA的重大缺陷是無法從理論上把握它的保密性能如何。在實踐上，RSA也有一些缺點：

　　產(chǎn)生密鑰很麻煩，受到素數(shù)產(chǎn)生技術(shù)的限制，因而難以做到一次一密；

　　分組長度太大，為保證安全性，n 至少也要 600 bits 以上，使運算代價很高，尤其是速度較慢。

　　公鑰加密算法舉例——RSA公鑰加密

　　RSA公鑰加密算法是目前使用最廣泛的公鑰加密算法。對于某一明文塊M和密文塊C，加密和解密有如下的形式：

　　發(fā)送者和接收者都必須知道n和e的值，并且只有接收者知道d的值。RSA公鑰加密算法的公鑰KU={e，n}，私鑰KR={d，n}。

　　該算法的步驟如下表：

　　開始時選擇兩個素數(shù)p和q，計算它們的積n作為加密和解密時的模。接著計算n的歐拉函數(shù)值φ（n）。φ（n）表示小于n且與n互素的正整數(shù)的個數(shù)。然后選擇與φ（n）互素的整數(shù)e。最后，計算e關(guān)于模φ（n）的乘法逆元d。

　　舉例：假設(shè)用戶A已經(jīng)公布了他的公鑰，且用戶B希望給A發(fā)送消息M。那么B計算C=Me （mod n）并且發(fā)送C。當(dāng)接收到密文時，用戶A通過計算M=Cd （mod n）解密密文。按下列步驟生成密鑰

　　（1）選擇兩個素數(shù)：p=17和q=11。

　　（2）計算n=pq=17*11=187。

　　（3）計算φ（n）=（p-1）（q-1）=16*10=160。

　　（4）選擇e，使得e與φ（n）=160互素且小于φ（n），我們選擇e=7。

　　（5）計算d，使得de mod 160=1且d《160。正確的值是d=23，

　　這是因為23*7=161=10*16+1。這樣我們就得到公鑰PU={7，187}，私鑰PR={23，187}。下面說明輸入明文M=88時密鑰的使用情況。

　　對于加密，計算C=887 mod 187=11。

　　對于解密，計算M=1123 mod 187=88