0

Alice has public key (n,ea) and Bob has public key (n,eb) with gcd(ea,eb)=1. If sent the same message m to Alice and Bob, how someone who follow the channel can find m ?

iostream007
  • 4,529
SSMath
  • 49
  • 4
  • We consider that the eavesdropper knows the K1, K2,n and wants to find M, where Ki= M^2 mod n ...? We can solve these equations using Chinese theorem? – SSMath May 17 '13 at 09:09
  • PLease may you tidy up the english in your please it is a little difficult to read as it is – Kane Blackburn May 17 '13 at 09:14

1 Answers1

1

The eavesdropper gets $r=m^{e_a}\mod n$ and $s=m^{e_b}\pmod n$. Since $\gcd(e_a,e_b)=1$, eavesdropper can find $x,y$ with $e_ax+e_by=1$ (right?). Eavesdropper calculates $r^xs^y$. Can you take it from there?

Gerry Myerson
  • 179,216
  • Could you tell what theorem you are using in order to follow? – SSMath May 17 '13 at 13:00
  • I think the only theorem I am using is the one that says that integers $r$ and $s$ are relatively prime if and only if there are integers $x$ and $y$ such that $rx+sy=1$. Well, that and the laws of exponents, $(a^b)^c=a^{bc}$, $a^ba^c=a^{b+c}$, $a^1=a$. – Gerry Myerson May 17 '13 at 23:23