Maojui

Codegate 2018 - RSAbaby (Crypto, 349)

2018-02-04

Challenge

This code generates general(random) RSA keys

Given

1
2
3
4
5
6
7
#[*] Encrypted Data : 380838525806255337893946743050327173947433371586247814759050430578204300094635270877953690129762202769875996939276197842147224857220372679703619497806927398399795108952962442891905146440202908075035070979097412854358636621348531277713225298087614167276769631514565642627640343771883615641654535423058064397195504442204533423747451626752470200734177912209703945585196661670059908372263823148356525332391696830864610833871912286943309315368473809329884078356658600058695228563250424729883958206468130236010169302227516477051342268478958591705205358855157076547042386496593253499052139707216013118968009859098636706611794339780312391554420587540660796607687910531233690474314728367495027785278881971814489961127141923005420385579115964806930701533734013794866357390109761177291603859980361697959155126598284421792362843501361967548503757576918138895493498276658301936707818035503138088925361983300854592909022681075014994189523262500924039153521343614460622246152945716505290603455309333333560506091410274263241508522602811994582040578653226240563907254131889033343189265841619698442130035569880428826546382882121430886993470180883869383405219173399698928360778092640513571913940390199302310817294277155376000921294944591121246587133744

#[*] N : 523639805914061918270627443134741619704989339108811345591765650823383811679404400743730300288077320843234806116907796484315512386749183735427076044515394957782722144465236043561036957495670530886847413432636828661793513741180618385135095922719611444315861194066682307139969523206842728092440966461922557111209480112023032164065707216752568624317883094770784553451376502893748762652573604180632157059219119741129827017117558208565054860250853978397405747507844727903363351081745897472675235414693294079400158465019978970101063161094836772073302365997371679643083941089269169502839517043186914783290465318781726781533226599462066259256698885200843104424722505593942510854302401488139137362276492532699951880474157691347473741517183512613811731637427562990396497067805682564174185792379491573312640862381843195615293946630128509982267460922475624107750277459002662884836031305873522960659017891138316482378312004790485681371129328860344989214941450460756203906709954285455206483931555441550631622907560476932030275168094874500348941952385811045752980245084909805234648503736291123092594689494187215718382724496356220857628352007757197464098872772987476828030721472777531411032286344430474215475330008833588291692767417022829531866323051

#[*] h : 200972731730097636976827049698214756107439330058946586294810837394189769656758467301378455256704981506024979360358854939307759891385801491668590432728409172325924823845795802068569504027458509726942683684845099685005724309372842055251251103232234279320256975662933177657993600463290652464246399357992101963313348397652939723188131041888535203383479379782750484175239116419074864386243581748425119257869351582631464696880797553969260415636591522791709442079709586828716914705946883433533874750682958642851920347897328709815665287336267018234850211541263570668304013958387590188226346947851729783080697306777656948546082

#[*] g : 14511485561279877242490049924164262671564856980418706493772866848857612385453104346586350276227873984815502106112389832011566814347565705873657427101510533972939335373118027470906354834216983842099812965592939768854241417529908124711818216182341332507918374220901579987851767888710421089266081280013256600425746557269742268670300714949183260246617797156425767983027415373581836147225552931559016487193903056680274018867169067069164417868649729813464306199388375773268972224468436723728788928618254041886532217172217283880677562744928063668302190530092708676086756514664006766909499651097644447881334032649057611965077951245778537347658519214651268439995915614667939336569800565797702566887133370244643122543689011224353239395653153094885449557256699923700742653930928887024447374907536229536501931493386170594869542262576409686250950887746501725676758035668270309685358291271363775138099327895323451901829587908987436831617628346535627562925010698445652286450107659802164994355539623617745529876829000553355956755914526849056343372137493951531663650121127924626353148067965144997177441402726593083629261964699315644045714647617156724816370270635144953182744245498998992807987174252376199074131496163299914588620694929584594866873400406185502626180264465104468365933575409921644759774899908018217623256295871823903858740112075223018089096313796599554636163186830200265892525403238639070366999401808068998639590975305617369688731214141047568939908240058088089504343104889824160334560324387496383256518400827927341943755279126157377196722373876343583757261084975726106468397487366825775319965557539853162973895788663508023419482720093445137085452233528426725965549266605359644884153719762909553953900709890192728260024241748671796401590112629479273363064208874240854298225057415248756216847693518038319188675206377870041466557414694779134628404260587970

In the code, the generating rule 

1
2
3
4
5
6
7
8
9
def GenerateKeys(p, q):
    e = 65537
    n = p * q
    pi_n = (p-1)*(q-1)
    d = mulinv(e, pi_n)
    h1,h2 = (d+p),(d-p)
    h = (d+p)^(d-p)         
    g = d*(p-0xdeadbeef)    #3735928559
    return [e, p,q, n, h1,h2,h, g,d]

Solution

$h$ looks very strange and … I think is useless LOL.
So, I get started from $g$

$g=d*(p-const)$ (which const is 0xdeadbeef)

As we know

$m^{ed} \equiv m^1 \ mod\ \ N$
$\Rightarrow e*g = ed *( p - const )$

Get any const a, I choose a=2

$2^{eg} \equiv 2^{ed(p-const)} \equiv 2^{(p-const)} \ mod\ \ N$

By fermat little theorem

$a^{p-1} \equiv 1 \ mod\ \ p$
$\Rightarrow a^{p-1}-1=k*p$

Therefore

$2^{eg} \equiv 2^{ed(p-const)} \equiv 2^{(p-const)} \ mod\ \ N$
$2^{( p - const )} * 2^{( const - 1 )} \equiv 2^{(p-1)} \ mod\ \ N$ 

1
2
3
kp = pow(2,e*g,N) * pow(2,0xdeadbeef-1,N)
p  = gcd(kp-1,N) # N = pq
# p = 31811409645348549623053449127882290862674231133369271929416098209276377067302796737455793747462538422614379700918706241193833498111023310629026997212318192772109850300415441179803269106674140038023990825750895043565738242596321975272419171937493287441285653336571630433705006757726534166691981294592999707642674052088390419616606622130059758448387087832788561620913931294383792135875155036952024480631900978472396033035431761843696320186521041303944663483631883324759141512482298880961799997836823971848883954715830737467614012122590472338779677938311809056604574465104112824215617234766193478186952789711517365429489

solve

1
2
3
4
5
q = N//p
phi = (p-1)*(q-1)
d = invmod(e,phi)
flag = pow(cipher,d,N)
# flag = 43102361581588400293486968859330563551049298421482381837949433414001504038987794297690309874948971163645516656255162724207275662748436840875659000783360764387865950468145308535319158870968028438035192968094537367626465682759570235337713015491246737263958140007155146453204681810745327369946497520663481516647737843575879879594670178893503223294016433194786948905360184679836630688780836664185790932651151193371918232225560089315912225170475894517021837792188313935952127373178417391474388262723380180403375105303643254787662618179496251024916035400032349271509022850038288167064841265553164123470742009409172023850

Flag:Whatever you do, the Basics are the most important :-D

Tags: RSA
← Seccon 2017 - Ps & Qs (Crypto, 200) Codegate 2018 - Miro (Crypto, 404) →