概述
RSA算法是現(xiàn)今使用最廣泛的公鑰密碼算法，也是號稱地球上最安全的加密算法。在了解RSA算法之前，先熟悉下幾個術(shù)語根據(jù)密鑰的使用方法，可以將密碼分為對稱密碼和公鑰密碼
對稱加密：加密和解密使用同一種密鑰的方式
非對稱加密：加密和解密使用不同的密碼的方式，因此公鑰密碼通常也稱為非對稱密碼。
好多人都知道RSA加密的數(shù)學公式，但是不知道其的內(nèi)部運作，那么我們以下就詳細分析一波！
離散對數(shù)問題
圖1，mod就是取余的意思，上面公式的意思是3的多少次方除以17余數(shù)為12。由圖2可知道3的13次方的時候就滿足圖1的公式。由圖2的可知，公式后面的余數(shù)都是不一樣的，而且是1-16。當我們好奇試試3^17%17時候，結(jié)果就是3，好明顯等于了3^1%17的結(jié)果，那么我們稱3為17的原根。
歐拉函數(shù)
思考：任意給定正整數(shù)n，請問在小于等于n的正整數(shù)之中，有多少個與n構(gòu)成互質(zhì)關系？
計算這個值的方式叫做歐拉函數(shù)，使用：Φ(n)表示
計算8的歐拉函數(shù)，和8互質(zhì)的 1、2、3、4、5、6、7、8? ? 所以 φ(8) = 4
計算7的歐拉函數(shù)，和7互質(zhì)的?1、2、3、4、5、6、7 ?所以?φ(7) = 6
計算56的歐拉函數(shù)：φ(56) =?φ(8)*? φ(7) = 4 * 6 = 24
關于互質(zhì)關系
如果兩個正整數(shù)，除了1以外，沒有其他公因數(shù)，我們就稱這兩個數(shù)是互質(zhì)關系（coprime）。
歐拉函數(shù)特點
一、當n是質(zhì)數(shù)的時候，φ(n)=n-1。
二、如果n可以分解成兩個互質(zhì)的整數(shù)之積，如n=A*B則：?φ(A*B)=φ(A)*φ(B)
根據(jù)以上兩點得到：如果N是兩個質(zhì)數(shù)P1 和 P2的乘積則：φ(N)=φ(P1)* φ(P2)=(P1-1)*(P2-1)
歐拉定理
如果兩個正整數(shù)m和n互質(zhì)，那么m的φ(n)次方減去1，可以被n整除。如圖3所示：
我們可以設置互質(zhì)的數(shù)如m=5和n=3，那么φ(3) = 3-1=2，5^2%3=1。所以上面的公式是成立的。（有興趣的可以試多一點數(shù)字，注意是互質(zhì)的兩個數(shù)）
費馬小定理
歐拉定理的特殊情況：如果兩個正整數(shù)m和n互質(zhì)，而且n為質(zhì)數(shù)！那么φ(n)結(jié)果就是n-1。如圖4所示：
公式轉(zhuǎn)換
注意：滿足第3步的時候，m必須要小于n。
模反元素
如果兩個正整數(shù)e和x互質(zhì)，那么一定可以找到整數(shù)d，使得 ed-1 被x整除。那么d就是e對于x的“模反元素”。如圖6所示：
迪菲赫爾曼密鑰交換
公鑰： n和e
私鑰： n和d
明文:???m
密文:??? c
說明：
1、n會非常大，長度一般為1024個二進制位。（目前人類已經(jīng)分解的最大整數(shù)，232個十進制位，768個二進制位）
2、由于需要求出φ(n)，所以根據(jù)歐函數(shù)特點，最簡單的方式n ，由兩個質(zhì)數(shù)相乘得到:
質(zhì)數(shù)：p1、p2? Φ(n) = (p1 -1) * (p2 - 1)
3、最終由φ(n)得到e 和 d 。
總共生成6個數(shù)字：p1、p2、n、φ(n)、e、d
關于RSA的安全：
除了公鑰用到了n和e其余的4個數(shù)字是不公開的。目前破解RSA得到d的方式如下：
1、要想求出私鑰 d? 。由于e*d = φ(n)*k + 1。要知道e和φ(n);
2、e是知道的，但是要得到 φ(n)，必須知道p1和 p2。
3、由于 n=p1*p2。只有將n因數(shù)分解才能算出。
