Cryptanalysis of an RSA variant with moduli <i>N</i> = <i> p ^r q ^l </i>

Abstract In this paper we study an RSA variant with moduli of the form <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mrow> <m:mi>N</m:mi> <m:mo>=</m:mo> <m:mrow> <m:msup> <m:mi>p</m:mi> <m:mi>r</m:mi> </m:msup> <m:mo>⁢</m:mo> <m:msup> <m:mi>q</m:mi> <m:mi>l</m:mi> </m:msup> </m:mrow> </m:mrow> </m:math> {N=p^{r}q^{l}} ( <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mrow> <m:mi>r</m:mi> <m:mo>&gt;</m:mo> <m:mi>l</m:mi> <m:mo>≥</m:mo> <m:mn>2</m:mn> </m:mrow> </m:math> {r&gt;l\geq 2} ). This variant was mentioned by Boneh, Durfee and Howgrave-Graham [2]. Later Lim, Kim, Yie and Lee [11] showed that this variant is much faster than the standard RSA moduli in the step of decryption procedure. There are two proposals of RSA variants when <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mrow> <m:mi>N</m:mi> <m:mo>=</m:mo> <m:mrow> <m:msup> <m:mi>p</m:mi> <m:mi>r</m:mi> </m:msup> <m:mo>⁢</m:mo> <m:msup> <m:mi>q</m:mi> <m:mi>l</m:mi> </m:msup> </m:mrow> </m:mrow> </m:math> {N=p^{r}q^{l}} . In the first proposal, the encryption exponent e and the decryption exponent d satisfy <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mrow> <m:mrow> <m:mi>e</m:mi> <m:mo>⁢</m:mo> <m:mi>d</m:mi> </m:mrow> <m:mo>≡</m:mo> <m:mrow> <m:mn>1</m:mn> <m:mo>mod</m:mo> <m:mrow> <m:msup> <m:mi>p</m:mi> <m:mrow> <m:mi>r</m:mi> <m:mo>-</m:mo> <m:mn>1</m:mn> </m:mrow> </m:msup> <m:mo>⁢</m:mo> <m:msup> <m:mi>q</m:mi> <m:mrow> <m:mi>l</m:mi> <m:mo>-</m:mo> <m:mn>1</m:mn> </m:mrow> </m:msup> <m:mo>⁢</m:mo> <m:mrow> <m:mo>(</m:mo> <m:mrow> <m:mi>p</m:mi> <m:mo>-</m:mo> <m:mn>1</m:mn> </m:mrow> <m:mo>)</m:mo> </m:mrow> <m:mo>⁢</m:mo> <m:mrow> <m:mo>(</m:mo> <m:mrow> <m:mi>q</m:mi> <m:mo>-</m:mo> <m:mn>1</m:mn> </m:mrow> <m:mo>)</m:mo> </m:mrow> </m:mrow> </m:mrow> </m:mrow> </m:math> ed\equiv 1\bmod p^{r-1}q^{l-1}(p-1)(q-1) , whereas in the second proposal <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mrow> <m:mrow> <m:mi>e</m:mi> <m:mo>⁢</m:mo> <m:mi>d</m:mi> </m:mrow> <m:mo>≡</m:mo> <m:mrow> <m:mn>1</m:mn> <m:mo>mod</m:mo> <m:mrow> <m:mrow> <m:mo>(</m:mo> <m:mrow> <m:mi>p</m:mi> <m:mo>-</m:mo> <m:mn>1</m:mn> </m:mrow> <m:mo>)</m:mo> </m:mrow> <m:mo>⁢</m:mo> <m:mrow> <m:mo>(</m:mo> <m:mrow> <m:mi>q</m:mi> <m:mo>-</m:mo> <m:mn>1</m:mn> </m:mrow> <m:mo>)</m:mo> </m:mrow> </m:mrow> </m:mrow> </m:mrow> </m:math> ed\equiv 1\bmod(p-1)(q-1) . We prove that for the first case if <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mrow> <m:mi>d</m:mi> <m:mo>&lt;</m:mo> <m:msup> <m:mi>N</m:mi> <m:mrow> <m:mn>1</m:mn> <m:mo>-</m:mo> <m:mrow> <m:mrow> <m:mo>(</m:mo> <m:mrow> <m:mrow> <m:mn>3</m:mn> <m:mo>⁢</m:mo> <m:mi>r</m:mi> </m:mrow> <m:mo>+</m:mo> <m:mi>l</m:mi> </m:mrow> <m:mo>)</m:mo> </m:mrow> <m:mo>⁢</m:mo> <m:msup> <m:mrow> <m:mo>(</m:mo> <m:mrow> <m:mi>r</m:mi> <m:mo>+</m:mo> <m:mi>l</m:mi> </m:mrow> <m:mo>)</m:mo> </m