一种基于行公因子提取的改进Coppersmith算法

• 作者: 王云飞 李光松
• 来源期刊: 信息工程大学学报
• 关键词: Coppersmith算法 LLL算法 格基约化 公因子提取
• 年，卷（期）: 2021,（1）
• 所属期刊栏目: 网络空间安全
• 页码范围: 81-86
• 页数: 6页
• 分类号: TN918.1
• 语种: 中文
• DOI: 10.3969/j.issn.1671-0673.2021.01.014

摘要

1996年欧密会上,Coppersmith提出一种对单变元模方程求小根的多项式时间算法,该算法对公钥密码系统的安全性分析具有重要意义.结合Coppersmith算法中格基矩阵的结构特点和元素性质提出一种改进算法,通过逐次提取格基矩阵不同块中行向量的公因子,有效降低了Coppersmith算法的求解时间.同时通过实验证明了此改进算法可有效兼容一种预处理算法,通过将这两种算法结合,进一步提高了Coppersmith算法的求解效率,实验表明较原Cop-persmith算法最高可提升22.64％.