I have a situation in RSA like this.

Charles sends same message $m$ to Alice and Bob encrypted with $e_A$ and $e_B$ respectively. It happens that he they are under same modulus $n$ and $gcd(e_A, e_B)=1$. Now Eve intercepts two messages $c_A$ and $c_B$. The claim is that Eve can easily get $m$ in this situation.

My thought on this case is follows:

  1. With $e_A$ and $e_B$ coprime, Eve can use the extended Euclidean algorithm to get solution to $1=a_1e_A+a_2e_B$. She then calculate $(c_A)^{a_1}(c_B)^{a_2} \bmod n = m \bmod n $

  2. Now the problem is that one of $a_1$ and $a_2$ is actually negative (let's assume $a_1$). So the above $(c_A)^{a_1}$ involves calculation of an inverse modulo $n$. Yet I think $c_A$ is not necessarily be invertible.

  3. An concrete example I can think of: $p=5$, $q=7$, $n=35$, $\phi(n)=24$, $e=11$, $m=21$, in this case, $c_A = 21$, not invetible.

I think somehow Eve must be able to recover the message. But I simply got stuck in above analysis.

Am I missing something? Please point out! Thanks so much!


1 Answer 1


Hint: if $c_A$ is not invertible, what does that say about $gcd(c_A, n)$? How can you exploit that to obtain $m$ in another way?

  • $\begingroup$ Good way to give the answer to the question. $\endgroup$
    – ddddavidee
    Oct 24, 2014 at 12:11
  • $\begingroup$ Oh exactly. How come I didn't think about that. Thanks so much! $\endgroup$
    – Ray
    Oct 24, 2014 at 13:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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