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 xi + c. Here c is fixed and xi denotes small integers of the attacker's choosing. -A first version is illustrated here by producing selective roots of the form xi + c in Ln( ). This matches the special number field sieve's (snfs) complexity. -A second variant computes arbitrary e-th roots in Ln( . If the oracle is constrained to roots of the form Both methods are faster than factoring n using the gnfs (Ln( )). 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 xi > 3 √ n, but for which no algorithm faster than factoring was known before this work.
Joux et al. REF showed that given access to an oracle that computes e -th roots of numbers of the form x +c for a fixed c and any x , computing arbitrary e -th roots modulo n is easier than factoring n .
Thomé, When e-th roots become easier than factoring
Progress in Cryptology – Asiacrypt 2007, LNCS 4833
Mathematics Computer Science