CTF101 - leak (factoring with known multiple of phi)

ctf101_leak.py

from Crypto.Util.number import GCD, long_to_bytes as l2b
import random

n = 52883301925732518547300530023868858590931636853891275675649307100792183838996586482003865273456848522932479525234494362829984849206059984812526124129974173451230468439502215344021834912374540694716416754894463076546609884496979986021320585109396685097930385837804866215199828038329543126091147868086267601129
c = 35795213814057690397775320273632131942968992738349383455337416077120407224955930692779895141053824535029278792900544351786937759171849289796443513835057906273728946502669880416539370625985006208820280189553065500776676738701830454643998896534770514277496736350309310273306346714823731515132116960620058213700
leak_1 = 41788445330683886891197496562620157902949045870768970306080181162241014272216248767657126454723123373089846438219000191127720250796774663957331429054018519216129081868461359983069808084619947413259057236923756018306043112815471563321457359549156144621650815011995585224318715511493405758290851942797071849265341706822107022181301470803041818658707280424713681576728430835872974055184929558642040597704136594200874455643305910994725736823351330560740392260072264380485
leak_2 = 24492347282010171320763575568480220238915541185004042319592864577890784596518564165635275919873196349153961995204383165443322242559938394792528813268882625463235131309444057771894562225483771518637308659854005591412879867219116171052057598084852986554605066094456583889152164817806764413259716750228238738127704980229426070377501075564701953420471423869093175303487080779506680719557296435483944189196135013118198819001008773418481679649568503001232667757742780750847

# Get back the leak
leak = -1
for k1 in range(21, 43):
	for k2 in range(21, 43):
		y = GCD(leak_1 - k1, leak_2 - k2)
		if y > (2 << 10):
			print(f'{k1 = } {k2 = }')
			leak = y

print(f'{leak = }')

# Factor knowing a multiple of phi (https://math.stackexchange.com/questions/12328/rsa-fast-factorization-of-n-if-d-and-e-are-known)
def find_factor(ed, n):
	h = ed # ed is e*d - 1 (or any multiple of phi)
	while h % 2 == 0:
		h = h // 2
	h = int(h)

	for cnt in range(100):
		print(f'{cnt = }')
		a = random.randint(2, n-2)
		g = GCD(a, n)
		if g != 1:
			print(f'{g = }')
			return g

		b = pow(a, h, n)
		while True:
			g = GCD(b-1, n)
			if g == 1:
				b = pow(b, 2, n)
				continue
			if g == n:
				break
			print(f'{g = }')
			return g

p = find_factor(leak, n)
q = n // p

e = 65537
phi = (p-1)*(q-1)
d = pow(e, -1, phi)
m = pow(c, d, n)
print(f'{l2b(m) = }')