Welcome to the resource topic for 2007/424
Title:
When e-th Roots Become Easier Than Factoring
Authors: Antoine Joux, David Naccache, 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.
ePrint: https://eprint.iacr.org/2007/424
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .