昨天，心血來潮給大家分享了一個《每天一個算法——霍夫曼編碼壓縮算法》，大家的反應很好，挺感謝大家的支持。今天，準備繼續分享一個算法，我個人認為比較有意思，也比較重要。
RSA算法是一種"公鑰加密算法"。早期的加密模式，就是加密和解密都是用同一種規則（密鑰）。這種加密模式，就要求加密規則需要在雙方進行傳遞，信息是很不安全的。在這種加密模式下的算法，也叫"對稱加密算法"。而我們今天要講的RSA算法，是一種"非對稱加密算法"，加密和解密使用不同的規則，只要這兩種規則之間存在某種對應關係即可，這樣就避免了直接傳遞密鑰。
這種“非對稱加密算法”的模式，信息交互方式如下：
在這種加密模式下，只要私鑰不公開，通信就是安全的。
我自己今天看了挺久的加密原理，裡面設計到一點數學，具體為什麼就要這樣做，我也不懂更深層次的原因，這裡就講點比較淺的東西。
即使是淺，我們也要先了解一點比較基本的數學定理：
質數（素數）
在大於1的自然數中，除了1和它本身以外不再有其他因數的數稱為質數，也叫素數。
互質關係
如果兩個數除了1以外，沒有其他公因子，我們就稱這兩個數存在互質關係。比如，15和32沒有公因子，所以它們之間有互質關係（不是質數也可以構成互質關係）。
歐拉函數
在數論中，對於正整數N，小於或等於N （[1,N]），且與N互質的正整數（包括1）的個數，記作φ(n)。
任意兩個數p、q，如果p、q存在互質關係，我們有φ(p*q) = (p-1)*(q-1)。這裡就不證明了，舉個例子就好。互質關係2、5，則φ(10)=1*4。結論，在1到10中，和10互質的正整數有4個（1,3,7,9）。
模反元素
如果兩個互質數p,q，那麼一定可以找到整數x，使得 qx-1被p整除，或者說qx被p除的餘數是1。這時，x就叫做q的模反元素。(上面公式，可以變換求xq + yp = 1，求x，這裡y為負數)
例子：互質數3、5，這裡求5的模反元素，即5x + 3y = 1。可以口算一下，這裡x=2，y=-3（或者x=5,y=-8）。可以看出模反元素不唯一，但一旦x確定，y也是確定的。
上面提到的幾個概念，大家反覆推敲一下，RSA算法的密鑰就是從這幾個公式中推斷出來。瞭解了上面的幾個公式，下面我們來講解RSA算法，獲取到加密的公鑰和私鑰。
1.隨機選擇兩個不相等的質數p和q。
這裡我們選擇p = 3 ， q = 11。（實際應用中，這兩個質數越大，就越難破解。）
2.計算p和q的乘積n。
n = p * q = 3 * 11 = 33
3.計算n的歐拉函數φ(n)。
φ(n) = (p - 1) * (q - 1) = 2 * 10 = 20
4.隨機選擇一個整數e，條件是1< e < φ(n)，且e與φ(n) 互質。
我們選擇與20互質的數，e=7（隨機選擇）。
5.計算e對於φ(n)的模反元素d。
這裡要求7對於20的模反元素，可以有多個，我們計算出一個即可。
公式7*d + 20*m = 1，求d。
這裡我們選擇d=3，m=-1。（m這裡沒用）
6.將n和e封裝成公鑰，n和d封裝成私鑰。
這個例子中n=33，e=7，d=3，所以公鑰就是 (33,7)，私鑰就是（33, 3）。
有了公鑰和私鑰，我們就可以進行安全通信，公鑰進行加密，私鑰解密。但是RSA的算法可靠嗎？下面我們來討論一下。
回顧一下上面密鑰的生成步驟，總共出現了六個數字：
在這六個數字中，公鑰（33,7）用到了兩個（n和e），其他四個數都是不公開的。其中最關鍵的數是d，因為n和d組成了私鑰（33,3），假如d洩漏，就等於知道了n、d、e，密鑰就洩露了。
那麼，有沒有可能在知道n和e的情況下，推導出d？
結論：假如n可以被因數分解，那麼d就可以算出，也就意味著私鑰被破解。
對大整數進行因式分解，是一件很困難的事情，目前只有用暴力破解，就是一個一個去試。目前已知，被破解最長RSA密鑰是768個二進制位。就是說，長度超過768位的密鑰，還沒有被人破解（至少沒公開宣佈）。因此可以認為，1024位的RSA密鑰基本安全，2048位的密鑰極其安全。
舉個例子，我們可以對33進行分解成11和3，但下面這個數你沒辦法分解：
它等於下面兩個質數的乘積：
上面獲取到了公鑰和私鑰，還沒用他們加過密。這裡來舉例一下就好：
公式上大家一一對照就好，具體數學原理這裡不做解釋了。大家感興趣可以繼續深入研究其背後的數學，我想著才是真正的數學之美。