在密碼學的正史中，離散對數問題（DLP，discrete logarithm problem）比因式分解問題更早登場：RSA 出現於 1977 年，而另一個密碼學突破——Diffie–Hellman 金鑰協商（見第 11 章）——早了一年，其安全性正是建立在 DLP 的困難性上。

與因式分解問題一樣，DLP 處理的是大數，但它稍微沒那麼直截了當，需要多一點數學。所以先讓我們介紹群這個數學概念。

什麼是群#

在數學脈絡中，群（group）是一組依某些定義明確之規則彼此關聯的元素（通常是數）。

一個群的例子：某個質數 p 之模下的非零整數（介於 1 與 p − 1 之間）集合，寫作 Zp*。對 p = 5，我們得到：

Z5* = {1, 2, 3, 4}

在 Z5* 中，運算以模 5 進行。因此不是 3 × 4 = 12，而是 3 × 4 = 2（因為 12 mod 5 = 2）——儘管如此，我們仍使用與一般整數乘法相同的符號 ×。

同樣地，我們也用指數記法表示群元素與自身相乘（密碼學中常見的操作）。例如在 Z5* 中，2³ = 2 × 2 × 2 = 3 而非 8，因為 8 mod 5 = 3。

群公理#

一個數學集合要成為群，必須具備以下特徵（稱為群公理）：

  • 封閉性（closure）：對群中任意 x 與 y，x × y 也在群中。在 Z5* 中：2 × 3 = 1（因為 6 = 1 mod 5）、2 × 4 = 3……
  • 結合律（associativity）：對群中任意 x, y, z，(x × y) × z = x × (y × z)。在 Z5* 中：(2 × 3) × 4 = 1 × 4 = 4，而 2 × (3 × 4) = 2 × 2 = 4。
  • 單位元存在（identity existence）：存在元素 e 使 e × x = x × e = x。在任何 Zp* 中，單位元都是 1。
  • 反元素存在（inverse existence）：對群中任意 x，存在 y 使 x × y = y × x = e。在 Z5* 中，2 的反元素是 3、3 的反元素是 2，而 4 是自己的反元素（因為 4 × 4 = 16 = 1 mod 5）。

交換群與循環群#

  • 一個群稱為交換的（commutative），若對任意群元素 x 與 y 都有 x × y = y × x。所有整數乘法群 Zp* 都是交換的。
  • 一個群稱為循環的（cyclic），若存在至少一個元素 g，其冪次（g¹, g², g³, ...）模 p 能涵蓋所有相異的群元素。此時 g 稱為該群的生成元（generator）。
2¹=2, 2²=4, 2³=3, 2⁴=1
3¹=3, 3²=4, 3³=2, 3⁴=1

群運算不一定是乘法#

這裡用乘法當群運算子，但你也可以從其他運算子得到群。

最直截了當的群是「所有整數（含正負）配上加法」：x + y 是整數（封閉性）；(x + y) + z = x + (y + z)（結合律）；0 是單位元；任意數 x 的反元素是 −x（因為 x + (−x) = 0）。

但一個大差別是：這個整數群的大小是無限的，而在密碼學中我們只處理有限群。

典型情況下我們會用 Zp*，其中 p 長達數千位元（也就是若 p 是 m 位元長，該群含有 2^m 量級的數）。

困難的那件事#

名稱的由來：

  • 稱為離散（discrete），是因為我們處理的是整數，而非實數（連續）。
  • 稱為對數（logarithm），是因為我們要找的是 x 以 g 為底的對數。（例如 256 以 2 為底的對數是 8，因為 2⁸ = 256。）

因式分解與 DLP，哪個更安全#

常有人問作者：因式分解與離散對數哪個更安全，也就是哪個問題更難？

答案是：兩者大致一樣難。

事實上，解 DLP 的演算法與分解整數的演算法有相似之處，而且**「n 位元難分解的數」與「n 位元群中的離散對數」給出的安全等級大致相同**。

而且基於與因式分解相同的理由，DLP 也不是 NP-complete。

注意：在某些群中 DLP 比較容易解。這裡指的只是「由某質數之模下的數所構成的 DLP 群」這個情況。

Backward 因式分解問題 RSA Forward