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

12.4.1 普通RSA Plain RSA

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

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

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

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

• Gen：在输入时，运行以获得（N，e，d）。公钥是< N，e>，私钥是< N，d>。

• Sign：输入私钥sk=< N、d>和消息时，计算签名。

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

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

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

无消息攻击 A no-message attack