密码学问题归约关系梳理及DLOG≤ModExp的合理性疑问

嗨，我来帮你理清楚这些密码学问题之间的归约关系，顺便解答你纠结的DLOG和ModExp的归约问题～

先明确各个问题的定义 #

• BreakRSA：给定 $(n = pq, e)$，找到满足 $ed ≡ 1 \pmod{φ(n)}$ 的 $d$
• CDH（计算Diffie-Hellman）：在群中给定 $A = g^a$ 和 $B = g^b$，求出 $C = g^{ab}$
• DLOG（离散对数）：在群 $G$ 中给定 $(g, g^x)$，找到 $x ∈ {1, ..., |G|}$
• ModExp（模幂运算）：给定整数 $(x, n, e)$，计算 $x^e \mod n$
• IntegerFact（整数分解）：给定整数 $n = pq$，找到素因子 $p$ 和 $q$

你已提出的正确归约关系 #

你提到的这几个归约都是成立的，我再帮你确认下逻辑：

• BreakRSA ≤ IntegerFact：如果能分解 $n$ 得到 $p$ 和 $q$，就能算出 $φ(n)=(p-1)(q-1)$，接着用扩展欧几里得算法就能求出 $e$ 的模逆元 $d$，所以BreakRSA可以多项式时间归约到整数分解。
• IntegerFact ≤ BreakRSA：反过来，如果能破解RSA找到 $d$，那么 $ed-1$ 一定是 $φ(n)$ 的倍数，我们可以利用这个性质结合数论技巧（比如Pollard's p-1算法的变种）来分解 $n$，所以整数分解也能多项式时间归约到BreakRSA。
• CDH ≤ DLOG：如果能解离散对数问题，拿到 $a$ 和 $b$，直接计算 $g^{ab}$ 就能解决CDH问题，这个归约逻辑非常直接。

关于DLOG ≤ ModExp的疑问解答 #

你的朋友说的是对的，这个归约不成立，核心原因是归约要求必须是多项式时间归约，而你想到的暴力枚举方法是指数时间的，不符合归约的严格定义。

具体来说，归约的本质是：如果存在一个多项式时间算法能解决问题B，那么我们可以通过这个算法，配合多项式时间的转换步骤来解决问题A。针对这两个问题：

• ModExp是P类问题，用快速幂算法就能在 $O(\log e)$ 的多项式时间内完成计算。
• 如果DLOG能归约到ModExp，那就意味着DLOG也属于P类，但目前密码学界普遍认为离散对数问题是困难问题（不属于P），所以这种归约不可能存在。

你想到的暴力枚举，是用ModExp逐个验证 $g^k$ 是否等于给定的 $g^x$，但这个过程需要遍历 $O(|G|)$ 个可能的 $k$，而密码学中用到的群的阶 $|G|$ 通常是指数级的（比如椭圆曲线群的阶是 $2^{256}$ 量级），这显然不是多项式时间，所以这种方法不能算作有效的归约。

补充其他可能的归约关系 #

除了你提到的，还有一个值得注意的点：

• ModExp是所有这些密码学困难问题的基础操作，但它本身是易解问题，所以所有困难问题（BreakRSA、CDH、DLOG、IntegerFact）都不能归约到ModExp，反而ModExp是构造这些困难问题的核心工具。

备注：内容来源于stack exchange，提问作者RudeusGreyrat