05903545

j

05903545 Sarkar, Santanu Maitra, Subhamoy Some applications of lattice based root finding techniques. Adv. Math. Commun. 4, No. 4, 519-531 (2010). 2010 Shandong University, Jinan; American Institute of Mathematical Sciences, Springfield, MO EN CRT-RSA decryption exponent greatest common divisor factorization implicit factorization lattice LLL RSA smooth integers Zbl 1006.94528 Zbl 1172.94577

doi:10.3934/amc.2010.4.519

Summary: In this paper we present some problems and their solutions exploiting lattice based root finding techniques.\ In [Cryptography and lattices. 1st international conference, CaLC 2001, Lect. Notes Comput. Sci. 2146, 51--66 (2001; Zbl 1006.94528)] {\it N. Howgrave-Graham} proposed a method to find the Greatest Common Divisor (GCD) of two large integers when one of the integers is exactly known and the other one is known approximately. In this paper, we present three applications of the technique. The first one is to show deterministic polynomial time equivalence between factoring $N$ ($N = pq$, where $p > q$ or $p, q$ are of same bit size) and knowledge of $q^{-1}\bmod p$. Next, we consider the problem of finding smooth integers in a short interval. The third one is to factorize $N$ given a multiple of the decryption exponent in RSA. In [Advances in cryptology -- ASIACRYPT 2006, Lect. Notes Comput. Sci. 4284, 267--282 (2006; Zbl 1172.94577)] {\it E. Jochemsz} and {\it A. May} presented a general strategy for finding roots of a polynomial. We apply that technique to solve the following two problems. The first one is to factorize $N$ given an approximation of a multiple of the decryption exponent in RSA. The second one is to solve the implicit factorization problem given three RSA moduli considering certain portions of LSBs as well as MSBs of one set of three secret primes are same.