Skip to Main content Skip to Navigation
Conference papers

When e-th Roots Become Easier Than Factoring

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.The attack comes in two flavors:– A first version is illustrated here by producing selective roots of the form $x_i + c$ in $L_n(1/3, \sqrt[3]{32/9})$. This matches the special number field sieve’s (SNFS) complexity.– A second variant computes arbitrary $e$-th roots in $L_n(1/3, γ)$ after a subexponential number of oracle queries. The constant γ depends onthe type of oracle used.This addresses in particular the One More RSA Inversion problem, where the $e$-th root oracle is not restricted to numbers of a special form. The aforementioned constant γ is then $\sqrt[3]{32/9}$.If the oracle is constrained to roots of the form $\sqrt[e]{x_i + c \mod n}$, then $γ = \sqrt[3]{6}$.Both methods are faster than factoring n using the GNFS ($L_n(1/3, \sqrt[3]{64/9})$). This sheds additional light on RSA’s malleability in general and on RSA’sresistance to affine forgeries in particular – a problem known to be polynomial for $x_i > \sqrt[3]{n}$, but for which no algorithm faster than factoringwas known before this work.
Document type :
Conference papers
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download
Contributor : Emmanuel Thomé Connect in order to contact the contributor
Submitted on : Thursday, November 15, 2007 - 11:41:44 AM
Last modification on : Wednesday, October 20, 2021 - 12:24:14 AM
Long-term archiving on: : Monday, September 24, 2012 - 3:26:22 PM


Files produced by the author(s)




Antoine Joux, David Naccache, Emmanuel Thomé. When e-th Roots Become Easier Than Factoring. Advances in Cryptology -- ASIACRYPT 2007, Dec 2007, Kuching, Malaysia. pp.13-28, ⟨10.1007/978-3-540-76900-2_2⟩. ⟨inria-00187782⟩



Record views


Files downloads