信息安全研究2026，Vol.12Issue(4)：319-329,11.DOI:10.12379/j.issn.2096-1057.2026.04.04
针对wNAF实现ECDSA的格攻击研究
Research on Lattice Attack on ECDSA Implemented with wNAF
摘要
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分类
信息技术与安全科学引用本文复制引用
马自强,孟誉卓,魏良根,王名宇,张娟洋..针对wNAF实现ECDSA的格攻击研究[J].信息安全研究,2026,12(4):319-329,11.基金项目
宁夏自然科学基金青年项目B类(2025AAC050015) （2025AAC050015）
