When Students Fix Crypto Bugs, You Have Great Students

Every teacher thinks they have the best students, and on our Applied Cryptography module, we have some amazing students.

So I set a challenge of:

Bob has used the RSA method with three different moduli to encrypt the same message for Alice. These modulus values are 1594022851, 1608005621, and 2695456781. The corresponding ciphered values are 947692931, 369611262, and 1596261156. Determine the English town.

The generator for this is here:

CTF: Cracking RSA with Chinese Remainder Theory - Håstad's Broadcast Attack

And, diligently one of our students set about the problem, and was left puzzled:

“Hmm, been trying this aswell, I didn’t go with the CRT approach initially, since the moduli are small I could easily factorise into p & q, then select the lowest common value for the public exponent e (which is 5 as it turns out, 3 won’t work for the second and third, 5 works for all i.e., an inverse exists). Ok, decrypting with these gives gobbldygook, I can't be sure what public key was used — when I try the CRT it won't work (because the assumption is that e = 3 ). When I…