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 $2\times 2$ matrices over a finite field using a Montgomery ladder algorithm, so we have to find a way to solve the Diffie-Hellman problem in these (in fact, we will even compute logarithms).

The description of the protocol reads typical for a Diffie-Hellman-style system:

• Upon receiving a new connection, the server generates a prime $p$ of 64 bits and sends it to the client.
• The server generates a keypair: The private key is a randomly generated integer $x$; the corresponding public key is the $x$th power of the matrix \[A:=\begin{pmatrix}0&1\\1&1\end{pmatrix}\in(\mathbb Z/p)^{2\times 2}\] over the residue field $\mathbb Z/p$. As usual, the public key is sent to the client. (In fact, only the first row $\begin{pmatrix}a&b\end{pmatrix}$ of the matrix is transmitted, but due to the structure of $A$, the second row is easily seen to be $\begin{pmatrix}b&a+b\end{pmatrix}$, hence is redundant. This is tied to the fact that $A$ is chosen in such a way that its powers’ coefficients are just the Fibonacci numbers reduced modulo $p$.)
• The client then proceeds analogously, using the same $p$ but a different randomly generated exponent $y$.
• Raising the received public key to the $x$th or $y$th power, respectively, yields a shared “secret” $A^{xy}$ which is then used by the server to derive an AES key under which the flag is encrypted and sent to the client.

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 $x$ from the public (i.e. contained in the network dump) matrix $A^x$, we can simply compute the shared secret $A^{xy}$ and decrypt the flag. We let $B\in(\mathbb Z/p)^{2\times 2}$ denote the matrix $A^x$ obtained from the packet dump, hence our task is to compute the logarithm $\log_A B$ in $(\mathbb Z/p)^{2\times 2}$.

If we could diagonalize the matrix $A$, that is, obtain an invertible matrix $S\in(\mathbb Z/p)^{2\times 2}$ such that $S^{-1}AS$ is a diagonal matrix, then also $S^{-1}BS$ is a diagonal matrix and the exponentiation acts coefficient-wise, so we could compute the logarithm on the coefficients of the diagonalized matrices. By “exponentiation acts coefficient-wise”, we mean that for all $2\times 2$ diagonal matrices and exponents $e$, \[ \begin{pmatrix}a&0\\0&b\end{pmatrix}^e = \begin{pmatrix}a^e&0\\0&b^e\end{pmatrix} \text. \] Moreover, if $S$ is an invertible $2\times 2$ matrix such that $S^{-1}AS$ is diagonal (hence $S^{-1}BS$ is), then $A^x=B$ if and only if $S^{-1}A^xS=S^{-1}BS$ if and only if $(S^{-1}AS)^x=S^{-1}BS$, and this means we can compute the logarithm on the diagonalized matrices’ coefficients.

However, this is not immediately possible: $A$’s characteristic polynomial \[ \chi_A=\xi^2-\xi-1 \] is irreducible over $\mathbb Z/p$, hence $A$ has no eigenvalues in that field. But we can transition to an extension field in which $A$ is diagonalizable: Over the field \[ F\;:=\;(\mathbb Z/p)[\xi]/\chi_A \;\cong\; \mathbb F_{p^2} \text, \] the matrix $A$ does have distinct eigenvalues, namely the images of $\xi$ and $\xi^p$ in $F$.

Using the canonical injection $\mathbb Z/p\hookrightarrow F$, we may now consider $A$ and $B$ as matrices over $F$ and compute an invertible matrix $S\in F^{2\times 2}$ along with diagonal matrices $D_A,D_B\in F^{2\times 2}$ such that \[ D_B = S^{-1}BS = S^{-1}A^xS = (S^{-1}AS)^x = D_A^x \text, \] therefore we can now compute $x$ component-wise as the logarithm of a pair of corresponding diagonal entries of $D_A$ and $D_B$: If $D_A$’s upper left entry is $a$ and $D_B$’s upper left entry is $b$, then $x=\log_a b$. Since $a,b\in\mathbb Z/p$ and $p$ is so small, this is very much feasible.

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 $x$!) along with the other information from the network dump into the given client code and running it yields the flag!

9447{Pisan0_mU5t_nEv3r_hAve_THougHt_0f_bruTe_f0rce5}