基于格攻击的SM2签名算法的密钥恢复方法及存储介质

本发明公开了一种基于格攻击的SM2签名算法的密钥恢复方法及存储介质，所述密钥恢复方法，包括：S1，构建隐数问题；S2，将隐数问题归约到有界距离解码问题；S3，将有界距离解码问题归约到唯一最短向量问题；S4，采用带谓词的筛选算法求解唯一最短向量问题，恢复隐数获得签名私钥。本发明基于侧信道攻击获得的随机数最高l(l≥2)位比特信息，将SM2签名算法恢复密钥d的问题归约到隐数问题，再将隐数问题归约到有界距离解码问题，通过Kannan嵌入技术，进一步归约到唯一最短向量问题求解，最后结合小指数测试技术构建更高效的带谓词的筛选算法求解唯一最短向量问题，恢复隐数，获得签名私钥。本发明提出的新方法能减少格攻击开销，提高密钥恢复的效率。