Skip to content

Instantly share code, notes, and snippets.

@rcombs
Last active December 17, 2015 01:39
Show Gist options
  • Save rcombs/5530290 to your computer and use it in GitHub Desktop.
Save rcombs/5530290 to your computer and use it in GitHub Desktop.
Quick write-up on Broken RSA from PicoCTF
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))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment