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

Improved Coppersmith Algorithm Based on Extraction of Row Common Factor

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

In a seminal work at Eurocrypt1996,the polynomial-time Coppersmith algorithm has been proposed for finding small roots of univariate modular equations.This algorithm is of great significance to the security analysis of public-key cryptosystems.In this paper,an improved Coppersmith algorithm is proposed based on the structural characteristics and element properties of lattice basis matrix.This algorithm can effectively reduce the running time of the Coppersmith algorithm by successively extracting the common factors of the row vectors in different blocks of the lattice basis matrix.At the same time,the compatibility of this improved algorithm with a preprocessing algorithm is proved,and combining these two algorithms further improves the efficiency of Coppersmith algorithm,which can be up to 22.64%higher than the original Coppersmith algorithm.