> For the complete documentation index, see [llms.txt](https://elijahchia.gitbook.io/ctf-blog/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://elijahchia.gitbook.io/ctf-blog/l3ak-ctf-24/matrix-magic-crypto.md).

# Matrix Magic (crypto)

{% file src="/files/gIR3K8m8JSqGdFwwTfuE" %}

{% file src="/files/4IiLV7Wb0SAuAdmSbPap" %}

The encryption algorithm is a sage file given below:

```python
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](https://elijahchia.gitbook.io/ctf-blog/l3ak-ctf-24/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:

```python
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}
```