HXP CTF 2017 - flea (Crypto 150), CodeGate 2018 Quals - RsaBaby

1_solve.py

# FLEA
'''
n, l mod 2^t depend only on p,q mod 2^t.
So we can recover p,q bit-by-bit from LSB.
Given p mod 2^t, q mod 2^t = (n / p) mod 2^t is unique.
Ideally, l would give 1/2^t filter,
but here it gives a bit less and we get up to 2000 candidates in the end.

'''
from libnum import *

n = 0x624d0c1c938cb50badd063227b2b22067772aaa6e1b8b3d39a3f8ce4998ab2bab43eb82fe45c255e3393537ca6b40027c9fdb9216cee85424ca32aa2a4d0ed91349ff93b409e853f1a0869e46d5ce61cdf93bf3af6de5b2b8ee63fb7ac0927240bfb5ef510d265236b45b83e7672614d398721d82e9cf6ddab2082517337e279206b7d6f5764394c46e0e8ed70c03e5b54a1c783f0d4e301cae3397155daca9d85f2a56fa35fb235824c08b9eea186072d58c230a36a62b6e4ec4692332fc1573d07a0b199186ad9b3b3c5856379b517ee5ef0af4ab99e7831f4cf3210c3abc56eceff1d3e43dd9497b9837fa26c24f8f8647746ddb891775a94dc201b64431d
l = 0xe60af5a2461cf86dcbd1b55cf4b9726be3b33ea4cd59669de37a9c9ccaa0d3dfd61ebea99c40b1c6ae8d0ffcb0f3b86f76009a8e51831f8e8df90338dee9c17346f1b1cb17cd015657129fec7eb3c804750aaa10d541105a59177bab631410f9aa02727109a72d1bfeabc59ed45d1a09bf338e5bf4b02d59a650510a3d4a50b2aa1536c57751d14cc494911da7c4cd1fb173c30f1bff1460133b0c36d6326dd424f85b27f1134e9febefa52fc112607da92f66c0793725381b3c4b92a05efbe19962700dd687907167196057a0df8e33aa31b069099f4115793cb98960699a1d6b7e47d5ef3516086c8837149ed212bca42be24e5dea579fa809c98374f3dc48
ct = 0xdbe279d9beb56937b6cbf8d9fbcec7a687685b732aad5b4bb99514b8872b8a9c2e0794a2f0e7a44fd969091dc0ddb7e783cd09504cbdd4b492919c0b37503dae1368961ccfa2b2eeba88491cfa9501073ebd5116c1dfd4a9bbbf47d00fafef71ff73038885a3bb72b524b7ca73e33b8cdda2728d0f4c5e3fb57576aa138047e4579c4ddc29c302ace4ff2abeccf13f77a0760f26509f4d5c12bfd4064da6ba6ff2474ce99db1dbeb506447b6fed882404aa8da8809acd7c80dd6d3ce0b5b6cce7a962e62ca1670dc86dec97f29a222391c4cbcbf60c71eead6a66cd75cb301fcb469eb103593d73cc310c82539f5cffaf311d122e2bf8e18e849fd486cbde42

sols = {(0, 0)}

for m in xrange(1111):
    print m, "bits", len(sols), "candidates"
    sols2 = set()
    mask = (2 << m) - 1
    for x, y in sols:
        if x * y == n:
            d = invmod(65537, (x-1)*(y-1))
            print `n2s(pow(ct, d, n))`
            #'hxp{T0t4LLy_r3aL1st1c_Le4kag3}\n'
            quit()
        for bx in xrange(2):
            for by in xrange(2):
                xx = x + (bx << m)
                yy = y + (by << m)

                if (xx * yy) & mask != n & mask:
                    continue
                ll = (xx ^ yy) * (xx + yy)
                if ll & mask != l & mask:
                    continue
                sols2.add((xx, yy))
    sols = sols2

2_gen.py

# FLEA
#!/usr/bin/env python3
import random, gmpy2
random = random.SystemRandom()

bits = 2048

p = gmpy2.next_prime(random.randrange(1 << bits // 2))
q = gmpy2.next_prime(random.randrange(1 << bits // 2))

n = p * q
l = (p ^ q) * (p + q)

flag = open('flag.txt', 'rb').read()
m = int.from_bytes(flag, 'big')

with open('data.txt', 'w') as f:
    f.write('{:#x}\n'.format(n))
    f.write('{:#x}\n'.format(l))
    f.write('{:#x}\n'.format(pow(m, 65537, n)))

3_data.txt

# FLEA
0x624d0c1c938cb50badd063227b2b22067772aaa6e1b8b3d39a3f8ce4998ab2bab43eb82fe45c255e3393537ca6b40027c9fdb9216cee85424ca32aa2a4d0ed91349ff93b409e853f1a0869e46d5ce61cdf93bf3af6de5b2b8ee63fb7ac0927240bfb5ef510d265236b45b83e7672614d398721d82e9cf6ddab2082517337e279206b7d6f5764394c46e0e8ed70c03e5b54a1c783f0d4e301cae3397155daca9d85f2a56fa35fb235824c08b9eea186072d58c230a36a62b6e4ec4692332fc1573d07a0b199186ad9b3b3c5856379b517ee5ef0af4ab99e7831f4cf3210c3abc56eceff1d3e43dd9497b9837fa26c24f8f8647746ddb891775a94dc201b64431d
0xe60af5a2461cf86dcbd1b55cf4b9726be3b33ea4cd59669de37a9c9ccaa0d3dfd61ebea99c40b1c6ae8d0ffcb0f3b86f76009a8e51831f8e8df90338dee9c17346f1b1cb17cd015657129fec7eb3c804750aaa10d541105a59177bab631410f9aa02727109a72d1bfeabc59ed45d1a09bf338e5bf4b02d59a650510a3d4a50b2aa1536c57751d14cc494911da7c4cd1fb173c30f1bff1460133b0c36d6326dd424f85b27f1134e9febefa52fc112607da92f66c0793725381b3c4b92a05efbe19962700dd687907167196057a0df8e33aa31b069099f4115793cb98960699a1d6b7e47d5ef3516086c8837149ed212bca42be24e5dea579fa809c98374f3dc48
0xdbe279d9beb56937b6cbf8d9fbcec7a687685b732aad5b4bb99514b8872b8a9c2e0794a2f0e7a44fd969091dc0ddb7e783cd09504cbdd4b492919c0b37503dae1368961ccfa2b2eeba88491cfa9501073ebd5116c1dfd4a9bbbf47d00fafef71ff73038885a3bb72b524b7ca73e33b8cdda2728d0f4c5e3fb57576aa138047e4579c4ddc29c302ace4ff2abeccf13f77a0760f26509f4d5c12bfd4064da6ba6ff2474ce99db1dbeb506447b6fed882404aa8da8809acd7c80dd6d3ce0b5b6cce7a962e62ca1670dc86dec97f29a222391c4cbcbf60c71eead6a66cd75cb301fcb469eb103593d73cc310c82539f5cffaf311d122e2bf8e18e849fd486cbde42

4_solve.py

# RSABaby
from libnum import *

ct =  380838525806255337893946743050327173947433371586247814759050430578204300094635270877953690129762202769875996939276197842147224857220372679703619497806927398399795108952962442891905146440202908075035070979097412854358636621348531277713225298087614167276769631514565642627640343771883615641654535423058064397195504442204533423747451626752470200734177912209703945585196661670059908372263823148356525332391696830864610833871912286943309315368473809329884078356658600058695228563250424729883958206468130236010169302227516477051342268478958591705205358855157076547042386496593253499052139707216013118968009859098636706611794339780312391554420587540660796607687910531233690474314728367495027785278881971814489961127141923005420385579115964806930701533734013794866357390109761177291603859980361697959155126598284421792362843501361967548503757576918138895493498276658301936707818035503138088925361983300854592909022681075014994189523262500924039153521343614460622246152945716505290603455309333333560506091410274263241508522602811994582040578653226240563907254131889033343189265841619698442130035569880428826546382882121430886993470180883869383405219173399698928360778092640513571913940390199302310817294277155376000921294944591121246587133744
n = 523639805914061918270627443134741619704989339108811345591765650823383811679404400743730300288077320843234806116907796484315512386749183735427076044515394957782722144465236043561036957495670530886847413432636828661793513741180618385135095922719611444315861194066682307139969523206842728092440966461922557111209480112023032164065707216752568624317883094770784553451376502893748762652573604180632157059219119741129827017117558208565054860250853978397405747507844727903363351081745897472675235414693294079400158465019978970101063161094836772073302365997371679643083941089269169502839517043186914783290465318781726781533226599462066259256698885200843104424722505593942510854302401488139137362276492532699951880474157691347473741517183512613811731637427562990396497067805682564174185792379491573312640862381843195615293946630128509982267460922475624107750277459002662884836031305873522960659017891138316482378312004790485681371129328860344989214941450460756203906709954285455206483931555441550631622907560476932030275168094874500348941952385811045752980245084909805234648503736291123092594689494187215718382724496356220857628352007757197464098872772987476828030721472777531411032286344430474215475330008833588291692767417022829531866323051
h = 200972731730097636976827049698214756107439330058946586294810837394189769656758467301378455256704981506024979360358854939307759891385801491668590432728409172325924823845795802068569504027458509726942683684845099685005724309372842055251251103232234279320256975662933177657993600463290652464246399357992101963313348397652939723188131041888535203383479379782750484175239116419074864386243581748425119257869351582631464696880797553969260415636591522791709442079709586828716914705946883433533874750682958642851920347897328709815665287336267018234850211541263570668304013958387590188226346947851729783080697306777656948546082
g = 14511485561279877242490049924164262671564856980418706493772866848857612385453104346586350276227873984815502106112389832011566814347565705873657427101510533972939335373118027470906354834216983842099812965592939768854241417529908124711818216182341332507918374220901579987851767888710421089266081280013256600425746557269742268670300714949183260246617797156425767983027415373581836147225552931559016487193903056680274018867169067069164417868649729813464306199388375773268972224468436723728788928618254041886532217172217283880677562744928063668302190530092708676086756514664006766909499651097644447881334032649057611965077951245778537347658519214651268439995915614667939336569800565797702566887133370244643122543689011224353239395653153094885449557256699923700742653930928887024447374907536229536501931493386170594869542262576409686250950887746501725676758035668270309685358291271363775138099327895323451901829587908987436831617628346535627562925010698445652286450107659802164994355539623617745529876829000553355956755914526849056343372137493951531663650121127924626353148067965144997177441402726593083629261964699315644045714647617156724816370270635144953182744245498998992807987174252376199074131496163299914588620694929584594866873400406185502626180264465104468365933575409921644759774899908018217623256295871823903858740112075223018089096313796599554636163186830200265892525403238639070366999401808068998639590975305617369688731214141047568939908240058088089504343104889824160334560324387496383256518400827927341943755279126157377196722373876343583757261084975726106468397487366825775319965557539853162973895788663508023419482720093445137085452233528426725965549266605359644884153719762909553953900709890192728260024241748671796401590112629479273363064208874240854298225057415248756216847693518038319188675206377870041466557414694779134628404260587970
e = 65537

sols = {(0, 0, 0)}

for m in xrange(11111):
    print m, "bits", len(sols), "candidates"
    sols2 = set()
    mask = (2 << m) - 1
    for x, y, d in sols:
        if x * y == n:
            d = invmod(65537, (x-1)*(y-1))
            print `n2s(pow(ct, d, n))`
            quit()

        for bx in xrange(2):
            for by in xrange(2):
                xx = x + (bx << m)
                yy = y + (by << m)
                if (xx * yy) & mask != n & mask: continue
                for bd in xrange(2):
                    dd = d + (bd << m)

                    # h = (d+p)^(d-p)
                    # g = d*(p-0xdeadbeef)
                    if h & mask != ((d + xx) ^ (d - xx)) & mask: continue
                    if g & mask != (d*(xx-0xdeadbeef)) & mask: continue

                    sols2.add((xx, yy, dd))
    sols = sols2

5_RSAbaby.py

# RSABaby
def GenerateKeys(p, q):
    e = 65537
    n = p * q
    pi_n = (p-1)*(q-1)
    d = mulinv(e, pi_n)
    h = (d+p)^(d-p)
    g = d*(p-0xdeadbeef)
    return [e, n, h, g]

6_Result.txt

# RSABaby
[*] Encrypted Data : 380838525806255337893946743050327173947433371586247814759050430578204300094635270877953690129762202769875996939276197842147224857220372679703619497806927398399795108952962442891905146440202908075035070979097412854358636621348531277713225298087614167276769631514565642627640343771883615641654535423058064397195504442204533423747451626752470200734177912209703945585196661670059908372263823148356525332391696830864610833871912286943309315368473809329884078356658600058695228563250424729883958206468130236010169302227516477051342268478958591705205358855157076547042386496593253499052139707216013118968009859098636706611794339780312391554420587540660796607687910531233690474314728367495027785278881971814489961127141923005420385579115964806930701533734013794866357390109761177291603859980361697959155126598284421792362843501361967548503757576918138895493498276658301936707818035503138088925361983300854592909022681075014994189523262500924039153521343614460622246152945716505290603455309333333560506091410274263241508522602811994582040578653226240563907254131889033343189265841619698442130035569880428826546382882121430886993470180883869383405219173399698928360778092640513571913940390199302310817294277155376000921294944591121246587133744

[*] N : 523639805914061918270627443134741619704989339108811345591765650823383811679404400743730300288077320843234806116907796484315512386749183735427076044515394957782722144465236043561036957495670530886847413432636828661793513741180618385135095922719611444315861194066682307139969523206842728092440966461922557111209480112023032164065707216752568624317883094770784553451376502893748762652573604180632157059219119741129827017117558208565054860250853978397405747507844727903363351081745897472675235414693294079400158465019978970101063161094836772073302365997371679643083941089269169502839517043186914783290465318781726781533226599462066259256698885200843104424722505593942510854302401488139137362276492532699951880474157691347473741517183512613811731637427562990396497067805682564174185792379491573312640862381843195615293946630128509982267460922475624107750277459002662884836031305873522960659017891138316482378312004790485681371129328860344989214941450460756203906709954285455206483931555441550631622907560476932030275168094874500348941952385811045752980245084909805234648503736291123092594689494187215718382724496356220857628352007757197464098872772987476828030721472777531411032286344430474215475330008833588291692767417022829531866323051

[*] h : 200972731730097636976827049698214756107439330058946586294810837394189769656758467301378455256704981506024979360358854939307759891385801491668590432728409172325924823845795802068569504027458509726942683684845099685005724309372842055251251103232234279320256975662933177657993600463290652464246399357992101963313348397652939723188131041888535203383479379782750484175239116419074864386243581748425119257869351582631464696880797553969260415636591522791709442079709586828716914705946883433533874750682958642851920347897328709815665287336267018234850211541263570668304013958387590188226346947851729783080697306777656948546082

[*] g : 14511485561279877242490049924164262671564856980418706493772866848857612385453104346586350276227873984815502106112389832011566814347565705873657427101510533972939335373118027470906354834216983842099812965592939768854241417529908124711818216182341332507918374220901579987851767888710421089266081280013256600425746557269742268670300714949183260246617797156425767983027415373581836147225552931559016487193903056680274018867169067069164417868649729813464306199388375773268972224468436723728788928618254041886532217172217283880677562744928063668302190530092708676086756514664006766909499651097644447881334032649057611965077951245778537347658519214651268439995915614667939336569800565797702566887133370244643122543689011224353239395653153094885449557256699923700742653930928887024447374907536229536501931493386170594869542262576409686250950887746501725676758035668270309685358291271363775138099327895323451901829587908987436831617628346535627562925010698445652286450107659802164994355539623617745529876829000553355956755914526849056343372137493951531663650121127924626353148067965144997177441402726593083629261964699315644045714647617156724816370270635144953182744245498998992807987174252376199074131496163299914588620694929584594866873400406185502626180264465104468365933575409921644759774899908018217623256295871823903858740112075223018089096313796599554636163186830200265892525403238639070366999401808068998639590975305617369688731214141047568939908240058088089504343104889824160334560324387496383256518400827927341943755279126157377196722373876343583757261084975726106468397487366825775319965557539853162973895788663508023419482720093445137085452233528426725965549266605359644884153719762909553953900709890192728260024241748671796401590112629479273363064208874240854298225057415248756216847693518038319188675206377870041466557414694779134628404260587970

👍
didn't come up with the idea to recover bit-by-bit!