RSA 演算法--粗略數學推導篇

2 人贊了文章

之前一篇我們介紹完 RSA 演算法的基本原理了，了解了 RSA 演算法的加密鎖就是先冪後模的運算。這個鎖的特點是正向運算很容易，也就是加密過程很容易，但是解密過程很難，也就是要直接反向運算是不可能的。而要想讓反向運算成為可能，就要在先冪後模運算的各項參數上做文章，讓各項參數之間通過整數分解問題建立關係，這樣只要我們把握住這種關係，那麼反向運算就變得容易了。所以本節就來深入到整數分解問題，看看如何來構建先冪後模中的各項參數之間的關係，進而引申出如何生成公鑰和私鑰。

提出問題

下面我們把要解決的問題進一步明確一下，抽象成具體的數學任務。先冪後模函數的正向運算，從信息 m 獲得密文 c 是簡單的，而反向運算，從 c 運算獲得 m 是很難的。但是如果我們能夠合理的構建 e 和 N 之間的關係，同時把握體現 e 和 N 之間關係的關鍵信息，這個反向運算將不再困難。

實際上，我們總能找到一個合適的 d ，使得 c 的 d 次方對 N 求模的結果就是 m 。所以問題進一步的就是要構建 e , d 以及 N 的數學聯繫。顯然，這種聯繫要保證根據 e 和 N 是很難算出 d 來的。

實際上我們要做到的是，給定兩個大素數 p1 和 p2 ，讓 p1p2 = N ，由 e 容易算出 d 的前提是我們知道 p1p2 ，也就是是知道 N 的整數分解的結果。而如果不知道 ，那麼根據 e 和 N 算出 d 的難度就相當於對兩個大素數的乘積做反向分解，這個是很難的。說明一下，「很難」在這裡的意思就是沒有有效的求解方法，只能靠暴力搜索去解決。

好，看到這裡，我們要解決的問題就描述清楚了，怎麼解決呢？來繼續看下面的數學推導。

解決步驟

問題的關鍵就是使用歐拉函數。

在 RSA 這裡，歐拉函數的本來目的不重要，重要的是要使用的是它的一個屬性：也就是，只有滿足特定條件下才容易計算出它的結果，否則，就很難。推導過程我們就不說了，那這個特定條件是什麼呢？其實就是當 N 是兩個素數 p1 和 p2 的乘積的時候，因為此時可以保證下面的等式成立。

φ(N) = (p1-1)(p2-1)

例如 ，77 的歐拉函數其實是很難運算出來了，但是如果我們知道77可以分解為7和11，那麼就可以很容易得到結果60了。

φ(77) = (7-1)*(11-1) = 60

基於歐拉函數的這個特點，只要我們能推導出 e ，d 跟 φ(n) 的關係，那就能保證在 φ（n) 能夠運算出結果的時候，從 e 很容易得到 d ，否則，從 e 就很難算出 d 。推導過程要基於歐拉定理來進行。歐拉定理的具體意義我們不必深究。

其中三個橫杠是組成的等式叫做同餘式。例如，正整數 a，b 對 p 取模，它們的餘數相同，就記做 a ≡ b (mod p)。

推導過程我們也從略了。最終，經過歐拉定義和上面其他結論進行推導，可以得到下面兩個等式是同時成立的。

這樣，就可以得到 e 和 d 的關係了：也就是 e 和 d 的乘積，等於 k 乘以 φ(N) 加1 ：

d = (k*φ(N) + 1)/e

只要知道 φ(N) ，d 就可以算出來了。而如果不知道 φ(N) ，有了 e 也根本算不出 d 來。上面的 k 沒有預先的固定值，而是要在運算過程中算出來的。k 的取值要保證給定一個 e 的數值， d 最終可以算出整數來。

通過上面的討論，如何生成公鑰和私鑰的方法就有了，公鑰是 N 和 e ，e 是在一定範圍內隨機選擇的，而且是公開的。私鑰是由 N 和 d 組成的，而 d 是在知道 N 的整數分解結果的條件下，通過上面的運算計算出來的。同時，加密函數也有了，就是信息 m 的 e 次方對 N 取模，解密函數就是密文 c 的 d 次方對 N 取模。

運算公鑰和私鑰

下面我們就來實際使用一下上面的結論，生成一下公鑰和私鑰，並且做一遍加密和解密。

首先選擇兩個比較大的素數，實際中一般是幾百位，但是我們這裡為了演示方便，選擇小的一點的。p1 = 53 , p2 = 59 ，這樣 N = 53*59=3127 。

首先來生成公鑰和私鑰，Alice 選取 e = 3 。於是公鑰就是 e 和 N 這兩個數的組合。公鑰有了。下一步來生成私鑰，也就是去運算 d 。 因為知道 p1 和 p2 的值，所以 φ(N) 很容易算出結果，就是 3016 。根據上面運算 d 的公式，當 k 等於 2 的時候，d 可以取得整數值，d 就等於

d = (2*3016+1)/3 = 2011

私鑰就是 N 和 d 的組合。

接下來看加密和解密過程。Alice 把 e 和 N ，也就是公鑰發送給了 Bob 。

89^3 mod 3127 = 1394

Bob 把原文 89 ，e 和 N 帶入到加密函數中，最終得到密文 c = 1394 。加密過程完成。

Alice 收到密文之後，可以用私鑰進行解密。

1394^2011 mod 3127 = 89

也就是，把密文，d 和 n 都帶入解密函數，這樣就得到了信息 m = 89 。

這樣我們就完成了整個的過程。

總結

最後總結一下本文的內容。我們的問題是，如何構建先冪後模運算的各項參數之間的關係，從而保證如果一個人掌握了這種關係，是可以對加密鎖進行反向運算的。那個關係是通過整數分解問題去構建的，推導過程中會用到歐拉函數的一個重要特性，也就是如果參數的整數分解結果是知道的，那麼歐拉函數的結果也就很容易算出來，否則歐拉函數很難被求解。於是經過推導，我們可以得出 e*d 跟歐拉函數的值有著固定的聯繫，於是得到了從公鑰（也就是 e ）運算出私鑰（也就是 d ）的方法。

參考：

https://www.youtube.com/watch?v=wXB-V_Keiu8 https://en.wikipedia.org/wiki/RSA_(cryptosystem)https://www.kancloud.cn/kancloud/rsa_algorithm/48488