RSA加密

RSA背景

在1976年以前，傳統(tǒng)的加解密過(guò)程是:

1、A采用某種手段對(duì)數(shù)據(jù)進(jìn)行加密。

2、數(shù)據(jù)傳輸?shù)紹的手中。

3、B逆向的實(shí)施A加密采用的步驟。

4、數(shù)據(jù)被還原。

這就是所謂的對(duì)稱加密。

解密和加密的互為彼此的逆過(guò)程。加密的人必定知道解密的手段。解密的人也必定知道加密的手段。

這種加解密手段的最大特點(diǎn)就是對(duì)稱（易于操作），但這也正是它的最大缺點(diǎn)。因?yàn)榧用芊?，必須將加密?guī)則告知解密方。

這就造成兩個(gè)問(wèn)題:

1、加解密規(guī)則定期就要更新，如何將加解密規(guī)則順利的告訴對(duì)方。

2、如何安全的保存加解密規(guī)則。因?yàn)橹灰幸环綄⒓咏饷芤?guī)則泄露。那么這種加密手段就可以說(shuō)被破解了。

基于此，在1976年由兩位美國(guó)計(jì)算機(jī)科學(xué)家提出了一種全新的思路（"Diffie-Hellman密鑰交換算法"），即采用公鑰-私鑰對(duì)的形式進(jìn)行加解密。

1、解密方生成一對(duì)密鑰：公鑰-私鑰對(duì)。兩者不存在互相推導(dǎo)出彼此的可能。

2、公鑰隨普通網(wǎng)絡(luò)到達(dá)加密方，私鑰則始終保留在解密者手中。

3、加密方使用公鑰將文件轉(zhuǎn)為密文

4、將密文傳輸給解密方。

5、解密方使用私鑰將密文轉(zhuǎn)為明文，完成解密。

由于公鑰和私鑰在邏輯上無(wú)法互相推算出彼此。這樣只要私鑰不被泄露，那么密文就不會(huì)解密?；诖藢?duì)稱加密的第一個(gè)問(wèn)題的風(fēng)險(xiǎn)被解決，第二個(gè)問(wèn)題的風(fēng)險(xiǎn)被縮小了一半。

受這種思路的啟發(fā)，在次年，也就是1977年，由三位數(shù)學(xué)家（Rivest、Shamir 和 Adleman ）聯(lián)合發(fā)表了RSA算法，算法名稱的來(lái)源是三位科學(xué)家的首字母的和。在隨后的幾十年，RSA加密算法，在密碼領(lǐng)域中大放異彩，成為非對(duì)稱加密的代表加密算法。并且隨著密鑰長(zhǎng)度的不斷增加，以當(dāng)下的計(jì)算機(jī)運(yùn)算水平，是不可能在有限的時(shí)間下，暴力破解出密鑰，而攻破該算法的。

RSA加密算法的實(shí)現(xiàn)邏輯

在RSA算法中，需要存在五個(gè)重要的數(shù)字元素：

　　p、q：這是隨機(jī)選取的兩個(gè)不相等質(zhì)數(shù)

　　n：n=p*q，也就是p和q的乘積

　　φ(n)：φ(n) = (p-1)(q-1) ，也就是p-1和q-1的乘積

　　e：隨機(jī)選取一個(gè)和φ(n)互質(zhì)的正整數(shù)。并且保證 e < φ(n)

d：根據(jù)ed ≡ 1 (mod φ(n))，計(jì)算出對(duì)于φ(n)的模反元素d

ed ≡ 1 (mod φ(n)) 的含義是，ed整除φ(n)之后，余數(shù)為1。

也就是ed=k*φ(n)+1

可以看作

ed=φ(n)x+1最終利用輾轉(zhuǎn)相除法（看了一下網(wǎng)上的推導(dǎo)邏輯，覺得純數(shù)學(xué)領(lǐng)域了，純記住意義不大），可以計(jì)算出一組滿足的解(d,x)。

這樣(n,e)是公鑰，(n,d)是私鑰。

由于e，d的推導(dǎo)是依賴的φ(n)的，而φ(n)的值來(lái)自于p、q。p、q盡管是隨機(jī)取得的，但是可以由n因式分解而成。因此n的因式分解速度就成為整個(gè)解密的瓶頸。n的因式分解換言之，類似于判斷n是否是質(zhì)數(shù)，目前除去不斷的暴力嘗試，并沒(méi)有好的辦法。目前已知的最大分解數(shù)目的量級(jí)是10^232,占768bit位，所以一旦n突破了768位，就可以說(shuō)很難破解了。（但是據(jù)說(shuō)量子計(jì)算機(jī)非常適合于計(jì)算因式分解，可惜現(xiàn)在還是雛形）

知道了，公鑰和私鑰的生成后。來(lái)看下公鑰私鑰是如何使用的：

1、將原始信息轉(zhuǎn)化為數(shù)字：無(wú)論是ascii碼值，還是Unicode碼，或者是其他base64轉(zhuǎn)碼等等，生成數(shù)字序列之后。依次循環(huán)按照下文進(jìn)行加密：

公鑰(n,e)、原文m

m^e ≡ c (mod n)

換言之c等于m^e除以n的余數(shù)

也就是計(jì)算出密文c

2、將密文發(fā)送給解密者，解密者依次按照下文進(jìn)行還原

c^d ≡ m (mod n)公式

換言之m等于c^d除以n的余數(shù)

反向求出m即為明文

證明過(guò)程這里就忽略了，有興趣的可以看下阮一峰寫的RSA加密博客。里邊的算式推理比較嚴(yán)謹(jǐn)。

此外有一點(diǎn)需要說(shuō)明的是，在公鑰加密的過(guò)程中，需要m小于n，如果在加密的過(guò)程中，發(fā)現(xiàn)有元素比公鑰的n還要大，則需要將原文進(jìn)行切割成更小的元素，然后再進(jìn)行加密。

其它

另外最近流行面非常廣的病毒“永恒之藍(lán)”，始于歐洲，通過(guò)網(wǎng)絡(luò)傳播了半個(gè)世界的勒索病毒，其核心的思路就是將RSA公鑰傳播到本機(jī)，接著用RSA公鑰加密本地文件。使本地文件不可被正常使用，進(jìn)而勒索機(jī)主。待勒索成功后，只要將私鑰文件再發(fā)送到本機(jī)對(duì)文件進(jìn)行解密即可。思路簡(jiǎn)單，但是非常有效，難以破解，每臺(tái)機(jī)器的私鑰文件也幾乎不會(huì)相同。