非對稱加密 RSA加密算法原理簡述

估計密碼學一段時間内多不會有什麼更新了。

非對稱加密：

非對稱加密是與對稱加密完全相反的概念，對稱加密指的是加密解密使用的是同樣的密鑰Key，如流加密，塊加密，一次性密碼本之類的。而非對稱加密，使用加密Key叫公鑰，解密用的是私鑰。 至于為什麼要這樣做呢？因為這樣可以極大的友善看密鑰的管理。假設一個銀行機構，如果使用對稱加密，一個使用者一個Key，千萬使用者千萬Key，根本無法管理，而使用非對稱加密，一個解密用的私鑰就能解決一切問題。 另外，與對稱密鑰加密相比，公鑰加密無需共享的通用密鑰，減少了很多不必要的麻煩。

RSA：

1977年，由三位麻省理工的人提出，RSA取自他們三人名字的開頭。 1997年，披露了一位英國政府通信總部的數學家先與三人發現，但一經發現直接被列為機密，隻到1994年才被披露。

數學原理：

m=明文 c=密文 N=随機數 e=公鑰 d=密鑰 依舊以兩個大質數相乘得到的大數難以被因式分解為核心。 核心： m^e mod N = c    (明文m用公鑰e加密并和随機數N取餘得到密文c) c^d mod N = m　(密文c用密鑰解密并和随機數N取餘得到明文m) 是以，兩者合并就是：m^(e^d) mod N = m, 也就是：m^(ed) mod N =m

問題是，如何敲定這個解密用d呢？這就需要引入一個概念叫：歐拉函數 φ ( n ) ：小于或等于n的正整數中與n互質的數的數目。 比如φ ( 8 )，1 2 3 4 5 6 7，符合這個條件的是：1 3 5 7，是以φ ( 8 )=4 是以我們可以得知，φ ( n ) 如果n為質數，φ ( n ) = n - 1 而且φ ( n )還符合φ ( a*b ) = φ ( a ) * φ ( b )

此外，還得借助歐拉定理：

是以計算e的模返元素d的方式如下： 1.選取兩個大質數P1，P2，P1*P2=N，并能得到φ ( N ) 2.更具歐拉定理能得知，ed=1（mod φ ( n )） 3.等價于ed-1 = k φ ( n ) 4.于是等價于求解二進制一次方程 ex + φ ( n )y = 1 求得一組解中的x便為d

步驟：

具體還是來看看步驟，舉個栗子，假設Alice和Bob又要互相通信，這次用的是非對稱加密。 1.Alice 随機取大質數P1=53，P2=59，那N=53*59=3127，φ ( n )=3016，取一個e=3，計算出d=2011。 2.隻将n=3127，e=3 作為公鑰傳給Bob。 3.假設Bob需要加密的明文m=89，c = 89^3 mod 3127=1394，于是Bob傳回c=1394 4.Alice使用c^d mod n = 1394^2011 mod 3127，就能得到明文m=89。 回過頭來看看，攻擊者能截取到n=3127，e=3，c=1394，然而他仍然無法不通過d來進行密文解碼。