Paper 2007/424
When eth Roots Become Easier Than Factoring
Antoine Joux, David Naccache, and Emmanuel Thomé
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.
Metadata
 Available format(s)
 PDF PS
 Category
 Publickey cryptography
 Publication info
 Published elsewhere. RSA, NFS, factoring, digital signatures
 Contact author(s)
 Emmanuel Thome @ normalesup org
 History
 20071118: received
 Short URL
 https://ia.cr/2007/424
 License

CC BY
BibTeX
@misc{cryptoeprint:2007/424, author = {Antoine Joux and David Naccache and Emmanuel Thomé}, title = {When eth Roots Become Easier Than Factoring}, howpublished = {Cryptology ePrint Archive, Paper 2007/424}, year = {2007}, note = {\url{https://eprint.iacr.org/2007/424}}, url = {https://eprint.iacr.org/2007/424} }