数论基础

困难问题假设

• 大整数分解 (Factoring)：给定 $N=pq$，求 $p,q$。是 RSA 的基础。
• 离散对数 (DLP)：在循环群 $G$ 中，给定 $g,h=g^x$，求 $x$。
• CDH (计算 Diffie-Hellman)：给定 $g,g^a,g^b$，求 $g^{ab}$。
• DDH (判定 Diffie-Hellman)：区分 $(g,g^a,g^b,g^{ab})$ 和 $(g,g^a,g^b,g^z)$。这是最强的假设。

欧拉定理

• $\forall a\in Z_N^{\ast },a^{\varphi (N)}\equiv 1(\mathrm{mod}N)$。这是 RSA 解密有效性的数学基础。