Pailler_Oracle.py

from Crypto.Hash import SHA256
import string
from pwn import *
import hashlib
from Crypto.Util.number import *

conn = remote("oracle.tasks.ctf.codeblue.jp", 7485)
conn.recvuntil("SHA256(XXXX+")
proof = conn.recvuntil(") == ")[:-5]
digests = conn.recvuntil("\n")[:-1]
conn.recv()

# print proof
# print digests

alphabets = string.ascii_letters+string.digits

try:
	for c1 in alphabets:
		for c2 in alphabets:
			for c3 in alphabets:
				for c4 in alphabets:
					if digests == hashlib.sha256(c1 + c2 + c3 + c4 + proof).hexdigest():
					# if digests == SHA256.new(c1 + c2 + c3 + c4 + proof).hexdigest():
						x = "".join([c1, c2, c3, c4])
						# print x
						conn.send(x + "\n")
						raise StopIteration
except StopIteration:
	pass

conn.recvuntil("Generating the key...")
conn.recvuntil("Public key is here: (")

n = int(conn.recvuntil(", ")[:-2])
g = int(conn.recvuntil(")")[:-1])

conn.recvuntil("...and Encrypted Flag: ")
c = int(conn.recvuntil("Your ")[:-5])


def get_next(lsbs, c):
	if lsbs == "":
		return c

	if lsbs[0] == "1":
		c = c*inverse(g, n**2)%(n**2)
	return pow(c, inverse(2, n), n**2)
	
lsbs = ""
for i in range(1000):
	conn.recvuntil("ciphertext here: ")
	c = get_next(lsbs, c)
	conn.send(str(c) + "\n")

	conn.recvuntil("LSB is ")
	lsb = conn.recvuntil("Your ")[:-6]
	lsbs = lsb + lsbs

	print i, lsbs