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

Abstract: Elliptic curve digital signature algorithm (ECDSA) is one of the most widely used digital signature algorithms. During the signing process, it requires computing scalar multiplication on elliptic curves, which is typically the most timeconsuming component of the signature. In many present cryptographic libraries, the windowed nonadjacent form representation is commonly used to represent the ephemeral key in order to reduce time consumption. This exposes sidechannel vulnerability to malicious attackers, allowing them to extract partial information about the ephemeral key from sidechannel traces and subsequently recover the signing key. Leveraging the extended hidden number problem to extract information from sidechannel traces and applying latticebased attacks to recover keys constitutes one of the mainstream attack frameworks against ECDSA. Based on above, we propose three optimization methods. First, we introduce a neighboring dynamic constraint merge strategy. By dynamically adjusting the merging parameters, we reduce the dimension of the lattice and control the amount of known information lost during the attack, ensuring high success rates for key recovery across all signatures. Second, we analyze and optimize the embedding number in the lattice, reducing the Euclidean norm of the target vector by approximately 8%, thereby improving the success rate and reducing time consumption. Finally, we propose a linear predicate method which significantly reduces the time overhead of the lattice sieving. In this work, we achieve a success rate of 0.99 in recovering the private key using only two signatures.

Key words: elliptic curve digital signature algorithm, sidechannel attack, extended hidden number problem, lattice attack, lattice sieving