我们从讨论基于RSA假设的签名方案开始考虑具体的签名方案。

12.4.1 普通RSA Plain RSA

我们首先描述一个简单的、基于RSA的签名方案。虽然该方案不安全,但它是一个有用的起点。

通常,让GenRSA作为一种ppt算法,在输入alt上,输出两个N位素数(概率可以忽略不计的除外)的乘积的模N,以及满足ed = 1 mod φ(N)的整数e,d。普通RSA中的密钥生成只需要运行GenRSA,并输出< N,e>作为公钥,< N,d>作为私钥。签名alt,签名者计算alt。通过检查alt来验证消息m上关于公钥< N,e>的签名σ。参见构造12.5。

构造 12.5 纯RSA签名方案 The plain RSA signature scheme

让GenRSA如文中所示。按如下方式定义签名方案:

  • Gen:在输入alt时,运行alt以获得(N,e,d)。公钥是< N,e>,私钥是< N,d>。

  • Sign:输入私钥sk=< N、d>和消息alt时,计算签名alt

  • Vrfy:输入公钥pk=< N,e>,消息alt和签名alt,当且仅当alt时输出1。

很容易看出,对合法生成的签名的验证总是成功的,因为alt

人们可能认为该方案是安全的,因为对于只知道公钥< N,e>的对手来说,计算消息m上的有效签名似乎需要解决RSA问题(因为签名正是m的eth根)。不幸的是,这种推理是不正确的。首先,RSA假设只意味着计算统一消息m的签名(即计算eth根)的难度;它并没有说明在非均匀m或攻击者选择的某个消息m上计算签名的难度。此外,RSA假设没有说明一旦攻击者了解到其他消息上的签名,它可能会做什么。下面的示例演示了这两种观察结果都会导致对普通RSA签名方案的攻击。

无消息攻击 A no-message attack