離散對數

是在整數中，一種基於同餘運算和原根的一種對數運算 當模m有原根時，設l為模m的一個原根，則當時： ，此處的Indlx為x以整數l為底，模時的離散對數值 性質 離散對數和一般的對數有著相類似的性質：所謂離散對數，就是給定正整數x,y,n,求出正整數k(如果存在的話),使。

1976年，美國斯坦福大學教授赫爾曼(E.Hellman)和他的研究助理迪菲(W.Diffie)，

以及博士生默克勒(R.C.Merkle)（簡稱為DHM）首先創立並發表了所謂的“公鑰密碼體制”（public key cryptography），即加密、解密用兩個不同的鑰，加密用公鑰（public key），即可以公開，不必保密，任何人都可以用；解密用私鑰（private key），此鑰必須嚴加管理，不能泄漏。更為稱絕的是，他們還發明了所謂的數字簽名（digital signatures）技術，即用私鑰簽名，再用公鑰驗證。

在一般參考文獻中，都認為公鑰密碼體制是迪菲和赫爾曼發明的[1]，可鮮為人知的是，默克勒甚至在他倆之前的1975年就提出了類似的思想，儘管其文章是於1978年發表的[2]，但投稿比較早。因此，公鑰密碼體制的創始人應該是DHM三人，這種觀點目前已得到了國際上的認同，尤其得到了赫爾曼教授本人的認定。當然，英國軍用情報中心也曾宣稱他們早在1970年就發明了公鑰密碼體制，但經仔細分析其資料並與中心有關人員討論后發現，他們只是提及了公鑰密碼體制的某種特殊形式。更為重要的是，DHM的公鑰密碼體制還包含數字簽名，而情報中心的資料則是隻字未提。注意，美國國家安全局也有過類似的宣稱，不過這都是不可信的（至少不可全信）。如要詳細了解公鑰密碼體制的發展史，讀者可參考筆者的一本由赫爾曼教授作序的英文專著[3]。

當然，DHM只是提出了一種關於公鑰密碼體制與數字簽名的思想，而沒有真正實現。不過，他們確實是實現了一種體現公鑰密碼體制思想、基於離散對數問題的、在不安全的通道上進行密鑰形成與交換的新技術。這裡必須先介紹一下什麼叫離散對數。

所謂離散對數，就是給定正整數x，y，n，求出正整數k（如果存在的話），使。就目前而言，人們還沒有找到計算離散對數的快速演演算法（所謂快速演演算法，是指其計算複雜性在多項式範圍內的演演算法，即，其中k為常數）。雖然有快速計算離散對數的量子演演算法，其計算複雜性為?著，但現在並沒有量子計算機（實用的量子計算機也許根本就建造不出來）。

現在，說明一下DHM的運作過程（假定A和B兩個人要在一個不安全通道如網際網路上形成密鑰以備日後加密解密所用）。

首先，A、B兩人要共同公開約定一個素數q和有限域Fq中的一個生成元g；

A選定一個隨機數（a可以認為是A之私鑰），並將傳送給B；

B選定一個隨機數（b可以認為是B之私鑰），並將傳送給A；

此時A可以算出，B也可以算出，由於，因此，A和B就形成了一個公共的密鑰，日後便可以此鑰來進行傳統的加密解密計算，從而達到在不安全的通道上進行保密通訊的目的。

顯然，敵方可以截獲到g，q，，。因此，如果敵方有快速的求解離散對數的演演算法，就能從已截獲的上述信息中迅速求出a或b，從而算出。遺憾的是，目前世界上根本就沒有快速的求解離散對數的演演算法，因此當所選的有限域Fq很大時，a或b就很難算出。值得注意的是，DHM密鑰交換體制實際上是一座溝通密鑰密碼體制與公鑰密碼體制的橋樑，即用公鑰密碼體制的思想形成密鑰（雖然公鑰密碼體制計算速度慢，但密鑰的長度一般都很短，所以沒有關係），再用密鑰進行傳統的密鑰密碼體制的加密與解密運算（密鑰密碼體制的運算速度一般都很快，所以適合於對容量大的信息進行加密解密計算）。在這裡，這兩種密碼體制交叉使用，揚長避短，充分發揮了各自的優越性。

下面給出一個關於具體計算離散對數的實例。

A和B先約定公共的和。

A選隨機數a，並計算，且將其送給B（註：a不能向外泄漏）；