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

摘要： 椭圆曲线数字签名算法(elliptic curve digital signature algorithm, ECDSA)是应用最广的数字签名算法之一，在签名过程中需要计算椭圆曲线上的标量乘法，该操作通常是签名中最耗时的部分.在目前许多密码库的实现中都使用非相邻窗口形式表示临时密钥，从而减少标量乘法的计算时间，但是也使得攻击者能够通过侧信道攻击获取临时密钥的部分信息，恢复签名密钥.使用扩展隐藏数问题提取侧信道轨迹中的信息，并通过格攻击恢复密钥，是针对ECDSA的主流攻击框架之一.基于此，提出了3方面的优化方法：1)邻域动态约束合并策略.通过动态的合并参数可以降低格的维数，并控制攻击过程中已知信息的损失量，使得对于任意的签名均能够以很高成功率恢复密钥.2)对于格中嵌入数进行分析与优化，使得目标向量的欧几里得范数减少约8%，有效提高了攻击的成功率并减少了时间开销.3)提出了一种线性断言方法，能够显著降低格筛法的时间开销.在使用2个签名的情况下以0.99的成功率恢复签名密钥.

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