Matrix Magic (crypto)

914B

main.sage

6KB

output.txt

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] = 2^{flag} \space mod \space n$, $c[2][2] = 4^{flag} \space mod \space n$, $c[4][4] = 8^{flag} \space mod \space n$.

By property of modulo, we also have the following:

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

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

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

$$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,

$$x^3 \space - \space z \space \text{will be a multiple of } n$$

Similarly,

$$y^3 \space - \space z^2 \space \text{will be a multiple of } n$$

and

$$x^3 \space - \space z \space \text{will be a multiple of } n$$

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

$$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]$, notice that it follows the following sequence: 1, 4, 12, 32 as i = 1, 2, 3, 4 etc

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

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

So with the i-th power,

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

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

$2\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]$, say $x$, then

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

More simply,

$$(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}