SECCON 2015--Find the prime numbers--Crypto200

README.md

###Good writeup is at https://github.com/p4-team/ctf/tree/master/2015-12-05-seccon/paillier_crypto_200#eng-version

I use the fact that h=co (mod n*n) to brute force n, which took around 45 minutes.
Then I factor n to get p and q, and make into phi. Then I plug everything into the "simpler variant" on https://en.wikipedia.org/wiki/Paillier_cryptosystem

solve.py

#!/usr/bin/python3

c = 3089536481493958504
o = 430963121498067364
h = 2520077868883606433

n = 1
while True:
	if (c*o)%pow(n,2) == o:
		print(n)
		break
	n += 1
# n = 251051

def L(u):
	return (u-1)//n
p,q = factor(n)
phi = (p-1)*(q-1)
print((L(pow(c, phi, n**2))*modinv(phi, n))%n)
# 1510490612