Rem, Shinobu, Asuna
#!/usr/bin/env python3
from Crypto.Util.number import *
FLAG = open('flag.txt', 'rb').read()
bits = 512
e = 65537
p = getPrime(bits)
q = getPrime(bits)
n = p*q
phi = (p-1)*(q-1)
d = inverse(e, phi)
hint = 2*d*(p-1337)
m = bytes_to_long(FLAG)
c = pow(m, e, n)
print(f"n = {hex(n)}")
print(f"e = {hex(e)}")
print(f"c = {hex(c)}")
print(f"hint = {hex(hint)}")
Typical RSA challenge and YOU DON'T NEED TO FACTORIZE N every time you see an RSA challenge!
We have,
Actually, it's very hard to factor a 1024 bit RSA public modulus but If we have some of the leaked data about private keys or the modulus then we can use some tricks to factor the 1024-bit modulus.
Let's start with Fermat's little theorem which states that,
Let . Now we can apply this here,
With this trick, we can get one of the factors of the public modulus (n) and then simply decrypt the ciphertext!
Solve Script: solve.py
Flag: wormcon{RSA_And_Fermat's_Little_Theorem!?}
Last updated
Was this helpful?