We're given a broken implementation of RSA in Python:
from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes
e = 65536
def gen_key():
p = getPrime(1024)
q = getPrime(1024)
n = p # q
t = (p-1) * (q-1)
d = inverse(e, t)
return n, d
def encrypt(n, e, m):
c = pow(m, e, n)
return c
# for some reason my decrypt function doesn't work!
# can you help me recover the message?
def decrypt(n, d, c):
m = pow(c, d, n)
return m
FLAG = b'pwnEd{???...?}'
n, d = gen_key()
m = bytes_to_long(FLAG)
c = encrypt(n, e, m)
m = decrypt(n, d, c)
print(f'n = {n}')
print(f'Encrypted flag: {c}')
print(f'It just doesn\'t work!: {long_to_bytes(m)}')
The first things to notice are that e isn't the usual 65537, and isn't prime either. Then n evaluates to just p instead of pq, so the output we're given:
n = 158956010976836742521330254087275425096501583054825136137040889728364290468342445750425376148898452284963095323948276435573809460871703413808672473157217817381946017879464498512288960101002405275174672926496400917470509079465025417877720664744491054992376496575684398645703346912039046842844204816524282238459
Encrypted flag: 17696325213195819360084027228862087546075383230711834052302081670404491942278399339165629822030797913121661625273125782635636475385580385239446207346095935362399429412825040827923795088154904762207215060766109368707427481633970394393914176132798637385151502305355038711511174834777689397585730318578634645332
It just doesn't work!: b'\xb1s\xacL\x841\xff\r\xfd\x9e\x9e\xe29\xb2\xfd\xf7I\xe2?\x1bb\xd4\x8dZ\xce\xa0\x18\xc4\x040\x8c\xe1\xd2\x81B\xb1\xda\x9av\xd5Np\xf4m\xeb\xdc\xfd\xcc0\xe3\xa9h\x86\xb8c\x86\x84\xb7\xda\x99uJ\x0b\xbe\x1d@\xbf\x98\x95\x92\xc7\x04\xef,,\xd4\tt\x82\xba\xd8\x17O\x9bI\xf6\xe8j\x8a\xb3H5n\x0cEA|\x1d\xab(\xd4\x9dU&=\x8aVA\x04\xa62\x11\xa1\xdb\xf0\xf5\xd4%\xde+\xa3+\xe6\xc8*\xffv\xad'
uses the wrong private key. So, we're given n which is prime, thus there isn't really a p or q, the ciphertext c and e. Using sources to work out how RSA works and calculate the correct value for d, the totient φ(n) is n-1 since n is prime. Typically this is all that should be done, and RsaCtfTool managed to decrypt the ciphertext with python3 RsaCtfTool.py -n <N> -e 65536 --uncipher <CIPHER> --attack ecm2, but this was all we could get to during the CTF. Afterwards, it's revealed that since e isn't coprime with φ(n) we can't decrypt the message as you usually would.
One reason RSA works is that ed = 1 (mod φ(n)) holds, it follows that c^d = m^ed = m (mod n), proof here. Since the decryption isn't working even with the correct d then ed = x (mod φ(n)) where x isn't 1. Finding this x is rather simple, we just evaluate e*d%n, which gives us 2. Recall that m^ed = m (mod n), so we've got the message squared. To find the modular square root, we use the Tonelli-Shanks algorithm. Since there's an online implementation, we just enter our m^2 for a and n for p, convert this long into bytes and we get the flag.