RSA原理與實例

來自： http://my.oschina.net/sunchp/blog/628550

1 數學概念

1.1 質數

質數是這樣的整數，它除了能表示為它自己和1的乘積以外，不能表示為任何其它兩個整數的乘積。

例如，15＝3＊5，所以15不是質數；12＝6＊2＝4＊3，所以12也不是質數；13除了等于13＊1以外，不能表示為其它任何兩個整數的乘積，所以13是一個質數。

質數也稱為“素數”。

1.2 互質數

互質數為數學中的一種概念，公因數只有1的兩個非零自然數，叫做互質數。

關于互質數，有以下定理：

（1）兩個質數一定是互質數。例如，2與7、13與19。

（2）一個質數如果不能整除另一個合數，這兩個數為互質數。例如，3與10、5與 26。

（3）1不是質數也不是合數，它和任何一個自然數在一起都是互質數。如1和9908。

（4）相鄰的兩個自然數是互質數。如 15與 16。

（5）相鄰的兩個奇數是互質數。如 49與 51。

（6）大數是質數的兩個數是互質數。如97與88。

（7）小數是質數，大數不是小數的倍數的兩個數是互質數。如 7和 16。

1.3 取模運算

一個整數m，以n為模做取模運算，記作 m mod n。

怎樣做呢？讓m去被n整除，只取所得的余數作為結果，就叫做取模運算。

例如，10 mod 3=1；26 mod 6=2；28 mod 2 =0等等。 

1.4 同余符號

兩個整數a，b，若它們以整數n為模，做取模運算，所得的余數相等，則稱a，b對于模n同余。記作 a≡b mod n。

比如26 ≡ 14 mod 12

PS： ”≡“，非”=“

2 RSA算法描述

（1）選擇一對不同的、足夠大的互質數p，q。

（2）計算n=pq。

（3）計算f(n)=(p-1)(q-1)，同時對p, q嚴加保密，不讓任何人知道。

（4）隨機找一個與f(n)互質的數e，且1<e<f(n)。

（5）計算d，使得de≡1 mod f(n)。 顯而易見，不管f(n)取什么值，符號右邊1 mod f(n)的結果都等于1；符號的左邊d與e的乘積做模運算后的結果也必須等于1。這就需要計算出d的值，讓這個同余等式能夠成立。

（6）公鑰KU=(n,e)，私鑰KR=(n,d)。

（7）加密時，先將明文變換成0至n-1的一個整數M。若明文較長，可先分割成適當的組，然后再進行交換。

設原文為M，密文為C，則加密過程為：

解密過程為：

PS： ”=“，非”≡“

回顧上面的密鑰生成步驟，一共出現六個數字：

p
q
n
f(n)
e
d

3 RSA實例

在這篇科普小文章里，不可能對RSA算法的正確性作嚴格的數學證明，但我們可以通過一個簡單的例子來理解RSA的工作原理。為了便于計算。在以下實例中只選取小數值的素數p,q,以及e，假設用戶A需要將明文“key”通過RSA加密后傳遞給用戶B。（灰色為不公開的數據，綠色為需要公開的數據）

3.1 設計公鑰KU=(n,e)，私鑰KR=(n,d)

（1）p=3，q=11

（2）n=pq=3x11=33

（3）f（n）=(p-1)(q-1)=2×10=20

（4）隨機取e=3（3與20互質），則e×d≡1 mod f(n)，即3×d≡1 mod 20

d怎么取呢？可以用試算的辦法來尋找。試算結果如下：

通過試算我們找到，當d=7時，e×d≡1 mod f(n)同余等式成立。因此，可令d=7。

（5）從而我們可以設計出一對公私密鑰，加密密鑰（公鑰）為：KU =(n,e)=(33,3)，解密密鑰（私鑰）為：KR =(n,d)=(33,7)。

3.2 英文數字化

將明文信息數字化，假定明文英文字母編碼表為按字母順序排列數值，即：

則得到分組后明文”key“信息為：11，05，25。

3.3 明文加密

用戶A用公鑰KU(33,3) 將數字化明文信息加密成密文。

因此，得到相應的密文信息為：11，26，16。

3.4 密文解密

用戶B用私鑰KR（33，7）將密文解密成明文。

用戶B得到明文信息為：11，05，25。根據上面的編碼表將其轉換為英文，我們又得到了恢復后的原文“key”。 

RSA的原理就可以這么簡單地解釋！當然，實際運用要比這復雜得多。p、q、e的選取、公鑰私鑰的生成，加密解密模指數運算都有一定的計算程序，需要仰仗計算機高速完成。

4 RSA的安全性

為什么RSA密碼難于破解？

在RSA密碼應用中，公鑰KU是被公開的，即e和n的數值可以被第三方竊聽者得到。破解RSA密碼的問題就是從已知的e和n的數值（n等于pq），想法求出d的數值，這樣就可以得到私鑰來破解密文。

從上文中的公式：de≡1 mod f(n)≡1 mod ((p-1)(q-1))) ≡ 1 mod (pq-(p+q)+1) ≡ 1 mod (n-(p+q)+1) 可以看出,n，e已知，密碼破解的實質問題是：

只要求出p和q的值，我們就能求出d的值而得到私鑰。

當p和q是一個大素數的時候，從它們的積pq去分解因子p和q，這是一個公認的數學難題。

比如當pq的乘積n轉換為2進制表示，位數達到1024位時，迄今為止還沒有人能夠利用任何計算工具去完成分解因子的任務（目前被破解的最長RSA密鑰是768個二進制位，因此可以認為，1024位的RSA密鑰基本安全，2048位的密鑰極其安全）。因此，RSA從提出到現在已近二十年，經歷了各種攻擊的考驗，逐漸為人們接受，普遍認為是目前最優秀的公鑰方案之一。

然而，雖然RSA的安全性依賴于大數的因子分解，但并沒有從理論上證明破譯RSA的難度與大數分解難度等價。即RSA的重大缺陷是無法從理論上把握它的保密性能如何。

此外，RSA的缺點還有：

A)產生密鑰很麻煩，受到素數產生技術的限制，因而難以做到一次一密。

B)分組長度太大，為保證安全性，n 至少也要 600 bits 以上，使運算代價很高，尤其是速度較慢，較對稱密碼算法慢幾個數量級；且隨著大數分解技術的發展，這個長度還在增加，不利于數據格式的標準化。

因此，使用RSA只能加密少量數據，大量的數據加密還要靠對稱密碼算法。

5 RSA選用小公鑰指數（e）

現有的大部分RSA算法實現都遵循PKCS#1 v2.1/v1.5 (2002/1993)。根據PKCS#1的建議，公鑰指數e是可以選取較小的素數3或65537(=2^16+1)。這樣選取主要是為了提高加密或簽名驗證的性能，因為3或65537分別只需要2或17次模乘運算，而一個隨機選擇的e(假設n是1024-bit)則大約需要1000次。這種選用小公鑰指數的方法使用戶相信RSA在簽名驗證和加密操作方面確實要比“以高效著稱的ECC”還要高效很多。

然而在選用小公鑰指數時，有很多人則更傾向于選e=65537而不是e=3，他們認為3“似乎不安全”，然而又給不出所以然。在“正確使用”RSA算法的情況下，至今為止還沒有發現公開的攻擊方法能有效攻擊e=3。

6 加密解密 VS 驗證簽名

6.1 公鑰和私鑰的對立性

根據上述RSA算法的描述，可以知道：公鑰指數e是可以隨機選擇的一個質數，且根據 e×d≡1 mod f(n)試算出私鑰指數d。

上面實例中，我們選擇了e=3，d=7，且 3 x 7 ≡1 mod 20，公鑰（33，3），私鑰（33，7） ；如果我們選擇e=7，d=3，那么7 x 3=1 mod 20仍成立，此時公鑰就是（33，7），私鑰是（33，3）。

后續的加密解密步驟仍能正確執行。

所以，RSA算法中，公鑰和私鑰是一個相對的概念。一個作為公鑰，另一個就是私鑰，具有對立性。分發給公共持有的，便被叫做公鑰；私持不公布的，便被叫做私鑰。

根據公鑰和私鑰的對立性，可知：

（1）公鑰加密明文后，私鑰可以解密出來；

（2）私鑰加密明文后，公鑰可以解密出來；

6.2 加密解密 VS 驗證簽名

客戶端持有公鑰，將消息加密后，公開密文，因為只有服務端有私鑰，所以也只有服務端能解密出明文。這個過程叫做加密解密。

服務端持有密鑰，講消息加密后，公開密文和明文，因為客戶端都有公鑰，都能解密出明文，然后客戶端比較“解密得到的明文”和“接收到的明文”是否相等。如果相等，則說明內容未被篡改；如果不相等，則說明內容被篡改。用私鑰加密的明文，也叫做簽名。這個過程叫做驗證簽名。

PS：如果文中有瑕疵或者錯誤，歡迎各位吐槽