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. 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.
Keywords : rsa factoring nfs roots
Document type :
Conference papers
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/inria-00187782
Contributor : Emmanuel Thomé <>
Submitted on : Thursday, November 15, 2007 - 11:41:44 AM
Last modification on : Friday, November 23, 2018 - 9:22:04 AM
Long-term archiving on : Monday, September 24, 2012 - 3:26:22 PM

File

nfsforge.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Antoine Joux, David Naccache, Emmanuel Thomé. When e-th Roots Become Easier Than Factoring. 13th International Conference on the Theory and Application of Cryptology and Information Security - ASIACRYPT 2007, International Association for Cryptologic Research, Dec 2007, Kuching, Malaysia. pp.13-28, ⟨10.1007/978-3-540-76900-2_2⟩. ⟨inria-00187782⟩

Share

Metrics

Record views

378

Files downloads

380