Shared modulus attack on RSA

Question

Consider a scenario in which a group of people use a common modulus $n$ in the textbook RSA crypto system,
where $n=pq$, $p$ and $q$ are large distinct prime numbers.

Is there any chance for an attacker outside the group to view the original message?

Let me explain my solution. Assume the group members receive the same message. So $c_1= m^{e_1} \bmod n$ and $c_2= m^{e_2} \bmod n$. Assume $e_1$ and $e_2$ are co-prime. So if we can find $x, y$ satisfying $e_1x+ e_2y=1$ then an attacker can view the original message. Am I correct?

Answer 1

When you have a RSA key pair, it means that you know the private key (otherwise this is not "your" key pair). The private key format, normally, contains the two factors $p$ and $q$ (at least so it goes with PKCS#1). Even if all you have are the modulus $n$, the public exponent $e$ and the private exponent $d$, the factorization of $n$ can still be worked out from $e$ and $d$ (see this answer for a detailed description). The bottom-line is that if two people "share the same modulus" then they also both know the private keys of each other. In effect, there is only one actual key pair and they both know it.

The "shared modulus" situation is thus mostly irrelevant.

---

A second, most important point is that what you described ($c = m^e \pmod n$) is not RSA. It is often, confusingly, called "textbook RSA"; in the same way, a car engine, resting on the floor, could be called a "textbook Ferrari". RSA, as an asymmetric encryption algorithm, is a combination of several operations; the modular exponentiation is the most CPU-intensive of them, but not the only one, and the other operations are very important for security. In the case of PKCS#1, what enters the exponentiation is the padded message; the padding includes random bytes.

Even if you imagine a setup where the same message $m$ will be encrypted twice, once with $(n,e)$ and once with $(n,e')$ (same modulus, but distinct exponents), what will be really exponentiated will be, in the first case, a padded value $x$ that includes $m$ and some randomness, and, in the second case, another padded value $x'$ that includes $m$ and some other, distinct randomness. This would avoid the reconstruction of $m$ by an attacker observing both encrypted messages.