Skip to content

Instantly share code, notes, and snippets.

@r98inver
Last active October 22, 2023 22:26
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save r98inver/c041c72140b5512c35ae348d53a4e4d4 to your computer and use it in GitHub Desktop.
Save r98inver/c041c72140b5512c35ae348d53a4e4d4 to your computer and use it in GitHub Desktop.
CTF101 - leak (factoring with known multiple of phi)
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) = }')
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment