> For the complete documentation index, see [llms.txt](https://elijahchia.gitbook.io/ctf-blog/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://elijahchia.gitbook.io/ctf-blog/wargames.my-ctf-2024/ricks-algorithm-crypto.md).

# Rick'S Algorithm (crypto)

<figure><img src="/files/MOEkMjGCfJ8fGyaYcWNt" alt="" width="330"><figcaption></figcaption></figure>

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

```python
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:

```python
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))
```