Rick'S Algorithm (crypto)

For this challenge we get Python source code which is running on the server.

from Crypto.Util.number import *
import os
flag = bytes_to_long(b"wgmy{REDACTED}")

p = getStrongPrime(1024)
q = getStrongPrime(1024)
e = 0x557
n = p*q
phi = (p-1)*(q-1)
d = inverse(e,phi)

while True:
	print("Choose an option below")
	print("=======================")
	print("1. Encrypt a message")
	print("2. Decrypt a message")
	print("3. Print encrypted flag")
	print("4. Print flag")
	print("5. Exit")

	try:
		option = input("Enter option: ")
		if option == "1":
			m = bytes_to_long(input("Enter message to encrypt: ").encode())
			print(f"Encrypted message: {pow(m,e,n)}")
		elif option == "2":
			c = int(input("Enter ciphertext to decrypt: "))
			if c % pow(flag,e,n) == 0 or flag % pow(c,d,n) == 0:
				print("HACKER ALERT!!")
				break
			print(f"Decrypted message: {pow(c,d,n)}")
		elif option == "3":
			print(f"Encrypted flag: {pow(flag,e,n)}")
		elif option == "4":
			print("Revealing flag: ")
			revealFlag()
		elif option == "5":
			print("Bye!!")
			break
	except Exception as e:
		print("HACKER ALERT!!")

It implements classic RSA, with an encryption and decryption oracle. However, the decryption oracle imposes the following restrictions on the ciphertext: we cannot have c % pow(flag,e,n) == 0 or flag % pow(c,d,n) == 0

Background: In normal RSA decryption, the encrypted message is $c=m^e$, and decryption works because $c^d=(m^e)^d=m^{ed}=m$ since d = pow(e, -1, phi) (i.e. d is the inverse of e mod phi).

The first problem is that we do not even have the value of the modulus n. We can get it by encrypting two distinct plaintexts, say $m_1$ and $m_2$. Then our ciphertexts will be $m_1^e (mod \space n)$ and $m_2^e (mod \space n)$, which can also be expressed as $m_1^e-k_1n$ and $m_2^e-k_2n$ for some non-negative $k_1$ and $k_2$. Since we know $m_1^e$ and $m_2^e$ we can then obtain $-k_1n$ and $-k_2n$, and taking the GCD of those will most likely give us $n$.

We can bypass the check by asking for the decryption of a value which is not c, but the decrypted plaintext allows us to find m easily. Once such example is $c^{-1}$. The decryption would give us $(c^{-1})^d=c^{-d}=(m^e)^{-d}=m^{-ed}=m^{-1}$. By taking the inverse of the decrypted plaintext we can get the flag. However it is worth noting that this solution may sometimes fail due to $c$ not having an inverse mod n.

Below is my script:

from pwn import *
from Crypto.Util.number import *
from sympy import gcd


# context.log_level = 'debug'

e = 0x557
# p = process(["python3","server.py"])
p = remote("43.217.80.203", 33862)

p.sendlineafter(b"Enter option: ", b"1")
p.sendlineafter(b"encrypt: ", long_to_bytes(69))
p.recvuntil(b"message: ")
c1 = int(p.recvline()[:-1].decode())
d1 = c1 - pow(69, e)
p.sendlineafter(b"Enter option: ", b"1")
p.sendlineafter(b"encrypt: ", long_to_bytes(1337))
p.recvuntil(b"message: ")
c2 = int(p.recvline()[:-1].decode())
d2 = c2 - pow(1337,e)
n = int(gcd(d1, d2))
p.sendlineafter(b"Enter option: ", b"3")
p.recvuntil(b"Encrypted flag: ")
ct = int(p.recvline()[:-1].decode())
fake = pow(ct, -1, n)
p.sendlineafter(b"Enter option: ", b"2")
p.sendlineafter(b"decrypt: ", str(fake).encode())
p.recvuntil(b"message: ")
pt_inv = int(p.recvline()[:-1].decode())
m = pow(pt_inv, -1, n)
print(long_to_bytes(m))