对DSA和ECDSA的一种改进格攻击

摘要

利用格攻击DSA和ECDSA的方法,通过构造同余方程组可以将隐藏数字问题转化为格中最近向量问题,当同余方程组至多有一个解小于给定界限时,可通过求解格中最近向量获取签名私钥。给定界限越大,对解向量的大小要求越宽松,攻击的难度也越低。文章提出一种新的给定界限,其大小是原有界限的6.92倍,显著降低了格攻击的难度。利用从OpenSSL收集到的DSA和ECDSA的签名数据,设计验证新界限的格攻击实验。实验结果表明,新界限对已知解向量元素的要求由最高比特位6位降低到3位。对于DSA,当格的维度为350时,攻击成功率达80%;对于ECDSA,当格的维度为260时,攻击成功率达97%。通过解向量减去一个基准向量,可将对已知解向量元素的要求降低至1位,从而降低格攻击的难度。