前面有人讓我講解一下RSA算法，今天我就用我所學(xué)的知識(shí)講解一下，首先我們先了解一下RSA

RSA是一種非對(duì)稱加密算法，1977年由羅納德·李維斯特(Ron Rivest)、阿迪·薩莫爾(Adi Shamir)和倫納德·阿德曼(Leonard Adleman)一起提出的，因此以三人姓氏的首字母命名了該非對(duì)稱加密算法，RSA算法。

[[359956]]

在了解非對(duì)稱性加密的時(shí)候我們需要了解什么叫對(duì)稱性加密。我們就那徐克導(dǎo)演拍的電影《智取威虎山》，其中的一段對(duì)話

• 土匪：天王蓋地虎!
• 楊子榮：寶塔鎮(zhèn)河妖!
• 土匪：野雞悶頭鉆，哪能上天王山!
• 楊子榮：地上有的是米，喂呀，有根底!
• 土匪：拜見過阿媽啦?
• 楊子榮：他房上沒瓦，非否非，否非否!

通過他們的對(duì)話我們知道 土匪在試探楊子榮的身份。當(dāng)土匪說，天王蓋地虎，我就必須說 寶塔鎮(zhèn)河妖!也就是雙方都知道 這段話是什么意思。翻譯成程序員的話就是 雙方都有加密的密鑰。因此對(duì)稱加密也可以說是秘密交易者的暗號(hào)。

不過對(duì)稱加密有一個(gè)很大的問題，密鑰容易泄露。土匪的暗號(hào)被楊子榮知道了這個(gè)就很容易取得了他們的信任。

RSA加密

我們需要先預(yù)習(xí)一下還給數(shù)學(xué)老師的知識(shí)

歐拉函數(shù)

在數(shù)論中，存在正整數(shù) n，小于n并且與n互質(zhì)的正整數(shù)的數(shù)目稱為n的歐拉函數(shù)記著φ(n)。例如：

• φ(7) 7對(duì)應(yīng)的比7小的與7互質(zhì)的數(shù)有1、2、3、4、5、6共6個(gè)，因此φ(7)=6;
• φ(8) 8對(duì)應(yīng)的比8小的與8互質(zhì)的數(shù)有1，3，5，7共4個(gè)，因此φ(8)=4;
• φ(9) 9對(duì)應(yīng)的比9小的與9互質(zhì)的數(shù)有1，2，4，5，6，7，8共7個(gè)，，因此φ(9)=7。

通式(P是數(shù)N的質(zhì)因數(shù))

• φ(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互質(zhì)：φ(n * m)=φ(n)* φ(m)，如果n為質(zhì)數(shù)那么φ(n)=n-1。

分解質(zhì)因數(shù)求值：φ(12)=φ(4 * 3)=φ( 2^2 * 3^1 )=( 2^2 - 2^1 ) * (3^1 - 3^0)=4。

歐拉定理

如果兩個(gè)正整數(shù)m和n互質(zhì)，那么m的φ(n) 次方對(duì)n取余衡等于1。m^φ(n)%n≡1。

費(fèi)馬小定理

存在一個(gè)質(zhì)數(shù)p，而整數(shù)a不是p的倍數(shù)，則存在a^(p-1)%p≡1。費(fèi)馬小定理是歐拉定理的特殊情況。因?yàn)?phi;(p)=p-1(任何數(shù)都與質(zhì)數(shù)互質(zhì))。

模反元素

如果兩個(gè)正整數(shù)e和x互質(zhì)，那么一定存在一個(gè)整數(shù)d，使得ed-1能夠被x整除，則稱d是e對(duì)x的模反元素。e * d % x≡1，那么e * d ≡ k*x+1。

由以上定理得出以下幾個(gè)公式：

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就是我們需要的一個(gè)非對(duì)稱加密的公式。m為明文，e和d分別對(duì)應(yīng)的是公鑰私鑰。迪菲卡爾曼秘鑰交換對(duì)公式拆分：

• m^e%n=c 加密
• c^d%n=m 解密

其中c為通過e加密后的密文，然后通過d可以解出明文m。因此：

• 公鑰： e、n
• 秘鑰：d、n
• 明文：m
• 密文：c

RSA加密過程

1. 取兩個(gè)質(zhì)數(shù)p1、p2;
2. 確定n值，n=p1 * p2，n值一般會(huì)很大長(zhǎng)度一般為1024個(gè)二進(jìn)制位;
3. 確定φ(n)，φ(n)=(p1-1) * (p2-1);
4. 確定e值，1
5. 確定d值，e*d%φ(n)=1;
6. 加密 c=m^e%n;
7. 解密m=c^d%n。

實(shí)際驗(yàn)證：

1. p1=3， p2=7;
2. n=p1 * p2=3 * 7=21;
3. φ(n)=(p1-1) * (p2-1)=2*6=12;
4. 1
5. e * d % φ(n)=5 * d % 12=1，得d=17;
6. 設(shè)置明文m=3，則c = m^e % n = 3^5 % 21=12;
7. 解密密文m=c^d % n=12^17 % 21=3。

通過上面的講解我們知道在RSA 加密中用到的幾6個(gè)參數(shù)

p1  
p2  
n  
φ(n)  
e  
d 

這六個(gè)數(shù)字之中，公鑰用到了兩個(gè)(n和e)，其余四個(gè)數(shù)字都是不公開的。其中最關(guān)鍵的是d，因?yàn)閚和d組成了私鑰，一旦d泄漏，就等于私鑰泄漏。

那么，有無(wú)可能在已知n和e的情況下，推導(dǎo)出d?

1. e*d%φ(n)=1 (只有知道e和φ(n)，才能算出d。)
2. φ(n)=(p1-1) * (p2-1) (只有知道p1和p2，才能算出φ(n)。)
3. n=p1*p2 (只有將n因數(shù)分解，才能算出p和q。)

結(jié)論：如果n可以被因數(shù)分解，d就可以算出，也就意味著私鑰被破解。

可是，大整數(shù)的因數(shù)分解，是一件非常困難的事情。目前，除了暴力破解，還沒有發(fā)現(xiàn)別的有效方法。維基百科這樣寫道：

"對(duì)極大整數(shù)做因數(shù)分解的難度決定了RSA算法的可靠性。換言之，對(duì)一極大整數(shù)做因數(shù)分解愈困難，RSA算法愈可靠。

假如有人找到一種快速因數(shù)分解的算法，那么RSA的可靠性就會(huì)極度下降。但找到這樣的算法的可能性是非常小的。今天只有短的RSA密鑰才可能被暴力破解。到2008年為止，世界上還沒有任何可靠的攻擊RSA算法的方式。

只要密鑰長(zhǎng)度足夠長(zhǎng)，用RSA加密的信息實(shí)際上是不能被解破的。"

或許你看到這里還不相信，我寫個(gè)程序挨著試 不就可以破解出來嗎?例如 21 你或許會(huì)很快的分解成 3×7 但是這個(gè)數(shù)再大一點(diǎn) 比如 這個(gè)質(zhì)數(shù) 2^57,885,161-1 它有超過1千7百萬(wàn)個(gè)數(shù)位 如果讓傳統(tǒng)計(jì)算機(jī)來驗(yàn)證他是不是質(zhì)數(shù) 估計(jì)可以跑到天荒地老。