從對稱加密演算法到非對稱加密演算法

對稱加密演算法：資訊的收發方會通過事先商定好的密鑰對資料加密和解密，這種加密演算法會導致

• 每兩個人相互交流就需要一個密鑰，隨著用戶增多，密鑰管理愈加困難，
• 網路傳輸密鑰也需要加密，而沒有密鑰則無法解密，所以密鑰必須通過見面協商，

非對稱加密演算法：用不同的密鑰對資料進行加密和解密，加密的密鑰（公鑰）是公開的，而解密的密鑰（私鑰）僅接收者持有，

模運算 Modular Arithmetic

由于模運算（取余運算）正向計算非常容易，且不可逆的特性，我們可以保證用公鑰加密之后的明文不會被輕易破解，

考慮算式 3 3 % 7 3^3\ \%\ 7 33 % 7，可以很容易得出答案為6，而已知 3 x % 7 = 6 3^x\ \%\ 7=6 3x % 7=6時，反向推算 x x x就只能逐一代入驗證了，鑒于此例數量級較小，還是很容易就可以推算出答案，

而如果改為 3 x % 984426289703667782113631386235633223212587 = 6 3^x\ \%\ 984426289703667782113631386235633223212587=6 3x % 984426289703667782113631386235633223212587=6，再一一嘗試就不太現實了，因為有對大數來說求模運算非常困難的特性，模運算也被冠以“單向函式”（One-way Function）之名，

RSA公鑰加密演算法

假設要加密的資訊為m (message)，對其求 e 次冪，此處 e (encrypt)代表加密用的公鑰，隨后對N取模，得到密文c (cipher)：
m e m o d ?? N = c m^e\mod N=c memodN=c
顯然，由m得到c的正向計算很簡單，但由c推算m是非常困難的，
解密的程序與加密類似：
c d m o d ?? N = m c^d\mod N=m cdmodN=m
其中d (decrypt)代表解密用的私鑰，

將兩個式子合并，得
m e d m o d ?? N = m m^{ed}\mod N=m medmodN=m

到此為止，問題變為如何選取合適的 e 和 d ，

歐拉定理(Euler’s theorem)：
m，n互質時，取m的 ? ( n ) \phi(n) ?(n)次方，并對n取余數，結果恒等于1，即：
m ? ( n ) ≡ 1 ( m o d n ) m^{\phi(n)}\equiv 1\ (mod\ n) m?(n)≡1 (mod n)
其中， ? ( n ) \phi(n) ?(n)為歐拉函式，它代表小于等于n的數中，有幾個數與n互質，例如 ? ( 6 ) = 2 \phi(6)=2 ?(6)=2，

對 m ? ( N ) m o d ?? n = 1 m^{\phi(N)}\mod n= 1 m?(N)modn=1等式兩端同取k次冪，并乘以m，可以寫成
m k ? ( N ) + 1 m o d ?? N = m m^{k\phi(N)+1}\mod N = m mk?(N)+1modN=m

經過變換，這個式子形式上與上面的 m e d m o d ?? N = m m^{ed}\mod N = m medmodN=m 相同，可以得到
e d = k ? ( N ) + 1 ed=k\phi(N)+1 ed=k?(N)+1

將e移到式子右邊，得：
d = k ? ( N ) + 1 e d=\frac{k\phi(N)+1}{e} d=ek?(N)+1?

所以我們可以通過選取此處k、N、e的值來確定私鑰d，

問題在于 ? ( n ) \phi(n) ?(n)的計算是十分困難的，它只能夠根據定義計算，即對n做質因數分解，而對上百位的大數做質因數分解幾乎可以看做計算上不可行的(computational infeasible)，但如果n本身就是一個質數，我們可以很容易得到 ? ( n ) = n ? 1 \phi(n)=n-1 ?(n)=n?1，即n只與自己存在非1公因數，

且 ? ( n ) \phi(n) ?(n)還有一個重要的性質：積性函式，即對任意互質的數p, q，總有 ? ( p ? q ) = ? ( p ) ? ? ( q ) \phi(p*q)=\phi(p)*\phi(q) ?(p?q)=?(p)??(q)，例如選取 p = 17 q = 23 p=17\ q=23 p=17 q=23，就有 ? ( 17 ? 23 ) = ? ( 17 ) ? ? ( 23 ) = 16 ? 22 \phi(17*23)=\phi(17)*\phi(23)=16*22 ?(17?23)=?(17)??(23)=16?22，也即 ? ( 391 ) = 352 \phi(391)=352 ?(391)=352，

例如我們選取 k = 5 N = 391 e = 3 k=5\quad N=391\quad e=3 k=5N=391e=3（e應選與 ? ( N ) \phi(N) ?(N)互質的數，而k的選取較為隨意，保證d為整數即可），代入上式，得 d = 5 ? 352 + 2 3 = 587 d=\frac{5*352+2}{3}=587 d=35?352+2?=587
計算出d后，我們就不再需要p和q，將e和N作為加密的公鑰(public key)公布，而d作為解密的私鑰(private key)，

其他人因為不知道p，q兩個互質數，無法計算出 ? ( N ) \phi(N) ?(N)，也就無法破解私鑰d

舉例

利用上面得到的引數，加密字符’a’(ascii編碼97)
加密： 9 7 3 m o d ?? 391 = 79 97^3\mod 391=79 973mod391=79
解密： 7 9 587 m o d ?? 391 = 97 79^{587} \mod 391=97 79587mod391=97
成功解密字符a

參考 reference

https://www.bilibili.com/video/BV14y4y1272w