Photo by Mauro Sbicego on Unsplash

RSA Capture The Flag For Chinese Remainder Thereom — Meet Håstad’s Broadcast Attack

Our students love doing Capture The Flag (CTF) exercises, and it is a great way to develop coding skills in translating different cipher values. Hopefully, along the way, they will learn some core theories about discrete logarithms and exponential ciphers. One common challenge is to solve an RSA cipher and where the same message has been ciphered with three different moduli. This attack is known as Håstad’s Broadcast Attack [1].

So let’s create a challenge generator, and with a sample question of:

Bob has used the RSA with three different modulus' to encrypt the same message for Alice. These modulus values are 1028541090183196101522935378951727053, 611800257738058721678060612021626303, and 637990920592078042917836803557776639. The corresponding ciphered values are 909627621704647324353263925942071968, 143590219961128784057515688652190875, and 240523521479830533690881019502697561. Determine the message.

and another:

Bob has used the RSA with three different modulus' to encrypt the same message for Alice. These modulus values are 16291690676599334881, 12809246438477591491, and 11540201434385924291. The corresponding ciphered values are 15398372416686382412, 9202230456851114422, and 8685470170547581956. Determine the message.