前面有人讓我講解一下RSA算法，今天我就用我所學的知識講解一下，首先我們先了解一下RSA
RSA是一種非對稱加密算法，1977年由羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）一起提出的，因此以三人姓氏的首字母命名了該非對稱加密算法，RSA算法。
在了解非對稱性加密的時候我們需要了解什麼叫對稱性加密。我們就那徐克導演拍的電影《智取威虎山》，其中的一段對話
土匪：天王蓋地虎！
楊子榮：寶塔鎮河妖！
土匪：野雞悶頭鑽，哪能上天王山！
楊子榮：地上有的是米，餵呀，有根底！
土匪：拜見過阿媽啦？
楊子榮：他房上沒瓦，非否非，否非否！
通過他們的對話我們知道 土匪在試探楊子榮的身份。當土匪說，天王蓋地虎，我就必須說 寶塔鎮河妖！也就是雙方都知道 這段話是什麼意思。翻譯成程式設計師的話就是 雙方都有加密的密鑰。因此對稱加密也可以說是秘密交易者的暗號。
不過對稱加密有一個很大的問題，密鑰容易洩露。土匪的暗號被楊子榮知道了這個就很容易取得了他們的信任。
RSA加密
我們需要先預習一下還給數學老師的知識
歐拉函數
在數論中，存在正整數 n，小於n並且與n互質的正整數的數目稱為n的歐拉函數記著φ(n)。例如：
φ(7) 7對應的比7小的與7互質的數有1、2、3、4、5、6共6個，因此φ(7)=6；
φ(8) 8對應的比8小的與8互質的數有1，3，5，7共4個，因此φ(8)=4；
φ(9) 9對應的比9小的與9互質的數有1，2，4，5，6，7，8共7個，，因此φ(9)=7。
通式（P是數N的質因數）
φ（10）=10×（1－1/2）×（1－1/5）=4；
φ（30）=30×（1－1/2）×（1－1/3）×（1－1/5）=8；
φ（49）=49×（1－1/7）=42。若m n互質：φ(n * m)=φ(n)* φ(m)，如果n為質數那麼φ(n)=n-1。
分解質因數求值：φ(12)=φ(4 * 3)=φ( 2^2 * 3^1 )=( 2^2 - 2^1 ) * (3^1 - 3^0)=4。
歐拉定理
如果兩個正整數m和n互質，那麼m的φ(n) 次方對n取餘衡等於1。m^φ(n)%n≡1。
費馬小定理
存在一個質數p，而整數a不是p的倍數，則存在a^(p-1)%p≡1。費馬小定理是歐拉定理的特殊情況。因為φ(p)=p-1（任何數都與質數互質）。
模反元素
如果兩個正整數e和x互質，那麼一定存在一個整數d，使得ed-1能夠被x整除，則稱d是e對x的模反元素。e * d % x≡1，那麼e * d ≡ k*x+1。
由以上定理得出以下幾個公式：
1、m^φ(n)%n≡1
2、m^(k * φ(n))%n≡1 兩端同乘以m
3、m^(k * φ(n)+1)%n≡m
4、e * d≡k * x+1
5、m^e * d%n≡m 替換第3步k * φ(n)+1
而m^e*d%n≡m就是我們需要的一個非對稱加密的公式。m為明文，e和d分別對應的是公鑰私鑰。迪菲卡爾曼秘鑰交換對公式拆分：
m^e%n=c 加密
c^d%n=m 解密
其中c為通過e加密後的密文，然後通過d可以解出明文m。因此：
公鑰： e、n
秘鑰：d、n
明文：m
密文：c
RSA加密過程
1、取兩個質數p1、p2；
2、確定n值，n=p1 * p2，n值一般會很大長度一般為1024個二進位位；
3、確定φ(n)，φ(n)=(p1-1) * (p2-1)；
4、確定e值，1<e<φ(n)，e為整數並且與φ(n)互質；
5、確定d值，e*d%φ(n)=1；
6、加密 c=m^e%n；
7、解密m=c^d%n。
實際驗證：
1、p1=3， p2=7；
2、n=p1 * p2=3 * 7=21；
3、φ(n)=(p1-1) * (p2-1)=2*6=12；
4、1<e<12，e=5（e與12互質則取值{1,5,7,11}，φ(12)=4個互質數，滿足條件的有4個）；
5、e * d % φ(n)=5 * d % 12=1，得d=17；
6、設置明文m=3，則c = m^e % n = 3^5 % 21=12；
7、解密密文m=c^d % n=12^17 % 21=3。
通過上面的講解我們知道在RSA 加密中用到的幾6個參數
p1
p2
n
φ(n)
e
d
這六個數字之中，公鑰用到了兩個（n和e），其餘四個數字都是不公開的。其中最關鍵的是d，因為n和d組成了私鑰，一旦d洩漏，就等於私鑰洩漏。
那麼，有無可能在已知n和e的情況下，推導出d？
1) e*d%φ(n)=1 (只有知道e和φ(n)，才能算出d。)
2) φ(n)=(p1-1) * (p2-1) （只有知道p1和p2，才能算出φ(n)。）
3) n=p1*p2 (只有將n因數分解，才能算出p和q。)
結論：如果n可以被因數分解，d就可以算出，也就意味著私鑰被破解。
可是，大整數的因數分解，是一件非常困難的事情。目前，除了暴力破解，還沒有發現別的有效方法。維基百科這樣寫道：
"對極大整數做因數分解的難度決定了RSA算法的可靠性。換言之，對一極大整數做因數分解愈困難，RSA算法愈可靠。
假如有人找到一種快速因數分解的算法，那麼RSA的可靠性就會極度下降。但找到這樣的算法的可能性是非常小的。今天只有短的RSA密鑰才可能被暴力破解。到2008年為止，世界上還沒有任何可靠的攻擊RSA算法的方式。
只要密鑰長度足夠長，用RSA加密的信息實際上是不能被解破的。"
或許你看到這裡還不相信，我寫個程序挨著試 不就可以破解出來嗎？例如 21 你或許會很快的分解成 3×7 但是這個數再大一點 比如 這個質數 2^57,885,161-1 它有超過1千7百萬個數位 如果讓傳統計算機來驗證他是不是質數 估計可以跑到天荒地老。
本文參考了 百度百科和維基百科
來源：
https://www.toutiao.com/i6909656008197603843/
「IT大咖說」歡迎廣大技術人員投稿，投稿郵箱：aliang@itdks.com
IT大咖說 | 關於版權
由「IT大咖說（ID：itdakashuo）」原創的文章，轉載時請註明作者、出處及微信公眾號。投稿、約稿、轉載請加微信：ITDKS10（備註：投稿），茉莉小姐姐會及時與您聯繫！
感謝您對IT大咖說的熱心支持！