In this challenge, we were given the source code of a server and client along with a network dump generated from letting those communicate. The description reads:
Some secret communication was captured, and we’re having trouble decrypting it. Can you help?
The protocol consists of a Diffie-Hellman-style key agreement,
only the underlying operation seems to have been changed. Carefully reading
the code shows that the computation is performed in the ring of
The description of the protocol reads typical for a Diffie-Hellman-style system:
For completeness, here’s the relevant excerpts from the server code:
# fibCrypt.py
def mult(m1, m2, p):
r = [[0,0], [0,0]]
for i in range(2):
for j in range(2):
t = 0
for k in range(2):
t += m1[i][k] * m2[k][j]
r[i][j] = t % p
return r
def calcM(p, l, base):
if l == 0:
return [[base[1], base[0]], [base[0], base[1]]]
x1 = [[base[0], base[1]], [base[1], (base[0] + base[1]) % p]]
x2 = mult(x1, x1, p)
for i in bin(l)[3:]:
if i == '1':
x1 = mult(x1, x2, p)
x2 = mult(x2, x2, p)
else:
x2 = mult(x1, x2, p)
x1 = mult(x1, x1, p)
return x1
def genKey(p):
numBytes = int(math.ceil(math.log(p, 256)))
exp = int(os.urandom(numBytes).encode('hex'), 16) % p
r = calcM(p, exp, (0, 1))
return (r, exp)
# --------------------------------
# server.py
def handle(self):
p = fibCrypt.genPrime(8);
self.request.sendall(str(p) + "\n")
(key, secret) = fibCrypt.genKey(p)
self.request.sendall(str(key[0][0]) + "," + str(key[0][1]) + "\n")
parts = self.request.recv(200).split(",")
theirKey = (int(parts[0]), int(parts[1]))
shared = fibCrypt.calcM(p, secret, theirKey)
mess = encrypt(FLAG, str(shared))
self.request.sendall(mess + "\n")
self.request.close()
Hence, if we are able to compute the private exponent
If we could diagonalize the matrix
However, this is not immediately possible:
Using the canonical injection
Here’s sage
code that performs that computation:
#!/usr/bin/env sage
p = 981725946171163877
pubkey = 58449491987662952, 704965025359609904
A = matrix(Zmod(p), [[0,1],[1,1]])
B = matrix(Zmod(p), [pubkey, [pubkey[1], sum(pubkey)]])
# transition to a field extension over which A (hence B) is diagonalizable
K = PolynomialRing(Zmod(p), 'x').residue_field(A.charpoly(), 'y'); y = K.gen()
A, B = A.change_ring(K), B.change_ring(K)
# diagonalize A and B over K
DA, S = A.jordan_form(transformation = True)
DB = S.inverse() * B * S
print(DA); print(DB)
# finally compute the logarithm
print('\x1b[32m{}\x1b[0m'.format(int(DB[0][0].log(DA[0][0]))))
print('\x1b[32m{}\x1b[0m'.format(int(DB[1][1].log(DA[1][1]))))
Patching the obtained output
[ y| 0]
[------------------------+------------------------]
[ 0|981725946171163876*y + 1]
[ 704965025359609904*y + 58449491987662952 0]
[ 0 276760920811553973*y + 763414517347272856]
155959985731300133
155959985731300133
(the last two lines are the secret exponent
9447{Pisan0_mU5t_nEv3r_hAve_THougHt_0f_bruTe_f0rce5}