The Matrix Reloaded

Useful Sage documentation link about the syntax for matrices.

We are given a somewhat similar to a Diffie-Hellman key-exchange, a secret $s$$s$ is picked out, then $H=G\ast s$$H = G * s$ is calculated. They also generate a random vector $v$$v$ in the matrix space. The product of $H\times v=w$$H \times v = w$ is calculated. Given the two vectors $v,w$$v, w$, we have to derive the value of the secret $s$$s$ to obtain the decryption key.

The solution was just under my nose. Seems like Googling for some plural version discrete logarithm matrices leads us to this excellent resource to solve this problem.

I initially Google something like discrete logarithm matrix ctf, which leads to this CTF Writeup, discussing how to solve $G^x=H$$G ^ x = H$, with given matrices $A$$A$ and $B$$B$. The challenge name is Neo-Classical Key Exchange, detailing how we can use Jordan Canonical Form of the generator matrix $G$$G$ to solve for $x$$x$.

Unfortunately, the above does not work as generally, there are infinitely many solutions for $H$$H$ given $v,w$$v, w$ (as one can only construct $n$$n$ equations, while we need $n^2$$n^2$ entries to reconstruct matrix $H$$H$). Hence, this approach is discarded.

The first link on Crypto StackExchange should shed light on how to solve the problem, so I don't want to go into the math again. The Wikipedia link shows the concepts of "blocks" in Jordan Canonical Form. With this established, let's dive into the analysis.

We can first analyze the Jordan Normal form of the given generator matrix $G$$G$. The mathematical form is $PJ{P}^{-1}$$P J P^{-1}$. The formula for $H$$H$, or $G^s$$G ^ s$ will thus be $P{J}^s{P}^{-1}$$P J^{s} P^{-1}$.

Hence, the given equation becomes:

I did in this way:

xxxxxxxxxx
g, p = G.jordan_form(transformation=True)
f = open('test.txt', 'w')
f.write(str(g))

There are also neater ways to display the matrix also, kudos to hellman:

xxxxxxxxxx
for row in G.jordan_form():
    print(*["0X"[bool(v)] for v in row])

The output will look something like this:

xxxxxxxxxx
X 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 0 0 0 0
0 X 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 0 0 0
0 0 X 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 0 0
0 0 0 X 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 0
0 0 0 0 X 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
0 0 0 0 0 X 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 0 0 0 0 0 X 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 0 0 0 0 0 X 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 0 0 0 0 0 X 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 0 0 0 0 0 X 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 0 0 0 0 0 X 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 0 0 0 0 0 X 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 0 0 0 0 0 X 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 0 0 0 0 0 X 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 0 0 0 0 0 X 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 0 0 0 0 0 X 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 0 0 0 0 0 X 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 0 0 0 0 0 X 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 0 0 0 0 0 X 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 0 0 0 0 0 X 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 0 0 0 0 0 X 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 0 0 0 0 0 X 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 0 0 0 0 0 X 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 0 0 0 0 0 X 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 0 0 0 0 0 X 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 0 0 0 0 0 X 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 0 0 0 0 0 X 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 0 0 0 0 0 X 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 0 0 0 0 0 X X
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 0 0 0 0 X

where X represent some non-zero element. Hence, we can observe that the matrix "almost" diagonalizes. If it DOES diagonalize, then solving DLP is hard. Luckily, we can still consider the non-diagonalized block in the bottom right corner.

Call this mini-matrix $J^{\prime }$$J'$, then $J^{\prime k}$$J' ^ k$ is given by:

Following the CryptoStackExchange link, we can manipulate the given equation a bit:

Thus, denote $a=P^{-1}v=(x_1,x_2,...,x_{n-1},x_n)$$a = P^{-1} v = (x_1, x_2, ..., x_{n - 1}, x_{n})$ and $b=P^{-1}w=(y_1,y_2,...,y_{n-1},y_n)$$b = P^{-1} w = (y_1, y_2, ..., y_{n - 1}, y_{n})$, we can recover $s$$s$ by doing:

We can easily verify the correctness of this formula, and again, the first Crypto StackExchange link should show why. Since the $2\times 2$$2 \times 2$ matrix we are trying to do this is in the rightmost corner, hence only the terms of $x_{n-1},x_n$$x_{n - 1}, x_{n}$ and $y_{n-1},y_n$$y_{n - 1}, y_{n}$ are involved (this link should clarify if you do not understand what I am talking about).

With these, we can obtain the secret $s$$s$, and thus the flag.

Sage Implementation:

xxxxxxxxxx
from Crypto.Cipher import AES
from Crypto.Hash import SHA256
from Crypto.Util.number import *
from Crypto.Util.Padding import pad, unpad

import json


FLAG = b'crypto{?????????????????????????????????????}'

P = 13322168333598193507807385110954579994440518298037390249219367653433362879385570348589112466639563190026187881314341273227495066439490025867330585397455471
N = 30

# Not actually used, but useful for solving G ^ k = H
# May be used later
def solve_dlog(G, H):
    R = IntegerModRing(P)
    M = MatrixSpace(R, N, N)
    g = M(G)
    h = M(H)

    g, p_mat = g.jordan_form(transformation=True)

    h = p_mat.inverse() * h * p_mat

    a11 = g[N - 2][N - 2]
    b11 = h[N - 2][N - 2]
    b12 = h[N - 2][N - 1]

    return (a11 * b12 / b11)

def load_matrix(fname):
    data = open(fname, 'r').read().strip()
    rows = [list(map(int, row.split(' '))) for row in data.splitlines()]
    return Matrix(GF(P), rows)

G = load_matrix("generator.txt")
g, p = G.jordan_form(transformation=True)

f1 = open('output.txt', 'r')
dh = json.loads(f1.readline())
v = vector(GF(P), dh['v'])
w = vector(GF(P), dh['w'])

a = p.inverse() * v
b = p.inverse() * w 
theta = g[N - 2][N - 2]

# Solution to dlog
SECRET = theta * (b[N - 2] - (a[N - 2] * b[N - 1]) / a[N - 1]) / b[N - 1]
KEY_LENGTH = 128
KEY = SHA256.new(data=str(SECRET).encode()).digest()[:KEY_LENGTH]

ct = open('flag.enc', 'r')
enc_flag = json.loads(ct.readline())
iv = bytes.fromhex(enc_flag['iv'])
ciphertext = bytes.fromhex(enc_flag['ciphertext'])

cipher = AES.new(KEY, AES.MODE_CBC, iv)
print(unpad(cipher.decrypt(ciphertext), 16))