Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

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!

share|improve this question
    
This would be more on topic at crypto.stackexchange.com –  Ilmari Karonen Apr 28 '13 at 23:08
add comment

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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