Multiple Ciphertexts
Last updated
Was this helpful?
Last updated
Was this helpful?
Common Modulus Attack is used when the same plaintext is encrypted twice with the same modulus but distinct public exponent and . In other words:
If and are coprime, then Bezout's Identity tells us that s.t.
Here and can be solved using extended Euclidean Algorithm. Once we know and , we could compute
Correctness:
Chinese Remainder Theorem tells us the solution to the following equation exists:
Hastad Broadcast Attack is used when the same plaintext is encrypted multiple () times with the same public exponents but distinct modulus . In other words:
Denote this solution as . Chinese Remainder Theorem also provides a method for computing :
where . Note that the plaintext , hence . As a result, taking -th root of gives us the plaintext . No need to worry about modulo since is not large enough.