概述
RSA算法是現(xiàn)今使用最廣泛的公鑰密碼算法肛宋，也是號稱地球上最安全的加密算法绣夺。在了解RSA算法之前方援，先熟悉下幾個術(shù)語根據(jù)密鑰的使用方法，可以將密碼分為對稱密碼和公鑰密碼
對稱加密：加密和解密使用同一種密鑰的方式
非對稱加密：加密和解密使用不同的密碼的方式式镐，因此公鑰密碼通常也稱為非對稱密碼反镇。
好多人都知道RSA加密的數(shù)學(xué)公式，但是不知道其的內(nèi)部運(yùn)作娘汞，那么我們以下就詳細(xì)分析一波！
離散對數(shù)問題
圖1禽作，mod就是取余的意思，上面公式的意思是3的多少次方除以17余數(shù)為12。由圖2可知道3的13次方的時候就滿足圖1的公式磁浇。由圖2的可知缔赠，公式后面的余數(shù)都是不一樣的嗤堰，而且是1-16。當(dāng)我們好奇試試3^17%17時候，結(jié)果就是3，好明顯等于了3^1%17的結(jié)果，那么我們稱3為17的原根。
歐拉函數(shù)
思考：任意給定正整數(shù)n，請問在小于等于n的正整數(shù)之中，有多少個與n構(gòu)成互質(zhì)關(guān)系？
計(jì)算這個值的方式叫做歐拉函數(shù)，使用：Φ(n)表示
計(jì)算8的歐拉函數(shù)，和8互質(zhì)的 1三妈、2、3对室、4模燥、5、6掩宜、7蔫骂、8? ? 所以 φ(8) = 4
計(jì)算7的歐拉函數(shù)，和7互質(zhì)的?1牺汤、2纠吴、3、4慧瘤、5戴已、6、7 ?所以?φ(7) = 6
計(jì)算56的歐拉函數(shù)：φ(56) =?φ(8)*? φ(7) = 4 * 6 = 24
關(guān)于互質(zhì)關(guān)系
如果兩個正整數(shù)锅减，除了1以外糖儡，沒有其他公因數(shù)，我們就稱這兩個數(shù)是互質(zhì)關(guān)系（coprime）怔匣。
歐拉函數(shù)特點(diǎn)
一握联、當(dāng)n是質(zhì)數(shù)的時候，φ(n)=n-1每瞒。
二金闽、如果n可以分解成兩個互質(zhì)的整數(shù)之積，如n=A*B則：?φ(A*B)=φ(A)*φ(B)
根據(jù)以上兩點(diǎn)得到：如果N是兩個質(zhì)數(shù)P1 和 P2的乘積則：φ(N)=φ(P1)* φ(P2)=(P1-1)*(P2-1)
歐拉定理
如果兩個正整數(shù)m和n互質(zhì)剿骨，那么m的φ(n)次方減去1代芜，可以被n整除。如圖3所示：
我們可以設(shè)置互質(zhì)的數(shù)如m=5和n=3浓利，那么φ(3) = 3-1=2挤庇，5^2%3=1。所以上面的公式是成立的贷掖。（有興趣的可以試多一點(diǎn)數(shù)字嫡秕，注意是互質(zhì)的兩個數(shù)）
費(fèi)馬小定理
歐拉定理的特殊情況：如果兩個正整數(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ìn)制位糕殉。（目前人類已經(jīng)分解的最大整數(shù)，232個十進(jìn)制位殖告，768個二進(jìn)制位）
2阿蝶、由于需要求出φ(n)，所以根據(jù)歐函數(shù)特點(diǎn)黄绩，最簡單的方式n 羡洁，由兩個質(zhì)數(shù)相乘得到:
質(zhì)數(shù)：p1、p2? Φ(n) = (p1 -1) * (p2 - 1)
3爽丹、最終由φ(n)得到e 和 d 筑煮。
總共生成6個數(shù)字：p1、p2粤蝎、n真仲、φ(n)、e初澎、d
關(guān)于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ù)分解才能算出。
