This is a post about the crypto challenge embedded in the promo video for Hackerakademiet.
The video contains a couple of frames showing parts of the challenge. The frames show three of the same formatted text, each containing a public key for a team, and a cipher text. The three ciphertexts and public keys are all different, but about the same size. It also hints at the same file ("Operation_plan.txt") being encrypted three times.
Notably the public key contains an N and an e, and the e is 3.
Since we're in possession of three such messages, the challenge can be rather easily solved as a congruence system.
CRT
This involves using the Chinese Remainder Theorem, this theorem states that if the moduli of congruences are pairwise coprime, a unique soluion to the system exists and can be found. I will leave the proof for this to wikipedia. I will also not go into doing this by hand, as it is completely infeaseble in this case.
Let's say we have 3 ciphertexts, and corresponding 3 public keys.
c1, c2, c3
N1, N2, N2
e = 3
Assuming that the plaintexts are the same for the three ciphertexts, the following system can be solved for m^3.
m^3 = c1 mod (N1)
m^3 = c2 mod (N2)
m^3 = c3 mod (N3)
Notably CRT requires the moduli to be pairwise prime, and in the case of RSA, if they wouldn't be, the system would be broken since we would have a non-trivial factor of the Ni.
Solving the problem with CRT, we're left with finding the precise integer cubic-root of m. This can be difficult, but is doable in this case.
Sagemath
Sage has rather good speed on solving congruence systems with CRT, the following sage python code is used to solve the challenge:
def nroot(x,n):
return x**(1/n).n(digits=50000)
n1 = int(0xa5d1c341e4837bf7f2317024f4436fb25a450ddabd7293a0897ebecc24e443efc47672a6ece7f9cac05661182f3abbb0272444ce650a819b477fd72bf01210d7e1fbb7eb526ce77372f1aa6c9ce570066deee1ea95ddd22533cbc68b3ba20ec737b002dfc6f33dcb19e6f9b312caa59c81bb80cda1facf16536cb3c184abd1d5)
n2 = int(0xaf4ed50f72b0b1eec2cde78275bcb8ff59deeeb5103ccbe5aaef18b4ddc5d353fc6dc990d8b94b3d0c1750030e48a61edd4e31122a670e5e942ae224ecd7b5af7c13b6b3ff8bcc41591cbf2d8223d32eeb46ba0d7e6d9ab52a728be56cd284842337db037e1a1da246ed1da0fd9bdb423bbe302e813f3c9b3f9414b25e28bda5)
n3 = int(0x5ca9a30effc85f47f5889d74fd35e16705c5d1a767004fec7fdf429a205f01fd7ad876c0128ddc52caebaa0842a89996379ac286bc96ebbb71a0f8c3db212a18839f7877ebd76c3c7d8e86bf6ddb17c9c93a28defb8c58983e11304d483fd7caa19b4b261fc40a19380abae30f8d274481a432c8de488d0ea7b680ad6cf7776b)
c1 = int(0x9d0cc43ff3d1375671980076ad7b3940cb0d570e1ec355d4b9a2236d793fa86ccd88063c37c774279b41ef44190cd9896a58f303fa3474e7f921d176da637910998f8b005a85d850054bd5502bd751a8e0088fc765a2be21bcff2a2c7a6f48d71fac2f557decb65adaf9749897aacf6fd9574ad18cf060050015cca371b5af5d)
c2 = int(0x085441ba6d8c7e4745aa2e8ef338fe79b4e24f323e987d2f582aa08db7b590bffe75346600f3058e331ce042c0194074b9102409b755d9c5cae5c26f304e051d60a9206eddb9101727d13cd472399186e32b4acd85e7c12b698ef0cc18ccd4cdaca381f040090f08a34f2cc88d95b8310c5ccad50fb177bf3b4d76e847b9a4f2)
c3 = int(0x391294eacc25e9be7ed3f131dca286977cd55cbbbfb55b3eef9dba88fcea02a089c5226eb87ce752477225dd0c09d68b0fb35caf01f1d72abad950b9a0cf46a37b19179df440d653bf9290fab4a290c82f746bde440ed0e593fb495a0dd41296f491ecbaf09943fbf5de1ea763e843057c2e785049be8e7050c79fe2b93d8f93)
a = CRT_list([c1,c2,c3], [n1,n2,n3])
b =int(a)
c = nroot(a,3)
In retrospect, the hardest part of this challenge was transcribing the text from the images... :-)
Sources
https://cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/rsa.pdf