2
$\begingroup$

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?

Improve this question
$\endgroup$
13
  • $\begingroup$ Do you want any specific format for an answer to your homework dump? $\endgroup$ – DrLecter Sep 26 '15 at 16:22
  • $\begingroup$ This is not a homework. I'm studying RSA now. So thinking about different situations. OK. Let me explain my solution. Assume group members receive the same messages. So, c1= m^e1 mod n and c2= m^e2 mod n. Assume e1 and e2 are co-primes. so if we can find x, y s.t e1x+ e2y=1 then attacker can view the original message. Am I correct? $\endgroup$ – NinjaV Sep 26 '15 at 16:24
  • 1
    $\begingroup$ Did you search in the site before asking? What about this one?crypto.stackexchange.com/questions/16283/… $\endgroup$ – DrLecter Sep 26 '15 at 16:26
  • 1
    $\begingroup$ @Mr.Vendetta But what's the point of giving them different keys? Since each of them knows the factors of n, each of them can decrypt messages to any $e$. $\endgroup$ – CodesInChaos Sep 26 '15 at 17:05
  • 1
    $\begingroup$ @WDS: in RSA, the public exponent $e$ needs not be prime, and is not allways. The public exponent $e$ needs to be coprime with $\varphi(N)$, which is the case if $e$ is a small odd prime, and pulling a factor of $N$ is hard. $\endgroup$ – fgrieu♦ Sep 27 '15 at 7:47
3
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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