"It is my experience that proofs involving matrices can be shortened by 50% if one throws the matrices out." Emil Artin
We are given the main code running on the server in server.py, and gen.py which generates an encrypted message using RSA. We are given the RSA modulus n, exponent e and ciphertext c.
# server.pyfrom Crypto.Util.number import bytes_to_long, long_to_bytesfrom itertools import permutationsfrom SECRET import FLAG, p, q, rdefinputs():print("[DET] First things first, gimme some numbers:") M = [ [0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0], ]try: M[0][0] = p M[0][2] =int(input("[DET] M[0][2] = ")) M[0][4] =int(input("[DET] M[0][4] = ")) M[1][1] =int(input("[DET] M[1][1] = ")) M[1][3] =int(input("[DET] M[1][3] = ")) M[2][0] =int(input("[DET] M[2][0] = ")) M[2][2] =int(input("[DET] M[2][2] = ")) M[2][4] =int(input("[DET] M[2][4] = ")) M[3][1] = q M[3][3] = r M[4][0] =int(input("[DET] M[4][0] = ")) M[4][2] =int(input("[DET] M[4][2] = "))""" M = [ [p, 0, x, 0, x], [0, x, 0, x, 0], [x, 0, x, 0, x], [0, q, 0, r, 0], [x, 0, x, 0, 0], ] """except:returnNonereturn Mdefhandler(signum,frame):raiseException("[DET] You're trying too hard, try something simpler")deffun(M):defsign(sigma): l =0for i inrange(5):for j inrange(i +1, 5):if sigma[i]> sigma[j]: l +=1return (-1)**l res =0for sigma inpermutations([0,1,2,3,4]): curr =1for i inrange(5): curr *= M[sigma[i]][i] res +=sign(sigma)* currreturn resdefmain():print("[DET] Welcome") M =inputs()if M isNone:print("[DET] You tried something weird...")return res =fun(M)print(f"[DET] Have fun: {res}")if__name__=="__main__":main()# gen.pyfrom SECRET import FLAG, p, q, rfrom Crypto.Util.number import bytes_to_longn = p * qe =65535m =bytes_to_long(FLAG)c =pow(m, e, n)# printed to gen.txtprint(f"{n = }")print(f"{e = }")print(f"{c = }")
server.py imports the RSA primes p and q , along with r (but r is useless). main() first calls inputs(), which prompts us for entries to a matrix M. After inputting our values, M looks like this:
fun(M) is then printed. fun(M) is essentially using a permutation method to compute the determinant of a matrix. Let's compute the determinant of M using cofactor expansion:
Observing this expression closely, by controlling the different x values, we can obtain q alone. We can do this by setting x0=x2=x4=x6=x8=0 and x1=x3=x5=x7=1.
Providing these values to the server, we get that q = 12538849920148192679761652092105069246209474199128389797086660026385076472391166777813291228233723977872612370392782047693930516418386543325438897742835129. With q, we know n hence we can find p. We can then find phi and hence d. We can then find the plaintext m.