# Determined (crypto)

{% file src="<https://243380073-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FBIa0PcXGYuP6chd3J1Ry%2Fuploads%2F2oz5Uqe7ZNDOzvcnnsN6%2Fserver.py?alt=media&token=2f33f08e-702e-4a50-8714-dbb11ab1a500>" %}

{% file src="<https://243380073-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FBIa0PcXGYuP6chd3J1Ry%2Fuploads%2FFZ4rtHJy6RsK4HGpwWOj%2Fgen.py?alt=media&token=dd8c61b5-47e9-4d5b-830e-c91b503dafc9>" %}

We are given the main code running on the server in server.py, and gen.py which generates an encrypted message using RSA. We are given the RSA modulus `n`, exponent `e` and ciphertext `c`.

```python
# server.py
from Crypto.Util.number import bytes_to_long, long_to_bytes
from itertools import permutations
from SECRET import FLAG, p, q, r

def inputs():
    print("[DET] First things first, gimme some numbers:")
    M = [
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0],
    ]
    try:
        M[0][0] = p
        M[0][2] = int(input("[DET] M[0][2] = "))
        M[0][4] = int(input("[DET] M[0][4] = "))

        M[1][1] = int(input("[DET] M[1][1] = "))
        M[1][3] = int(input("[DET] M[1][3] = "))

        M[2][0] = int(input("[DET] M[2][0] = "))
        M[2][2] = int(input("[DET] M[2][2] = "))
        M[2][4] = int(input("[DET] M[2][4] = "))

        M[3][1] = q
        M[3][3] = r

        M[4][0] = int(input("[DET] M[4][0] = "))
        M[4][2] = int(input("[DET] M[4][2] = "))
        """
    M = [
        [p, 0, x, 0, x],
        [0, x, 0, x, 0],
        [x, 0, x, 0, x],
        [0, q, 0, r, 0],
        [x, 0, x, 0, 0],
    ]
        """
    except:
        return None
    return M

def handler(signum, frame):
    raise Exception("[DET] You're trying too hard, try something simpler")

def fun(M):
    def sign(sigma):
        l = 0
        for i in range(5):
            for j in range(i + 1, 5):
                if sigma[i] > sigma[j]:
                    l += 1
        return (-1)**l

    res = 0
    for sigma in permutations([0,1,2,3,4]):
        curr = 1
        for i in range(5):
            curr *= M[sigma[i]][i]
        res += sign(sigma) * curr
    return res

def main():
    print("[DET] Welcome")
    M = inputs()
    if M is None:
        print("[DET] You tried something weird...")
        return

    res = fun(M)
    print(f"[DET] Have fun: {res}")

if __name__ == "__main__":
    main()

# gen.py
from SECRET import FLAG, p, q, r
from Crypto.Util.number import bytes_to_long
n = p * q
e = 65535
m = bytes_to_long(FLAG)
c = pow(m, e, n)
# printed to gen.txt
print(f"{n = }")
print(f"{e = }")
print(f"{c = }")
```

server.py imports the RSA primes `p` and `q` , along with `r` (but `r` is useless). `main()` first calls `inputs()`, which prompts us for entries to a matrix `M`. After inputting our values, `M` looks like this:

$$
M=\begin{bmatrix} p & 0 & x\_0 & 0 & x\_1\ 0 & x\_2 & 0 & x\_3 & 0\ x\_4 & 0 & x\_5 & 0 & x\_6 \ 0 & q & 0 & r & 0 \ x\_7 & 0 & x\_8 & 0 & 0 \end{bmatrix}
$$

where all the $$x$$ values are our controlled inputs.&#x20;

`fun(M)` is then printed. `fun(M)` is essentially using a permutation method to compute the determinant of a matrix. Let's compute the determinant of `M` using cofactor expansion:

Along the fourth row:

$$
\begin{vmatrix} p & 0 & x\_0 & 0 & x\_1\ 0 & x\_2 & 0 & x\_3 & 0\ x\_4 & 0 & x\_5 & 0 & x\_6 \ 0 & q & 0 & r & 0 \ x\_7 & 0 & x\_8 & 0 & 0 \end{vmatrix}=q\begin{vmatrix}
p & x\_0 & 0 & x\_1\\
0 & 0 & x\_3 & 0 \\
x\_4 & x\_5 & 0 & x\_6\\
x\_7 & x\_8 & 0 & 0
\end{vmatrix} + r\begin{vmatrix}
p & 0 & x\_0 & x\_1\\
0 & x\_2 & 0 & 0 \\
x\_4 & 0 & x\_5 & x\_6 \\
x\_7 & 0 & x\_8 & 0
\end{vmatrix}
$$

Along second row for both:

$$
\=-qx\_3\begin{vmatrix}
p & x\_0 & x\_1\\
x\_4 & x\_5 & x\_6\\
x\_7 & x\_8 & 0
\end{vmatrix} + rx\_2\begin{vmatrix}
p & x\_0 & x\_1\\
x\_4 & x\_5 & x\_6\\
x\_7 & x\_8 & 0
\end{vmatrix}
$$

$$
\=(rx\_2-qx\_3)(x\_0x\_6x\_7+x\_1x\_4x\_8-x\_1x\_5x\_7-px\_6x\_8)
$$

Observing this expression closely, by controlling the different $$x$$ values, we can obtain $$q$$ alone. We can do this by setting $$x\_0=x\_2=x\_4=x\_6=x\_8=0$$ and $$x\_1=x\_3=x\_5=x\_7=1$$.

Providing these values to the server, we get that `q = 12538849920148192679761652092105069246209474199128389797086660026385076472391166777813291228233723977872612370392782047693930516418386543325438897742835129`. With `q`, we know `n` hence we can find `p`. We can then find phi and hence `d`. We can then find the plaintext `m`.

```python
from Crypto.Util.number import long_to_bytes

n = 158794636700752922781275926476194117856757725604680390949164778150869764326023702391967976086363365534718230514141547968577753309521188288428236024251993839560087229636799779157903650823700424848036276986652311165197569877428810358366358203174595667453056843209344115949077094799081260298678936223331932826351
"""
    M = [
        [p, 0, x, 0, x],
        [0, x, 0, x, 0],
        [x, 0, x, 0, x],
        [0, q, 0, r, 0],
        [x, 0, x, 0, 0],
    ]
"""
q = 12538849920148192679761652092105069246209474199128389797086660026385076472391166777813291228233723977872612370392782047693930516418386543325438897742835129

assert n % q == 0
p = n // q
tot = (p - 1) * (q - 1)
e = 65535
c = 72186625991702159773441286864850566837138114624570350089877959520356759693054091827950124758916323653021925443200239303328819702117245200182521971965172749321771266746783797202515535351816124885833031875091162736190721470393029924557370228547165074694258453101355875242872797209141366404264775972151904835111
d = pow(e, -1, tot)
m = pow(c, d, n)
print(long_to_bytes(m)) # uiuctf{h4rd_w0rk_&&_d3t3rm1n4t10n}
```