30
$\begingroup$

I was reading CLRS and is said:

If factoring large integers is easy, then breaking the RSA cryptosystem is easy.

Which makes sense to me because with the knowledge of $p$ and $q$, it is easy to create the secret key which the knowledge of the public key. Though, it explains the converse statement, which I don't quite understand:

The converse statement, that if factoring large integers is hard, then breaking RSA is hard, is unproven.

What does the statement above formally mean? If we assume factoring is hard (in some formal way), why does that not imply that breaking the RSA crypto system is hard?

Now consider that if we assumed that factoring is hard...and that we discovered that it meant that the RSA cryptosystem is hard to break. What would that formally mean?

$\endgroup$
  • 3
    $\begingroup$ It might imply that breaking RSA is hard, but it hasn't been proven. $\endgroup$ – Tom van der Zanden Dec 13 '15 at 23:07
  • 2
    $\begingroup$ the discrete logarithm problem at the heart of breaking RSA while "very similar" has not been proven to be equivalent to factoring, its a major open question of the field (both cryptography and TCS) $\endgroup$ – vzn Dec 14 '15 at 19:13
  • 1
    $\begingroup$ Shouldn't the second use a dash instead of commas? Isn't a dash used when there are commas inside of the dependent clause? The converse statement -- that if factoring large integers is hard, then breaking RSA is hard -- is unproven. $\endgroup$ – Czipperz Dec 15 '15 at 4:11
  • $\begingroup$ @ruakh: Whoops, yeah... I even made sure to double-check it but I still got it wrong. I keep forgetting that you're supposed to reduce to a problem that you know to be easy, not a problem that you know to be at least as hard as your current one. :-) Thanks for that, I removed it. $\endgroup$ – Mehrdad Dec 16 '15 at 1:27
  • $\begingroup$ Mathematical argument: "if $A$, then $B$" means the same as "if not $B$, then not $A$". You cannot say anything about "if not $A$, then not $B$". $\endgroup$ – drzbir Mar 8 '17 at 2:43
50
$\begingroup$

The easiest way to think about it is to think of the contrapositive.

The statement:

if factoring large integers is hard, then breaking RSA is hard

is equivalent to the following:

if breaking RSA is easy, then factoring large integers is easy

This statement has not been proven.

What they're saying is, assume we have an algorithm that solves factoring in polynomial time. Then we can use it to construct an algorithm that solves RSA in polynomial time.

But, there could be some other way to crack RSA that doesn't involve factoring integers. It's possible that we will find we can crack RSA in a way that doesn't let us factor integers in polynomial time.

In short, we know that RSA is at least as easy as factoring. There are two possible outcomes: RSA and factoring are of equivalent difficulty, or RSA is a strictly easier problem than factoring. We don't know which is the case.

$\endgroup$
  • 10
    $\begingroup$ "at least as easy" - that's a way of interpreting reductions that should be taught more expressly along with the other way around. $\endgroup$ – G. Bach Dec 14 '15 at 10:08
  • $\begingroup$ You can do it either way, if X is at least as hard as Y, Y is at least as easy as X. $\endgroup$ – jmite Dec 14 '15 at 18:34
  • 2
    $\begingroup$ That's what I meant - almost everyone has probably heard "X is at least as hard as Y", but "Y is at least as easy as X" is very rarely explained - although it's just as useful. $\endgroup$ – G. Bach Dec 14 '15 at 19:09
  • 1
    $\begingroup$ I seem to remember vaguely that Donald Knuth mentioned an algorithm which given a machine that can magically crack arbitrary RSA encrypted messages would be able to factor products of two large primes. I might have this wrong :-( $\endgroup$ – gnasher729 Dec 15 '15 at 15:59
31
$\begingroup$

The existence of a hard way does not imply there is no easy way.

There may be a number of ways to break RSA and we only need to find one of them.


One of these ways is factoring a large integer, so if that is easy we can do it this way and RSA is broken. This is also the only way we know yet. If it is unfeasible to do that, we can still find another, computationally less demanding way to perform our task without the need to explicitly calculate p and q from n.


To prove RSA is broken, we need to prove that one way to do it is easy.

To prove RSA is safe, we need to prove that all ways to do it are hard.


Finally, your statement is unproven because it is unproven that no other, easier method exists that extracts information from a cyphertext.

$\endgroup$
  • 1
    $\begingroup$ We could prove that RSA and factoring are equally hard if we could produce an algorithm that can factor products of two large primes by generating some special RSA encrypted messages, cracking them, and then doing some more calculations. That would mean RSA is not easier than factoring. It doesn't mean that either is easy or hard. $\endgroup$ – gnasher729 Dec 15 '15 at 16:03
  • $\begingroup$ @gnasher729 Would that be sufficient? If the algorithm could factor products of two large primes, but not products involving more than 2 primes, or products involving small primes? $\endgroup$ – otakucode Dec 16 '15 at 3:57
  • $\begingroup$ @I think RSA only depends on the factors being coprime. So getting around products of multiple factors would be straight forward. $\endgroup$ – Taemyr Dec 16 '15 at 7:09
10
$\begingroup$

One additional way to look at it, is that breaking RSA requires only a special case of factoring, which may or may not be easy regardless of the general question of factoring.

As a simple example, consider the case that factoring is indeed difficult, but only for numbers with $3$ different factors. Factoring composite numbers with only two different factors (as used in RSA) may still be easy.

$\endgroup$
7
$\begingroup$

It means that the RSA problem seems (at this time) to be more specific than factoring.

So the RSA problem is this: knowing a semiprime $pq$ and some exponent $e,$ and a value $v,$ find the $m$ such that $v \equiv m^e \mod pq$. (I actually got this wrong in my original answer, so that my phrasing of the RSA problem was equivalent to factoring up to some PP algorithm. Whoops! So you're not alone in being confused at the details here.)

The factoring problem is this: knowing a semiprime $pq,$ find both $p$ and $q$.

If you can efficiently solve the factoring problem, then you can efficiently solve the RSA problem: take the semiprime, factor it, use some theorems about prime moduluses to calculate an inverse exponent $d$ which reveals all ciphertexts as $m \equiv v^d$. (In fact these theorems are how the setup for RSA works: we know the two primes during the setup phase.)

However, it is not known that solving this above problem for arbitrary messages $m$ will tell you anything about the factors of the modulus or the exponents involved. It might or it might not; we don't know. Many smart people have presumably looked at the problem but nothing obvious has jumped out at any of them. So it's not known that the factoring problem is solved by solutions to the RSA problem (plus polynomial effort), only that the RSA problem is solved by solutions to the factoring problem (plus polynomial effort).

In fact in 1998 Boneh and Venkatesan published a proof that a certain simple class of algorithms (plus, times, exponents, no XOR/NAND type stuff) cannot be used to turn an RSA-problem solution into a factoring algorithm. The argument had a simple ingenuity to it: by manipulating those arithmetic operations mathematically, we can find out that the "reduction algorithm" (for precision: this is the algorithm which uses an RSA "oracle" for a semiprime to factor that semiprime) turns out to be a factoring algorithm in its own right, so that we can modify it to a variant which makes no calls to its oracle. So we have a trichotomy: either (a) there is no such reduction algorithm, or (b) the reduction algorithm does not have a nice arithmetic interpretation or (c) factoring is polynomial-time just like the reduction algorithm was.

$\endgroup$
  • $\begingroup$ “it is not known that finding this inverse exponent d to any given e will tell you anything about the factors of the modulus” Isn't it? You can calculate $p$ and $q$ given $n$, $e$ and $d$. The algorithm as expressed is obviously PP, is it not known to be in P? $\endgroup$ – Gilles 'SO- stop being evil' Dec 14 '15 at 16:37
  • $\begingroup$ @Gilles actually I think you're right, so I've fixed my answer accordingly. $\endgroup$ – CR Drost Dec 14 '15 at 18:28
3
$\begingroup$

RSA depends on two abstract mathematical tasks that are believed to be hard: integer factoring, as you know, but also the discrete logarithm problem. You can break RSA if you can quickly factor a number that's the product of two large unknown primes; but you can also break RSA if you can quickly find $\log_e C$ in the finite group $\mathbb{Z}_{m}$, where $e$ and $m$ are the public RSA exponent and modulus, and $C$ is the ciphertext.

These two mathematical tasks are related, but (if I remember correctly) it's believed that a solution to one would not imply a solution to the other. I don't know if they are the only two ways to break RSA mathematically.

$\endgroup$
  • $\begingroup$ I think you might be misremembering things. Those aren't really two different problems: if you can find the discrete log modulo $m$, then you can factor $m$. In other words, a solution to the discrete log problem certainly does imply a solution to the factoring problem. $\endgroup$ – D.W. Dec 14 '15 at 19:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.