第 13 章：RSA反演、签名伪造与安全假设

第12章已经区分了恢复私钥与恢复某条消息。本章继续回答：知道消息及其签名，为什么不能直接推出私钥？能够构造一个通过数学验签的数值对，为什么还不等于能随意改写消息？这些问题需要同时看清计算任务、归约方向和签名方案的安全定义。

13.1 先分清消息、消息代表值与签名

继续固定 $n=pq$ ，其中 $p,q$ 是不同奇质数。公开指数 $e>1$ 与 $\lambda(n)=\operatorname{lcm}(p-1,q-1)$ 互质，私钥指数 $d$ 满足 $ed\equiv1\pmod{\lambda(n)}$ 。

用 $m$ 表示实际消息，例如一段文字或一个文件；用 $x$ 表示进入RSA幂运算的整数代表，取 $0\le x<n$ ；用 $t$ 表示签名的整数代表。暂时只看原始RSA运算：

$t=x^d\bmod n,\qquad t^e\equiv x\pmod n.$

签名使用 $d$ ，验证使用公开的 $e$ 。这里的 $x$ 并不自动等于实际消息 $m$ ：如何从消息得到代表值，是完整签名方案的一部分。现代PSS编码会在消息和RSA运算之间增加明确的步骤，见第13.9节。

13.2 一组消息和签名约束了哪个指数

假设 $x$ 与 $n$ 互质，记 $h=\operatorname{ord}_n(x)$ 为它的乘法阶。已知 $t\equiv x^d\pmod n$ ，尝试求一个指数 $z$ 满足 $x^z\equiv t\pmod n$ 。对于非负指数 $z$ ，有

$x^z\equiv x^d\pmod n \quad\Longleftrightarrow\quad h\mid(z-d).$

因为 $x$ 有逆元，可把两边化成 $x^{z-d}\equiv1$ ；第4章说明回到1的指数恰是阶的倍数。因此即使找到一个解，确定的也是 $z\equiv d\pmod h$ ，不是唯一的整数 $d$ 。这个求秘密指数的任务具有离散对数的形式；它与给定 $x$ 求 $t$ 的RSA反演任务不同。

例如 $n=55,e=3,d=27,x=2$ 。计算得到 $2^{27}\bmod55=18$ ，而 $2^7\bmod55$ 也为18。由于 $\operatorname{ord}_{55}(2)=20$ ，全部非负指数解为 $z\equiv7\pmod{20}$ 。这个例子中 $7$ 也恰好是有效私钥指数，因为 $3\cdot7\equiv1\pmod{20}$ 。

但这种巧合不能推广到任意底数。取 $x=1$ 时，任何指数都满足 $x^z\equiv1$ ，其中 $z=1$ 显然不能作为同一公钥的有效私钥： $3\not\equiv1\pmod{20}$ 。因此“对这一组 $x,t$ 成立”与“对全部消息完成正确私钥运算”是两个条件。

若 $x$ 与 $n$ 不互质，就不能直接套用乘法群中的阶；先算 $\gcd(x,n)$ ，若结果介于1和 $n$ 之间，已经得到非平凡因子。特殊数值 $x=0,1$ 尤其不能代表一般实例的困难性。

13.3 三个计算问题各自要求输出什么

问题	已知输入	需要输出
整数分解	$n=pq$	$p,q$
私钥恢复	合法的 $n,e$	一个正整数 $d$ ，满足 $ed\equiv1\pmod{\lambda(n)}$
RSA反演	合法的 $n,e$ 和给定的 $x$	$t$ ，满足 $t^e\equiv x\pmod n$

有效私钥不必是最初生成的那个整数代表；相差 $\lambda(n)$ 的指数代表可给出同样的私钥运算。RSA反演则只要求当前输入的原像，不要求输出指数。

对合法RSA参数，幂映射 $t\mapsto t^e\bmod n$ 是全部剩余类上的置换。因为第7章证明 $(t^e)^d\equiv t\pmod n$ ， $d$ 次幂提供逆映射，所以每个 $x$ 都有唯一的模 $n$ 原像。原像唯一并不意味着知道高效求出它的方法。

讨论困难性时，通常在 $U_n$ 上定义随机挑战；第7章的正确性则覆盖全部剩余类。不要把“某些特殊输入很容易反演”误读成“随机挑战普遍容易反演”。

13.4 归约符号为什么容易把方向写反

说 $B\le_P A$ ，表示：可以调用问题 $A$ 的求解算法，再用多项式时间的额外计算解决问题 $B$ 。因此如果 $A$ 容易， $B$ 也容易；从这种归约看， $B$ 不比 $A$ 更难。

用“有A的解法，就能解B”的口头箭头时，方向是 $A\Longrightarrow B$ ；用归约符号时，写的是 $B\le_P A$ 。两种记号表达同一关系，但左右位置相反。

分解的算法可以用于恢复私钥：先得到 $p,q$ ，计算 $\lambda(n)$ ，再求 $e$ 的模逆元。因此私钥恢复归约到分解。

私钥恢复的算法也可以用于分解：先取得有效 $d$ ，计算正数 $K=ed-1$ ，再运行第8—11章的随机分解算法。因此分解随机归约到私钥恢复。该算法总能核验输出的因子，期望运行时间为多项式；也可限制重试轮数，得到失败概率可控的有界时间算法。

知道 $d$ 以后，快速幂给出 $t=x^d\bmod n$ ，所以RSA反演归约到私钥恢复。综合起来，允许随机化归约时可写成

$\text{RSA反演}\ \le_{\mathrm{rand\text{-}poly}}\ \text{私钥恢复}\ \equiv_{\mathrm{rand\text{-}poly}}\ \text{分解}.$

这里前一个归约实际可取确定性的；随机性用于从私钥到分解的方向。本章的等价性针对给定合法公钥的标准双素数RSA实例：比较同一 $n,e$ 下的分解任务与私钥恢复任务。

多项式等价说明的是可解性能够转移，不说明最佳算法的实际耗时相同。算法的次数、成功概率与输入位长仍要分别记录。具体私钥与分解联系可参照《Handbook of Applied Cryptography》Fact 8.6。

13.5 为什么反演能力不自动交出私钥

假设有一个程序，输入 $x$ 就输出它的RSA原像 $t$ 。它给出的是幂映射的输出能力，并没有直接给出整数 $d$ 。第8章的分解算法需要明确的 $K=ed-1$ ；不能因为程序会做私钥运算，就把这个未知整数当作已知。

即使程序可处理任意输入，也不能凭上述证明断言能从它恢复 $d$ 或分解 $n$ 。一般RSA反演到分解的多项式归约仍不是这里已有的结论；关于两者关系，参照《Handbook of Applied Cryptography》Remark 8.7。

逻辑上， $B\le_P A$ 允许从“A容易”推出“B容易”，也允许从“B困难”推出“A困难”；却不允许从“A困难”推出“B困难”。因此相信分解困难，仍不足以仅靠上面的归约证明RSA反演困难；同时，尚未证明等价也不足以证明反演严格更容易。

13.6 已知数值对为什么未必多出私钥信息

只用公钥，也能生成一个满足原始RSA等式的数值对：先选 $t$ ，再算 $x=t^e\bmod n$ 。随后 $t^e\equiv x$ 当然成立；由于RSA幂映射是置换，这个 $t$ 也就是 $x$ 的原始RSA签名值。

所以，如果某算法只需要任意有效数值对 $(x,t)$ 就能高效恢复有效 $d$ ，可以先用公钥制造这样的数值对，再调用它，最后分解 $n$ 。这是一个算法转换，不是因为“数值对没有任何信息”而直接宣告不可能。

还要核对算法要求的输入分布：若要求 $x$ 在 $U_n$ 上均匀，先均匀选 $t\in U_n$ ，置换保证 $x=t^e$ 也均匀；若算法要求特定消息格式、额外签名样本或特殊输入，不能直接说这个构造满足全部条件。PSS的有效消息—签名对还要满足编码验证，不能用任意 $x,t$ 替代。

13.7 修改签名的字节，与伪造有效签名

消息和签名都是可被修改的字节串。签名的作用是让验证者检查收到的消息是否与该签名相符，而不是阻止攻击者写入新字节。

在原始RSA中，若把代表值 $x$ 换成不同的 $x'$ ，保留 $t$ 就不能通过等式验证。若同时换成 $t'$ ，就必须满足 $(t')^e\equiv x'\pmod n$ 。对预先给定的原始代表值 $x'$ ，这个要求正是RSA反演。

但不能把一切伪造攻击都直接归为“求一个独立RSA挑战的原像”。攻击者可能已取得合法签名，甚至可以请求签名；这些额外能力会改变计算任务。下一节说明原始RSA怎样利用这种额外信息。

13.8 原始RSA的乘法性质怎样产生伪造

若已有两组合法原始签名 $t_1^e\equiv x_1$ 、 $t_2^e\equiv x_2$ ，相乘得到

$(t_1t_2)^e\equiv x_1x_2\pmod n.$

所以 $t_1t_2\bmod n$ 是 $x_1x_2\bmod n$ 的签名。若乘积代表此前未获签名的消息，就得到一个新消息的有效签名。这说明反演困难也不能单独保证原始RSA签名安全。

允许请求原始签名时，还可对指定目标 $x\in U_n$ 构造攻击。选一个可逆 $r$ ，令

$y=xr^e\bmod n.$

选取满足 $y\ne x$ 的 $r$ ，请求 $y$ 的合法签名 $s=y^d\bmod n$ 。因为 $r^{ed}\equiv r$ ，有 $s\equiv x^d r\pmod n$ ，于是

$t=sr^{-1}\bmod n \quad\Longrightarrow\quad t^e\equiv x\pmod n.$

这里仅请求了其他代表值的签名，就得到目标 $x$ 的签名。逆元和快速幂都可高效计算；攻击利用了签名接口，所以不意味着已经找到只输入 $n,e,x$ 的通用反演算法。

这也补足“随便生成的 $x$ 没有实际意义”的讨论：简单反向构造确实不能让攻击者自由指定 $x$ ，但在更强的攻击模型中，原始RSA仍会出现针对指定目标的伪造。若消息还需经过编码，上述请求的 $y$ 未必是某条消息的合法编码，攻击步骤就不能直接照搬。

13.9 PSS怎样把实际消息与RSA运算接起来

RSA-PSS先对实际消息 $m$ 计算哈希，再结合盐和掩码生成函数按EMSA-PSS规则编码为字节串 $EM$ ；将它转换成整数代表 $x$ ，最后计算 $t=x^d\bmod n$ 。简记为

$m\ \xrightarrow{\text{哈希与PSS编码}}\ EM \ \xrightarrow{\text{转成整数}}\ x \ \xrightarrow{\text{RSA私钥运算}}\ t.$

验证者从 $t$ 计算 $x'=t^e\bmod n$ ，转回编码字节串，检查编码结构、位长、盐与消息哈希的一致性。盐可由编码恢复，验证者不需要事先保存签名时使用的盐。

因此攻击者先选 $t$ 算出的 $x'$ ，还必须通过完整PSS验证。它不一定是合法PSS编码，更不一定与攻击者想要的 $m'$ 一致。不能把这个要求简化为 $H(m')=x'$ ：PSS的RSA输入代表不是一个裸哈希值。

原始RSA的乘法性质仍存在，但两个合法编码代表的乘积未必是任何目标消息的合法编码。因此原始数值域中的攻击不再自动成为PSS消息域中的攻击。这个观察解释编码的作用；PSS的安全性还需正式归约，而不是仅由“乘积通常格式不对”证明。操作规则参照RFC 8017 §8.1.1—8.1.2及§9.1。

13.10 为什么“没有攻击意义”仍可能违反安全定义

实际攻击可能要求伪造有意义的转账指令。形式化签名安全采用更严格、也更便于分析的标准：允许攻击者拿到公钥并请求若干消息的签名，最后它必须难以输出一条此前未请求签名的新消息及其有效签名。这里允许请求的接口称为签名预言机；它是安全模型给攻击者的能力，不是说攻击者知道私钥。

攻击者可以根据先前答复选择下一条请求。如果输出的新消息通过验证，即使内容没有实际用途，也算赢得这个攻击实验。这称为选择消息攻击下的存在性不可伪造性，缩写EUF-CMA。定义与实验见Boneh–Shoup《A Graduate Course in Applied Cryptography》§13.1。

“选择消息攻击”描述攻击者能选择请求签名的消息；“存在性伪造”描述最终只需伪造某条新消息。两者不矛盾。希望伪造一条预先指定消息，是更具体的目标；若不说明目标何时选定，本章不把它直接命名为selective forgery。

原始RSA把整数代表本身当作消息，先选 $t$ 再算 $x$ 的构造已经破坏这种标准，即使 $x$ 毫无实际意义。PSS把实际消息作为输入，必须在消息域上判断伪造是否成立。普通EUF-CMA也不要求排除“同一已签消息的另一份新签名”；那是更强的安全定义，不能混在一起。

13.11 可证明安全到底证明了哪一步

RSA假设描述一个随机挑战实验：按指定方式生成合法公钥，均匀选取 $u\in U_n$ ，计算 $x=u^e\bmod n$ ，只向攻击者提供 $n,e,x$ 。假设随着参数位长增加，任何经典概率多项式时间算法都不能以非可忽略的概率恢复 $u$ 。这里“可忽略”指最终小于任意固定的位长负幂，排除了仍有逆多项式成功率的攻击。它是关于实例分布和成功概率的假设，不是声称每个输入都难。

签名安全证明则从一个假设存在的伪造算法出发，构造一个解决RSA挑战的算法。构造必须处理攻击者的签名请求，并定量控制运行时间和成功概率。因此，若反演困难，就能在证明条件下推出伪造也困难。

PSS的相关证明把哈希和掩码生成函数理想化为随机预言机：对同一个输入始终给出同一个输出，对新输入按规则给出独立均匀输出。这是模型条件；实际固定哈希函数不是数学上真正的随机预言机。RFC 8017 §8.1明确以该模型说明PSS伪造与RSA反演的联系。本文解释归约的含义，不重现PSS的完整安全证明。

需要分别记录三个判断：归约在指定模型下成立，是数学证明；RSA反演对相应随机实例困难，是假设；现实部署能否抵抗已知攻击，还涉及参数与实现。不能从其中一个判断直接省略另外两个。

13.12 为什么没有无条件困难性证明仍会研究和使用

未证明某个问题困难，并不等于已找到容易的解法；长期未发现高效攻击，也不等于已经证明永远不存在。密码学的做法是明确假设、公开分析攻击，并用归约说明方案是否额外引入了可利用的弱点。

多项式归约是渐近结论，实际参数还需要结合已知算法的资源成本。即使数学模型中的归约成立，也不能自动涵盖不安全的随机数、错误的编码验证或实现泄漏。本章只解释安全依据，不给出现实系统的参数推荐，也不把原对话的安全强度表当作固定不变的数学定理。

原对话还提到一次一密和量子计算，作为边界比较即可。一次一密 $c=m\oplus k$ 在密钥独立均匀、与消息等长、保密且只使用一次时，可提供信息论保密：对每个固定 $m,c$ ，恰有一个 $k$ 产生这个 $c$ ，所以密文分布不随明文变化。但这个结论只谈保密，不自动提供消息认证；攻击者翻转密文位会相应翻转明文位。

上述RSA假设特意限定经典算法。Shor的量子分解算法表明，允许相应量子计算模型时，可以在多项式时间分解整数；这与“目前是否具备攻击具体密钥的硬件”是不同问题。算法来源见Shor的原论文。后量子标准与迁移时间属于会变化的工程信息，不在这份初等数论笔记中固定为结论。

13.13 用四个问题回查整条逻辑

回看一个RSA论断时，依次问：输入究竟是什么？要输出什么？攻击者还能请求哪些运算？结论在哪个模型与假设下成立？

论断	能得出的结论	不能省略的条件
已知有效 $d$	可构造 $ed-1$ 并随机分解 $n$	标准双素数实例， $ed-1>0$
已知某条原像 $t$	已解出当前 $x$ 的反演	未必得到有效 $d$
随便选 $t$ 再算 $x$	得到原始RSA有效数值对	未必对应目标消息或PSS合法编码
可请求原始RSA签名	可利用乘法结构伪造目标代表的签名	请求代表可被签名接口接受
PSS具有条件性安全证明	在相应模型、假设下限制新消息伪造	不是无条件困难性定理

你在对话末尾提出“这个 $x$ 不一定有攻击意义，攻击者不能随心所欲修改”，准确指出了反向构造的局限。接下来还要保留两点：形式化安全不以消息是否有用作为唯一判据；原始RSA在允许签名请求时仍可能伪造指定目标。把这两点与PSS的消息编码放在一起，才能从数学等式走到完整签名安全。

第 13 章：RSA反演、签名伪造与安全假设 ​

13.1 先分清消息、消息代表值与签名 ​

13.2 一组消息和签名约束了哪个指数 ​

13.3 三个计算问题各自要求输出什么 ​

13.4 归约符号为什么容易把方向写反 ​

13.5 为什么反演能力不自动交出私钥 ​

13.6 已知数值对为什么未必多出私钥信息 ​

13.7 修改签名的字节，与伪造有效签名 ​

13.8 原始RSA的乘法性质怎样产生伪造 ​

13.9 PSS怎样把实际消息与RSA运算接起来 ​

13.10 为什么“没有攻击意义”仍可能违反安全定义 ​

13.11 可证明安全到底证明了哪一步 ​

13.12 为什么没有无条件困难性证明仍会研究和使用 ​

13.13 用四个问题回查整条逻辑 ​