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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://elijahchia.gitbook.io/ctf-blog/l3ak-ctf-24/matrix-magic-crypto.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.