2
$\begingroup$

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.

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

1 Answer 1

Reset to default
1
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Thank you, Do you know exactly how she uses the Chinese remainder theorem to do this ? $\endgroup$
    – user166421
    Commented Jul 26, 2014 at 13:42
  • $\begingroup$ 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 $\endgroup$
    – user166421
    Commented Jul 26, 2014 at 14:00
  • $\begingroup$ 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}$. $\endgroup$
    – user21530
    Commented Jul 26, 2014 at 14:11
  • $\begingroup$ 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 $\endgroup$
    – user166421
    Commented Jul 27, 2014 at 20:28
  • $\begingroup$ 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$. $\endgroup$
    – user21530
    Commented Jul 27, 2014 at 21:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .