RSA Possible Vulnerability?

Question

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!

Answer 1

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 n₁, n₂... n_e are all relatively prime to each other (otherwise a simple GCD will break two keys, at which point the problem is solved), knowing m^e modulo all the n_i is sufficient to rebuild m^e modulo the product of all the n_i. So you recompute m^e modulo N = n₁n₂...n_e. However, m is smaller than each n_i, so m^e is smaller than N. In other words, you get m^e itself, not m^e 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.