Matrix Over Mind

RSA lifted from scalars to 2×2 matrices over Z/nZ: C = M^e mod n, with the public constants trace(M) = T and det(M) = D. The matrix analogue of RSA still leaks the plaintext because the characteristic polynomial collapses matrix exponentiation to a short recurrence.

Files

• output.txt — n, e, T, D, ciphertext matrix C
• solve.sage
• README.md

Analysis

By Cayley-Hamilton, M satisfies

M² - T·M + D·I = 0

so every power of M reduces to a linear combination of I and M modulo that polynomial. Concretely, compute x^e mod (x² - T·x + D) in Z/nZ[x]:

R.<x> = PolynomialRing(Zmod(n))
A = power_mod(x, e, x^2 - T*x + D)      # A = A0 + A1·x

Then C = A₀·I + A₁·M, and A₁ is invertible with overwhelming probability:

M = (C - A0*identity_matrix(Zmod(n), 2)) * inverse_mod(A1, n)

The four entries of M are then converted to bytes (big-endian) and concatenated — the flag is the byte string spread across the matrix.

Why it fails

This isn't "RSA over matrices" in any secure sense. The public trace/determinant determine the ring generated by M, so the ciphertext is a linear function of the plaintext matrix; no factorisation or discrete log is needed. The scheme inherits RSA's algebra without its one-way structure.

Takeaway

Exponentiation in a commutative algebra is reversible when the algebra is low-dimensional and its structure is public. Publishing trace and det hands the attacker the entire characteristic polynomial — the minimal polynomial of the "private" element.

Flag

Flag: not recovered in the writeup.