solve_eazy_RSA.py

from Crypto.Util.number import *
import itertools
from gmpy2 import *

c=3708354049649318175189820619077599798890688075815858391284996256924308912935262733471980964003143534200740113874286537588889431819703343015872364443921848
e=16
p=75000325607193724293694446403116223058337764961074929316352803137087536131383
q=69376057129404174647351914434400429820318738947745593069596264646867332546443

def square_root(c):
	n=p*q
	mp=pow(c,(p+1)//4,p)
	mq=pow(c,(q+1)//4,q)
	yp=int(gcdext(p,q)[1])
	yq=int(gcdext(p,q)[2])
	r1=(yp*p*mq+yq*q*mp)%n
	r2=(yp*p*mq-yq*q*mp)%n
	return list((r1,n-r1,r2,n-r2))
	
def solve(arr):
	tmp=[]
	for i in arr:
		tmp.append(square_root(i))
	return list(itertools.chain.from_iterable(tmp))

tmp=square_root(c)

for i in range(4):
	arr=tmp
	tmp=(solve(arr))

for i in arr:
	if b'flag' in long_to_bytes(i):
		print(long_to_bytes(i))
		break