2

Given c1 = cipher text of m encrypted with n1 and e Given c2 = cipher text of the same m encrypted with n2 and the same e, Is it possible to figure out either of the n's or m? I can't seem to solve for it myself, but I know that doesn't mean it isn't possible!

1

1 Answer 1

5

If RSA is done properly (as per PKCS#1), then no.

If RSA is done very improperly (i.e. without any kind of padding), then message reconstruction is possible if you encrypt the same message m with e distinct RSA keys, provided they all use e as public exponent. This is done with the Chinese Remainder Theorem: since n1, n2... ne are all relatively prime to each other (otherwise a simple GCD will break two keys, at which point the problem is solved), knowing me modulo all the ni is sufficient to rebuild me modulo the product of all the ni. So you recompute me modulo N = n1n2...ne. However, m is smaller than each ni, so me is smaller than N. In other words, you get me itself, not me modulo some integer. Computing an e-th root in the non-modular integers is easy, and this reveals m.

I insist, this is not a weakness of RSA. Rather, it is an illustration of why RSA, the real one, is not merely a modular exponentiation, but includes a padding step (and that padding includes random bytes, which is also important for a completely different reason). The RSA-without-padding is often called "textbook RSA" because most textbooks describe RSA that way.

You must log in to answer this question.

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