Matrix Magic (crypto)

The encryption algorithm is a sage file given below:

from sage.all import *
from Crypto.Util.number import getPrime, isPrime
import os

def get_random(n):
    return int.from_bytes(os.urandom(n//8  + 1), "big")

def get_safe_prime(nbit):
    result = 2 * getPrime(nbit // 2) * getPrime(nbit // 2) + 1
    while not isPrime(int(result)):
        result = 2 * getPrime(nbit // 2) * getPrime(nbit // 2) + 1
    return result


FLAG = int.from_bytes(open("flag.txt", "rb").read().strip(), "big")

nbit = 1024

p = get_safe_prime(nbit // 2)
q = get_safe_prime(nbit // 2)
n = p*q

Mat = matrix(Zmod(n), [
    [2, 1] + [get_random(nbit) for _ in range(4)],
    [0, 2] + [get_random(nbit) for _ in range(4)],
    [0, 0] + [4, 1] + [get_random(nbit) for _ in range(2)],
    [0, 0] + [0, 4] + [get_random(nbit) for _ in range(2)],
    [0, 0] + [0, 0] + [8, 1],
    [0, 0] + [0, 0] + [0, 8]
])

C = Mat^FLAG
C = list(C)

with open("output.txt", "w") as f:
    f.write(f"{C = }")

It obtains the primes p and q, and multiplies them to get the modulus n. It then creates a matrix using powers of 2 and random 1024-bit numbers. The matrix is exponentiated with the flag, and every element in the matrix is in an integer ring modulo n. We are given the elements of the resulting matrix.

Notice that this is an upper triangular matrix. As a result, the diagonal entries are just multiplied with themselves every time we perform the matrix multiplication. In other words, c[0][0]=2flag mod nc[0][0] = 2^{flag} \space mod \space n, c[2][2]=4flag mod nc[2][2] = 4^{flag} \space mod \space n, c[4][4]=8flag mod nc[4][4] = 8^{flag} \space mod \space n.

By property of modulo, we also have the following:

2flag=an + x (we get x)2^{flag} = an\space+\space x\space \text{(we get x)}

4flag=bn + y (we get y)4^{flag} = bn\space+\space y\space \text{(we get y)}

8flag=cn + z (we get z)8^{flag} = cn\space+\space z\space \text{(we get z)}

x2=(2flag − an)2 =22×flag − 2an×2flag + a2n2 = 4flag + n(a2n − 2a×2flag)x^2 = (2^{flag} \space - \space an)^2 \space = 2^{2 \times flag}\space - \space 2an\times 2^{flag} \space + \space a^2n^2 \space = \space 4^{flag} \space + \space n(a^2n\space - \space 2a\times 2^{flag})

Therefore,

x3 − z will be a multiple of nx^3 \space - \space z \space \text{will be a multiple of } n

Similarly,

y3 − z2 will be a multiple of ny^3 \space - \space z^2 \space \text{will be a multiple of } n

and

x3 − z will be a multiple of nx^3 \space - \space z \space \text{will be a multiple of } n

Therefore, we can get a multiple of nn (and thereafter nn) using

GCD(GCD(x2 − y, x3 − z), y3 − z2)GCD(GCD(x^2 \space - \space y, \space x^3 \space - \space z), \space y^3 \space - \space z^2)

We also need to verify that it is 1024 bits long.

For c[0][1]c[0][1], notice that it follows the following sequence: 1, 4, 12, 32 as i = 1, 2, 3, 4 etc

Let c[0][0]c[0][0] be a0a_0. In one round of matrix multiplication,

c[0][1]=a0(prev)+c[0][1](prev)×2c[0][1]=a_0(prev)+c[0][1](prev)\times 2

So with the i-th power,

c[0][1]=(i−1)×2i−1+2i−1=i×2i−1c[0][1] = (i - 1)\times 2^{i - 1} + 2^{i - 1} = i\times 2^{i - 1}

Now that we know nn, and that c[0][0]=2i mod n,c[0][1]=i×2i−1 mod nc[0][0] = 2^{i} \space mod \space n, c[0][1] = i\times 2^{i - 1} \space mod \space n,

2×c[0][1] mod n=i×2i mod n2\times c[0][1] \space mod \space n = i\times 2^{i} \space mod \space n. If we know the modular inverse of c[0][0] c[0][0] , say xx, then

((2×c[0][1] mod n)×x) mod n=i((2\times c[0][1] \space mod \space n) \times x) \space mod \space n = i

More simply,

(2×c[0][1] ×x) mod n=i(2\times c[0][1] \space \times x) \space mod \space n = i

Which gives us our flag!

The solve script is as follows:

from sage.all import *
from Crypto.Util.number import *
# c[0][0]
two_power_flag = 34285747519707996626385667339662460790207453899564234933279840884637317470277963204844978855648863282661822817842406467276103235437115285776600339324582650206354227684286926765912841373720037206104315460984467834472878792871363724319500026730744559032592830317957861116684230815080884748210510265257121727411
# c[2][2]
four_power_flag = 80891788386112939497749276978496951092908047537517752191112348346041605282820278415204830919700840360371114407873821260986140627885494462923855784343766007471406691139724032186081486065167152331309928933439563087594932165713814698240940689654799590764311096627705559355661741126880749623083953480524440103996
# c[4][4]
eight_power_flag = 36580210170460317737762146444885635769591964296289890711389087000847139534806165797517572963756420701630101713343229692997790887039708011239887899158602488099058023454307392387825436996066794401349180417178870019892425641929320878895403740655587101563655595067050855919740156100994268635382369423383067032821

n = GCD(GCD(pow(two_power_flag, 2) - four_power_flag, pow(two_power_flag, 3) - eight_power_flag), pow(four_power_flag, 3) - pow(eight_power_flag, 2))
print(int(n).bit_length()) 
# bit length still not 1024, need to find a small factor and divide it
n = n // 5
print(int(n).bit_length())
x = 82389813574193236731268728055226346949935905889688170425892513962291738546070054175286986817742962125712704451033935523159914920684418980229184675189392660990212113237529057511102468180315624316711603102279872782413287481544411903032504611191117588506754985276936284421146109462510942343677179125102460355334

flag = 2 * x * inverse(two_power_flag, n) % n

print(long_to_bytes(int(flag)))
# L3AK{jordan_normal_matrix_is_so_special_86351adeff}

Last updated