ECDSA签名方案的颠覆攻击与改进

Subversion Attack and Improvement of ECDSA Signature Scheme

斯诺登事件揭露了某些密码体制的确存在被颠覆的事实.椭圆曲线数字签名算法(elliptic curve digital signature algorithm,ECDSA)在同等安全强度下,因其签名长度短而被广泛应用,如被用于比特币交易单的签名.ECDSA签名算法是否会被颠覆且存在修复方法仍是一个挑战.正面回答了这一问题:首先利用伪随机函数(pseudorandom function,PRF)计算k替换ECDSA签名中使用的随机数k,实现了对ECDSA签名的颠覆,使得敌手只需获得至多3个连续签名就能够提取出签名私钥;然后,将签名私钥、签名消息与其他随机签名组件的哈希值作为签名算法的第2个随机数,对ECDSA签名进行了改进,提出了抗颠覆攻击的ECDSA签名,即使敌手替换新签名算法的某个组件,也无法提取签名私钥的任何信息;最后,对提出的算法与已有算法进行了效率测试,实验结果证明了提出的算法在计算复杂度与算法执行效率方面都具备优势.

The Snowden incident revealed the fact that certain cryptosystems were indeed subverted.Elliptic curve digital signature algorithm(ECDSA)has been widely used due to its short signature length advantage under the same security level,for example,signing bitcoin transactions.However,whether the ECDSA can be subverted and how to resist this attack remain a challenge.This study answers this question positively.Firstly,it is shown that how to use a pseudorandom function(PRF)to calculate a random value to replace the randomness used in the ECDSA.The subverted ECDSA enables an adversary to extract signing private key by obtaining at most three consecutive signatures.Secondly,the hash value of private key,message,and the random signature component are used as the second random number to improve the ECDSA scheme,and as a result,the signature scheme against subversion-resistant attack is proposed.Even an adversary replaces the component of the new signature algorithm,it cannot extract any information of the signing key.Finally,the proposed algorithm and existing algorithm are implemented,and the implementation demonstrates that the proposed scheme has advantages in terms of computational complexity and efficiency.