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

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.