动机
加密的目的是隐藏消息。数字签名通常让消息保持公开,而是让任何人都能验证该消息确实经密钥持有者授权。把 RSA 的指数运算等式反过来使用,就得到一个候选的签名规则,但安全目标必须改变:敌手可以请求对自己选定的消息的签名,然后尝试授权一条新的消息。
原始 RSA 因一个初等的代数攻击而达不到这一目标。先对消息做哈希再签名是一种可能的修补,但“哈希”一词本身并不是安全假设。我们分析一个理想的随机函数,其取值遍布 RSA 置换的整个定义域。在该模型中,归约可以把一个 RSA 求逆挑战放在某个未知的预言机查询处,并利用已知的根来回答其余查询。
证明包括选中该查询的概率、重复查询的一致性,以及有界的公平比特采样。它给出的是理想模型中的条件性定理,并不认证某个固定的真实哈希函数、某种标准化的签名编码或某个已部署的实现。
定义
假设给定一个可高效生成的 RSA 密钥族,其安全参数为 ,并以 的形式公开提供。模数为 ,其中 是不同的奇素数,其比特长度是 的多项式,且 。指数 与 互素,秘密指数满足 。记 。先前的 RSA 算术已证明 是 上的置换,其逆为 。
这里使用的 RSA 单向性假设是:任何有界的概率多项式时间算法,在给定公钥以及在 中均匀取值的 时,仅以可忽略的概率找到满足 的单位 ,该概率同时对所生成的密钥取平均。“可忽略”沿用先前以反多项式渐近方式给出的定义。密钥族和该假设都是给定的前提;我们并不断言 RSA 求逆与因数分解等价。
在选择消息伪造实验中,敌手获得公钥,可以请求对多项式个消息的签名,最后输出 。当验证通过且 从未被请求签名时,敌手获胜。这就是选择消息攻击下的存在性不可伪造性。重复一个已被签名消息的签名在该实验中不算获胜。
对于原始 RSA,消息属于 ,签名返回 。对于全域哈希,消息是多项式长度的比特串,一个理想的随机预言机 把它们映射到 :
随机预言机对每个新的字符串给出独立均匀的单位作为回答,并在之后的调用中重复其已保存的回答。它是一个数学上的预言机模型,而不是普通的固定哈希算法。敌手可以同时访问这个预言机和签名预言机。
定理/命题
定理 4.3.1
(正确性并不能阻止原始 RSA 的伪造)
上述两种签名规则都能通过对其诚实生成的签名的验证。然而原始 RSA 允许在不做任何签名查询的情况下成功伪造:任选一个单位 ,构造 ,输出 。它还允许把两个签名相乘,得到这两条消息之积的签名。
定理 4.3.2
(全域哈希的条件性安全)
固定可计算的多项式上界 ,分别界定敌手的哈希查询数和签名查询数。设它在理想实验中以概率 伪造成功。令 ,并令 为不小于 的最小的 2 的幂。则存在一个有界的多项式时间 RSA 求逆算法,其成功概率至少为
因此,RSA 单向性假设蕴含该随机预言机模型中的伪造概率可忽略。最后多出的一次查询,使得对一条此前从未被哈希过的伪造消息也能进行验证。
证明思路或证明
证明
(指数求逆,以及先选定根)
对每个单位 ,指数求逆给出 。取 或 ,即证明了正确性。但原始验证等式也可以这样满足:先选定签名,再计算其对应的消息。存在性伪造让敌手自行选择伪造哪一条新消息,因此它无需对预先给定的目标求逆。
同样地,若 且 ,则 。当该乘积是一条新消息时,这一对数据就是一次选择消息伪造。全域哈希把所需的等式改为一个新鲜而独立的预言机取值;两个早先哈希值之积,未必是任何所选新消息的哈希值。
全域哈希的安全性证明分为三部分:用选定的根模拟哈希预言机;把挑战隐藏在被猜测的表项中;以及一个有界采样器,其代价由耦合来计算。
证明
(模拟预言机、植入挑战、限制采样)
通过选择根来模拟哈希回答。 对于任何普通的新哈希查询,在 中均匀选取 ,返回 作为哈希值,并保存这两个数。由于指数运算是置换,返回值在 中均匀分布。不同的新选择给出相互独立的哈希回答;与随机函数完全一样,允许出现碰撞。对该消息的签名查询,可以用已保存的 来回答,它正是签名规则所要求的唯一的根。
如果某条消息首先是通过签名请求而出现的,则在返回根之前,以同样方式为它建立哈希表条目。重复的哈希或签名请求复用该条目。新条目的总数(包括对伪造消息的最终验证)至多为 。如果只计入敌手显式的哈希调用,就会漏掉由签名和验证所产生的条目。
把求逆挑战隐藏在一个随机条目中。 给定一个 RSA 挑战 ,归约恰好使用 个公平比特,在 中均匀选取 。在第 个新表项处,它返回 ,而不是自己生成的 。其根是未知的。若该消息被请求签名,归约报告失败。所有其他条目与签名按上述方式模拟。如果敌手最终对该特殊消息伪造成功,那么通过验证的签名就是 的一个 次根,从而解决了求逆挑战。
要看出为什么即使查询是自适应的,成功概率仍然含有 ,先分析一个假想的完美实验,它知道秘密密钥,甚至能回答特殊消息的签名查询。挑战 是均匀的,因此无论选中哪个位置,每个哈希条目都具有正确的独立均匀分布。签名是其条目的唯一的根。所以这个完美实验中敌手的完整转录与 无关。
在任何一个成功伪造的转录中, 的第一个表项有某个下标 。由于 独立且均匀,它等于该下标的概率为 。在此事件上,根据获胜实验中的新鲜性要求,该特殊消息从未被签名。因此,实际的归约从不会遇到其特殊的中止情形,并且一直到伪造发生都沿着完全相同的转录进行。在理想的单位采样下,其成功概率至少为 。完美实验只是分析的工具;实际实现的归约从不使用秘密指数。
使每一次模拟采样的运行都有界。 要从 中精确均匀采样,一般无法在没有失败分支的情况下使用固定数目的公平比特。令 。抽取一个均匀的 比特整数,若它小于 且与 互素则接受。每个被接受的整数都是均匀的单位。由于
每次尝试成功的概率至少为 。互素性由多项式时间的欧几里得(Euclid)算法检验,不需要对 做因数分解。
把每次求根采样调用限制在 次独立尝试以内,若达到上限则报告求逆失败。其失败概率至多为 。这样的调用至多有 次,所以某个上限改变了被模拟的实验的概率至多为 。
为精确起见,把每次带上限的调用与使用相同尝试比特的理想的无上限采样器耦合。在第一次触及上限失败之前,两者的输出一致。在以所有过去的转录为条件时,下一批新的尝试具有同样的成功界,所以并集界可以控制首次失败的概率。从理想求逆的成功概率中减去耦合失败的概率,即证明了该定理,并且所有采样、建表和指数运算的工作量都有多项式最坏情形上界。
由于 且 有多项式上界,若在无穷多个长度上伪造概率不可忽略,则在减去可忽略的采样项之后,这些长度上的求逆概率也不可忽略。这正是 RSA 单向性所要求排除的矛盾。
猜测的下标和耦合,是这个论证最容易悄悄出错的两处,值得单独拆开来看。
证明透视
猜测、新鲜性规则与耦合在哪里起作用
是置换这一性质用了一次:它使 均匀分布,所以模拟的哈希表恰好具有随机预言机的分布;它也使已保存的 成为唯一有效的签名。挑战 同样是均匀的,因此完美转录与 无关。只有先确立了这种独立性,才能说 的概率为 ;先条件化、再断言选择无偏,就是循环论证。
新鲜性正是消除归约唯一无法完成的那次模拟的假设。成功的伪造所用的消息从未被签名,所以在事件 上,特殊条目从不被请求签名,归约的中止分支永远不会出现。若没有新鲜性,重放的签名就能获胜,而被植入的条目也可能必须被签名。
耦合取代了一个诱人但无效的步骤,即以每个带上限采样器都成功为条件:在自适应运行中,后来的调用依赖于先前的输出,这种条件化可能重新加权各种历史。在相同尝试比特上比较带上限与无上限的采样器,只需并集界 。最后, 使损失因子保持多项式,这才把不等式变成与单向性的矛盾。
例题详解
例题 4.3.3
(玩具群中先给签名的伪造)
取 ,,则 ,秘密的逆指数为 ,因为 。选取单位 。其立方为 ,所以 不需任何签名查询就能通过原始 RSA 的验证。攻击者并没有对指定的 RSA 挑战 求逆;它先选定了一个根,从而选择了消息。这个小模数只是正确性的示例,可以立即被分解。
例题 4.3.4
(把两个被请求的签名相乘)
在同一个玩具密钥下,消息 和 的签名分别为 和 ,因为 、。相乘得到签名 ,对应新消息 ,因为 。因此,请求两个签名就在没有秘密指数的情况下授权了第三条消息。
在全域哈希中,把签名相乘得到的是 的一个根。对于一个新鲜选定的字符串 ,其独立哈希恰好等于这个特定单位的概率为 ,而不是由某个代数恒等式保证。这一观察解释了旧攻击为何不再自动奏效;而完整的条件性定理是由归约证明的,并非仅靠这一观察。
例题 4.3.5
(一个挑战槽位与一次较晚的哈希查询)
设想归约选中了 。前两个新字符串得到模拟值 和 ,在玩具密钥下保存的根分别为 和 ,它们都能被一致地签名。第三个不同的字符串得到求逆挑战 。对这个新字符串的一个有效签名 ,就会对该挑战求逆。
如果敌手从未显式查询该字符串,则第三个条目可能直到最后验证时才被创建。它仍然属于被猜测的表项顺序,这正是计数中要多算一次的原因。反过来,如果敌手请求归约对这条特殊字符串签名,模拟就会中止;这样的转录不可能是概率下界中所用的、与之匹配的新鲜消息成功事件。
常见错误
常见错误
(随机预言机证明并不是关于每个固定哈希的定理)
模拟依赖于选择独立的哈希输出,并在其中一个输出处植入挑战。一个固定的、已公开的哈希算法并不给归约这种编程能力。该定理只在其明确的理想模型中、并在 RSA 单向性之下确立安全性。具体的编码、标准与实现保证需要另行分析。
常见错误
(单向性关乎一个预先给定的随机目标)
安全假设所涉及的是对一个随机的、预先给定的群元素求逆,而不是不可能产生任何有效的签名等式。原始方案先给签名的攻击不必求任何逆就产生有效的一对 ,因此并不与单向性矛盾。重复查询、哈希碰撞和新鲜消息的验证都属于实验本身;把它们从模型中删去,会简化掉证明中真正的义务。
常见错误
(只计算显式的哈希查询)
取 会遗漏由签名请求以及对 的最终验证所创建的表项。若被伪造的消息从未被显式哈希,它的条目是最后创建的一个,下标可达 ;只按 选定的猜测范围可能在该下标之前就结束,那么猜测永远不会命中。
总结
仅有正确的 RSA 指数运算,并不能给出不可伪造的签名。全域哈希为每个字符串提供一个理想的独立目标。被猜测的新表项嵌入求逆挑战,而所选的根回答其余的每个查询。有界采样和显式的耦合完成了这个条件性的随机预言机证明,既没有隐藏非二进制的随机选择,也没有隐藏期望时间的假设。
练习
快速检查
(为什么返回一条旧消息及其已经得到的签名,不能赢得所述实验?)
重读伪造实验的获胜条件。
解答
实验要求被伪造的消息从未被签名。否则敌手总能通过重放一条已授权的消息而获胜,而这并不是该定义所要衡量的授权失败。更强的安全概念可以进一步考虑旧消息上的另一些签名。
快速检查
(为什么归约要同时保存模拟的哈希值和它所选的根?)
考虑之后对同一字符串的哈希调用和签名调用。
解答 · 答案
该值必须在之后的哈希调用中被一致地重复。已保存的根使归约能够在不知道秘密密钥的情况下,对之后的签名调用给出该值所要求的那个唯一的签名。
快速检查
(为什么猜测取自包含 的 2 的幂区间,而不是声称能从任意的 中以有界比特精确均匀采样?)
数一数在 个位置中均匀选择所需的公平比特。
解答
2 的幂区间恰好使用固定数目的公平比特。未被使用的位置只是把成功概率的下界降为 ,而 ,因此仍保持反多项式的成功概率。对下标而言,不需要未说明的变时间采样器或有偏的取余规则。
快速检查
(如果简单地以所有自适应的带上限采样器都成功为条件,并宣称所得转录是理想的,会有什么问题?)
之后的查询可能依赖于先前的输出。
解答
在自适应过程中,之后的采样行为可能依赖于先前的输出,所以对全局成功的条件化可能会重新加权各种历史。改为在相同的新尝试比特上耦合带上限与无上限的执行,就能界定二者发生分歧的概率,而无需这样的分布性断言。
快速检查
(在玩具密钥 、、 下,计算消息 的原始 RSA 签名并加以验证。)
用反复平方计算 ,或直接寻找立方根。
解答
模 :,所以 ,因为 。于是 。验证:,而 ,因为 。所以签名为 ,并且如验证所要求,。