2
$\begingroup$

I am giving a one hour presentation on the RSA crypto-system as one of the requirements for Masters degree. I just want to get some facts straight here. I was told casually by a professor that RSA is equivalent to factoring, but I am having a hard time verifying this with resources online.

So, is breaking RSA generically equivalent to factoring as in the title of this paper? https://eprint.iacr.org/2008/260.pdf

What does it mean to use the word "generically" to describe the difficulty of breaking RSA.

Any other resources would be helpful.

$\endgroup$
3
  • 1
    $\begingroup$ Technically, RSA is secure under the RSA assumption, which is possibly weaker than the assumption that factoring is hard. See here: en.wikipedia.org/wiki/RSA_problem $\endgroup$ Commented Nov 24, 2014 at 19:45
  • $\begingroup$ At least 2 different users have entered this post and down-voted all the answers without leaving any reasonable explanation. Extremely rude. $\endgroup$ Commented Nov 24, 2014 at 19:59
  • $\begingroup$ Since I am trying to get the most reliable information as possible it would be nice to know which answers are mathematically correct and which are incorrect (if any). It is possible that the down votes refer to mathematical incorrectness or instead refer to the fact that they don't exactly answer my question. In either case I would also like an explanation. Whether the comment is correct or incorrect still provides me with useful information as long as I know which it is. $\endgroup$ Commented Nov 24, 2014 at 20:05

4 Answers 4

2
$\begingroup$

I am turning my comment into an answer.

RSA is secure under the RSA Assumption, which basically states that RSA is secure. This assumption is not known to be the same as the assumption that factorization is hard. While others have pointed out that factorization is sufficient to break RSA, it has not been proven that factorization is necessary to break RSA.

Supporting the position that breaking RSA is easier than factoring, if factoring is easy then the RSA secret key may be obtained from the public key, but breaking RSA encryption only requires distinguishing between the encryptions of two adversarially-chosen plaintexts, which is intuitively an easier task. Similarly, breaking RSA signing does not require obtaining the secret key, but instead forging the signature of an adversarially-chosen message, which is again intuitively easier. Of course I can't offer any proofs because the problem is open.


As for the meaning of the word "generically", it appears to mean "only by performing operations in the algebraic structure being analyzed" as opposed to exploiting additional structure, such as the bit representation of numbers. Note that proving the equivalence of factoring and the RSA assumption "generically" is a more modest result than proving their equivalence universally because the computational models that they consider have been restricted to just perform certain operations, and it's possible that by allowing other operations, the two problems are no longer equivalent.

$\endgroup$
2
  • $\begingroup$ So if I were to talk about this is it safe to say something like breaking RSA and factoring may not be of equivalent difficulty. I can then go on to say that if we know that factoring is easy, then we can certainly break RSA easily, and give some examples. For the converse, it is an open problem whether the difficulty of breaking RSA will imply that integer factorization is just as difficult. $\endgroup$ Commented Nov 24, 2014 at 20:08
  • $\begingroup$ Yes. The upshot is that the two problems are not known to be equivalent, despite what the other answers imply. $\endgroup$ Commented Nov 24, 2014 at 20:11
-1
$\begingroup$

The assumption in RSA is the hardness of computing $\phi(n)$ without knowing $p$ or $q$.

Given an algorithm which takes $n$ and computes $\phi(n)$, we can factor $n$ using $\phi(n)$:

  • $n = pq$

  • $\phi(n) = (p-1)(q-1) = pq-p-q+1 = n-\frac{n}{q}-q+1$

  • $q^2-(n-\phi(n)+1)q+n = 0$

  • $q = \frac{(n-\phi(n)+1)+\sqrt{(n-\phi(n)+1)^2-4n}}{2}$

  • $p = \frac{n}{q}$

$\endgroup$
9
  • $\begingroup$ @HenningMakholm: Please explain the down-vote. $\endgroup$ Commented Nov 24, 2014 at 19:47
  • $\begingroup$ x @barak: Heck if I know. $\endgroup$ Commented Nov 24, 2014 at 19:51
  • $\begingroup$ @HenningMakholm: What does that mean? $\endgroup$ Commented Nov 24, 2014 at 19:51
  • $\begingroup$ x @barak: I have no information about why whoever downvoted did so. $\endgroup$ Commented Nov 24, 2014 at 19:52
  • $\begingroup$ RSA security requires being unable to distinguish between the ciphertexts of two adversarially-chosen plaintexts, which seems to be stronger than the hardness of computing $\phi(n)$. $\endgroup$ Commented Nov 24, 2014 at 20:15
-2
$\begingroup$

I think the idea is this: the RSA algorithm is powerful because it relies on the fact that for large numbers, say numbers with 200 digits, it is very difficult to factor them or even find out if they are composite. If we were somehow able to figure a way to factor large numbers relatively easily, then the RSA algorithm would no longer be that powerful, thus it would be "broken".

Edit: As for what "generically" means, it might explain that in the paper but my guess is that the author is using the word "generic" to mean that this is characteristic of the RSA algorithm, i.e. that is why we can say it is equivalent to factoring.

$\endgroup$
2
  • 2
    $\begingroup$ This describes one direction of the equivalence. The interesting direction is the other one: If I had an oracle for decrypting RSA messages given the public key, could I somehow use that to factor numbers? $\endgroup$ Commented Nov 24, 2014 at 19:27
  • $\begingroup$ Right. This is is what I was wondering. The first direction is pretty obvious. As suggested here crypto.stanford.edu/~dabo/papers/no_rsa_red.pdf, computing $e^{th}$ roots modulo $n=pq$ might be easier than factoring $n=pq$ $\endgroup$ Commented Nov 24, 2014 at 19:32
-2
$\begingroup$

The general concept behind cryptography is the requirement that one operation takes a small amount of time, while undoing the same operation without a priori knowledge must take a large amount of time.

The entire premise of RSA is the idea that the time complexity to multiply two numbers together is much lower than factoring a number into two numbers. Thus, we might be able to encrypt a message in a few seconds, but it might takes years to decrypt the message without the key. If we could find a faster way to factor a number, then the entire premise behind RSA would be invalidated.

Obviously there is more to it than that, but it is the underlying premise, hence 'generically'.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .