International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: When e-th Roots Become Easier Than Factoring

Antoine Joux
David Naccache
Emmanuel Thomé
Search ePrint
Search Google
Abstract: We show that computing $e$-th roots modulo $n$ is easier than factoring $n$ with currently known methods, given subexponential access to an oracle outputting the roots of numbers of the form $x_i + c$. Here $c$ is fixed and $x_i$ denotes small integers of the attacker's choosing. Several variants of the attack are presented, with varying assumptions on the oracle, and goals ranging from selective to universal forgeries. The computational complexity of the attack is $L_n(\frac{1}{3}, \sqrt[3]{\frac{32}{9}})$ in most significant situations, which matches the {\sl special} number field sieve's ({\sc snfs}) complexity. This sheds additional light on {\sc rsa}'s malleability in general and on {\sc rsa}'s resistance to affine forgeries in particular -- a problem known to be polynomial for $x_i > \sqrt[3]{n}$, but for which no algorithm faster than factoring was known before this work.
  title={When e-th Roots Become Easier Than Factoring},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography /},
  note={RSA, NFS, factoring, digital signatures 13829 received 12 Nov 2007},
  author={Antoine Joux and David Naccache and Emmanuel Thomé},