Suppose Alice, Abigail and Anna all have public keys with exponent e = 3, which Bob uses to encrypt the same message to send to each of them. Show how an attacker can obtain the key by intercepting these encrypted messages.

I have the answer for this question which says:

Bob sends $y1≡x^3\mod l,\ y2≡x^3\mod l,\ y3 ≡x^3 \mod l.$ An attacker can then compute $Y < lmn$ such that: $$Y ∼= y1\ mod\ l,$$ $$Y ∼= y2\ mod\ m,$$ $$Y ∼= y3\ mod\ n$$

But $x^3 < lmn$, and so $x = Y^{1/3}$

I assume there is a typo in the answer and that the 3 messages should be $mod\ l$, $mod\ m$ and $mod\ n$ respectively instead of all being $mod\ l$.

But I am unsure exactly how this answers the question. How does the attacker compute $Y$?

  • 1
    $\begingroup$ en.wikipedia.org/wiki/Chinese_remainder_theorem $\endgroup$ – SEJPM May 6 '17 at 17:00
  • 1
    $\begingroup$ Also, the question had 'Show how an attacker can obtain the key', actually, the attacker can't obtain any of the keys; the attacker can obtain the message. Your answer does talk about obtaining the answer, and so this is just a typo within the question. $\endgroup$ – poncho May 6 '17 at 17:06

Your Answer

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

Browse other questions tagged or ask your own question.