Quick write-up on Broken RSA from PicoCTF

gistfile1.txt

C = ciphertext
M = plaintext
e = exponent (constant, 3)
n = modulus

RSA Algorithm: C = M^e % n

M[0] (M-Prime) = The flag we're trying to get. It's constant.

Choose 3 more values for M, call them M[1], M[2], M[3]. They should be very large.

n changes every time we connect to the crypto service. Call which connection we're on i (start at 1) and which M-value we're on j (start at 0).
We'll connect to the cryptoserver 3 times. Each time, we'll get a value for the ciphertext of each M value; call them C[j][i].

So now we have 12 values of C: 3 for encryptions of the flag, and 9 for encryptions of our chosen M's.

Psuedocode time!
For i = 1..3:
n[i] = GCD(M[1]^3 - C[1][i], M[2]^3 - C[2][i], M[3]^3 - C[3][i])
Done

So, we've got our modulus values. Next up, Hastad's Broadcast Attack using Chinese Remainder Theorem:

M[0]^3 = CRT(C[0], n)
M[0] = CubeRoot(CRT(C[0], n))