International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 27 May 2013

Kaoru Kurosawa, Takuma Ueda
ePrint Report ePrint Report
Let $N_1=p_1q_1$ and $N_2=p_2q_2$ be two different RSA moduli. Suppose that $p_1=p_2 \\bmod 2^t$ for some $t$, and $q_1$ and $q_2$ are $\\alpha$ bit primes. Then May and Ritzenhofen showed that $N_1$ and $N_2$ can be factored in quadratic time if

\\[ t \\geq 2\\alpha+3. \\]

In this paper, we improve this lower bound on $t$. Namely we prove that $N_1$ and $N_2$ can be factored in quadratic time if

\\[ t \\geq 2\\alpha+1. \\]

Further our simulation result shows that our bound is tight.

Expand

Additional news items may be found on the IACR news page.