# Solve a Modular Exponentiation

It might be common, but if we had to solve an equation like this $m=s^{e}$ mod $n$ where $m,e,n$ are known. How can we find $s$. What optimisations could be applied? And what would the complexity of finding $s$ be relative to $n,e$? Moreover, if we use GNFS or anything similar what does the complexity express exactly. For example, what do we mean when we say that for 1024-bit key the complexity for factoring it is ~86.7?

Finally, why can't we reform the equation like $m=s^e$ mod $n$ => $m+k*n=s^e$ => $s=(m+k*n)^{1/e}$ and start trying different k, as long as, we just want to find an s satisfying this equation?

Thank you

-
Is it safe to assume that this is RSA? – mikeazo Dec 21 '13 at 12:47
yes we can assume it is RSA – Yannis Assael Dec 21 '13 at 12:48

When $n$ is prime, solving for $e$-th roots modulo $n$ is easy, since it suffices to compute $d = e^{-1} \pmod {n-1}$ and then $s = m^d \pmod n$. If $n$ is not prime, but is instead a RSA modulus (a composite integer that is the product of two big primes), then the problem becomes apparently hard (in the sense that we don't have a clue how to do it efficiently) and is known as, indeed, the RSA problem.

The most efficient known methods to break the RSA problem, for non-special values of $m$ (e.g. the values which result from the padding step in standard RSA encryption and signatures), rely on integer factorization. If you can factor $n$ into its prime factors, then the RSA problem can be solved efficiently. Note the important point: we do not know if the RSA problem is equivalent to factorization; the RSA problem cannot be harder than factorization, but it might be easier. It is just that, right now, we do not know any RSA-breaking algorithm which is more efficient than factorizing the modulus.

The most efficient known method for integer factorization is GNFS, whose complexity is expressed as a barbaric-looking equation which you will find on the Wikipedia page. This is asymptotic complexity, so it does not given readily applicable results for two reasons:

1. The expression is valid for a big enough modulus; it does not tell whether a specific modulus length (say, 1024 bits) is sufficient for the expression to be at least approximately correct.

2. In practical terms, we want to express attack complexity in terms of dollars, not operations. In particular, the mathematical expression speaks only on CPU cost, not on memory cost, and says nothing about parallelization.

For big cracking jobs, a key to efficiency is how well we can split the problem into individual units which can run in parallel of each other, and how much data they have to exchange with each other. Heavy clusters achieve a lot of raw power through a lot of parallelization, which works wonders for, say, meteorological simulations, but not so much for integer factorization.

Roughly speaking, GNFS consists in two main phases, the sieve and then the linear reduction. The sieve is amenable to some rather high level of parallelization. For big integers (say, 1024-bit), the linear reduction appears to be the bottleneck. It is very hard to parallelize, and our best method so far is to find a big computer with an awful lot of very fast RAM. Existing "supercomputers" are ill-suited for such jobs. In fact, baring some non-trivial algorithmic enhancement for this phase, breaking a 1024-bit RSA modulus will require special-purpose hardware which exists only theoretically (we have plans, but turning plans into silicon takes money, time, and a lot of extra thinking).

Some people have tried to estimate how much this would all cost, and compared that to the cost of breaking a symmetric key through brute force (there again with dedicated special-purpose hardware). The result depends on a lot of parameters, including how much developers are paid (academics tend to think in terms of "developer = PhD student = free") and how many keys you try to break (hardware can be reused). Depending on who does the estimate, a 1024-bit RSA modulus will be deemed "as robust" as a symmetric key in the 75 to 85 range, meaning that it would cost the same to break it (note that this range hides a 1000-times factor !).

This site is the usual reference for pointers to the relevant papers.

-
Thank you very much for your reply but why can we reform the equation like: $m=s^e$ mod $n$ => $m+k*n=s^e$ => $s=(m+k*n)^{1/e}$ and start trying different k, as long as, we just want to find an s satisfying this equation? Thank you for the detailed explanation. – Yannis Assael Dec 23 '13 at 0:40
This solving method would take an awful lot of time, because the size of $k$ is several thousands of bits (the correct value of $k$ exists, but finding it that way would take billions of times the age of the Universe). – Thomas Pornin Dec 23 '13 at 11:42