The Matrix

Platform: cryptohack | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-06-22 | Status: Solved Techniques: bit_unpacking, gf2_matrix_exponentiation, inverse_exponent_mod_order, matrix_order_via_minpoly_factorization

Summary

Task: a 50x50 invertible matrix over GF(2) encodes the flag bits (mat[i][j]=msg[i+jN]) and only ciphertext=mat^E with public E=31337 is given. Solution: a matrix over a finite field is periodic, so compute the multiplicative order of the ciphertext matrix via factoring its minimal polynomial over GF(2) (ord(C)=351843720888315), invert the exponent d=E^-1 mod ord, recover mat=C^d by fast GF(2) matrix exponentiation (verify mat^E==C), then read the first 280 flag bits from mat[i][j]=msg[i+jN].

The Matrix — cryptohack (Diffie-Hellman)

Description

"I must get out of here. I must get free, and in this mind is the key, my key!" Challenge files: the_matrix.sage, flag.enc. Contributed by jschnei.

The flag bits are packed column-wise into a 50x50 matrix over GF(2), then "encrypted" by raising the matrix to a fixed public power E = 31337:

 python read-only • copy allowed Copy
P = 2; N = 50; E = 31337
def generate_mat():
    msg = bytes_to_binary(FLAG)
    msg += [random bits to fill N*N]
    rows = [msg[i::N] for i in range(N)]      # mat[i][j] = msg[i + j*N]
    mat = Matrix(GF(2), rows)
    if mat.determinant() != 0 and mat.multiplicative_order() > 10^12:
        return mat
ciphertext = mat^E
save_matrix(ciphertext, 'flag.enc')           # only C = mat^E is published

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

We get only C = mat^E. Goal: undo the exponentiation to recover mat, then the flag bits.

Recon / Analysis

An invertible matrix over a finite field lives in the finite group GL(N, GF(2)), so it has a finite multiplicative order r = ord(C). If gcd(E, r) = 1, then E is invertible mod r, and:

mat = C^d   where   d = E^-1 mod r        (because (mat^E)^d = mat^(E*d) = mat^1)

So the whole challenge is computing ord(C). The order divides lcm of the orders contributed by the irreducible factors of the minimal polynomial of C over GF(2); factoring minpoly(C) and combining the per-factor multiplicative orders gives the exact order. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

ord(C) = 351843720888315
gcd(31337, 351843720888315) = 1   ->  E invertible mod ord

Solution

1. Load C as a GF(2) bit-matrix (each row a bitmask).
2. Compute ord(C) via minimal-polynomial factorization over GF(2).
3. d = pow(E, -1, ord); mat = C^d by square-and-multiply GF(2) matrix exponentiation.
4. Verify mat^E == C.
5. Read flag bits back out: mat[i][j] = msg[i + j*N], take the first 35*8 = 280 bits.

 python read-only • copy allowed Copy
from gf2 import load_bitmatrix, matpow
from order_gf2 import matrix_order
from math import gcd
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

N = 50; E = 31337
C, n = load_bitmatrix("flag.enc")              # C[i] bitmask, bit j = entry [i][j]

ordC = matrix_order(C, n)                       # via minpoly factorization over GF(2)
assert gcd(E, ordC) == 1
d   = pow(E, -1, ordC)
mat = matpow(C, d, n)
assert matpow(mat, E, n) == C                   # verify the inverse exponent

# mat[i][j] = msg[i + j*N]  ->  bit k has i=k%N, j=k//N
def bit(i, j): return (mat[i] >> j) & 1
bits = [bit(k % N, k // N) for k in range(35 * 8)]
flag = bytes(
    sum(bits[b + t] << (7 - t) for t in range(8))
    for b in range(0, len(bits), 8)
)
print(flag)

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

ord(C) = 351843720888315
recovered mat, verified mat^E == C
crypto{REDACTED}

Takeaways

• "Encrypting" by raising an invertible matrix over a finite field to a public power is trivially reversible: the matrix group is finite, so compute the order r and invert the exponent d = E^-1 mod r (RSA-style, but the modulus is the group order, which here is small and public-derivable).
• Get the matrix multiplicative order from the minimal polynomial factorization over the base field, combining the orders contributed by each irreducible factor.
• The challenge even hands you ord > 10^12 as a hint — it's small enough to factor E against.
• Recognize it by: a single matrix as ciphertext, a public exponent, and a known bit-packing layout (mat[i][j] = msg[i + j*N]) to reassemble the plaintext after recovery. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍