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

Subversion Attack and Improvement of ECDSA Signature Scheme

作　　者：严都力 禹勇 李艳楠 李慧琳 赵艳琦 田爱奎[4] YAN Du-Li;YU Yong;LI Yan-Nan;LI Hui-Lin;ZHAO Yan-Qi;TIAN Ai-Kui(School of Computer Science,Shaanxi Normal University,Xi’an 710119,China;State Key Laboratory of Cryptology,Beijing 100878,China;School of Computer and Information Technology,University of Wollongong,Wollongong 2522,Australia;School of Computer Science and Technology,Shandong University of Technology,Zibo 255049,China)

机构地区：[1]陕西师范大学计算机科学学院,陕西西安710119 [2]密码科学技术国家重点实验室,北京100878 [3]School of Computer and Information Technology,University of Wollongong,Wollongong 2522,Australia [4]山东理工大学计算机科学与技术学院,山东淄博255049

出　　处：《软件学报》2023年第6期2892-2905,共14页Journal of Software

基　　金：国家自然科学基金(61872229,U19B2021);教育部2020年度区块链核心技术战略研究项目(2020KJ010301);陕西省重点研发计划(2020ZDLGY09-06,2021ZDLGY06-04)。

摘　　要：斯诺登事件揭露了某些密码体制的确存在被颠覆的事实.椭圆曲线数字签名算法(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.

关 键 词：斯诺登事件 ECDSA签名 比特币 颠覆攻击 哈希函数 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]