search

Determined (crypto)

"It is my experience that proofs involving matrices can be shortened by 50% if one throws the matrices out." Emil Artin

file-download
2KB
server.py
arrow-up-right-from-squareOpen
file-download
211B
gen.py
arrow-up-right-from-squareOpen

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.

# 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=[p0x00x10x20x30x40x50x60q0r0x70x800]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 xx values are our controlled inputs.

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:

∣p0x00x10x20x30x40x50x60q0r0x70x800∣=q∣px00x100x30x4x50x6x7x800∣+r∣p0x0x10x200x40x5x6x70x80∣\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:

=−qx3∣px0x1x4x5x6x7x80∣+rx2∣px0x1x4x5x6x7x80∣=-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}
=(rx2−qx3)(x0x6x7+x1x4x8−x1x5x7−px6x8)=(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 xx values, we can obtain qq alone. We can do this by setting x0=x2=x4=x6=x8=0x_0=x_2=x_4=x_6=x_8=0 and x1=x3=x5=x7=1x_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.

Last updated