In this challenge we have file output.txt with encrypted message, public key and script which performs encryption. The following encryption scheme looks like this:

  1. Generates private and public key. Public key is a Matrix of size 57x63
  2. Converts a message into sequence of bits, adds padding and splits into chunk of size 57
  3. Encodes each chunk using public key
  4. Joins encoded chunks and converts sequence of bits to hex

Chunk encryption works as follows: multiplies chunk as vector of size 1x57 with public key of size 57x63 by modulo 2. As a result it returns vector of bits of size 1x63. After that, it randomly swaps one bit and the result is encoded chunk.

Let’s see how matrix multiplication works:

\[ \begin{aligned} &m \cdot A = \begin{bmatrix} x_1 & x_2 & x_3 \end{bmatrix} \cdot \begin{bmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \\ a_{31} & a_{32} \end{bmatrix} = \begin{bmatrix} x_1 a_{11} + x_2 a_{21} + x_3 a_{31} \\ x_1 a_{12} + x_2 a_{22} + x_3 a_{32} \end{bmatrix} = \begin{bmatrix} r_1 \\ r_2 \end{bmatrix} \end{aligned} \]

So, in our case m is vector of message bits and r is a vector or encrypted bits. So we can find message bits by solving the system of following equations:

\[ \left\{ \begin{aligned} x_1 a_{11} + x_2 a_{21} + x_3 a_{31} &= r_1 \\ x_1 a_{12} + x_2 a_{22} + x_3 a_{32} &= r_2 \end{aligned} \right. \]

This can be solved using Gauss elimination.

The last thing we should handle is randomly swapped bit. Since message is small we can brute each bit position. if position is right we should get printable text and if it’s not the SLAR won’t have solutions.

Therefore, the algorithm is as follows:

  1. Split encrypted text into chunks
  2. For each chunk check possible swapped bit and try to solve SLAR. If solution found, add decrypted bits to message
  3. Decode full message and optionally unpad it

Here SageMath script do decrypt message:

import string
import numpy as np
ct = '33b4ba0c3c11ad7e298b79de7261c5dd8edd7b537007b383cad9f38dbcf584e66a07c9808edad6e289516f3c6cc4186686f3a7fc8e1603e80aba601efe82e8cf2f6a28aa405cf7419b9dd1f01925c5'
G_pub = np.load("./alice_pub.npy")
def bits_to_str(bits):
    return bytes([int("".join([str(b) for b in bits[i:i+8]]),2) for i in range(0, len(bits), 8)])
    
def try_to_decode_chunk(chunk, chunk_idx):
    try:
        g = GF(2)
        A = Matrix(g, G_pub)
        m_bits = A.transpose().solve_right(vector(chunk))
        start = (-(chunk_idx*63) % 8) % 8
        return m_bits
    except Exception as e:
        return None
    
def decode_chunk(chunk, chunk_idx):
    for i in range(63):
        bits = try_to_decode_chunk([c if i!=j else (c+1)%2 for j, c in enumerate(chunk)], chunk_idx)
        if bits:
            return bits
    
ct_bits = [int(b) for b in bin(int(ct, 16))[2:]]
chunks = [ct_bits[i:i+63] for i in range(0,len(ct_bits), 63)]
m = []
for i, chunk in enumerate(chunks):
    m+=decode_chunk(chunk, i)
print("Flag: ", bits_to_str(m))