離散對數

在整數中，離散對數（英語：Discrete logarithm）是一種基於同餘運算和原根的一種對數運算。

基本介紹

• 中文名：離散對數
• 外文名：Discrete logarithm
• 提出者：迪菲(W.Diffie)和赫爾曼(E.Hellman)默克勒(R.C.Merkle)
• 套用學科：數學
• 適用領域範圍：密碼學,計算機技術
• 定義：基於同餘和原根的對數運算

歷史

普遍大家都認為公鑰密碼體制是迪菲(W.Diffie)和赫爾曼(E.Hellman)發明的，可鮮為人知的是，默克勒(R.C.Merkle)甚至在他倆之前的1975年就提出了類似的思想，儘管其文章是於1978年發表的，但投稿比較早。因此，公鑰密碼體制的創始人應該是他們三人。 當然，他們三人只是提出了一種關於公鑰密碼體制與數字簽名的思想，而沒有真正實現。不過，他們確實是實現了一種體現公鑰密碼體制思想、基於離散對數問題的、在不安全的通道上進行密鑰形成與交換的新技術。

介紹

在整數中，離散對數（英語：Discrete logarithm）是一種基於同餘運算和原根的一種對數運算。而在實數中對數的定義 log_ba是指對於給定的a和b，有一個數x，使得b^x=a。相同地在任何群G中可為所有整數k定義一個冪數為b^x，而離散對數log_ba是指使得b^x=a的整數k。

離散對數在一些特殊情況下可以快速計算。然而，通常沒有具非常效率的方法來計算它們。公鑰密碼學中幾個重要算法的基礎，是假設尋找離散對數的問題解，在仔細選擇過的群中，並不存在有效率的求解算法。

定義

當模m有原根時，設l為模m的一個原根，則當 時：

此處的 為x以整數l為底，模 時的離散對數值。

性質

離散對數和一般的對數有著相類似的性質：

實例

A和B先約定公共的q=2739·(7149-1)/6+1和g=7。

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

B將收到7a=127402180119973946824269244334322849749382042586931621654557735290322914679095998681860978813046&595166455458144280588076766033781。

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

A將收到7b=180162285287453124447828348367998950159670&466953466973130251&2173405995377205847595817691062538069210165184866236213793&4026803049。

此時A和B都能計算出密鑰7ab(modq)，但別人不太容易算出，因為別人不知道a和b。有興趣的讀者不妨將此作為一個練習，試著計算出7ab(modq)的值。