# If the same message is sent to Alice and Bob who are using different public keys, how can somoene following the channel find $m$

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.

• You have to use the Chinese remainder theorem to find m^2modN1N2. Does anyone know how to find this? Commented Jul 26, 2014 at 12:26

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 ? Commented Jul 26, 2014 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 Commented Jul 26, 2014 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}$.
– user21530
Commented Jul 26, 2014 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 Commented Jul 27, 2014 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$.
– user21530
Commented Jul 27, 2014 at 21:33