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

422 Views Asked by At

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.

1

There are 1 best solutions below

5
On

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$.