离散对数问题 (DLP)

模 $p$ 下，已知底数 $g$ 与 $y=g^x\bmod p$ 反求指数 $x$ 称离散对数。正向模幂易算、反向求 $x$ 极难——这种单向性是另一类公钥密码的根基。$g$ 取原根时其幂遍历所有非零剩余。

Diffie–Hellman 密钥交换

双方在公开信道上协商出共享密钥而不泄露它：

Alice 选私密 $a$ 发 $g^a$；Bob 选 $b$ 发 $g^b$；各自算 $(g^b)^a=(g^a)^b=g^{ab}$ 为共享密钥。

窃听者只见 $g,g^a,g^b$，要算 $g^{ab}$ 须解 DLP（计算 DH 难题）。

ElGamal

把 DH 思想做成加密：基于 DLP 的公钥加密与签名体系。

例题

例　$p=23,g=5$：Alice $a=6\Rightarrow g^a=8$；Bob $b=15\Rightarrow g^b=19$。共享密钥 $19^6\bmod23=8^{15}\bmod23=2$。

应用

DH 是 TLS 握手协商会话密钥的核心；其「临时密钥」变体提供前向保密（即使长期私钥泄露，过去会话仍安全）。ElGamal 思想用于 PGP 与数字签名标准 DSA。