区块链与密码学全民课堂第6-9讲：数字签名算法的可证明安全性

导语：本课堂用通俗易懂的系列内容为大家呈现区块链与密码学领域相关知识。这里有知识也有故事，从感兴趣到有乐趣，全民课堂等你来学。这个系列中的课程内容首先从比特币着手进行入门介绍，再延伸至区块链的相关技术原理与发展趋势，然后深入浅出地依次介绍在区块链中应用的各类密码学技术。欢迎大家订阅本公众号，持续进行学习。

【本课堂内容全部选编自PlatON首席密码学家、武汉大学国家网络安全学院教授、博士生导师何德彪教授的《区块链与密码学》授课讲义、教材及互联网，版权归属其原作者所有，如有侵权请立即与我们联系，我们将及时处理。】

6.9 数字签名算法的可证明安全性

– 可证明安全性的定义 –

可证明安全性是指这样一种「归约」方法：

首先确定密码体制的安全目标，例如，加密体制的安全目标是信息的机密性，签名体制的安全目标是签名的不可伪造性。

然后根据敌手的能力构建一个形式化的安全模型；最后指出如果敌手能成功攻破密码体制，则存在一种算法在多项式时间内解决一个公认困难的数学问题或公认安全的密码体质。

总之，可证明安全性就是利用反证法的思想把密码算法/协议规约到一个数学难题或密码体质，通过后者的困难性或安全性来证明前者的安全。

对于数字签名体制，存在以下3种伪造类型：

• 完全攻破：敌手能够产生与私钥持有者相同的签名，这相当于恢复出了私钥

• 选择性伪造：敌手能够伪造一个他选择的消息的签名

• 存在性伪造：敌手能够伪造一个消息的签名，这个消息可能仅仅是一个随机比特串

对于数字签名体制，存在以下2种伪造类型：

被动攻击：在被动攻击中，敌手被告知一个公钥，要求产生一个选择性伪造或存在性伪造。这是一种比较弱的攻击模型。

主动攻击：积极攻击中最强的攻击是适应性选择消息攻击(Adaptive Chosen Messages Attack)，即敌手可以访问一个签名预言机，它能够产生合法的签名。敌手的目标是产生一个消息的签名，当然这个消息不能是已经询问过签名预言机的消息。

对于一个安全参数为k的密码体制，如果敌手成功的概率大于1/p(k)，我们就说这个敌手以一个不可忽略的概率成功，这里的p是一个以k为变量的多项式。

可证明安全性的目的在于证明：如果一个敌手能够攻破一个密码体制的某个安全概念，那么我们就可以利用该敌手做一些认为不可能的事情。我们假设敌手A是一个主动攻击敌手，即对于Schnorr签名算法，他能进行签名询问。

我们现在希望能够构造一个新算法B_A，它能够在输入一个离散对数问题实例和调用多项式次敌手A的情况下，以一个不可忽略的概率求解离散对数问题。

算法B_A说明了如果存在敌手A，就存在一个多项式时间离散对数问题求解算法，能够以一个不可忽略的概率解决离散对数问题。

既然我们目前并不相信存在这样的离散对数问题求解算法，我们也可以断定这样的敌手A是不存在的。

– 随机预言模型 –

可证明安全的思想就是给定一个算法A，我们提出一个新算法B_A，B_A把A作为子程序。输入给B_A的是我们希望解决的困难问题，输入给A的是某个密码算法。

然而，如果A是一个积极攻击敌手，即A可以对输入的公钥进行签名预言询问。算法B_A要想使用A作为子程序，就需对A的询问提供回答。算法B_A需要应对以下几个问题：

• 它的回答应该看起来是合法的。因为加密应该能够解密，签名应该能够被验证，否则，算法A就知道它的预言机在撒谎。算法B_A就不能再确保算法A是以一个不可忽略的概率成功。 

• 它的回答应该与如果预言机是真正的解密/加密预言机时A期望的回答具有相同的概率分布。

• 自始至终，预言机的回答应该是一致的。

• 算法B_A需要在不知道私钥的情况下提供这些回答。

我们必须让B_A在不知道私钥的情况下能够签名，但既然我们的体制是安全的，这一点意味着是不可能的。为了回避这个问题，我们通常使用随机预言模型。

• 随机预言是一个理想的哈希函数。对于每一个新的询问，随机预言产生一个随机值作为回答，如果进行两次相同的询问，回答一定相同。

• 在随机预言模型中，我们假设敌手并不使用密码算法中定义的那个哈希函数，而是使用预言机查询得到哈希运算的结果。

• 对于A的签名预言询问，算法B_A是通过欺骗随机预言的回答来适合自己的需要的。

– 分叉引理 –

如果算法B_A使用随机预言运行敌手A一次，并成功获得一个消息m的两个签名。当算法B_A使用不同的随机预言再运行敌手A一次时，B_A能够以一个不可忽略的概率获得这个消息m的另外一个签名。[1]

– Schnorr数字签名算法的安全性证明 –

假设p和q是大素数，且q能被p-1整除，q是大于等于160 bit的整数，p是大于等于512 bit的整数，保证GF(p)中求解离散对数困难；g是GF(p)中元素，且g^q≡1 mod p。

密钥生成

• Alice选择随机数x为私钥，其中1<x<p

• Alice计算公钥y≡g^x (mod p)

签名算法 

• Alice首先随机数k，并计算K=g^k mod p，这里1<k<q

• Alice计算e=h(M, K)

• Alice计算s=k–x·e(mod q) 

• Alice输出签名(e, s)

验证算法

• Bob计算g^k=g^s·y^e mod p     

• Bob验证e=h(M, g^k mod p)

• 如果相等则输出「Accept」，否则输出「Reject」

– RSA-PSS数字签名算法的安全性证明 –

定理：在随机预言模型中，假设离散对数问题是一个困难问题，RSA-PSS数字签名算法在主动攻击下是安全的。

密钥生成 

• 生成一个模数n，一个公钥e和一个私钥d

• 假设安全参数为k(n是k比特的数)，我们定义两个整数k₀和k₁并且满足：k₀+k₁≤k–1

然后我们定义两个哈希函数：

扩展数据：

压缩数据：

签名算法

为了对一个消息m进行签名，签名者执行以下步骤：

• 生成一个随机数

• 计算w=H(m||r)

• 设置y=0||w||(G₁(w)⊕r)||G₂(w)

• 计算s=y^d mod n

• 消息m的签名为s

验证算法

为了对一个消息m进行的签名s进行验证，验证者执行以下步骤：

• 计算y=s^e mod n

• 将y分解成: b||w||α||γ，其中b的长度为1比特，w的长度为k₁比特，α的长度为k₀比特，γ的长度为k–k₀–k₁-1比特

• 计算r=⊕G₁(w)

• 当且仅当下列等式成立时，接受该签名：b=0, G₂(w)= γ，且w=H(m||r)

今天的课程就到这里啦，数字签名算法单元的学习就结束啦，同学们记得复习哦~下节课开始我们将进入盲签名的学习，敬请期待！

同学们可以关注PlatON World，持续学习哦。我们下节课见啦。