I am trying to understand the RSA broadcast attack, and have become quite confused. Maybe someone on here can help me to understand and learn how to solve a problem. I have been given a message that was encrypted with three individual RSA public keys (N1,N2,N3), resulting in three cypher texts (C1,C2,C3). The public exponent e=3. I understand from Hastads's broadcast attack that:
c1≡m3 mod N1,
c2≡m3 mod N2,
c3≡m3 mod N3.
Using the Chinese remainder theorem, it should be possible to find a fourth cipher text value C4 that has the following properties:
c4≡c1 mod N1,
c4≡c2 mod N2,
c4≡c3 mod N3,
c4≡m3 mod (N1 N2 N3)
In theory, I should be able to solve for m=∛c4, or (m=cube root of c4). Here is where I'm stuck, and my woeful understanding of math is no help.
Can I simply solve for c4 by letting c4= C1 mod N1? Using the values provided to me (actual hex numbers)? And then use this c4 value in m=∛c4 equation? This seems way too simple, and I don't think it will produce the correct value. Any help is greatly appreciated; I'm trying to solve the problem, but also wish to gain a better understanding of Hastads attack and Chinese remainder theorem. Thank you!
1 Answer
C4 is already C1 in mod N1. You get nothing from there.
The Hastads attack works for small encryption exponent since the modulus reduction is not performed.
You only need to perform a cube root algorithm.
