Quantum_Safe

The challenge provides a SageMath script used to encrypt a flag and an output file containing the resulting ciphertext vectors. The encryption process uses a linear transformation involving a 3x3 public key matrix, a random noise vector, and a constant shift vector.

Encryption Method

Based on the source.sage file, each character $c$ of the flag is processed as follows:

• A vector is created using the character’s ASCII value and two random integers: $v = [ord(c), \text{rand}_1, \text{rand}_2]$.

• This vector is multiplied by a public key matrix $M$:

  $$M = \begin{pmatrix} 47 & -77 & -85 \ -49 & 78 & 50 \ 57 & -78 & 99 \end{pmatrix}$$

• A persistent random “shift” vector $r = [r_1, r_2, r_3]$ (generated once at the start) is added to the result of every character.

• The final ciphertext vector $C$ is calculated as: $C = v \cdot M + r$.

Decryption Strategy

To recover the flag, we need to reverse the matrix multiplication and account for the constant shift $r$.

• Matrix Inversion: Since $M$ is a static 3x3 matrix, we can calculate its inverse $M^{-1}$.

• Isolating the Character: Multiplying the ciphertext by the inverse gives:

  $$C \cdot M^{-1} = (v \cdot M + r) \cdot M^{-1} = v + (r \cdot M^{-1})$$

• Handling the Shift: The first element of the resulting vector is $ord(c) + S$, where $S$ is the first element of the transformed shift vector $(r \cdot M^{-1})$.

• Known Plaintext: Since flags typically start with a known character (e.g., ‘H’), we can solve for $S$ using the first ciphertext vector $V_0$: $S = (V_0 \cdot M^{-1})_0 - ord(‘H’)$.

Solution Implementation

The solve.sage script automates this recovery:

1. Define the Matrix: Recreate $M$ and calculate $M^{-1}$ over the Rational Field ($\mathbb{Q}$) for precision.

2. Calculate Shift: Use the first ciphertext vector and the assumed first character ‘H’ to find the constant shift $S$.

3. Iterate and Decrypt: For every vector in output.txt, multiply by $M^{-1}$, subtract $S$, and convert the resulting integer back to a character.

import ast

# 1. Define the Public Key Matrix
M = Matrix(ZZ, [
    [47, -77, -85],
    [-49, 78, 50],
    [57, -78, 99]
])

# 2. Calculate the inverse over Rational Field (QQ) for precision
inv_M = M.change_ring(QQ).inverse()

# 3. Load the ciphertext vectors from the file
cipher_vectors = []
with open('output.txt', 'r') as f:
    for line in f:
        # ast.literal_eval converts "(1, 2, 3)" string to a Python tuple
        data = ast.literal_eval(line.strip())
        cipher_vectors.append(vector(QQ, data))

# 4. Calculate the constant shift 'S' using the first character 'H'
# (C * inv_M)[0] = ord(c) + S
V0_transformed = cipher_vectors[0] * inv_M
S = V0_transformed[0] - ord('H')

# 5. Decrypt the flag
flag = ""
for C in cipher_vectors:
    V_transformed = C * inv_M
    # Subtract the shift and round to the nearest integer
    char_code = round(V_transformed[0] - S)
    flag += chr(int(char_code))

print(f"Decoded Flag: {flag}")