前文中介紹了 RSA 演算法的基本原理了，瞭解了 RSA 演算法的加密鎖就是先冪後模的運算。這個鎖的特點是正向運算很容易，也就是加密過程很容易，但是解密過程很難，也就是要直接反向運算是不可能的。而要想讓反向運算成為可能，就要在先冪後模運算的各項引數上做文章，讓各項引數之間透過整數分解問題建立關係，這樣只要我們把握住這種關係，那麼反向運算就變得容易了。所以本節就來深入到整數分解問題，看看如何來構建先冪後模中的各項引數之間的關係，進而引申出如何生成公鑰和私鑰
提出問題
下面我們把要解決的問題進一步明確一下，抽象成具體的數學任務。先冪後模函式的正向運算，從資訊 m 獲得密文 c 是簡單的，而反向運算，從 c 運算獲得 m 是很難的。但是如果我們能夠合理的構建 e 和 N 之間的關係，同時把握體現 e 和 N 之間關係的關鍵資訊，這個反向運算將不再困難。
實際上，我們總能找到一個合適的 d ，使得 c 的 d 次方對 N 求模的結果就是 m 。所以問題進一步的就是要構建 e , d 以及 N 的數學聯絡。
實際上我們要做到的是，給定兩個大素數 p1 和 p2 ，讓 p1*p2 = N ，由 e 容易算出 d 的前提是我們知道 p1 和 p2 的值，也就是是知道 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 ）的方法。
