RSA 函数与 RSA 假设 | Codeboy's Blog

形式陈述

RSA 参数生成器在输入 $1^\lambda$ 后选择位长受 $\lambda$ 控制、大小相近的不同奇素数 $p,q$ ，令 $N=pq$ 。此时欧拉函数值为 $\varphi(N)=(p-1)(q-1)$ ；用于确定所有单位元素指数周期的 Carmichael 函数值为

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

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

在单位群 $\mathbb Z_N^*$ 上，RSA 函数定义为

f_{N,e}(x)=x^e\bmod N.

因为 $ed\equiv1\pmod{\lambda(N)}$ ，对每个 $x\in\mathbb Z_N^*$ 都有 $(x^e)^d\equiv x\pmod N$ ，所以 $f_{N,e}$ 是一个置换，逆映射为 $y\mapsto y^d\bmod N$ 。整数中国剩余定理可把私钥运算分解到模 $p$ 与模 $q$ ，从而加速实现；这不会改变函数或困难假设。某些教材把 RSA 置换扩展到整个 $\mathbb Z_N$ ，该结论需要 $N$ 的生成条件和 $e$ 对各分量指数的互素性；本页把定义域固定在 $\mathbb Z_N^*$ ，避免无条件混用。

RSA 反演实验先生成 $(N,e,p,q)$ ，再均匀采样 $x\leftarrow\mathbb Z_N^*$ ，令 $y=x^e\bmod N$ ，把 $(1^\lambda,N,e,y)$ 交给 uniform PPT 对手 $A$ 。若 $A$ 输出 $x'\in\mathbb Z_N^*$ 且 $(x')^e\equiv y\pmod N$ ，实验成功。记

\operatorname{Succ}^{\mathsf{RSA}}_A(\lambda) =\Pr[(A(1^\lambda,N,e,y))^e\equiv y\pmod N].

由于函数是置换，有效原像就是原采样的 $x$ 。RSA 假设断言：对每个 PPT $A$ ，上述成功概率随安全参数 $\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\cdot7\equiv1\pmod{20}$ 。对单位 $x=12$ ，

12^3\equiv23\pmod{55}, \qquad 23^7\equiv12\pmod{55}.

这个例子只展示逆指数的代数作用；模数可以立即分解，完全没有安全性。互素条件本身也不保证困难性： $e=1$ 同样满足它，却使 RSA 函数成为任何人都能反演的恒等映射。真实生成器还要规定素数分布、模数位长、公开指数选择和素性测试，并针对已知分解算法选择参数。

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

f_{N,e}(m_1m_2)=f_{N,e}(m_1)f_{N,e}(m_2)\pmod N,

攻击者可在不知道明文时系统地改变密文对应的明文。加密必须避免上述确定性泄漏；加密与签名都需采用与各自安全游戏匹配的编码和归约，不能把“加密需要随机化”直接当作所有签名算法也必须随机化的结论。“RSA 函数难反演”本身不推出 textbook RSA 的 CPA 或 CCA 安全。

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

推论与应用

RSA 函数是单向函数与陷门置换的经典候选。它为 RSA-OAEP 类公钥加密、RSA-PSS 和全域哈希类签名提供代数核心；这些构造的安全性还取决于编码方式、随机预言机或标准模型假设，以及与目标攻击游戏匹配的归约。

RSA全域哈希签名给出单位群编码、惰性预言机模拟及猜测查询索引的成功概率账本。RSA-PSS则把盐、掩码、保留高位和严格长度验证变成可运行字节算法；它还说明编码整数不必是单位时，正确性如何借助模p、模q及CRT补全。两者的方案条件都不能从本页函数可逆性单独推出。

在证明中应区分三条箭头：因式分解可计算陷门，陷门可高效反演函数，方案攻击可在特定条件下转化为 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。

形式陈述 ​

反向链接

形式陈述