Devil's Night

Diffie-Hellman密钥交换带我们认识了离散对数方程. 现在让我们仔细研究一下离散对数方程的性质

例子

首先随便选取一个质数 比如 7, 那么则存在一个循环群 C_n, 当 n = 7 时, C₇ = {1, 2, 3, 4, 5, 6 ,}. 这个群中的每个元素 都和 7 互质, 而且我们可以找到一个生成元 g. 在这个例子中 g = 3. 下面展示了3是如何生成C₇的

• 3¹ mod 7 = 3
• 3² mod 7 = 2
• 3³ mod 7 = 6
• 3⁴ mod 7 = 4
• 3⁵ mod 7 = 5
• 3⁶ mod 7 = 1

离散对数方程即是以上过程的逆运算.
比如有这样一个方程 3^k ≡ 6 (mod 7), 如上面所示 k = 3 就是这个方程的根, 但它并不是唯一解, 不难发现 3⁹ ≡ 6(mod 7) 即 k = 9 也能使等式成立. 我们甚至能发现这样一个规律 3³⁺⁹ⁿ ≡ 6 (mod 7) 当n为自然数的情况下永远成立. 但只有3是方程 3^k ≡ 1 (mod 7)的最小自然数解, 并且只有3属于 (Z₇)*, 所以 这个方程的解可以写作 k ≡ 3 (mod 7).

定义

一个有限循环群G中含有n个元素. b 是群G的生成元; 也就是说G中的每个元素g都可以改写成以下形式 g = b^k k为整数.

• log_b: G→Z

目前有效计算离散对数方程是很困难的. 不仅仅是计算特殊情况, 即是一般情况下使用随机自我检测, 计算复杂性仍然不会降低. 这中计算上的复杂性 就构成了Diffie-Hellman密钥交换的基础