离散对数问题

概述

离散对数问题（Discrete Logarithm Problem）是计算复杂度理论中的一个困难问题：给定 g、p 和 g^a mod p，求 a。目前没有已知的经典多项式时间算法。

关键内容

问题定义

给定： - 一个大素数 p - 一个模 p 的原根 g - 一个值 A = g^a mod p

求：秘密整数 a

计算困难性

• 正向计算（模幂运算）很容易：O(log a) 时间
• 逆向计算（离散对数）目前最优算法是数域筛法，复杂度为亚指数级
• 对于 2048 位以上的素数，计算量远超现有计算能力

在密码学中的应用

• Diffie-Hellman 密钥交换：安全性直接基于此问题
• ElGamal 加密：基于离散对数
• DSA/ECDSA 数字签名：基于离散对数
• 椭圆曲线密码学（ECC）：椭圆曲线上的离散对数问题

量子威胁

1994年 Peter Shor 提出量子算法，可在多项式时间内解决离散对数问题。一旦大规模量子计算机成为现实，所有基于此问题的密码系统都将不再安全。

来源

• raw/books/计算机科学/11-diffie-hellman-new-directions.md

相关

• Diffie-Hellman 密钥交换 — 安全性基础
• 公钥密码学 — 多个方案基于此
• 后量子密码学 — Shor 算法威胁
• 计算复杂度理论 — 计算困难性问题