非對稱加密（2）非對稱加密算法非對稱加密（2）非對稱加密算法

基本流程很簡單，那麼公鑰加密，私鑰解密的算法原理到底是什麼呢？本節簡要闡述RSA算法、DSA算法、ECC算法、Diffie-Hellman算法的基本原理，其中涉及很多數論、離散數學以及解析幾何方面的數學知識，感興趣的讀者可以借此加強相關理論基礎。

RSA算法是目前最著名、應用最廣泛的公鑰系統，1978年由美國麻省理工學院的Ron Rivest、 Adi Shamir 和Leonard Adleman在論文《獲得數字簽名和公開鑰密碼系統的方法》中提出的。這是一個基于數論的非對稱（公開鑰）密碼體制，采用分組加密方式。其名稱來自于三個發明者的姓名首字母。它的安全性是基于大整數素因子分解的困難性，而大整數因子分解問題是數學上的著名難題，至今沒有有效的方法予以解決，是以可以確定RSA算法的安全性。RSA系統是公鑰系統的最具有典型意義的方法，大多數使用公鑰密碼進行加密和數字簽名的産品和标準使用的都是RSA算法。

RSA算法是第一個既能用于資料加密也能用于數字簽名的算法，是以它為公用網絡上資訊的加密和鑒别提供了一種基本的方法。它通常是先生成一對RSA 密鑰，一個是保密密鑰，由使用者儲存；另一個為公開密鑰，可對外公開，甚至可在網絡伺服器中注冊，人們用公鑰加密檔案發送給個人，個人就可以用私鑰解密接收。為提高保密強度，RSA密鑰一般為1024或者2048位。

RSA算法的工作原理如下：

步驟 1  任意選取兩個不同的大質數p和q，計算乘積r=p*q。

步驟 2   任意選取一個大整數e，e與（p-1）*（q-1）互質，整數e用做加密密鑰。注意：e的選取是很容易的，所有大于p和q的質數都可用。

步驟 3  确定解密密鑰d： d * e = 1 mod（p - 1）*（q - 1）根據e、p和q可以容易地計算出d。

步驟 4  公開整數r和e，但是不公開d。

步驟 5  将明文P（P是一個小于r的整數）加密為密文C，計算方法為C = P^e  mod r 。

步驟 6  将密文C解密為明文P，計算方法為： P = C^d modulo r 。

然而隻根據r和e（不是p和q）要計算出d是不可能的。是以，任何人都可對明文進行加密，但隻有授權使用者（知道d）才可對密文解密。

如果你對RSA算法的數學證明感興趣的話，可以看擴充閱讀。

擴充閱讀   RSA算法的數學證明

定理  若 p, q 是相異質數, rm == 1 mod （p-1）（q-1）； a 是任意一個正整數，b == a^m mod pq, c == b^r mod pq, 則 c == a mod pq 。

費馬小定理    m 是任一質數, n 是任一整數, 則 n^m = = n mod m 。（或者如果 n 和 m 互質, 則 n^（m-1） = = 1 mod m） 。

證明

因為 rm = = 1 mod （p-1）（q-1）, 是以 rm = k（p-1）（q-1） + 1, 其中 k 是整數 。

因為在 modulo 中是 preserve 乘法的 

x = = y mod z  and  u = = v mod z  =>  xu = = yv mod z

 是以 

c = = b^r = = （a^m）^r = = a^（rm） = = a^（k（p-1）（q-1）+1） mod pq 

1. 如果 a 不是 p 的倍數, 也不是 q 的倍數時,    則

 a^（p-1） = = 1 mod p （費馬小定理）  =>  a^（k（p-1）（q-1）） = = 1 mod p 

       a^（q-1） = = 1 mod q （費馬小定理）  =>  a^（k（p-1）（q-1）） = = 1 mod q 

   是以 p, q 均能整除

 a^（k（p-1）（q-1）） - 1  =>  pq | a^（k（p-1）（q-1）） - 1 

   即 

a^（k（p-1）（q-1）） == 1 mod pq    =>  c = = a^（k（p-1）（q-1）+1） = = a mod pq 

2. 如果 a 是 p 的倍數, 但不是 q 的倍數時,    則 

a^（q-1） == 1 mod q （費馬小定理） 

   =>  a^（k（p-1）（q-1）） = = 1 mod q 

   =>  c = = a^（k（p-1）（q-1）+1） = = a mod q 

   =>  q | c - a 

   因 p | a 

   =>  c = = a^（k（p-1）（q-1）+1） = = 0 mod p 

   =>  p | c - a 

   是以

 pq | c - a  =>  c = = a mod pq 

3. 如果 a 是 q 的倍數, 但不是 p 的倍數時, 證明同上 。

4. 如果 a 同時是 p 和 q 的倍數時, 則

 pq | a 

   =>  c = = a^（k（p-1）（q-1）+1） == 0 mod pq 

   =>  pq | c - a =>  c = = a mod pq 

在做編碼解碼時, 限制 0 <= a < n, 0 <= c < n, 這就是說 a = =c, 是以這個過程确實能做到編碼解碼的功能。

為了說明該算法的工作過程，下面給出一個簡單例子。顯然，這裡隻能取很小的數字，但是如上所述，為了保證安全，在實際應用上所用的數字要大得多。

例 選取p=3, q=5，則r=15，（p-1）*（q-1）=8。選取e=11（大于p和q的質數），通過d * 11 = 1 modulo 8，計算出d =3。

假定明文為整數13。則密文C為 ：

 C = P^e mod r

 = 1311 mod 15

 = 1,792,160,394,037 mod 15

 = 7

複原明文P為：

 P = C^d mod r

= 73 mod 15

= 343 mod 15

= 13

因為e和d互逆，公開密鑰加密方法也允許采用這樣的方式對加密資訊進行"簽名"，以便接收方能确定簽名不是僞造的。

RSA算法解決了大量網絡使用者密鑰管理的難題，這是公鑰密碼系統相對于對稱密碼系統最突出的優點。但是它同時也存在一定的缺點：

1）産生密鑰很麻煩，受到素數産生技術的限制，因而難以做到一次一密。

2）安全性。RSA的安全性依賴于大數的因子分解，但并沒有從理論上證明破譯RSA的難度與大數分解難度等價。目前，人們已能分解140多個十進制位的大素數，這就要求使用更長的密鑰，速度更慢；另外，目前人們正在積極尋找攻擊RSA的方法，如選擇密文攻擊，一般攻擊者是将某資訊僞裝（Blind），讓擁有私鑰的實體簽署。然後，經過計算就可得到它所想要的資訊。實際上，攻擊利用的都是同一個弱點，即存在這樣一個事實：乘幂保留了輸入的乘法結構： （XM ）d = Xd *Md mod n。前面已經提到，這個固有的問題來自于公鑰密碼系統的最有用的特征：每個人都能使用公鑰。但從算法上無法解決這一問題，主要措施有兩條：一條是采用好的公鑰協定，保證工作過程中實體不對其他實體任意産生的資訊解密，不對自己一無所知的資訊簽名；另一條是決不對陌生人送來的随機文檔簽名，簽名時首先使用One-Way Hash Function對文檔作HASH處理，或同時使用不同的簽名算法。除了利用公共模數，人們還嘗試一些利用解密指數或φ（n）等攻擊。

3）速度慢。由于RSA 的分組長度太大，使運算代價很高，尤其是速度較慢，較對稱密碼算法慢幾個數量級；且随着大數分解技術的發展，這個長度還在增加，不利于資料格式的标準化。目前，SET（Secure Electronic Transaction）協定要求CA采用2048比特的密鑰，其他實體使用1024比特的密鑰。為了速度問題,目前人們廣泛采取單、公鑰密碼結合使用的方法,優缺點互補:單鑰密碼加密速度快,人們用它來加密較長的檔案,然後用RSA給檔案密鑰加密，極好地解決了單鑰密碼的密鑰分發問題。

DSA（Digital Signature Algorithm，數字簽名算法）是Schnorr和ElGamal簽名算法的變種，被美國NIST作為DSS（DigitalSignature Standard，數字信号标準）。DSA算法是基于整數有限域離散對數難題的，其安全性與RSA相似。DSA的一個重要特點是兩個素數公開，這樣，當使用别人的p和q時，即使不知道私鑰，也能确認它們是否是随機産生的，還是作了手腳。RSA算法卻做不到。

（1）  DSA算法參數

p：L bits長的素數。L是64的倍數，範圍是512到1024；

q：p - 1的160bits的素因子；

g：g = h^（（p-1）/q） mod p，h滿足h < p - 1, h^（（p-1）/q） mod p > 1；

x：x < q，x為私鑰；

y：y = g^x mod p ，（ p, q, g, y ）為公鑰；

H（ x ）：One-Way Hash函數。DSS中選用SHA（ Secure Hash Algorithm ）。

其中，p、 q、g可由一組使用者共享，但在實際應用中，使用公共模數可能會帶來一定的威脅。

（2）  簽名及驗證協定

1)        p産生随機數k，k < q。

2)        p計算：

r = （ g^k mod p ） mod q

s = （ k^（-1）（H（m） + xr）） mod q

簽名結果是（ m, r, s ）。

3)        驗證時計算：

w = s^（-1）mod q

u1 = （ H（ m ） * w ） mod q

u2 = （ r * w ） mod q

v = （（ g^u1 * y^u2 ） mod p ） mod q

若v = r，則認為簽名有效。

（3）  安全性

DSA主要依賴于整數有限域離散對數難題。素數 P 必須足夠大，且p-1至少包含一個大素數因子以抵抗Pohlig & Hellman算法的攻擊。M一般都應采用資訊的HASH值（官方推薦為SHA算法）。DSA的安全性主要依賴于p和g，若選取不當則簽名容易僞造，應保證g對于p-1的大素數因子不可約。個人認為：DSA的安全性要次于ECC， 與RSA不相上下。但是，在DSA算法的驗證過程中， R和S 是以明文形式出現的，這點很容易被惡意攻擊者利用。

DSA算法在破解時關鍵的參數就是X，根據 Y = G^X mod P ，隻要知道 P，G，Y，Q 且能分解出 X ，就可以僞造R、S，進而寫出KeyGen了。

ECC（Elliptic Curve Cryptosystem，橢圓曲線密碼體制）算法中，橢圓曲線指的是由韋爾斯特拉斯（Weierstrass）方程所确定的平面曲線。如下：

 y2+a1xy+a3y＝x3+a2x2+a4x+a6(1)                                                    

若F是一個域（ai ∈F,i=1,2,…,6），且滿足式（1）的數偶（x,y）稱為F域上的橢圓曲線E的點。F域可以是有理數域，還可以是有限域GF（Pr）。橢圓曲線通常用E表示。除了曲線E包含的點，還有一個無窮遠點O。

在ECC中，利用了定義在有限域上的橢圓曲線。其方程如下：

y2=x3+ax+b(mod p)（4a3+27b2(mod p)≠0 其中，x,y,a,b∈Fp）(2)                  

這裡p是素數，a和b為兩個小于p的非負整數。滿足式（2）的點（x,y）和一個無窮點O就組成了橢圓曲線E。

橢圓曲線離散對數問題ECDLP定義如下：

給定素數p和橢圓曲線E，對 Q=kP,在已知P,Q的情況下求出小于p的正整數k。

可以證明，已知k和P計算Q比較容易，而由Q和P計算k則比較困難，至今沒有有效的方法來解決這個問題，這就是ECC原理之所在。

ECC與RSA相比，有以下的優點：

q  安全性能更高。如160位ECC與1024位RSA、DSA有相同的安全強度。

q  計算量小，處理速度快。在私鑰的處理速度上（解密和簽名），ECC遠 比RSA、DSA快得多。

q  存儲空間占用小。ECC的密鑰尺寸和系統參數與RSA、DSA相比要小得多， 是以占用的存儲空間小得多。

q  帶寬要求低。

由于該算法本身限于密鑰交換的用途，許多商用産品用做密鑰交換技術，是以該算法通常稱為Diffie-Hellman密鑰交換算法。這種密鑰交換技術的目的在于使得兩個使用者安全地交換一個秘密密鑰以便用于以後的封包加密。

Diffie-Hellman密鑰交換算法的有效性依賴于計算離散對數的難度。離散對數的定義如下：

首先定義一個素數p的原根，為其各次幂産生從1 到p-1的所有整數根，也就是說，如果a是素數p的一個原根，那麼數值

                  a mod p, a2 mod p, ..., ap-1 mod p

是各不相同的整數，并且以某種排列方式組成了從1到p-1的所有整數。

對于一個整數b和素數p的一個原根a，可以找到惟一的指數i，使得

                  b = ai mod p     其中0 ≤ i ≤（p-1）

指數i稱為b的以a為基數的模p的離散對數或者指數。該值被記為inda ,p（b）。

基于此背景知識，可以定義Diffie-Hellman密鑰交換算法。該算法描述如下：

1）有兩個全局公開的參數，一個素數Q和一個整數A，A是Q的一個原根。

2）假設使用者A和B希望交換一個密鑰，使用者A選擇一個作為私有密鑰的随機數XA<Q，并計算公開密鑰YA=AXA mod Q。A對XA的值保密存放而使YA能被B公開獲得。類似地，使用者B選擇一個私有的随機數XB<Q，并計算公開密鑰YB=AXB mod Q。B對XB的值保密存放而使YB能被A公開獲得。

3）使用者A産生共享秘密密鑰的計算方式是K = （YB）XA mod Q。同樣，使用者B産生共享秘密密鑰的計算是K = （YA）XB mod Q。這兩個計算産生相同的結果：

              K = （YB）XA mod Q

                = （AXB mod Q）XA mod Q

                = （AXB）XA mod Q

                = AXBXA mod Q

                = （aXA）XB mod q

                = （AXA mod Q）XB mod Q

                = （YA）XB mod q

是以相當于雙方已經交換了一個相同的秘密密鑰。

4）  因為XA和XB是保密的，一個敵對方可以利用的參數隻有Q、A、YA和YB。因而敵對方被迫取離散對數來确定密鑰。例如，要擷取使用者B的秘密密鑰，敵對方必須先計算

               XB = indA ,Q（YB）

然後再使用使用者B采用的同樣方法計算其秘密密鑰K。

Diffie-Hellman密鑰交換算法的安全性依賴于這樣一個事實：雖然計算以一個素數為模的指數相對容易，但計算離散對數卻很困難。對于大的素數，計算出離散對數幾乎是不可能的。下面以一個簡單的例子來說明。

密鑰交換基于素數Q = 97和97的一個原根A = 5。A和B分别選擇私有密鑰XA = 36和XB = 58。每人計算其公開密鑰：

                YA = 536 = 50 mod 97

                YB = 558 = 44 mod 97

它們互相擷取了公開密鑰之後，各自通過計算得到雙方共享的秘密密鑰如下：

                    K = （YB）XA mod 97 = 4436 = 75 mod 97

                    K = （YA）XB mod 97 = 5058 = 75 mod 97

從|50，44|出發，攻擊者要計算出75很不容易。實際應用環境類似下面的情節。

現在假設有一組使用者（例如一個區域網路上的所有使用者），每個人都産生一個長期的私有密鑰XA，并計算一個公開密鑰YA。這些公開密鑰數值連同全局公開數值Q和A都存儲在密鑰管理中心。在任何時刻，使用者B都可以通路使用者A 的公開數值，計算一個秘密密鑰，并使用這個密鑰發送一個加密封包給A。因為隻有A和B可以确定這個密鑰，其他使用者都無法解讀封包。接收方A知道隻有使用者B才能使用此密鑰生成這個封包。鑒于此，ECC加密算法既可保證加密特性又可實作鑒别功能。

-----------------------注：本文部分内容改編自《.NET 安全揭秘》

本文轉自玄魂部落格園部落格，原文連結：http://www.cnblogs.com/xuanhun/archive/2012/06/23/2559550.html，如需轉載請自行聯系原作者