什麼是RSA
前面文章我們講了AES算法，AES算法是一種是對稱加密算法，本文我們來介紹一個十分常用的非對稱加密算法RSA。
非對稱加密算法也叫公鑰密碼算法，通過生成的公私鑰來對明文密文進行加密解密。RSA的名字是由它的三個開發者Ron Rivest, Adi Shamir和 Leonard Adleman的首字母而來的。
RSA公司在1983年為RSA算法申請了專利。
RSA的加密
RSA的加密可以用下面的公式來表示：
通過公式我們可以知道RSA的密文是通過明文的E次方再對N進行mod運算得到的。這個加密過程隻用到了階乘和取模運算，可以算是非常簡單明了了。
簡潔的才是最好的，這可能也是RSA算法這麼通用的原因吧。
如果知道了E和N，那麼就可以得到密文，是以我們把E和N的組合稱為公鑰，可以這樣表示 公鑰{E,N}。
如何選擇E和N是一個複雜的數學過程，我們會在後面講到。
RSA的解密
先看一下RSA解密的公式：
通過公式可以看到，明文是通過密文的D次方，再和N取模得到的。這裡的N和加密的N是同一個數字。
D和N的組合表示為私鑰{D,N}。
N,E,D的生成
知道了RSA的加密和解密原理之後，接下來我們就要探讨一下加密和解密過程中的N,E,D是怎麼生成的。
生成過程如下：
1. 生成N
生成N的公式如下：
p和q是兩個很大的質數，太小的話容易被破譯，太大的話會影響計算速度。通常p和q的大小為1024比特。這兩個數是通過僞随機數生成器生成的。僞随機數生成器不能直接生成質數，它是通過不斷的重試得到的。
2. 求L
L是一個中間數，它和p，q一樣，不會出現在RSA的加密和解密過程。
L的計算公式如下：
L是p-1和q-1的最小公倍數
3. 求E
E就是用來加密的公鑰了，E是一個比1大，比L小的數。并且E和L必須互質。隻有E和L互質才能計算出D值。
這裡E也是通過僞随機數生成器來生成的。
找到了E和N，我們的公鑰就生成了。
4. 求D
計算D的公式如下：
破解RSA
如果想破解RSA， 對于密碼破解者來說，他知道了公鑰{E,N}, 知道了密文，根據公式：
有沒有可能直接通過已知的三個變量，求出未知變量明文呢？
這個求解其實是一個離散對數的問題。目前還沒有發現求離散對數的高效的方法。可以說是非常困難的。
那麼有沒有可能通夠暴力破解來得出密鑰中的D呢？
目前RSA算法中p和q的長度一般為1024比特以上，生成的N的長度為2048比特以上，E和D的長度和N差不多，如果要暴力破解2048比特的D是非常困難的。
由公式：
可知，如果破解者知道了L的值，那麼就可以輕易的求出D。而L是通過p和q計算出來的，是以p和q一定要保密，否則跟密碼洩露是一樣的。
因為 N= p * q ， 而p和q都是質數， N又是已知的，那麼我們可不可以通過質因數分解來得到 p和q呢？
目前來說，還沒有有效的對大整數進行質因素分解的高效算法，是以目前來說RSA算法還是很安全的，但是一旦有這樣的算法出現，那麼RSA将會很容易被攻破。
是以官方推薦：1024比特的RSA算法不應該被用于新的用途。2048比特的RSA算法可以用到2030年，4096比特的算法可以用到2031年。
更多教程請參考 flydean的部落格