離散對數加密算法

 與前章所述RSA公鑰加密算法類似，離散對數加密算法也屬于公鑰加密算法，RSA依賴大數因數分解的困難性，而離散對數則依賴有限域上的離散指數的難計算性保障其安全。

目前三大公鑰加密算法（RSA、離散對數、橢圓曲線）都依賴數論與群論的知識，在介紹具體的算法前有必要再簡介下所關聯的數學知識。

1.歐拉公式與φ(m)特性

在RSA公鑰加密算法中已經提到歐拉公式、費馬小定理，可以說是三大加密算法的基礎，φ(m)描述的是m的既約剩餘系（與m互素的餘數構成的集合）的大小，對素數p來說，其既約剩餘系為1,2,...,p-1，即除0外，集合中的任何元素均與p互素，是以φ(p)=p-1。這其實是歐拉剩餘系大小的一個特例，一般地m=p1p2...pn(pi為素數)，有φ(m)=(p1-1)(p2-1)...(pn-1)。

2. 模乘法群

對任意的正數m，其既約剩餘系關于模乘構成一個群，如RSA公鑰加密算法中所述，該群存在下面的性質：

• 封閉性：群中的任意元素a,b，c= a*b(mod m)，則c也在群中
• 逆元：若對任意的a都存在b，使得：ab≡1(mod m)，則稱b為a的逆元，記為：a-1

3. 原根

對任意的整數(a,m)=1，則存在d滿足： ad≡1(mod m)（證明請參考初等數論） 若d0是滿足上式的最小值，則d0|d，即d是d0倍數，若d0=φ(m)，則稱a為模m的原根，存在原根的模乘法群稱為循環群。需要指出的是：對任意的模m來說，原根可能不存在，也可能存在多個。 下面自然引出一個問題：什麼樣的m才存在原根？數論中已經證明，m有原根的沖要條件為： 1,2,4,pe,2pe，其中：p為奇素數，e為任意正整數 也就是說m=2n(n>=3)，必無原根。而m=17的原根為3，因為316≡1(mod 17)

4. 離散對數

設g為素數p的模循環群的原根，對任意的a，計算：

b=ga mod p----（1）

是容易的（通過幂取模算法）。反過來，給定b計算滿足（1）式的a是非常困難的，a稱為以g為基b的離散對數。

如果隻是實數領域的指數運算，則可解出a = loggb，因為取模運算導緻（1）式無法表達為該形式，但仍稱a為離散對數。

因為a、b均為整數，不像實數那麼“連續”，故稱離散對數。

因為限定a，b都屬于模p的循環群，而該群的大小為：φ(p)=p-1，故稱“有限域”上的離散對數。

5.加密過程

離散對數加密存在三種形式，本質上這三種形式都是等價的：

5.1 加密形式1---标準Diffie-Hellman算法

假設A希望發送一條消息m（0<m<p）給B

1. A選擇一個随機數c（A的密鑰），0<c<p-1，(c,p-1)=1。發送 x = mc mod p，發送給B
2. B選擇一個随機整數d（B的密鑰），0<d<p-1，(d,p-1)=1。發送y = xd mod p =mcd mod p給A

3. A産生z = yc-1，發送給B。其中cc-1≡1(mod p-1)，因為(c,p-1)=1，是以逆元素c-1必存在。

   z = yc-1 mod p = mcdc-1 mod p =md mod p（費馬小定理）

4. B計算zd-1=mdd-1= m。dd-1≡1(mod p-1)

過程的證明與RSA類似，參考RSA公鑰加密算法即可。

這樣通過AB之間的三次通信可以完成一次安全的資料傳輸，竊聽者可以取得mc、mcd、md，但卻無法計算出其離散對數c,d的值，進而保證加密算法的安全性。

5.2 加密形式2---T. ElGamal算法

A公開模p循環群及其原根g和ga作為公鑰，a作為私鑰。a随機選擇，滿足：1=<a<p。

假設B發送消息m給A

1. B選擇随機數k，1=<k<=p-2，不同的消息m必須選擇不同的k

   B發送(gk , mgak)給A，注意，實際發送的是（x = gk mod p, y = mgak mod p）

2. A可以計算xa≡gak(mod p)，則m = (gak )-1y（一次同餘方程的解）

這裡面有幾個問題：

• 為什麼不同的m要選擇不同的k？

  如果所有的m都使用相同的k，竊聽者在已知消息m1（m1是竊聽者産生的測試消息）的情況下，可能會截獲他人的消息m2：

  m1gak ≡y1 ---- (a)

  m2gak ≡y2 -----(b)

  因為m1已知，根據(a)很容易計算出gak =(m1)-1y1，進而根據(b)能很容易計算出消息m2=(gak)-1y2。但如果每個m選擇不同的k，則可以避免這種情況。

• 為什麼要選擇原根g作為生成元（計算基礎）？

  對任意的a，ga都唯一對應群中的一個元素；同樣，對任意的群元素b，都存在唯一的a(0<a<p)，滿足：b=ga，這就保證了(gak)-1的唯一性，也就保證恢複出消息m的唯一性。

與加密形式1相比較，加密形式2僅需要一次通信便可傳遞消息m，但卻需要傳遞兩個群元素(g k , mg ak)。通信次數少了，但每次通信的資料量增加不少。從本質上來講，形式2是形式1的一個變種。

5.3 加密形式3---密鑰交換

形式1和形式是通過直接加密消息m，在接收端直接還原消息m的方式，形式3于此稍有不同，是通過先交換共同密鑰，在加密消息m的方式進行通信。 與形式2相同，A公開模p的循環群和原根g，假設使用者A希望與B交換密鑰：

1. A選擇一個随機數c,(0<c<p)，發送gc mod p給B，作為公鑰；将c妥善保管作為私鑰
2. B選擇一個随機數d,(0<d<p)，發送gd mod p給A，作為公鑰；将d妥善保管作為私鑰
3. 此時A、B雙方都能計算K=(gc mod p)d=(gd mod p)c=(gcd mod p)，即K即為A、B之間的密鑰

交換密鑰的過程與消息m無關，有了密鑰K後，A、B之間可以進行對稱加密。形式3隻是在密鑰交換階段進行了2此通信，之後便隻有消息通信，非常适合程式實作。

6. 離散對數的困難性

上述三種加密形式都依賴離散對數的困難性，知道(g,g c)但無法得到c，目前存在幾種攻擊離散對數的方法：

1. Shanks算法

   該方法類似大整數因子分解的試除法，若c有1024位将是一個天文數字，即使超級計算機也無法完成

2. Pollard算法

   針對p-1有素因子的特殊情況

3. Pohlig-Hellman算法
4. 指數演算法

關于每種攻擊算法的特點，及為抵禦攻擊選取素數p的方法，不再做詳細介紹。（有興趣的可以參考<<密碼學原理與實踐>>） 但無論何種算法，隻要精心選取素數p都可抵禦目前的攻擊，目前普遍認為攻擊離散對數的困難性要高于RSA。

7. 離散對數與RSA的差別

RSA的公鑰、私鑰均有接收端（比如Server）簽發，非常适合網際網路上的證書服務：服務端簽發證書，用戶端使用該證書，保證用戶端到服務端之間的通信安全。如果雙端都需要非對稱加密，則雙方都必須釋出公鑰，并且公鑰不能頻繁變更，做不到每個端點一個公鑰，是以，任何一個接收端都可以檢視發送端的消息（公鑰解密）。 離散對數形式相對比較靈活，每個發送端可以在發送每條消息是指定自己的公鑰，但接收端回複的消息也隻有發送端才能解密；也可通信握手階段協商密鑰，接下來根據協商的密鑰走對稱加密。

8.總結

複雜的公鑰加密過程，其實僅依賴一個簡單的數學公式，這也正是數學之美。很多人研究公鑰加密算法，而另一些人卻拼命研究如何破解這些加密算法，正所謂“道高一尺，魔高一丈”。正是這種“自己創造問題，自己解決”的“愚公”精神，推動了整着整個網絡安全向前發展。 【參考資料】

• http://en.wikipedia.org/wiki/Discrete_logarithm
• http://blog.sina.com.cn/s/blog_5b5ed0720100atsy.html
• 初等數論（潘承洞）
• 密碼學原理與實踐