在公钥与私钥加密的情况下，“本机”签名方案的效率比消息认证码低几个数量级。幸运的是，与混合加密一样（见第11.3节），至少对于足够长的消息，可以以私钥操作的渐进成本获得数字签名的功能。这可以使用下面讨论的哈希和签名方法来完成。

散列和符号方法背后的直觉是直截了当的。假设我们有一个长度为l的消息的签名方案，并希望对一个（较长的）消息进行签名. 我们可以使用散列函数H将消息散列到长度为l的固定长度摘要，然后对结果摘要进行签名，而不是对m本身进行签名。该方法与第5.3.1节中讨论的哈希和MAC方法完全类似。

构造 12.3 哈希和符号范式

设∏=（Gen，Sign，Vrfy）是长度为了l（n）的消息的签名方案，设是输出长度为l（n）的哈希函数。构造签名方案∏'=（Gen'，Sign'，Vrfy'），如下所示：

• Gen'：在输入时，运行获得（pk，sk），运行获得s；公钥是< pk，s>，私钥是< sk，s>。

• Sign'：输入私钥< sk、s>和消息时,输出σ← Signsk（Hs（m））。

• Vrfy'：输入公钥< pk，s>，消息, 签名σ，当且仅当时输出1。

定理 12.4

如果∏是长度为l的消息的安全签名方案，且∏H是抗冲突的，则构造12.3是安全签名方案（用于任意长度的消息）。

该定理的证明与定理5.6的证明几乎相同。