如此重要的個人數據，怎樣才能保證其在互聯網上的安全傳輸呢？當然要靠各種加密算法。說起加密算法，大家都知道有哈希、對稱加密和非對稱加密了。哈希是壹個散列函數，具有不可逆操作；對稱加密即加密和解密使用同壹個密鑰，而非對稱加密加密和解密自然就是兩個密鑰了。稍微深入壹些的，還要說出非對稱加密算法有DES、3DES、RC4等，非對稱加密算法自然就是RSA了。那麽當我們聊起RSA時，我們又在聊些什麽呢？今天筆者和大家壹起探討壹下，有不足的地方，還望各位朋友多多提意見，***同進步。
RSA簡介：1976年由麻省理工學院三位數學家***同提出的，為了紀念這壹裏程碑式的成就，就用他們三個人的名字首字母作為算法的命名。即 羅納德·李維斯特 （Ron Rivest）、 阿迪·薩莫爾 （Adi Shamir）和 倫納德·阿德曼 （Leonard Adleman）。
公鑰：用於加密，驗簽。
私鑰：解密，加簽。
通常知道了公鑰和私鑰的用途以後，即可滿足基本的聊天需求了。但是我們今天的主要任務是來探究壹下RSA加解密的原理。
說起加密算法的原理部分，肯定與數學知識脫不了關系。
我們先來回憶幾個數學知識：
φn = φ(A*B)=φ(A)*φ(B)=(A-1)*(B-1)。
這個公式主要是用來計算給定壹個任意的正整數n，在小於等於n的正整數中，有多少個與n構成互質的關系。
其中n=A*B，A與B互為質數，但A與B本身並不要求為質數，可以繼續展開，直至都為質數。
在最終分解完成後，即 φ(N) = φ(p1)*φ(p2)*φ(p3)... 之後，p1，p2，p3都是質數。又用到了歐拉函數的另壹個特點，即當p是質數的時候，φp = p - 1。所以有了上面給出的歐拉定理公式。
舉例看壹下：
計算15的歐拉函數，因為15比較小，我們可以直接看壹下，小於15的正整數有 1、2、3、4、5、6、7、8、9、10、11、12、13、14。和15互質的數有1、2、4、7、8、11、13、14壹***四個。
對照我們剛才的歐拉定理： 。
其他感興趣的，大家可以自己驗證。
之所以要在這裏介紹歐拉函數，我們在計算公鑰和私鑰時候，會用到。
如果兩個正整數m 和 n 互質，那麽m 的 φn 次方減1，可以被n整除。
?其中? .
其中當n為質數時，那麽 ?上面看到的公式就變成了
?mod n? ?1.
這個公式也就是著名的 費馬小定理 了。
如果兩個正整數e和x互為質數，那麽壹定存在壹個整數d，不止壹個，使得 e*d - 1 可以被x整除，即 e * d mode x? ?1。則稱 d 是 e 相對於 x的模反元素。
了解了上面所講的歐拉函數、歐拉定理和模反元素後，就要來壹些化學反應了，請看圖：
上面這幅圖的公式變化有沒有沒看明白的，沒看明白的咱們評論區見哈。
最終我們得到了最重要的第5個公式的變形，即紅色箭頭後面的：
?mod n? ?m。
其中有幾個關系，需要搞明白，m 與 n 互為質數，φn = x，d 是e相對於x的模反元素。
有沒有看到壹些加解密的雛形。
從 m 到 m。 這中間涵蓋了從加密到解密的整個過程，但是缺少了我們想要的密文整個過程。
OK，下面引入本文的第四個數學公式：
我們來看壹下整個交換流程：
1、客戶端有壹個數字13，服務端有壹個數字15;
2、客戶端通過計算 3的13次方 對 17 取余，得到數字12; 將12發送給服務端；同時服務端通過計算3的15次方，對17取余，得到數字6，將6發送給客戶端。至此，整個交換過程完成。
3、服務端收到數字12以後，繼續計算，12的15次方 對 17取余，得到 數字10。
4、客戶端收到數字 6以後，繼續計算，6的13次方 對 17 取余，得到數字 10。
有沒有發現雙方，最終得到了相同的內容10。但是這個數字10從來沒有在網絡過程中出現過。
好，講到這裏，可能有些人已經恍然大悟，這就是加密過程了，但是也有人會產生疑問，為什麽要取數字3 和 17 呢，這裏還牽涉到另壹個數學知識，原根的問題。即3是17的原根。看圖
有沒有發現規律，3的1~16次方，對17取余，得到的整數是從1~16。這時我們稱3為17的原根。也就是說上面的計算過程中有壹組原根的關系。這是最早的迪菲赫爾曼秘鑰交換算法。
解決了為什麽取3和17的問題後，下面繼續來看最終的RSA是如何產生的：
還記得我們上面提到的歐拉定理嗎，其中 m 與 n 互為質數，n為質數，d 是 e 相對於 φn的模反元素。
當迪菲赫爾曼密鑰交換算法碰上歐拉定理會產生什麽呢？
我們得到下面的推論：
好，到這裏我們是不是已經看到了整個的加密和解密過程了。
其中 m 是明文；c 是密文； n 和 e 為公鑰；d 和 n 為私鑰 。
其中幾組數字的關系壹定要明確：
1、d是e 相對於 φn 的模反元素，φn = n-1，即 e * d mod n = 1.
2、m 小於 n，上面在講迪菲赫爾曼密鑰交換算法時，提到原根的問題，在RSA加密算法中，對m和n並沒有原根條件的約束。只要滿足m與n互為質數，n為質數，且m < n就可以了。
OK，上面就是RSA加密算法的原理了，經過上面幾個數學公式的狂轟亂炸，是不是有點迷亂了，給大家壹些時間理壹下，後面會和大家壹起來驗證RSA算法以及RSA為什麽安全。