Crypto - Big Stuff

Studies show that 80% of adults face anxiety on seeing big and complicated matrices. So I have used big and complicated matrices to encrypt my flag! - DarthVishnu

Full Implementation

Challenge

from Crypto.Util.number import bytes_to_long
from sage.all import *

flag = "Breach{[REDACTED]}"[7:-1]

def random_invertible_matrix_gf_p(m, p, a):
    assert 0 <= a < p, "a must be in the range [0, p-1]"
    F = GF(p)
    while True:
        M = Matrix(F, m, m, [F(randint(0, a)) for _ in range(m * m)])
        if M.is_invertible():
            return M

def generate_matrices_with_det_below(num_matrices, m, p, a):
    matrices = []
    while len(matrices) < num_matrices:
        M = random_invertible_matrix_gf_p(m, p, a)
        # Convert the determinant to an integer in [1, p-1]
        d = int(M.determinant())
        # Accept matrix only if d is below the bound and not already seen
        if d <p//2:
            matrices.append(M)
    return matrices
num_matrices = 256
p = 2**553+549
a = 2        
m = 10      

matrix_array = generate_matrices_with_det_below(num_matrices, m, p, a)

mid = len(matrix_array) // 2
A1 = matrix_array[:mid]
A2 = matrix_array[mid:]

print("A1 = ", A1)
print("A2 = ", A2)

def encrypt_message(message, A1, A2):
    # Get the base field from the first matrix in A1.
    F = A1[0].base_ring()
    # Start with the identity matrix of appropriate size.
    C = identity_matrix(F, A1[0].nrows())
    
    for i,bit in enumerate(message):
        if bit == '0':
            # Select next matrix from A1.
            M = A1[i]
        elif bit == '1':
            # Select next matrix from A2.
            M = A2[i]
        else:
            raise ValueError("Message must be a binary string.")
        # Multiply into the ciphertext product.
        C = C * M
    return C

m = bin(bytes_to_long(flag.encode()))[2:]

C = encrypt_message(m, A1, A2)
print("C = ",C)

We are given a file which contains a ciphertext matrix C and two lists A1 and A2 which consists of 128 10x10 matrices

The lists are generated using generate_matrices_with_det_below(), which returns 128 10x10 matrices which have elements in the range {0,2}.

In the encrypt_message() , an 10x10 identity matrix is initialized, which is then multiplied the matrices in the lists, depending on the index and the value of the bit of the flag, which then produces a ciphertext matrix.

We can use the fact that the starting matrix is not a matrix with large coefficients (identity matrix) and the prime used is very large to retrieve the flag.

To get the flag, we need to backtrack from a large ciphertext matrix back to an identity matrix. First, we need to check whether the values of the entries while generating the ciphertext matrix exceed the modulus or not at any point. To do this, we need to assume the largest values for all the matrices. The max value during the first round is $10*2^2$, during the second round is $10^2 * 2^3$ ... during the last(128th) round it will be $10^{127}*2^{128}$ ~ $2^{551}$ which is less than the modulus.

Now how do we decide which matrix from A1 or A2 to choose from? Given the modulus is large, the entries of the inverse matrix would also be very large, even larger than the ciphertext matrix. We can use this to figure out which matrix from A1[index] or A2[index] to choose from. Suppose the matrix that was multiplied last was A1[index] and we assumed it to be A2[index]. Then the values of C*A2[index]^-1 would be much larger then the current ciphertext matrix, which means that we considered the wrong list. Using this, we can find the index corresponding to the right list and find the flag

from sage.crypto.util import bin_to_ascii
load('pub.sage')
A1 = A1[::-1]
A2 = A2[::-1]
bits = []
for i in range(128):
    size = sum(ZZ(i) for i in C.list())
    C1 = C * A1[i]^-1
    if sum(ZZ(i) for i in C1.list()) > size:
        bits.append(1)
        C *= A2[i]^-1
    else:
        bits.append(0)
        C = C1
print(bin_to_ascii(bits[::-1]))
#'U_4r3_m47r1x_g0d'