2

Alice and Bob are using different public keys, Alice is using ($N_{1,2}$) and Bob ($N_{2,2}$). A message, $m$ is sent to both of them using their RSA systems. It is also true that $N_1$ and $N_2$ are relatively prime.

Can anyone explain how Eve can now find $m$? I'm quite sure it has an application of the Chinese remainder theorem.

user35603
  • 3,002
user166421
  • 31

1 Answers1

1

This is known as the Håstad's Broadcast Attack. If all public exponents are equal to $e$, Eve can recover $m$ as soon as the number of parties is greater than or equal to $e$.

Suppose Eve collects $c_1$ and $c_2$, where $c_i \equiv m^2\pmod {N_i}$, $i = 1, 2$. By the Chinese Remainder Theorem, Eve may compute $c \in \mathbb Z_{N_1 N_2}$ such that $c \equiv m^2\pmod {N_1 N_2}$. $c = m^2$ holds over the integers, so Eve can compute the square root of $c$ to obtain $m$.

  • Thank you, Do you know exactly how she uses the Chinese remainder theorem to do this ? – user166421 Jul 26 '14 at 13:42
  • Thank you, Do you know exactly how she uses the Chinese remainder theorem to do this ? is it using some for of euclids algorithim @Stavros – user166421 Jul 26 '14 at 14:00
  • It's just an application of CRT. We know that $N_1$ and $N_2$ are relative prime. Then, for the given sequence of integers $c_1, c_2$, there exists an integer $x$ solving the system of the following simultaneous congruences: $x \equiv c_1\pmod {N_1}$ and $x \equiv c_2\pmod {N_2}$. –  Jul 26 '14 at 14:11
  • The requirement for Hastads Broadcast attack state that m < N1 and m<N2. However in my question the only condition is that m < N1. Any ideas on how to overcome this @Stavros Mekesis – user166421 Jul 27 '14 at 20:28
  • Are you sure that the only given is $m < N_1$? Beware of the fact that if $m > N_2$, you won't get the exact $m$ back when you decrypt $c_2$. –  Jul 27 '14 at 21:33