RSA算法原理——（3）RSA加解密過程及公式論證

上期（RSA算法原理——（2）RSA簡介及基礎數論知識）為大家介紹了：互質、歐拉函數、歐拉定理、模反元素這四個數論的知識點，而這四個知識點是了解RSA加密算法的基石，忘了的同學可以快速的回顧一遍。

一、RSA算法原理——（1）目前常見加密算法簡介

二、RSA算法原理——（2）RSA簡介及基礎數論知識

三、RSA加解密過程及公式論證

今天的内容主要分為三個部分：

rsa密鑰生成過程：講解如何生成公鑰和私鑰
rsa加解密示範：示範加密解密的過程
rsa公式論證：解密公式的證明

1、rsa密鑰生成過程

大家都知道rsa加密算法是一種非對稱加密算法，也就意味着加密和解密是使用不同的密鑰，而這不同的密鑰是如何生成的呢？下面我們來模拟下小紅是如何生成公鑰和私鑰的。

六步生成密鑰：

（1）随機選擇兩個不相等的質數p和q

（2）計算p和q的乘積n

n的長度就是密鑰長度，3233寫成二進制是110010100001，一共有12位，是以這個密鑰就是12位。實際應用中，RSA密鑰一般是1024位，重要場合則為2048位。

（3）計算n的歐拉函數φ(n)

這裡利用我們上篇講到的歐拉函數求解的第四種情況：

又因為61和53都是質數，是以可以根據歐拉函數求解的第二種情況：

是以 φ(n)=3120

（4）随機選擇一個整數e，條件是1< e < φ(n)，且e與φ(n) 互質

小紅就在1到3120之間，随機選擇了17。（實際應用中，常常選擇65537）

（5）計算e對于φ(n)的模反元素d

讓我們來回顧一下什麼是模反元素：

所謂“模反元素”就是指有一個整數d，可以使得ed除以φ(n)的餘數為1，公式表示：

這個公式等價于

将e=17、φ(n)=3120代入得：

設x=d、y=-k，得

是以我們要求的模反元素d就是對上面的二進制一次方程求解

根據擴充歐幾裡得算法（輾轉相除法）求解：

上圖我們使用擴充歐幾裡得求得x=-367，是以d=x=-367，但通常我們習慣取正整數，這樣友善計算，還記得我們上節講過的模反元素的特性嗎：

是以我們取d=d+kφ(n)=-367+1x3120=2753，到這裡所有的計算已經全部完畢！

（6）将n和e封裝成公鑰，n和d封裝成私鑰

讓我們來回顧一下我們一共出現的6個數字：

p=61; 随機數與q互質
q=53;随機數與p互質
n=pq=6153=3233
φ(n)=φ(p*q)=φ(61x53) = φ(61)φ(53)=60x52=3120
e=17; 随機數，條件是1< e < φ(n)，且e與φ(n) 互質
d=2753; e對于φ(n)的模反元素d

在這個例子中n=3233，e=17，d=2753，是以公鑰就是 (n,e)=(3233,17)，私鑰就是(n,d)=(3233, 2753)，這樣小紅就将公鑰公布出去，自己儲存好私鑰就可以啦！

至此我們公鑰、私鑰就生成完畢，是不是覺得并不是很難呢？是不是有點懷疑私鑰會不會被人破解呢？下面我們來看看如何才能暴力破解私鑰。

（7）rsa算法可靠性

回顧我們一共生成了六個數字：p q n φ(n) e d，這六個數字之中，公鑰用到了兩個（n和e），其餘四個數字都是不公開的。其中最關鍵的是d，因為n和d組成了私鑰，一旦d洩漏，就等于私鑰洩漏。

那麼，有無可能在已知n和e的情況下，推導出d？

ed≡1 (mod φ(n))。隻有知道e和φ(n)，才能算出d
φ(n)=(p-1)(q-1)。隻有知道p和q，才能算出φ(n)
n=pq。隻有将n因數分解，才能算出p和q

結論：如果n可以被因數分解，d就可以算出，也就意味着私鑰被破解。

看到這裡有同學可能會驚呼：原來破解RSA算法的方法這麼簡單？？？

可是，大整數的因數分解，是一件非常困難的事情。也許你可以對3233進行因數分解（61×53），但是你沒辦法對下面的大整數分解：

它等于兩個質素的乘積：

這也是目前維基百科記錄的人類分解的最大整數（232個十進制位，768個二進制位），除了暴力破解，還沒有發現别的有效方法。是以限制人類分解大整數的是計算機的計算能力，相信如果有一天真正的量子計算機問世後，又會引發一輪安全加密競賽！

1999年，RSA-155 (512 bits)被成功分解，花了五個月時間（約8000 MIPS年）和224 CPU hours在一台有3.2G中央記憶體的Cray C916計算機上完成。
2009年12月12日，編号為RSA-768（768 bits, 232 digits）數也被成功分解[10]。這一事件威脅了現通行的1024-bit密鑰的安全性，普遍認為使用者應盡快更新到2048-bit或以上。

2、rsa加解密示範

小紅有了公鑰和私鑰這樣就可以進行加解密了，于是小紅拉着小明一起來測試一下！

（1）加密要用公鑰 (n,e)

假設小明先測試性的給小紅發一個字母m=“A”，我們都知道在通信傳輸中隻能傳輸0和1，是以我們先将“A”轉ascii碼為65，是以m=65，m必須是整數（字元串可以取ascii值或unicode值），且m必須小于n。

所謂”加密”，就是使用下面的加密公式算出下式的密文c：

小明得到的公鑰是(n,e)=(3233, 17)，m=65，那麼得到下面的等式：

小明通過電腦一算c=2790，是以他就把2790發給小紅了。

（2）解密要用私鑰(n,d)

小紅拿到小明發過來的密文c=2790，就用下面的公式進行解密出明文m：

而小紅的私鑰為：(n,d) = (3233,2753)，是以得到下面的等式：

小紅通過電腦一算，得m=65，然後小紅對照着ascii碼表得出65對應得字母為A。

至此，整個加解密過程就示範完了，我們來總結一下：

小明擷取到小紅的公鑰(n,e)=(3233,17)
小明選取發送的消息m=A=65，注意m要小于n，如果消息大于n，則可以分段加密！
小明通過加密公式：m^e ≡ c (mod n) 算出密文c=2790
小紅擷取到小明的密文c=2790
小紅使用解密公式：c^d ≡ m (mod n) 算法明文m=65=A

我們可以看到，其實RSA加密算法最核心的就是用公式來加解密，那麼我們會有個疑問？為什麼解密公式一定可以得到明文m呢？也就是說這個公式是怎麼推導出來的？公式一定成立嗎？

感興趣的同學我們可以來一起證明一下解密公式，這也是整個RSA加密算法的最後最核心的一個知識點了。這裡我會一步一步的推理，盡可能通俗易懂；

3、rsa公式論證

首先讓我們再來回顧一下我們一共出現的8個數字

p：随機數與q互質
q：随機數與p互質
n=p*q
φ(n)=φ(pq)=φ(p)φ(q)=(p-1)(q-1)
e：随機數，條件是1< e < φ(n)，且e與φ(n) 互質
d：e對于φ(n)的模反元素d：ed≡1 (mod φ(n))
m：小明發送的明文
c：小明用公鑰加密後的密文

驗證rsa算法成立，主要就是驗證解密公式成立：

根據加密公式：

将c代入要我們要證明的那個解密公式：

上式等同于下面的公式，原因如下

原因：我們都知道下面的二進制一次方程分解，隻有第一項不包含n，而所有包含n的項在對n 取餘的操作中都可以消掉。是以得出了上面那個結論

又因為生成密鑰的第五步中我們取e并求了他對φ(n)的模反元素d：

是以将ed代入上式得

是以，我們隻要證明這個公式成立，就證明解密公式的成立，也就證明了RSA算法的成立。

下面我們分兩種情況來驗證上面的例子

（1） m與n互質

根據歐拉定理：如果兩個正整數a和n互質，則n的歐拉函數 φ(n) 可以讓下面的等式成立：

證明：因為m與n互質，得

而(1 + kn)^h對n取模為1，因為對(1 + kn)^h拆分隻有第一項1不含有n，是以有

同理

而 (1 + kn)*m對n取模為m，因為前面說過0 < m < n，是以有

當m與n互質時，證明原式成功！！！

（2） m與n不是互質關系

此時m與n不互質，是以m與n必定有除1以外的公因子，而又因為n等于質數p和質數q的乘積，是以m必然等于kp或kq。

以 m = kp為例，考慮到這時m與質數q必然互質，則根據歐拉定理和歐拉函數（第二種：當q為質數，則φ(q)=q-1）使下面的式子成立：

同上（m與n互質中）證明原理可得：

又因為

将ed代入上式

上式中，等式左邊(kp)^ed對p取模為0，右邊kp對p取模也為0，是以tq一定能整除p，但q是與p互質的，是以t必然能整除p，設t=rp，得

因為 m=kp，n=pq，是以

将ed代入上式得：

當m與n不互質時，證明原式成功！！！

附手稿：