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

今天，微軟智匯學(xué)院就將給大家講講RSA加密算法。其理論基礎(chǔ)是一系列嚴(yán)格的數(shù)學(xué)推導(dǎo)過程，但原理并不難懂，甚至主要和我們小學(xué)就學(xué)過的質(zhì)數(shù)、約數(shù)和質(zhì)因數(shù)分解有關(guān)。

RSA加密算法

RSA加密算法非常有名，在計(jì)算機(jī)領(lǐng)域的應(yīng)用非常廣泛，幾乎是一般用戶在信息加密時(shí)的首選。

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

這三人在1977年一起提出了RSA算法，當(dāng)時(shí)他們都在麻省理工學(xué)院工作。

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

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

作為加密算法，RSA的原理實(shí)際上就是一系列非常嚴(yán)格的數(shù)學(xué)推導(dǎo)過程。一說到數(shù)學(xué)可能有人又要頭疼了，數(shù)學(xué)啊，很難吧?

其實(shí)，并不難。

RSA算法背后的數(shù)學(xué)概念

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

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

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

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

因數(shù)分解：把一個(gè)正整數(shù)寫成幾個(gè)約數(shù)的乘積。

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

質(zhì)數(shù)：一個(gè)大于1的自然數(shù)，除了1和它本身，再?zèng)]有別的約數(shù)了，那么這個(gè)數(shù)就是質(zhì)數(shù)。比如2，它大于1，只有1和2兩個(gè)約數(shù)，它就是質(zhì)數(shù)。

1)密鑰生成

這里說的密鑰又分為公鑰和私鑰兩個(gè)部分，各對(duì)應(yīng)兩個(gè)數(shù)字，公鑰為 n 和 e，私鑰為 n 和 d。

因?yàn)楣€和私鑰的 n 是同一個(gè) n，因此，其實(shí)RSA的密鑰總共涉及三個(gè)數(shù)字：n，e 和 d，它們都是非常非常大的正整數(shù)。

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

Step1.1：選擇兩個(gè)質(zhì)數(shù) p 和 q.

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

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

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

這里的 ≡ 是同余符號(hào)——同余是數(shù)論中的一種等價(jià)關(guān)系，當(dāng)兩個(gè)整數(shù)除以同一個(gè)正整數(shù)，若得相同余數(shù)，則二整數(shù)同余。

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

在這里還需要了解另一個(gè)函數(shù)：

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

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

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

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

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

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

當(dāng) n 為1、2、4、奇質(zhì)數(shù)的次冪、奇質(zhì)數(shù)的次冪的兩倍時(shí)，λ(n) 為 φ(n)，當(dāng) n 為2、4以外的2的次冪時(shí)，λ(n) 為 φ(n) 的一半：

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

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

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

其中：p1 < p2 <... < pk 是質(zhì)數(shù)，而 r1, r2,..., rk 是正整數(shù)。

還有，因?yàn)?n 為兩個(gè)質(zhì)數(shù) p 和 q 的積，所以 n 的卡邁克爾函數(shù)等于 p 和 q 的卡邁克爾函數(shù)的最小公倍數(shù)，計(jì)作 λ(n) = lcm(λ(p), λ(q)) 。

又因?yàn)楦鶕?jù) 歐拉函數(shù)的情況 c)可得：λ(p) = φ(p) = p – 1且 λ(q) = φ(q) = q − 1。因此，λ(n) = lcm(p − 1, q − 1)。

也就是說，這一步要計(jì)算 p-1 和 q-1 的最小公倍數(shù)。

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

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

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

也就是說 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)，當(dāng)人們想要用RSA算法加密一段信息時(shí)，需要按以下步驟進(jìn)行：

Step 3.1：將信息按照約定的方法轉(zhuǎn)化為一個(gè)正整數(shù)m，滿足 0 ≤ m < n 。

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

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

4) 解密

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

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

RSA加密全過程實(shí)例

下面我們來看一個(gè)例子：

1) 密鑰生成

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

1.2：計(jì)算n = 61 × 53 =3233.

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

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

我們選擇 e = 17.

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

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

求得d = 413，驗(yàn)算：413 ×17 = 780 × 9 + 1，d成立。

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

2)密鑰發(fā)布

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

3)加密

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

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

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

4) 解密

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

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

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

以上就是RSA的整個(gè)運(yùn)作過程。

RSA算法原理推導(dǎo)

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

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

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

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

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

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

因?yàn)?p 是質(zhì)數(shù)，所以如果 m 要么是 p 的倍數(shù)，要么與 p 互質(zhì)——

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

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

歐拉定理：兩個(gè)互質(zhì)的正整數(shù) 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).

根據(jù)中國(guó)剩余定理，med ≡ m (mod p) 和 med ≡ m (mod q) 同時(shí)成立，等同于 med ≡ m (mod pq) 成立，又因?yàn)?pq = n，因此，我們得以證明：med ≡ m (mod n)

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

為什么RSA難于破解?

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

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

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

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

n = p·q，那么我們只要對(duì) n 進(jìn)行質(zhì)因數(shù)分解，找到它的最大質(zhì)因數(shù)就可以了。

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

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

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

只要其鑰匙的長(zhǎng)度足夠長(zhǎng)，用 RSA 加密的信息，就可以認(rèn)為在事實(shí)上是不能被破解的。

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