Using LLL-Reduction for Solving RSA and Factorization Problems
Using LLL-Reduction for Solving RSA and Factorization Problems
复制标题
DOI：
10.1007/978-3-642-02295-1_10
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Alexander May
中科院分区：
文献类型：
--
作者：
Alexander May
二十五年前，Lenstra，Lenstra和Lovász提出了他们著名的LLL格约简算法。在各种应用程序的LLL算法是一种方法，由于铜史密斯寻找小根多项式方程。本文综述了这种求根方法在RSA函数求逆问题和因子分解问题中的应用。正如我们将看到的，大多数结果具有双重性质，它们可以被解释为密码分析结果或硬度/安全性结果。
Twenty five years ago, Lenstra, Lenstra and Lovász presented their celebrated LLL lattice reduction algorithm. Among the various applications of the LLL algorithm is a method due to Coppersmith for finding small roots of polynomial equations. We give a survey of the applications of this root finding method to the problem of inverting the RSA function and the factorization problem. As we will see, most of the results are of a dual nature, they can either be interpreted as cryptanalytic results or as hardness/security results.