可证明安全的思想 可证明安全的思想就是给定一个算法A，我们提出一个新算法BA，BA把A作为子程序。输入给BA的是我们希望解决的困难问题，输入给A的是某个密码算法。然而，如果A是一个积极攻击敌手，即A可以对输入的公钥进行解密预言询问或签名预言询问。算法BA要想使用A作为子程序，就需对A的询问提供回答。算法BA需要应对以下几个问题： 它的回答应该看起来是合法的。因为加密应该能够解密，签名应该能够被验证，否则，算法A就知道它的预言机在撒谎。算法BA就不能再确保算法A是以一个不可忽略的概率成功。 它的回答应该与如果预言机是真正的解密/加密预言机时A期望的回答具有相同的概率分布。 自始至终，预言机的回答应该是一致的。 算法BA需要在不知道私钥的情况下提供这些回答。

2．数字签名体制的安全性概念 对于数字签名体制，存在以下几种伪造类型： （1）完全攻破:敌手能够产生与私钥持有者相同的签名，这相当于恢复出了私钥。 （2）选择性伪造:敌手能够伪造一个他选择的消息的签名。 （3）存在性伪造:敌手能够伪造一个消息的签名，这个消息可能仅仅是一个随机比特串

分叉引理 我们首先来介绍一下分叉引理，它适用于下面类型的数字签名算法： 为了对消息m签名，签名者执行如下步骤： ①签名者产生一个承诺 。 ②签名者计算 。 ③签名者计算 ，它是关于 和u的“签名”。 签名算法的输出为 。 在DSA中， ， ， ，这里，r = (gk mod p) mod q。