When e-th Roots Become Easier Than Factoring

Summary

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 . This matches the special number field sieve’s (SNFS) complexity. A second variant computes arbitrary e-th roots in after a subexponential number of oracle queries. The constant γ depends on the 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 . Constraining the oracle to roots of the form increases γ. Both methods are faster than factoring n using the GNFS . This sheds additional light on RSA’s malleability in general and on RSA’s resistance to affine forgeries in particular – a problem known to be polynomial for , but for which no algorithm faster than factoring was known before this work.