RSA 函数与 RSA 假设

形式陈述 ​

RSA 参数生成器在输入 $1^{\lambda }$ 后选择位长受 $\lambda$ 控制、大小相近的不同奇素数 $p,q$，令 $N=pq$。此时欧拉函数公理库欧拉函数Euler totient function计数不超过 n 且与 n 互素的正整数的算术函数。值为 $\phi (N)=(p-1)(q-1)$；用于确定所有单位元素指数周期的 Carmichael 函数值为

$$\lambda (N)=\mathrm{lcm}(p-1,q-1).$$

选择满足 $gcd(e,\lambda (N))=1$ 的公开指数 $e$，再计算 $d\equiv e^{-1}(\mathrm{mod}\lambda (N))$。公钥是 $(N,e)$；陷门可由 $(p,q)$ 表示，并据此求得 $d$，具体接口也可能保存 $d$ 及 CRT 加速参数。素因子、私钥指数和 CRT 系数相互关联，却不是同一份数据，安全陈述应明确攻击者实际获得哪一种。

在单位群 ${\mathbb{Z}}_N^{\ast }$ 上，RSA 函数定义为

$$f_{N,e}(x)=x^{e}modN.$$

因为 $ed\equiv 1(\mathrm{mod}\lambda (N))$，对每个 $x\in {\mathbb{Z}}_N^{\ast }$ 都有 $(x^e{)}^d\equiv x(\mathrm{mod}N)$，所以 $f_{N,e}$ 是一个置换，逆映射为 $y\mapsto y^{d}modN$。整数中国剩余定理公理库整数中国剩余定理Chinese remainder theorem for integers两两互素模数下的同余方程组在模其乘积意义下有唯一解。可把私钥运算分解到模 $p$ 与模 $q$，从而加速实现；这不会改变函数或困难假设。某些教材把 RSA 置换扩展到整个 ${\mathbb{Z}}_N$，该结论需要 $N$ 的生成条件和 $e$ 对各分量指数的互素性；本页把定义域固定在 ${\mathbb{Z}}_N^{\ast }$，避免无条件混用。

RSA 反演实验先生成 $(N,e,p,q)$，再均匀采样 $x\leftarrow {\mathbb{Z}}_N^{\ast }$，令 $y=x^{e}modN$，把 $(N,e,y)$ 交给 PPT 对手 $A$。若 $A$ 输出 $x^{\prime }\in {\mathbb{Z}}_N^{\ast }$ 且 $(x^{\prime }{)}^e\equiv y(\mathrm{mod}N)$，实验成功。记

$${\mathrm{Succ}}_A^{\mathsf{RSA}}(\lambda )=\text{Pr}[(A(N,e,y){)}^e\equiv y(\mathrm{mod}N)].$$

由于函数是置换，有效原像就是原采样的 $x$。RSA 假设断言：对每个 PPT $A$，上述成功概率随安全参数公理库安全参数Security parameter共同索引密码算法族、资源规模与失败概率的渐近尺度。 $\lambda$ 可忽略。概率包含密钥生成、随机输入和对手随机币；这是求逆成功事件，没有 $1/2$ 猜测基线，也不应套用隐藏位优势的因子。

知道 $p,q$ 可以计算 $\lambda (N)$ 与 $d$，因此分解 $N$ 足以高效反演 RSA。反过来，从任意随机像上的 RSA 反演算法普遍恢复 $p,q$，目前没有一般性的已知证明。RSA 假设与整数分解假设有关但不等价；把二者写成同一个命题会掩盖归约尚未建立的方向。

直觉 ​

RSA 把模幂看成一扇带陷门的旋转门。公开指数 $e$ 让任何人都能把 $x$ 推到 $x^e$；只有知道模数结构的一方才能算出逆指数 $d$，把像稳定地转回原像。函数的代数可逆性由同余与 CRT 保证，单向性则是一项关于随机生成模数和高效攻击者的计算假设，两者不能混为“公式看起来复杂”。

这一页只描述函数族与反演任务。加密还要定义消息编码、随机性和 IND 游戏，签名还要定义编码、验证与不可伪造性；把这些方案层内容直接塞进 RSA 函数，会让“可逆”“难反演”和“安全使用”三个不同命题失去边界。

例子与边界 ​

取演示参数 $p=5,q=11$，则 $N=55$、$\lambda (N)=20$。选择 $e=3$ 得 $d=7$，因为 $3\cdot 7\equiv 1(\mathrm{mod}20)$。对单位 $x=12$，

$${12}^3\equiv 23(\mathrm{mod}55),{23}^7\equiv 12(\mathrm{mod}55).$$

这个例子只展示逆指数的代数作用；模数可以立即分解，完全没有安全性。真实生成器还要规定素数分布、模数位长、公开指数选择和素性测试，并针对已知分解算法选择参数。

Textbook RSA 加密若直接发送 $c=m^{e}modN$，是确定性的：相同消息产生相同密文，攻击者可自行加密候选消息并比较，故不满足 IND-CPA。它还具有乘法可塑性，

$$f_{N,e}(m_1{m}_2)=f_{N,e}(m_1)f_{N,e}(m_2)(\mathrm{mod}N),$$

攻击者可在不知道明文时系统地改变密文对应的明文。随机编码与经过证明的填充方案是具体加密或签名构造的必要组成部分；“RSA 函数难反演”本身不推出 textbook RSA 的 CPA 或 CCA 安全。

实现泄漏也超出基础反演实验。CRT 私钥运算若出现单侧故障，错误签名可能暴露因子；非恒定时间模幂、填充错误差异和选择密文接口都可能提供额外能力。缓解这些问题需要消息盲化、故障检查、恒定时间实现和统一错误处理，而不能靠重新陈述 RSA 假设解决。

推论与应用 ​

RSA 函数是单向函数公理库单向函数One-way function易于正向计算，但随机输入所产生的像难以被任何高效算法反演的函数族。与陷门置换的经典候选。它为 RSA-OAEP 类公钥加密、RSA-PSS 和全域哈希类签名提供代数核心；这些构造的安全性还取决于编码方式、随机预言机或标准模型假设，以及与目标攻击游戏匹配的归约。

在证明中应区分三条箭头：因式分解可计算陷门，陷门可高效反演函数，方案攻击可在特定条件下转化为 RSA 反演。每条箭头都有自己的输入分布、运行时间与成功概率损失。只有逐条成立时，才能从底层困难性得到上层安全结论。

参考资料

• Ronald L. Rivest, Adi Shamir, and Leonard Adleman, “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems,” Communications of the ACM 21(2), 1978。
• Dan Boneh and Victor Shoup, A Graduate Course in Applied Cryptography, version 0.6, 2023，RSA functions, assumptions, and schemes。
• Jonathan Katz and Yehuda Lindell, Introduction to Modern Cryptography, 3rd ed., CRC Press, 2020，trapdoor permutations and RSA-based constructions。