When e-th Roots Become Easier Than Factoring

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.

  • PDF / 532,464 Bytes
  • 16 Pages / 430 x 660 pts Page_size
  • 63 Downloads / 193 Views

DOWNLOAD

REPORT


tract. 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. The attack comes in two flavors: – A first version is illustrated here by producing selective roots of the  ). This matches the special number field form xi + c in Ln ( 13 , 3 32 9 sieve’s (snfs) complexity. – A second variant computes arbitrary e-th roots in Ln ( 31 , γ) 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 tonumbers of a special . form. The aforementioned constant γ is then 3 32 9 √ Constraining the oracle to roots of the form e xi + c mod n increases γ.

Both methods are faster than factoring n using the gnfs )). (Ln ( 13 , 3 64 9 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. Keywords: rsa, factoring, nfs, roots.

1

Introduction

The rsa cryptosystem [17] is commonly used for providing privacy and authenticity of digital data. A very common historical practice for signing with rsa 

Work partially supported by dga research grant 05.34.058.

K. Kurosawa (Ed.): ASIACRYPT 2007, LNCS 4833, pp. 13–28, 2007. c International Association for Cryptology Research 2007 

14

A. Joux, D. Naccache, and E. Thom´e

was to first hash the message, add a padding pattern c and then raise the result to the power of the decryption exponent. This paradigm is the basis of numerous standards such as pkcs#1 v1.5 [18]. Let n and e denote usual rsa public parameters (with log2 n = N )1 . In this paper we explore rsa signatures with a fixed c but without the hash function, i.e. modular roots of the form: √ e c + x mod n We call such numbers affine modular roots (amrs). A thread of publications [15,7,10,14,4,13] stretching over a decade progressively established that given access√to an amr-oracle, new amrs could be forged in polynomial complexity for x > 3 n. √ No strategies faster than factoring n are known for x < 3 n – a case tackled here at the cost of subexponential complexity. The main novelty in this paper is that, while subexponential, our method forges new amrs for arbitrarily small x √ (down to x <  n, ∀ > 0) faster than factoring n. Moreover, we show that access to an e-th root oracle (in particular, an amroracle) even allows to compute arbitrary e-th roots faster than factoring n. Here, the arbitrary e-th root to be computed is not known before all oracle queries have been completed. We achieve this by tweaking the quadratic sieve (qs) and the number field sieve (nfs) factoring algorithms.   The Results. Denoting Ln (α, c) = exp c (1 + o(1)) (log n)α (log log n)1−α , we show that: – Using a qs