RSA加密算法原理入門知識

以前也接觸過RSA加密算法，感覺這個東西太神秘了，是數學家的事，和我無關。但是，看了很多關於RSA加密算法原理的資料之後，我發現其實原理並不是我們想象中那麼復雜，弄懂之後發現原來就只是這樣而已..

學過算法的朋友都知道，計算機中的算法其實就是數學運算。所以，再講解RSA加密算法之前，有必要了解一下一些必備的數學知識。我們就從數學知識開始講解。

必備數學知識

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

素數

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

互質數

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

　　常見的互質數判斷方法主要有以下幾種：

1. 兩個不同的質數一定是互質數。例如，2與7、13與19。
2. 一個質數，另一個不為它的倍數，這兩個數為互質數。例如，3與10、5與 26。
3. 相鄰的兩個自然數是互質數。如 15與 16。
4. 相鄰的兩個奇數是互質數。如 49與 51。
5. 較大數是質數的兩個數是互質數。如97與88。
6. 小數是質數，大數不是小數的倍數的兩個數是互質數。例如 7和 16。
7. 2和任何奇數是互質數。例如2和87。
8. 1不是質數也不是合數，它和任何一個自然數在一起都是互質數。如1和9908。
9. 輾轉相除法。

指數運算

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

模運算

　　模運算即求余運算。“模”是“Mod”的音譯。和模運算緊密相關的一個概念是“同余”。數學上，當兩個整數除以同一個正整數，若得相同余數，則二整數同余。

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

RSA加密算法

RSA加密算法簡史

　　RSA是1977年由羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）一起提出的。當時他們三人都在麻省理工學院工作。RSA就是他們三人姓氏開頭字母拼在一起組成的。

公鑰與密鑰的產生

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

1. 隨意選擇兩個大的質數p和q，p不等於q，計算N=pq。
2. 根據歐拉函數，求得r = (p-1)(q-1)
3. 選擇一個小於 r 的整數 e，求得 e 關於模 r 的模反元素，命名為d。（模反元素存在，當且僅當e與r互質）
4. 將 p 和 q 的記錄銷毀。

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

加密消息

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

　　n^e ≡ c (mod N)

計算c並不復雜。Bob算出c後就可以將它傳遞給Alice。

解密消息

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

　　c^d ≡ n (mod N)

得到n後，她可以將原來的信息m重新復原。

解碼的原理是：

　　c^d ≡ n ^e·d(mod N)

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

　　n ^e·d ≡ n (mod p) 　　和 　n ^e·d ≡ n (mod q)

這說明（因為p和q是不同的質數，所以p和q互質）

　　n ^e·d ≡ n (mod pq)

簽名消息

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

編程實踐

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

計算公鑰和密鑰

1. 假設p = 3、q = 11（p，q都是素數即可。），則N = pq = 33；
2. r = (p-1)(q-1) = (3-1)(11-1) = 20；
3. 根據模反元素的計算公式，我們可以得出，e·d ≡ 1 (mod 20),即e·d = 20n+1 (n為正整數)；我們假設n=1，則e·d = 21。e、d為正整數，並且e與r互質，則e = 3，d = 7。（兩個數交換一下也可以。）

　　到這裡，公鑰和密鑰已經確定。公鑰為(N, e) = (33, 3)，密鑰為(N, d) = (33, 7)。

編程實現

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

RSA算法實現：

public class RSA { 
    /**
    *  加密、解密算法
    * @param key 公鑰或密鑰
    * @param message 數據
    * @return
    */ 
    public static long rsa(int baseNum, int key, long message){ 
        if(baseNum < 1 || key < 1){ 
            return 0L; 
        } 
        //加密或者解密之後的數據 
        long rsaMessage = 0L; 
         
        //加密核心算法 
        rsaMessage = Math.round(Math.pow(message, key)) % baseNum; 
        return rsaMessage; 
    } 
     
     
     
    public static void main(String[] args){ 
        //基數 
        int baseNum = 3 * 11; 
        //公鑰 
        int keyE = 3; 
        //密鑰 
        int keyD = 7; 
        //未加密的數據 
        long msg = 24L; 
        //加密後的數據 
        long encodeMsg = rsa(baseNum, keyE, msg); 
        //解密後的數據 
        long decodeMsg = rsa(baseNum, keyD, encodeMsg); 
         
        System.out.println("加密前：" + msg); 
        System.out.println("加密後：" + encodeMsg); 
        System.out.println("解密後：" + decodeMsg); 
         
    } 
     
} 

RSA算法結果：

加密前：24

加密後：30

解密後：24

（看程序最清楚了，對於要加密的數字m, m^e%N=c, c就是加密之後的密文。c^d%N=m, 就能解密得到m）

RSA加密算法的安全性

　　當p和q是一個大素數的時候，從它們的積pq去分解因子p和q，這是一個公認的數學難題。然而，雖然RSA的安全性依賴於大數的因子分解，但並沒有從理論上證明破譯RSA的難度與大數分解難度等價。

　　1994年彼得·秀爾（Peter Shor）證明一台量子計算機可以在多項式時間內進行因數分解。假如量子計算機有朝一日可以成為一種可行的技術的話，那麼秀爾的算法可以淘汰RSA和相關的衍生算法。（即依賴於分解大整數困難性的加密算法）

　　另外，假如N的長度小於或等於256位，那麼用一台個人電腦在幾個小時內就可以分解它的因子了。1999年，數百台電腦合作分解了一個512位長的N。1997年後開發的系統，用戶應使用1024位密鑰，證書認證機構應用2048位或以上。

RSA加密算法的缺點

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

1. 產生密鑰很麻煩，受到素數產生技術的限制，因而難以做到一次一密；
2. 分組長度太大，為保證安全性，n 至少也要 600 bits 以上，使運算代價很高，尤其是速度較慢。