RSA 全域哈希签名

模拟器没有长期私钥，却可以先选一个“已经知道签名”的随机u，再把它的公开e次幂安排成哈希答复。攻击者看到的仍是均匀单位；其后请求这条消息的签名，模拟器直接交出u。

唯一例外是被猜中的消息，它的哈希是待反演挑战。模拟器希望攻击者最终在这里伪造，而不提前请求这里的签名。新消息伪造条件正好保证：如果猜中了最终获胜消息，这一项此前不可能被要求签名，中止分支便不会发生。

一张四行模拟表 ​

教学RSA取$N=11\cdot 13=143,e=7,d=43$。固定挑战逆像17仅供验算，挑战$Y={17}^{7}mod143=30$。依次处理哈希a、签名b、哈希c以及最终新消息d。若猜$J=4$，其他行选择逆像2、3、5，得到哈希答复128、42、47；b的签名就是3，d行答复30。攻击者若给出d的有效签名17，模拟器恢复挑战逆像。

若猜$J=2$，b行答复30，但下一步必须给b签名，模拟器中止。若猜1或3，d不是挑战行，即使d上的伪造有效，也不能从这条输出反演Y。这里四种猜法只有一种命中；下载器用知道教学d的模拟“全能伪造者”演示这些分支，不把它称为现实RSA攻击。

为什么还要处理未查过的消息 ​

攻击者可能直接输出一对消息和猜测签名，从未查询该消息的哈希。真实验证者仍会计算该哈希，成功概率并不被定义为零。因此归约把最后验证所需的新表项也计入，Q中保留加1；不能因“正常攻击者应该先查哈希”就删掉该事件。

不先哈希的textbook方案更直接失守：任取单位$\sigma$，再令$M={\sigma }^{e}modN$，便得到一份有效新消息签名，完全不需要私钥。FDH把待签对象固定为某个消息的哈希，攻击者不能这样倒过来任意指定消息的语义。

成功概率与唯一签名 ​

将真实的完整获胜轨迹和一个独立均匀J配对。最终新消息有一个不超过Q的首次出现编号；J恰好等于它的概率为$1/Q$。在这一事件上，模拟器此前没有给挑战行签过名，全部答复分布正确，且最后签名就是Y的逆像。因此

这是直接按全部首次请求编号得到的较松界。更精细的归约可以不为签名先出现的行支付同样损失；这里不把这个简易界称作最紧结果。概率包含密钥生成、随机预言机、挑战、攻击者随机币和模拟器猜测。量子查询、现实哈希替换、相关密钥和侧信道都不在这条经典ROM证明里。

固定公钥和消息后，RSA置换只有一个逆像，规范整数编码又只有一种表示。所以FDH具有唯一接受签名：在相同接口下，强不可伪造的新增获胜情形不会比普通新消息情形更多。若解析器接受$\sigma +N$之类非规范表示，这个字节级结论就失去前提。

下载器的具体字节实验 ​

下载器另给可执行的教学hash-to-unit：先对包含域、N、e和消息的无歧义编码求SHA-256，再以四字节计数器和MGF1扩展到$\lceil \mathrm{bitlen}(N)/8\rceil$字节，掩去多余高位，拒绝0、至少N或不互素的候选。对于固定消息，使用同一输入和计数器重现同一结果。它显示全宽编码及拒绝路径；其固定SHA-256输出不被声称是数学上均匀随机预言机。

本例消息字段为Theoryroad/lesson/v1、signature、allow=demo，结果哈希单位42、签名3，第二次候选才被接受。小N无安全性。换成另一消息类型或域后必须重新哈希；不能把域分离字段只写在显示标签里而不放进实际字节。

模拟器若出现t条表项，在把“均匀抽取单位”作为采样原语时，需要最多t次采样与t次公开模幂、O(t)个RSA域元素及保存消息字节。若从n位均匀整数实现该原语，则每次尝试还要检查范围并做gcd，成功概率为$\phi (N)/2^n$，期望尝试数为$2^n/\phi (N)$；这些随机采样及最大公因数成本应另外相加。散列表查找的期望基础工作另加所有读入消息的长度。签名、验证各增加一次相应指数模幂。若一份n位模幂用平方乘法实现，需O(n)次模乘用于私钥指数，公开指数成本按其自身位数计。教学hash-to-unit在先预哈希消息后，每次候选扩展O(n)位并做一次gcd；实际尝试次数单独计，不对固定哈希许诺确定上界。

签名执行实验要求读者改变查询顺序：先签b、再重复哈希b，观察编号只在第一次出现时增加；再输出一个从未查过的新消息，核对最后插入与猜测条件。迁移中若攻击者输出已签过的b，即使碰巧命中J，也应先判定它不满足新消息获胜事件。