計算機領域常用的RSA加密算法具有非常高的穩(wěn)定性，發(fā)明至今，世界上仍然沒有可靠的攻擊它的方法。有人說，RSA加密算法是地球上最重要的算法，如果沒有 RSA加密算法，現(xiàn)在的網絡世界將毫無安全可言，更不可能有現(xiàn)在的網上交易。

今天，微軟智匯學院就將給大家講講RSA加密算法。其理論基礎是一系列嚴格的數學推導過程，但原理并不難懂，甚至主要和我們小學就學過的質數、約數和質因數分解有關。

RSA加密算法

RSA加密算法非常有名，在計算機領域的應用非常廣泛，幾乎是一般用戶在信息加密時的首選。

它是一種非對稱加密演算法，名字來源于它的三個發(fā)明人——羅納德·李維斯特(RonRivest)、阿迪·薩莫爾(Adi Shamir)和倫納德·阿德曼(Leonard Adleman)——名字的首字母縮寫。

這三人在1977年一起提出了RSA算法，當時他們都在麻省理工學院工作。

雖然已經被發(fā)明了四十多年，但是至今世界上仍然沒有可靠的攻擊它的方法。在技術瞬息萬變的今天，這樣的穩(wěn)定性尤其難能可貴。

RSA為什么這么保險呢?當然和它的實現(xiàn)原理有關系，我們要了解RSA，就需要掌握它的理論基礎。

作為加密算法，RSA的原理實際上就是一系列非常嚴格的數學推導過程。一說到數學可能有人又要頭疼了，數學啊，很難吧?

其實，并不難。

RSA算法背后的數學概念

最近筆者給一位小學生檢查數學作業(yè)，由此得知他們已經在學習下面這些概念：

余數：如果有兩個整數a和b，a除以b不能除盡，那么a中不能除盡的部分就是。比如11除以5，商是2，余數是1。

MOD函數：求余數的函數，mod(11,5)就是對11除以5求余數。

約數：又稱因數，如果有兩個整數a和b，a除以b能除盡，那么b就是a的約數，比如，2÷1=2，2÷2=1，2的約數就是1和2。

因數分解：把一個正整數寫成幾個約數的乘積。

公約數：有幾個整數，它們都有一個相同的約數，那么這個約數就是這幾個整數的公約數，比如2的約數是1和2，4的約數是1、2和4，6的約數是1、2、3、6，2、4和6的公約數就是1和2。

質數：一個大于1的自然數，除了1和它本身，再沒有別的約數了，那么這個數就是質數。比如2，它大于1，只有1和2兩個約數，它就是質數。

1)密鑰生成

這里說的密鑰又分為公鑰和私鑰兩個部分，各對應兩個數字，公鑰為 n 和 e，私鑰為 n 和 d。

因為公鑰和私鑰的 n 是同一個 n，因此，其實RSA的密鑰總共涉及三個數字：n，e 和 d，它們都是非常非常大的正整數。

它們是通過以下步驟生成的：

Step1.1：選擇兩個質數 p 和 q.

Step1.2：計算出 p 和 q 的積 n：n = p·q。

Step1.3：計算n的卡邁克爾函數λ(n)。

卡邁克爾函數，n 的卡邁克爾函數計作 λ(n)，定義為：對任意正整數 n，它的卡邁克爾函數λ(n) 是滿足如下條件的最小的正整數：這個正整數 m 使得 am ≡ 1 (mod n)，其中 a 是 1 到 m 之間任意一個與 m 互質的整數。

這里的 ≡ 是同余符號——同余是數論中的一種等價關系，當兩個整數除以同一個正整數，若得相同余數，則二整數同余。

所以式子 am ≡ 1 (mod n) 表示：a的m次冪除以n之后的余數為1，又可以稱作：am 和1對于模n同余。

在這里還需要了解另一個函數：

歐拉函數，n的歐拉函數計作φ(n)，定義為：對任意正整數n，它的歐拉函數就是在小于或等于n的正整數里與n互質的數字的個數。

φ(n) 分不同情況來看：

a) 如果n=1，那么φ(1)=1

b) 如果n是質數，那么φ(n)=n-1

c)如果n是一個質數p的k次方，即n=pk，那么φ(n)=φ(pk)= pk- pk-1

d)如果n是兩個互質的數p和q的乘積，那么φ(n)=φ(p) ⋅φ(q)

當 n 為1、2、4、奇質數的次冪、奇質數的次冪的兩倍時，λ(n) 為 φ(n)，當 n 為2、4以外的2的次冪時，λ(n) 為 φ(n) 的一半：

(i) 歐拉函數的情況 c);

(ii)正整數 n 可寫作它的質因數的積。

因此對于任意正整數n，它的卡邁克爾函數 λ(n )是 n 的質因數的卡邁克爾函數的最小公倍數，

其中：p1 < p2 <... < pk 是質數，而 r1, r2,..., rk 是正整數。

還有，因為 n 為兩個質數 p 和 q 的積，所以 n 的卡邁克爾函數等于 p 和 q 的卡邁克爾函數的最小公倍數，計作 λ(n) = lcm(λ(p), λ(q)) 。

又因為根據 歐拉函數的情況 c)可得：λ(p) = φ(p) = p – 1且 λ(q) = φ(q) = q − 1。因此，λ(n) = lcm(p − 1, q − 1)。

也就是說，這一步要計算 p-1 和 q-1 的最小公倍數。

Step1.4：選擇一個正整數e，滿足：1 < e < λ(n) ，并且 e 和 λ(n) 互質。

Step1.5：確定 e 的模反元素 d。

模反元素：如果有兩個互質的正整數a和n，那一定可以找到一個整數b，能讓 ab - 1 能被 n 整除，也就是說ab除以n的余數是1，記作 ab ≡ 1(mod n)。數學家們已經利用歐拉定理也能證明模反元素的存在。

也就是說 d 滿足：d ≡ e−1 (mod λ(n)) ，即 ed ≡ 1 (mod λ(n))。

至此，第一階段完成。在這一階段，Step1.2 生成的 n 和 Step1.4 生成的 e 組成了公鑰：(n，e);而 Step1.2 生成的 n 和 Step1.5 生成的 d 組成了私鑰：(n，d)。

2)密鑰發(fā)布

密鑰生成之后，公鑰被公之于眾，任何人都可以獲取并使用，而私鑰則被保留在特定的，被允許解讀加密信息的人手中。

3)加密

加密只需要用到公鑰(n，e)，當人們想要用RSA算法加密一段信息時，需要按以下步驟進行：

Step 3.1：將信息按照約定的方法轉化為一個正整數m，滿足 0 ≤ m < n 。

此處的將信息轉化為數字的方法也是公開的，如果信息實在太多也可以考慮分段，每段分別轉化為一個大于等于0，小于n的正整數。

Step 3.2：計算c = mod(me， n)，c就是加密后的密文。 加密完成，將生成的密文傳遞給要送達的人。

4) 解密

收到密文的人，如果手中有私鑰(n，d)，就可以開始解密了，方法如下：

Step 4.1：計算 m = mod(cd， n)，m就是原本的原文。

RSA加密全過程實例

下面我們來看一個例子：

1) 密鑰生成

1.1：我們選擇 p = 61 和 q = 53.

1.2：計算n = 61 × 53 =3233.

1.3：計算λ(n) = λ(3233) = Icm(60, 52) = 780.

1.4： 選擇 e，需滿足 1 < e <780，且 e 和780互質。

我們選擇 e = 17.

1.5：求e的模反元素d，使得 ed ≡ 1 mod λ(n)，也就是17d ≡ 1 mod 780.

求 17d = 780 h + 1 ，其中h為正整數。

求得d = 413，驗算：413 ×17 = 780 × 9 + 1，d成立。

我們生成了公鑰 (n = 3233, e =17)，和私鑰 (n = 3233, d =413).

2)密鑰發(fā)布

公布公鑰，將密鑰交給我們要通信的朋友。

3)加密

原文為m(正整數)，計算：c = mod(me, n).

假設m = 65， 則c = mod(6517, 3233) = 2790.

原文 65，通過公鑰加密得到密文 2790。將其交給有私鑰的人。

4) 解密

計算m = mod (cd, n) 得到原文。

密文為2790，則m = mod(2790413, 3233) = 65

密文為2790，通過私鑰解密得到原文65。

以上就是RSA的整個運作過程。

RSA算法原理推導

為什么這個加密解密過程能夠有效?為什么當 c = mod (me,n) 時，就一定有m = mod(cd, n)呢?

首先， 根據 Step 3.2 可知：me ≡ c (mod n)，根據同余關系保持基本運算的性質，有 cd ≡ (me)d = med (mod n)，也就是 cd ≡ med (mod n)

其次，因為 ed ≡ 1 (mod λ(n))，即 ed - 1 ≡ 0 (mod λ(n))，也就是說ed - 1 可以被λ(n) 整除。

又因為 λ(n) = lcm(p − 1, q − 1) ，也就是 λ(n) 可以被 p -1 和 q-1 整除，因此有 ed - 1 = h(p -1) = k(q-1)， h和k都是非負整數。

于是有：med = m⋅m (ed-1)= m (m (p-1) ) h

根據Step1.3 中 φ(p) = p – 1，med = m (m (p-1) ) h = m (mφ (p) ) h

因為 p 是質數，所以如果 m 要么是 p 的倍數，要么與 p 互質——

i)若 m 是 p 的倍數，則 med 也是 p 的倍數， med ≡ 0 ≡ m (mod p) ;

ii)若 m 與 p 互質，根據歐拉定理則有 mφ(p) ≡ 1 (mod p)

歐拉定理：兩個互質的正整數 a 和 b， aφ(b) ≡1 (mod b)。

于是，有 med = m · mφ (p) ≡ m (mod p)，即 med ≡ m (mod p)

綜合i)和ii)有：med ≡ m (mod p) .

同理，可證明 med ≡ m (mod q).

根據中國剩余定理，med ≡ m (mod p) 和 med ≡ m (mod q) 同時成立，等同于 med ≡ m (mod pq) 成立，又因為 pq = n，因此，我們得以證明：med ≡ m (mod n)

然后，根據同余的傳遞性，有 cd ≡ med ≡ m (mod n)。且已知 m < n，所以mod(cd ， n)= m，這也就是為什么 Step 4.1 能夠求出m的原因。

為什么RSA難于破解?

這件事我們不妨反過來想，如果我們要破解RSA加密文件，我們需要什么?

我們需要私鑰，私鑰包括兩個部分：n 和 d，n 就是公鑰中的 n，所以我們唯一需要知道的就是 d。

那么我們能不能自己把 d 求出來呢?理論上是可行的。

因為 ed ≡ 1 mod λ(n)，e 是已知的，且 λ(n) = lcm(p − 1, q − 1)，因此，我們只需要知道 p - 1 和 q - 1 就好了。

n = p·q，那么我們只要對 n 進行質因數分解，找到它的最大質因數就可以了。

可是，實際操作起來，卻不那么容易。

如果 p 和 q 很大，n 就會更大。而大整數的因數分解，是一件非常困難的事情。目前，除了暴力破解，還沒有發(fā)現(xiàn)別的有效方法。

只有短的 RSA 鑰匙才可能被暴力方式破解。迄今為止，世界上還沒有任何可靠的攻擊RSA算法的方式。

只要其鑰匙的長度足夠長，用 RSA 加密的信息，就可以認為在事實上是不能被破解的。

沒想到吧，小學數學課上就學過的質數、余數、質因數分解竟然這么有用，居然就在生活中時時處處保護著我們的信息安全。