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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://elijahchia.gitbook.io/ctf-blog/wargames.my-ctf-2024/ricks-algorithm-crypto.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.