Comparative Study of Digital Signature Standards Based on Discrete Logarithm

doi:10.3969/j.issn.1000-3428.2016.01.026

Abstract

Abstract: As Chinese state encryption administration is seeking the next generation of Digital Signature Standard(DSS),this paper analyzes and compares seven DSS listed in ISO/IEC 14888-3 and SM2 which are based on Discrete Logarithm Problem(DLP) or Elliptic Curve Discrete Logarithm Problem(ECDLP).Results show that the widely used Digital Signature Algorithm(DSA) is a combination of Schnorr and ElGamal signature algorithm and it becomes Elliptic Curve Digital Signature Algorithm (EC-DSA).SM2 may be more vulnerable than EC-DSA.Moreover,the Pointcheval/Vaudenay algorithm is provably secure.The Korean Certificate-based Digital Signature Algorithm(KCDSA) and its elliptic curve version Elliptic Curve Korean Certificate-based Digital Signature Algorithm(EC-KCDSA) performs better both in security and efficiency issues.The signature algorithms of Elliptic Curve Russia Digital Signature Algorithm(EC-RDSA) and Elliptic Curve Germany Digital Signature Algorithm(EC-GDSA) are faster.It is worth noting that an attack against EC-RDSA is proposed,implying that EC-RDSA is not strongly existential unforgeability under the adaptive chosen-message attack.The comparative results is helpful for the research,as well as for the finalization of the next generation of DSS.

Key words: Discrete Logarithm Problem(DLP), Elliptic Curve Discrete Logarithm Problem(ECDLP), Digital Signature Standard(DSS), Random Oracle Model(ROM), SM2 algorithm

摘要： 在国家密码管理局公开征集下一代商密公钥密码算法标准的背景下,从效率和安全性方面,对基于离散对数问题(DLP)或椭圆曲线DLP的ISO/IEC 14888-3中7种数字签名标准及国密SM2标准进行对比分析。结果表明,数字签名算法（DSA)是Schnorr和ElGamal签名算法的结合,其应用广泛,现已发展为EC-DSA,且安全性高于SM2。Pointcheval/Vaudenay算法是可证明安全的,KCDSA和EC-KCDSA的效率及安全性均较高,EC-RDSA和EC-GDSA的签名生成过程较快。给出针对EC-RDSA的攻击方法,证明其在自适应性选择消息攻击下不是强存在性不可伪造的。上述研究结果对我国下一代商密公钥密码算法标准的设计和制定具有参考作用。

关键词: 离散对数问题, 椭圆曲线离散对数问题, 数字签名标准, 随机谕示模型, SM2算法

CLC Number:

TP309

FENG Zeyu,GONG Boru,ZHAO Yunlei. Comparative Study of Digital Signature Standards Based on Discrete Logarithm[J]. Computer Engineering.

冯泽宇,巩博儒,赵运磊. 基于离散对数的数字签名标准对比研究[J]. 计算机工程.

/ Recommend / Download Citations

URL:

https://www.ecice06.com/EN/Y2016/V42/I1/145

References

参考文献［1］El Gamal T.A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms［C］//Proceedings of CRYPTO’84.Berlin,Germany:Springer,1985:10-18. ［2］Schnorr C P.Efficient Identification and Signatures for Smart Cards［C］//Proceedings of CRYPTO’89.Berlin,Germany:Springer,1990:239-252. ［3］Schnorr C P.Efficient Signature Generation by Smart Cards［J］.Journal of Cryptology,1991,4(3):161-174. ［4］Pointcheval D,Stern J.Security Arguments for Digital Signatures and Blind Signatures［J］.Journal of Cryptology,2000,13(3):361-396. ［5］Vaudenay S,Pointcheval D.On Provable Security for Digital Signature Algorithms,LIENS-96-17［R］.LIENS,1996. ［6］Lim C,Lee P.The Korean Certificate-based Digital Signature［J］.Computers & Electrical Engineering,1999,25(4):249-265. ［7］Johnson D,Menezes A,Vanstone S.The Elliptic Curve Digital Signature Algorithm(ECDSA)［J］.International Journal of Information Security,2001,1(1):36-63. ［8］American National Standards Institute.ISO/IEC 14888-3-2013 Information Technology-Security Techniques-Digital Signatures with Appendix,Part 3:Discrete Logarithm Based Mechanisms［S］.2013. ［9］Michels M,Naccache D,Petersen H.GOST 34.10-A Brief Overview of Russia’s DSA［J］.Computers & Security,1996,15(8):725-732. ［10］Hess E,Schafheutle M,Serf P,et al.The Digital Signature Scheme ECGDSA［EB/OL］.(2006-12-24).https://www.teletrust.de/fileadmin/files/oid/ecgdsa_final.pdf. ［11］国家密码管理局.SM2椭圆曲线公钥密码算法［EB/OL］.(2010-12-17).http://www.oscca.gov.cn/News/201012/News_1197.htm. ［12］Boneh D,Shen E,Waters B.Strongly Unforgeable Signatures Based on Computational Diffie-Hellman［C］//Proceedings of PKC’06.Berlin,Germany:Springer,2006:229-240. ［13］Liu Mingjie,Chen Jiazhe,Li Hexin.Partially Known Nonces and Fault Injection Attacks on SM2 Signature Algorithm［C］//Proceedings of Information Security and Cryptography Conference.Berlin,Germany:Springer,2014:343-358. ［14］Varnovskii N P.Provable Security of Digital Signatures in the Tamper-proof Device Model［J］.Discrete Math-ematics and Applications,2008,18(4):427-437. 编辑陆燕菲

[1]	CHEN Hong, HOU Yuting, GUO Pengfei, ZHOU Mo, ZHAO Jufang, XIAO Chenglong. Efficient Certificateless Aggregate Signcryption Scheme with Public Verifiability [J]. Computer Engineering, 2022, 48(10): 146-157.
[2]	CAO Suzhen,SUN Han,DAI Wenjie,WANG Xiuya. Selectively Linkable and Convertible Ring Signature Scheme Based on DLP [J]. Computer Engineering, 2019, 45(2): 144-147,153.
[3]	ZHU Jun,CHEN Linlin,ZHU Xian,XIE Ling,WEI Wei. Certificateless Proxy Re-encryption Scheme for Cloud Computing Security [J]. Computer Engineering, 2017, 43(8): 8-14.
[4]	LI Zichen,LIU Boya,WANG Peidong,YANG Yatao. Two-way Authentication Protocol Based on SM2 and Zero Knowledge for Radio Frequency Identification [J]. Computer Engineering, 2017, 43(6): 97-100,104.
[5]	ZUO Liming,ZHANG Tingting,GUO Hongli,CHEN Zuosong. Certificateless Aggregate Signature Scheme Based on No Pairing Mapping [J]. Computer Engineering, 2017, 43(5): 313-316.
[6]	TANG Yongli,WANG Feifei,YAN Xixi,LI Zichen. Efficient and Provably Secure Certificateless Signature Schemes [J]. Computer Engineering, 2016, 42(3): 156-160.
[7]	CAO Su-Zhen, WANG Cai-Fen. Content Extraction Signature Scheme Based on DLP [J]. Computer Engineering, 2013, 39(4): 132-136.
[8]	YANG Bei, XIAO Zi-Bi, LI Shou-Gui, SONG Chun-Guang. Analysis and Improvement of Certificateless Signature Scheme [J]. Computer Engineering, 2012, 38(9): 15-18.
[9]	CAO Su-Zhen, WANG Cai-Fen, CHEN Xiao-Yun, LV Gao-Yin. Content Extraction Signature Scheme Without Bilinear Pairings [J]. Computer Engineering, 2012, 38(3): 110-112.
[10]	WANG Xi, ZHANG Bin. SAML Single Sign-on Protocol Based on Proxy Signature [J]. Computer Engineering, 2012, 38(16): 130-133.
[11]	ZHANG Yan-Li, ZHANG Jian-Zhong. Verifiable Multi-secret Sharing Scheme on Elliptic Curves [J]. Computer Engineering, 2011, 37(3): 124-125,128.
[12]	ZHANG Jian-Zhong, ZHANG Yan-Li. Dynamic Multi-secret Sharing Scheme with Updatable Sub-secret [J]. Computer Engineering, 2011, 37(20): 117-119.
[13]	DIAO Ti-Hua, LIU Shen-Jun. Analysis and Improvement of Secure Authentication Mechanism for Session Initiation Protocol [J]. Computer Engineering, 2011, 37(20): 114-116.
[14]	CHENG Hui; OUYANG Dan. Research on Application of Digital Signature Standard 　　to the Key Exchange Protocols [J]. Computer Engineering, 2006, 32(20): 168-169.

Please choose a citation manager

Content to export