基于椭圆曲线的可批量验证签名方案分析

doi:10.3778/j.issn.1002-8331.2411-0207

摘要/Abstract

摘要： 分析了Ruan等人提出的SM2数字签名批量验证方案和Wu等人提出的双参数椭圆曲线批量验证方案，从商用密码应用安全性评估角度进行了密码协议正确性和安全性两方面的验证。针对Ruan等人的方案，指出方案的正确性分析不成立，并基于底层代数结构的椭圆曲线上点加运算规则给出详细推理和测试过程；针对Wu等人的方案，基于生日攻击原理分析了Hash函数错误使用方式导致的消息碰撞概率增大，整体签名方案在安全性方面难以抵御伪造攻击，并通过伪造具体消息和签名值给出伪造攻击过程和测试结果，基于车联网用户和路侧单元之间的交互信息给出了仿真测试。最后，给出在商用密码应用过程中将经典签名方案转化成批量验证方案时需要注意的关键点。

关键词: 数字签名, 批量验证, 正确性分析, 安全性分析, 伪造攻击

Abstract: There are two schemes analyzed in this paper, one is the SM2 digital signature batch verification scheme proposed by Ruan et al., and the other is the dual parameter elliptic curve batch verification scheme proposed by Wu et al. The correctness and security are verified from the perspective of commercial cryptographic application evaluation. For Ruan et al.’s scheme, it is pointed out that the correctness analysis of the scheme is not valid, and a detailed reasoning and testing process is provided following the point addition operation rules on elliptic curves based on the underlying algebraic structure. For Wu et al.’s scheme, according to the birthday attack principle, the incorrect use of Hash functions leads to an increased probability of message collision, so that the overall signature scheme is difficult to resist forgery attacks. The specific forgery attack process and test results are provided by forging messages and signature values, for which simulation tests are conducted by the information between car networking users and roadside units. Finally, several key points are presented to note when classic signature scheme is converted into batch verification scheme in commercial cryptographic applications.

Key words: digital signatures, batch verification, correctness analysis, safety analysis, forgery attacks

项勇, 李艳俊, 王伊婷, 刘健, 丁漪. 基于椭圆曲线的可批量验证签名方案分析[J]. 计算机工程与应用, 2025, 61(19): 273-281.

XIANG Yong, LI Yanjun, WANG Yiting, LIU Jian, DING Yi. Analysis of Batch Verifiable Signature Scheme Based on Elliptic Curve[J]. Computer Engineering and Applications, 2025, 61(19): 273-281.

参考文献

[1] SHESHASAAYEE A, ANANDAPRIYA B. Digital signatures security using cryptography for industrial applications[C]//Proceedings of the 2017 International Conference on Innovative Mechanisms for Industry Applications. Piscataway: IEEE, 2017: 379-382.
[2] FIAT A. Batch RSA[C]//Advances in Cryptology CRYPTO’89. New York: Springer, 1990: 175-185.
[3] NACCACHE D, MRAIHI D, VAUDENAY S, et al. Can DSA be improved?-Complexity trade-offs with the digital signature standard[C]//Advances in Cryptology EUROCRYPT’94: Workshop on the Theory and Application of Cryptographic Techniques. Berlin, Heidelberg: Springer, 1995: 77-85.
[4] GUO F C, MU Y, CHEN Z D. Efficient batch verification of short signatures for a single-signer setting without random oracles[C]//Advances in Information and Computer Security. Berlin, Heidelberg: Springer, 2008: 49-63.
[5] HUANG D J, MISRA S, VERMA M, et al. PACP: an efficient pseudonymous authentication-based conditional privacy protocol for VANETs[J]. IEEE Transactions on Intelligent Transportation Systems, 2011, 12(3): 736-746.
[6] 宋成, 张明月, 彭维平, 等. 基于非线性对的车联网无证书批量匿名认证方案研究[J]. 通信学报, 2017, 38(11): 35-43.
SONG C, ZHANG M Y, PENG W P, et al. Research on pairing-free certificateless batch anonymous authentication scheme for VANET[J]. Journal on Communications, 2017, 38(11): 35-43.
[7] REN Y, WANG S, ZHANG X, et al. An efficient batch verifying scheme for detecting illegal signatures[J]. International Journal of Network Security, 2015, 17(4): 463-470.
[8] LI J G, ZHANG Y C. Cryptanalysis and improvement of batch verification certificateless signature scheme for VANETs[J]. Wireless Personal Communications, 2020, 111(2): 1255-1269.
[9] YU J R, CUI J S, TU H, et al. A SM2 based efficient and lightweight batch verification approach for IC cards[J]. Journal of Information Security and Applications, 2023, 73: 103409.
[10] KARATI S, DAS A, ROYCHOWDHURY D, et al. Batch verification of ECDSA signatures[C]//Progress in Cryptology-AFRICACRYPT 2012. Berlin, Heidelberg: Springer, 2012: 1-18.
[11] THUMBUR G, RAO G S, REDDY P V, et al. Efficient and secure certificateless aggregate signature-based authentication scheme for vehicular ad hoc networks[J]. IEEE Internet of Things Journal, 2021, 8(3): 1908-1920.
[12] WANG X D, JIA W X, QIN H. An improved secure and efficient certificateless conditional privacy-preserving authentication scheme in VANETs[C]//Proceedings of the 2020 International Conference on Cyberspace Innovation of Advanced Technologies. New York: ACM, 2020: 496-503.
[13] 阮鸥, 陈吉晨, 毛浩. 一种高效的SM2数字签名批量验证算法[J]. 计算机工程与科学, 2021, 43(7): 1236-1242.
RUAN O, CHEN J C, MAO H. An efficient batch verification algorithm for SM2 signatures[J]. Computer Engineering & Science, 2021, 43(7): 1236-1242.
[14] XIONG H, JIN C J, ALAZAB M, et al. On the design of blockchain-based ECDSA with fault-tolerant batch verification protocol for blockchain-enabled IoMT[J]. IEEE Journal of Biomedical and Health Informatics, 2022, 26(5): 1977-1986.
[15] 郭健, 龚银燕. 一个可溯源的车联网群签名批量验证协议[J]. 长沙大学学报, 2023, 37(5): 7-12.
GUO J, GONG Y Y. A traceable group signature batch authentication protocol for vehicular ad hoc networks[J]. Journal of Changsha University, 2023, 37(5): 7-12.
[16] 巫光福, 傅晓艳, 周建东. 一种高效轻量的双参数椭圆曲线数字签名批量验证方案[J]. 佳木斯大学学报(自然科学版), 2024, 42(1): 1-5.
WU G F, FU X Y, ZHOU J D. An efficient and lightweight two-parameter ECDSA batch verification scheme[J]. Journal of Jiamusi University (Natural Science Edition), 2024, 42(1): 1-5.
[17] NEGI L, KUMAR D. A bilinear mapping based ring signature scheme with batch verification for applications in VANETs[J]. Wireless Personal Communications, 2024, 134(4): 1987-2011.
[18] LI X, JEON G, WANG W S, et al. A linkable signature scheme supporting batch verification for privacy protection in crowd-sensing[J]. Digital Communications and Networks, 2024, 10(3): 645-654.
[19] ZHOU X T, LUO M, VIJAYAKUMAR P, et al. Efficient certificateless conditional privacy-preserving authentication for VANETs[J]. IEEE Transactions on Vehicular Technology, 2022, 71(7): 7863-7875.
[20] 郭瑞, 胡国梁, 王俊茗. 车联网中可匿名的无证书聚合签名方案[J]. 计算机工程, 2024, 50(11): 207-222.
GUO R, HU G L, WANG J M. Anonymous certificateless aggregate signature scheme in VANETs[J]. Computer Engineering, 2024, 50(11): 207-222.
[21] 刘健, 李艳俊, 郑继虎, 等. 可溯源车联网匿名签名和批量验证方案设计[J]. 计算机工程与应用, 2024, 60(23): 268-274.
LIU J, LI Y J, ZHENG J H, et al. Design of anonymous signature and batch verification scheme for traceable connected vehicles[J]. Computer Engineering and Applications, 2024, 60(23): 268-274.
[22] 国家密码管理局. SM2椭圆曲线公钥密码算法第2部分: 数字签名算法: GM/T 0003.2—2012[S]. 北京: 中国标准出版社, 2012.
State Cryptography Administration of China. Public key cryptographic algorithm SM2 based on elliptic curves: Part 2: Digital signature algorithm: GM/T 0003.2—2012[S]. Beijing: Standards Press of China, 2012.
[23] KITTUR A S, PAIS A R. Batch verification of digital signatures: approaches and challenges[J]. Journal of Information Security and Applications, 2017, 37: 15-27.