Research on Lattice Attack on ECDSA Implemented with wNAF

Journal of Information Security Reserach ›› 2026, Vol. 12 ›› Issue (4): 319-.

Previous Articles Next Articles

Research on Lattice Attack on ECDSA Implemented with wNAF

Ma Ziqiang1,2,3, Meng Yuzhuo1,2,3, Wei Lianggen1,2,3, Wang Mingyu4, and Zhang Juanyang1,2,3

1(School of Information Engineering, Ningxia University, Yinchuan 750021)
2(Ningxia Key Laboratory of Artificial Intelligence and Information Security for Channeling Computing Resources from the East to the West(Ningxia University), Yinchuan 750021)
3(Collaborative Innovation Center for Ningxia Big Data and Artificial Intelligence Cofounded by Ningxia Municipality and Ministry of Education(Ningxia University), Yinchuan 750021)
4(College of Information Science and Technology, Dalian Maritime University, Dalian, Liaoning 116026)

Online:2026-04-07 Published:2026-04-07

针对wNAF实现ECDSA的格攻击研究

马自强1,2,3孟誉卓1,2,3魏良根1,2,3王名宇4张娟洋1,2,3

1(宁夏大学信息工程学院银川750021)
2(宁夏“东数西算”人工智能与信息安全重点实验室(宁夏大学)银川750021)
3(宁夏大数据与人工智能省部共建协同创新中心(宁夏大学)银川750021)
4(大连海事大学信息科学技术学院辽宁大连116026)

通讯作者: 马自强博士，副教授， CCF会员.主要研究方向为计算机系统安全、网络流量识别分析、网络舆情分析、区块链应用安全. maziqiang@nxu.edu.cn
作者简介:马自强博士，副教授， CCF会员.主要研究方向为计算机系统安全、网络流量识别分析、网络舆情分析、区块链应用安全. maziqiang@nxu.edu.cn 孟誉卓硕士研究生.主要研究方向为计算机系统安全、格攻击、格密码. 1244919669@qq.com 魏良根硕士研究生.主要研究方向为计算机系统安全、格攻击、格密码. 1225215144@qq.com 王名宇博士，讲师.主要研究方向为缓存侧信道、密钥安全、云计算安全. wangmignyu@163.com 张娟洋博士，副教授.主要研究方向为公钥密码、格密码、区块链技术. jyzhang@nxu.edu.cn
基金资助:
宁夏自然科学基金青年项目B类(2025AAC050015)

Abstract

Abstract: To mount an attack on the elliptic curve digital signature algorithm (ECDSA) using the windowed nonadjacent form (wNAF) for scalar multiplication, one first requires sidechannel analysis to gather information, followed by latticebased methods to recover the private key. Since the information collected from sidechannel analysis about secret parameters such as the signing private key is partial, it typically necessitates scores or even hundreds of signatures to fully recover the private key. However, in practical attacks, there are stringent limitations on the number of signatures available, making it challenging for attackers to obtain such a large volume of signature data. To maximize the utilization of information gathered through sidechannel analysis and recover the complete private key using only a few signatures, a lattice attack construction method based on the extended hidden number problem (EHNP) is proposed. Initially, cache sidechannel attacks are employed to collect DoubleAddInvert chains during the actual execution of the ECDSA algorithm. Subsequently, these DoubleAddInvert chains are converted into EHNP instances. Next, EHNP is leveraged to construct a lattice matrix, within which exists a target lattice vector bearing the private key. Finally, the block KorkinZolotarev (BKZ) lattice basis reduction algorithm is applied to locate this target lattice vector, thereby recovering the private key. Experimental results demonstrate that the proposed attack scheme can recover the complete signing private key using only two signatures, achieving the theoretical limit.

Key words: ECDSA, cache sidechannel attack, lattice attack, EHNP, private key

摘要： 利用标量乘法的窗口非相邻形式(windowed nonadjacent form, wNAF)的实现攻击椭圆曲线数字签名算法(the elliptic curve digital signature algorithm, ECDSA)首先需要一些侧信道分析收集信息，然后使用基于格的方法恢复密钥.由于从侧信道分析收集的关于签名私钥等秘密参数的信息是部分的，因此通常需要几十个或几百个签名才能恢复出完整签名私钥.然而，在实际攻击中，签名的个数是有严格限制的，攻击者难以获取如此多的签名数据.为了更大程度上利用侧信道分析收集的信息并且仅用几个签名恢复出完整的私钥，提出一种基于扩展隐藏数问题(the extended hidden number problem, EHNP)的格攻击构造方法：首先，利用缓存侧信道攻击收集ECDSA算法实际运行过程中的“DoubleAddInvert链”；然后将其转换为EHNP问题，利用EHNP构造1个格矩阵，使得其中存在1个带有私钥的目标格向量；最后通过BKZ(block KorkinZolotarev)格基约减算法找到这个目标格向量，进而恢复出私钥.实验结果显示，该方案仅需要2个签名就可以恢复出完整的签名私钥，达到了理论极限.

关键词: 椭圆曲线数字签名算法, 缓存侧信道攻击, 格攻击, 扩展隐藏数问题, 私钥

CLC Number:

TP309

马自强, 孟誉卓, 魏良根, 王名宇, 张娟洋, . 针对wNAF实现ECDSA的格攻击研究[J]. 信息安全研究, 2026, 12(4): 319-.

References

［1］Johnson D, Menezes A, Vanstone S A. The elliptic curve digital signature algorithm (ECDSA)［J］. International Journal of Information Security, 2001, 1(1): 3663［2］Gruss D, Maurice C, Wagner K, et al. Flush+Flush: A fast and stealthy cache attack［C］ Proc of the 13th Int Conf on DIMVA. Berlin: Springer, 2016: 279299［3］Jain H, Balaraju D A, Rebeiro C. Spy cartel: Parallelizing evict+timebased cache attacks on lastlevel caches［J］. Journal of Hardware and Systems Security, 2019, 3: 147163［4］Moghimi D, Sunar B, Eisenbarth T, et al. TPMFAIL: TPM meets timing and lattice attacks［C］ Proc of the 29th USENIX Security Symposium. Berkeley, CA: USENIX Association, 2020: 20572073［5］Purnal A, Turan F, Verbauwhede I. Prime+Scope: Overcoming the observer effect for highprecision cache contention attacks［C］ Proc of the 2021 ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2021: 29062920［6］Shusterman A, Agarwal A, O’Connell S, et al. Prime+Probe 1, JavaScript 0: Overcoming browserbased sidechannel defenses［C］ Proc of the 30th USENIX Security Symposium. Berkeley, CA: USENIX Association, 2021: 28632880［7］Weiser S, Schrammel D, Bodner L, et al. Big numbersbig troubles: Systematically analyzing nonce leakage in (EC) DSA implementations［C］ Proc of the 29th USENIX Security Symposium. Berkeley, CA: USENIX Association, 2020: 17671784［8］Yarom Y, Falkner K. FLUSH+RELOAD: A high resolution, low noise, L3 cache sidechannel attack［C］ Proc of the 23rd USENIX Security Symposium. Berkeley, CA: USENIX Association, 2014: 719732［9］Boneh D, DeMillo R A, Lipton R J. On the importance of eliminating errors in cryptographic computations［J］. Journal of Cryptology, 2001, 14: 101119［10］Liu Mingjie, Chen Jiazhe, Li Hexin. Partially known nonces and fault injection attacks on SM2 signature algorithm［C］ Proc of the 9th Int Conf on Information Security and Cryptology (Inscrypt 2013). Berlin: Springer, 2013: 343358［11］Mus K, Dorz Y, Tol M C, et al. Jolt: Recovering TLS signing keys via rowhammer faults［C］ Proc of the 2023 IEEE Symp on Security and Privacy (SP). Piscataway, NJ: IEEE, 2023: 17191736［12］Naccache D, Nguyen P Q, Tunstall M, et al. Experimenting with faults, lattices and the DSA［C］ Proc of the 8th Int Workshop on Theory and Practice in Public Key Cryptography(PKC 2005). Berlin: Springer, 2005: 1628［13］Ryan K. Return of the hidden number problem: A widespread and novel key extraction attack on ECDSA and DSA［J］. IACR Trans on Cryptographic Hardware and Embedded Systems, 2019 (1): 146168［14］Schmidt J M, Medwed M. A fault attack on ECDSA［C］ Proc of 2009 Workshop on Fault Diagnosis and Tolerance in Cryptography (FDTC). Piscataway, NJ: IEEE, 2009: 9399［15］Benger N, van de Pol J, Smart N P, et al. Ooh Aah… Just a little bit: A small amount of side channel can go a long way［C］ Proc of Cryptographic Hardware and Embedded Systems (CHES 2014). Berlin: Springer, 2014: 7592［16］Fan Shuqin, Wang Wenbo, Cheng Qingfeng. Attacking OpenSSL implementation of ECDSA with a few signatures［C］ Proc of the 2016 ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2016: 5051515［17］Sun C, Espitau T, Tibouchi M, et al. Guessing bits: Improved lattice attacks on (EC) DSA with nonce leakage［J］. IACR Trans on Cryptographic Hardware and Embedded Systems, 2022 (1): 391413［18］Wang Leizhang, Xia Wenwen, Wang Geng, et al. Improved pump and jump BKZ by sharp simulator［EBOL］. 2022 ［20220501］. https:eprint.iacr.org2022468［19］Wang Wenbo, Fan Shuqin. Attacking OpenSSL ECDSA with a smallamount of sidechannel information［J］. Science China Information Sciences, 2018, 61(3): 100121［20］Ma Ziqiang, Li Shuaigang, Lin Jingqiang, et al. Another lattice attack against ECDSA with the wNAFto recover more bits per signature［C］ Proc of the 18th EAI Int Conf on Security and Privacy in Communication Networks. Berlin: Springer, 2022: 111129［21］Thibault J P, O’Flynn C, Dewar A. Ark of the ECC: An opensource ECDSA power analysis attack on a FPGA based curve P256 implementation ［EBOL］. 2021 ［20250507］. https:eprint.iacr.org20211520.pdf［22］Lomne V, Roche T. A side journey to titan.［EBOL］. 2021 ［20250507］. https:ninjalab.iowpcontentuploads202101a side journey to titan.pdf［23］Jancar J, Sedlacek V, Svenda P, et al. Minerva: Thecurse of ECDSA nonces systematic analysis of lattice attacks on noisy leakageof bitlength of ECDSA nonces［J］. IACR Trans on Cryptographic Hardwareand Embedded Systems, 2020 (4): 281308［24］Zhao Z N, Morrison A, Fletcher C W, et al. Lastlevel cache sidechannel attacks are feasible in the modern public cloud［C］ Proc of the 29th ACM Int Conf on Architectural Support for Programming Languages and Operating Systems(ASPLOS’24). New York: ACM, 2024: 582600［25］Nguyen P Q, Shparlinski I E. The insecurity of the elliptic curve digital signature algorithm with partially known nonces［J］.Designs, Codes and Cryptography, 2003, 30(2): 201217［26］van de Pol J, Smart N P, Yarom Y. Just a little bit more［C］ Proc of the Cryptographer’s Track at the RSA Conf on Topics in Cryptology(CTRSA 2015). Berlin: Springer, 2015: 321［27］Boneh D, Venkatesan R. Hardness of computing the most significant bits of secret keys in DiffieHellman and related schemes［C］ Proc of the 16th Annual Int Cryptology Conf on Advances in Cryptology(CRYPTO’96). Berlin: Springer, 1996: 129142［28］Nguyen P Q, Shparlinski I E. The insecurity of the digital signature algorithm with partially known nonces［J］. Journal of Cryptology, 2002 (3): 151176［29］Hlavác M, Rosa T. Extended hidden number problem and its cryptanalytic applications［C］ Proc of the 13th Int Workshop on Selected Areas in Cryptography. 2006: 114133［30］Cao Jinzheng, Weng Jian, Pan Yanbin, et al. Generalized attack on ECDSA: Known bits in arbitrary positions［J］. Designs, Codes and Cryptography, 2023, 91(11): 38033823［31］Laarhoven T, Mariano A. Progressive lattice sieving［C］ Proc of Int Conf on PostQuantum Cryptography. Berlin:Springer, 2018: 292311［32］Li Shuaigang, Fan Shuqin, Lu Xianhui. Attacking ECDSA leaking discrete bits with a more efficient lattice［C］ Proc of the 17th Int Conf on Information Security and Cryptology(Inscrypt 2021). Berlin: Springer, 2021: 251266［33］Micheli G D, Piau R, Pierrot C. A tale of three signatures: Practical attack of ECDSA with wNAF［C］ Proc of the 12th Int Conf on Cryptology in Africa. Berlin: Springer, 2020: 361381［34］Nguyen P Q, Vallée B. The LLL Algorithm—Survey and Applications［M］. Berlin: Springer, 2009: 100140［35］Albrecht M, Ducas L, Herold G, et al. The general sieve kernel and new records in lattice reduction［C］ Proc of Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2019: 717746［36］Aono Y, Wang Y, Hayashi T, et al. Improved progressive BKZ algorithms and their precise cost estimation by sharp simulator［C］ Proc of the 35th Annual Int Conf on the Theory and Applications of Cryptographic Techniques(EUROCRYPT 2016). Berlin: Springer, 2016: 789819［37］De Micheli G. Discrete logarithm cryptanalyses: Number field sieve and lattice tools for sidechannel attacks［D］. Nancy, France: Université de Lorraine, 2021［38］Ducas L, Stevens M, van Woerden W. Advanced lattice sieving on GPUs, with tensor cores［C］ Proc of Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2021: 249279［39］Ducas L, Stevens M, van Woerden W. Advanced lattice sieving on GPUs, with tensor cores［C］ Advances in Cryptology—EUROCRYPT 2021. Berlin: Springer, 2021: 249279［40］Zhao Ziyu, Ding Jintai. Practical improvements on BKZ algorithm［C］ Proc of Int Symp on Cyber Security, Cryptology, and Machine Learning. Berlin: Springer, 2023: 273284［41］Alkim E, Ducas L, Pppelmann T, et al. Postquantum key exchange—A new hope［C］ Proc of the 25th USENIX Security Symposium (USENIX Security 16). Berkeley, CA: USENIX Association, 2016: 327343［42］Albrecht M R, Heninger N. On bounded distance decoding with predicate: Breaking the “lattice barrier” for the hidden number problem［C］ Proc of Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2021: 528558［43］Aranha D F, Novaes F R, Takahashi A, et al. LadderLeak: Breaking ECDSA with less than one bit of nonce leakage［C］ Proc of the 2020 ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2020: 225242［44］Ducas L. Shortest vector from lattice sieving: A few dimensions for free［C］ Proc of Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2018: 125145［45］Gao Y, Wang J, Hu H, et al. Attacking ECDSA with nonce leakage by lattice sieving: Bridging the gap with fourier analysisbased attacks［C］ Advances in Cryptology—ASIACRYPT 2024. Berlin: Springer, 2024: 334［46］Allan T, Brumley B B, Falkner K, et al. Amplifying side channels through performance degradation［C］ Proc of the 32nd Annual Conf on Computer Security Applications(ACSAC 2016). New York: ACM, 2016: 422435

[1]	. Research on ECDSA Key Recovery Attacks Based on the Extended Hidden Number Problem [J]. Journal of Information Security Reserach, 2026, 12(2): 174-.
[2]	. Design and Implementation of ECDSA Collaborative Signature Scheme#br# #br# [J]. Journal of Information Security Reserach, 2023, 9(11): 1120-.
[3]	. An Improved Scheme for Elliptic Curve Digital Signature [J]. Journal of Information Security Research, 2019, 5(3): 217-222.
[4]	. A Remote Authentication Scheme Based on CPK [J]. Journal of Information Security Research, 2018, 4(11): 1034-1039.
[5]	. Comparative Study on the Properties of CFL [J]. Journal of Information Security Research, 2016, 2(7): 600-607.

Research on Lattice Attack on ECDSA Implemented with wNAF

针对wNAF实现ECDSA的格攻击研究

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 5

Recommended Articles

Metrics