← Landing page Writeups home

Use the tree to jump between collections without leaving the reader.

archive Select writeup Open tree
NullconCTF2026/WriteupMatrixfunII.en.md READ_ONLY

Matrixfun II (Crypto)

Challenge Data

Field Value
CTF Nullcon CTF 2026
Challenge Matrixfun II
Category Crypto
Flag ENO{l1ne4r_alg3br4_i5_ev3rywh3re}

Challenge Description

The server encrypted blocks over the Base64 alphabet using an affine transformation of the form c = A·x + b (mod 65). It also let us encrypt arbitrary messages with the same key. That oracle was enough to recover A and b.

Reconnaissance

Each block of 16 Base64 symbols was converted into indices 0..64, and over that vector the server applied this transformation.

c = A·x + b (mod 65)

With chosen plaintext encryption under the same matrix and the same vector, recovering the key came down to preparing the right inputs.

Analysis

There were two very simple observations here.

  • If the input block was all zeros, the output was directly b.
  • If the input block had a single 1 at position j, the output was column j of A plus b.

Since in Base64 the index 0 corresponds to 'a', the required messages were those whose first block represented this.

  • aaaaaaaaaaaaaaaa to obtain b
  • one block with a single 1 in the desired position to recover each column of A

Once b and the 16 columns of A were known, the only thing left was to invert the matrix modulo 65 and decrypt the initial ciphertext.

There was no need for brute force. The recovery came from exploiting the linearity of the scheme.

Solution

The full procedure was this.

  1. Save the flag ciphertext.
  2. Request the encryption of a block that translates to 16 zeros and extract b.
  3. Repeat the process 16 times with blocks containing a single 1 to recover each column of A.
  4. Compute A^-1 mod 65.
  5. Apply x = A^-1(c - b) to each ciphertext block.
  6. Rebuild the Base64 string and decode it.

In code, this required a function to recover A and b from the service, another to invert matrices modulo 65, and a final one to transform the encrypted blocks back into the original text.

Once that was in place, the encryption could be inverted block by block.

Flag

ENO{l1ne4r_alg3br4_i5_ev3rywh3re}