github twitter facebook email
Rsababy
Sep 16, 2019
3 minutes read

https://blackperl-security.gitlab.io/blog/2018/02/17/2018-02-17-codegate2018-rsababy/ 를 보면

#!/usr/bin/python
#-*- coding:utf-8 -*-

from gmpy2 import *
import sys
import time
import struct

def PrintIntro():
    print "██████╗ ███████╗ █████╗ ██████╗  █████╗ ██████╗ ██╗   ██╗"
    print "██╔══██╗██╔════╝██╔══██╗██╔══██╗██╔══██╗██╔══██╗╚██╗ ██╔╝"
    print "██████╔╝███████╗███████║██████╔╝███████║██████╔╝ ╚████╔╝ "
    print "██╔══██╗╚════██║██╔══██║██╔══██╗██╔══██║██╔══██╗  ╚██╔╝  "
    print "██║  ██║███████║██║  ██║██████╔╝██║  ██║██████╔╝   ██║   "
    print "╚═╝  ╚═╝╚══════╝╚═╝  ╚═╝╚═════╝ ╚═╝  ╚═╝╚═════╝    ╚═╝   "

def xgcd(b, n):
    x0, x1, y0, y1 = 1, 0, 0, 1
    while n != 0:
        q, b, n = b // n, n, b % n
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return  b, x0, y0

def mulinv(b, n):
    g, x, _ = xgcd(b, n)
    if g == 1:
        return x % n

def GenerateN(randomST):
    k1 = mpz_urandomb(randomST, 2048)
    k2 = mpz_urandomb(randomST, 2048)

    p = next_prime(k1)
    q = next_prime(k2)

    if is_prime(p, 50) and is_prime(q, 50):
        return [p, q]

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]

def EncryptMsg():
    Flag = "########################################"

    PrintIntro()

    f = open("/dev/urandom")
    seed = f.read(8)
    f.close()
    randomST = random_state(struct.unpack(">Q", seed)[0])

    print("[*] Generating Key ...\n")
    p, q = GenerateN(randomST)
    e, N, hint, gint = GenerateKeys(p, q)
    time.sleep(2)

    print("[*] Completed !!!\n")
    time.sleep(1)

    Flag = Flag.ljust(255, "\x2a")
    Flag = int(Flag.encode('hex'),16)

    EncryptedData = powmod(Flag, e, N)

    print("[*] Encrypted Data : %d\n" % EncryptedData)
    print("[*] N : %d\n" % N)
    print("[*] h : %d\n" % hint)
    print("[*] g : %d\n" % gint)

if __name__ == '__main__':
    EncryptMsg()

다음같은 코드와

[*] Encrypted Data : 380838525806255337893946743050327173947433371586247814759050430578204300094635270877953690129762202769875996939276197842147224857220372679703619497806927398399795108952962442891905146440202908075035070979097412854358636621348531277713225298087614167276769631514565642627640343771883615641654535423058064397195504442204533423747451626752470200734177912209703945585196661670059908372263823148356525332391696830864610833871912286943309315368473809329884078356658600058695228563250424729883958206468130236010169302227516477051342268478958591705205358855157076547042386496593253499052139707216013118968009859098636706611794339780312391554420587540660796607687910531233690474314728367495027785278881971814489961127141923005420385579115964806930701533734013794866357390109761177291603859980361697959155126598284421792362843501361967548503757576918138895493498276658301936707818035503138088925361983300854592909022681075014994189523262500924039153521343614460622246152945716505290603455309333333560506091410274263241508522602811994582040578653226240563907254131889033343189265841619698442130035569880428826546382882121430886993470180883869383405219173399698928360778092640513571913940390199302310817294277155376000921294944591121246587133744

[*] N : 523639805914061918270627443134741619704989339108811345591765650823383811679404400743730300288077320843234806116907796484315512386749183735427076044515394957782722144465236043561036957495670530886847413432636828661793513741180618385135095922719611444315861194066682307139969523206842728092440966461922557111209480112023032164065707216752568624317883094770784553451376502893748762652573604180632157059219119741129827017117558208565054860250853978397405747507844727903363351081745897472675235414693294079400158465019978970101063161094836772073302365997371679643083941089269169502839517043186914783290465318781726781533226599462066259256698885200843104424722505593942510854302401488139137362276492532699951880474157691347473741517183512613811731637427562990396497067805682564174185792379491573312640862381843195615293946630128509982267460922475624107750277459002662884836031305873522960659017891138316482378312004790485681371129328860344989214941450460756203906709954285455206483931555441550631622907560476932030275168094874500348941952385811045752980245084909805234648503736291123092594689494187215718382724496356220857628352007757197464098872772987476828030721472777531411032286344430474215475330008833588291692767417022829531866323051

[*] h : 200972731730097636976827049698214756107439330058946586294810837394189769656758467301378455256704981506024979360358854939307759891385801491668590432728409172325924823845795802068569504027458509726942683684845099685005724309372842055251251103232234279320256975662933177657993600463290652464246399357992101963313348397652939723188131041888535203383479379782750484175239116419074864386243581748425119257869351582631464696880797553969260415636591522791709442079709586828716914705946883433533874750682958642851920347897328709815665287336267018234850211541263570668304013958387590188226346947851729783080697306777656948546082

[*] g : 14511485561279877242490049924164262671564856980418706493772866848857612385453104346586350276227873984815502106112389832011566814347565705873657427101510533972939335373118027470906354834216983842099812965592939768854241417529908124711818216182341332507918374220901579987851767888710421089266081280013256600425746557269742268670300714949183260246617797156425767983027415373581836147225552931559016487193903056680274018867169067069164417868649729813464306199388375773268972224468436723728788928618254041886532217172217283880677562744928063668302190530092708676086756514664006766909499651097644447881334032649057611965077951245778537347658519214651268439995915614667939336569800565797702566887133370244643122543689011224353239395653153094885449557256699923700742653930928887024447374907536229536501931493386170594869542262576409686250950887746501725676758035668270309685358291271363775138099327895323451901829587908987436831617628346535627562925010698445652286450107659802164994355539623617745529876829000553355956755914526849056343372137493951531663650121127924626353148067965144997177441402726593083629261964699315644045714647617156724816370270635144953182744245498998992807987174252376199074131496163299914588620694929584594866873400406185502626180264465104468365933575409921644759774899908018217623256295871823903858740112075223018089096313796599554636163186830200265892525403238639070366999401808068998639590975305617369688731214141047568939908240058088089504343104889824160334560324387496383256518400827927341943755279126157377196722373876343583757261084975726106468397487366825775319965557539853162973895788663508023419482720093445137085452233528426725965549266605359644884153719762909553953900709890192728260024241748671796401590112629479273363064208874240854298225057415248756216847693518038319188675206377870041466557414694779134628404260587970

다음같은 결과를 줬었다고 합니다.

RSA를 decrypt하는 과정에서 다음을 이용합니다.

_1.gif

이를 조금 이용해서 g = d*(p - k), k=0xdeadbeef라 하면

_2.gif

다음 결과를 얻을 수 있습니다.

c^(p-1) (mod N) = r이라고 하면

c^(p-1) = Ns + r, s는 임의 정수 라고 나타낼 수 있습니다.

여기서 페르마 소정리를 이용하면 (a^(p-1) = 1 (mod p)) => c^(p-1) = 1 (mod p)

(Ns+r) ^ (p-1) = 1 (mod p)라고 할 수 있고, N = p*q임으로 r^(p-1) = 1 (mod p)라고 할 수 있습니다.

r = tp + 1, t는 임의 정수가 되고 c^(p-1)= c^(eg) * c^(k-1) = tp + 1 (mod N)가 됩니다.

결과적으로 우리는 tp를 구할 수 있고, 이를 N과 gcd연산을 통하면 온전한 p를 구할 수 있습니다.

그럼 q=N/p를 이용하면 두 소수 p,q 를 완전히 얻을 수 있고, 이를 이용해서 d를 구해 복호화를 진행하면 됩니다.

from gmpy2 import *

c = 380838525806255337893946743050327173947433371586247814759050430578204300094635270877953690129762202769875996939276197842147224857220372679703619497806927398399795108952962442891905146440202908075035070979097412854358636621348531277713225298087614167276769631514565642627640343771883615641654535423058064397195504442204533423747451626752470200734177912209703945585196661670059908372263823148356525332391696830864610833871912286943309315368473809329884078356658600058695228563250424729883958206468130236010169302227516477051342268478958591705205358855157076547042386496593253499052139707216013118968009859098636706611794339780312391554420587540660796607687910531233690474314728367495027785278881971814489961127141923005420385579115964806930701533734013794866357390109761177291603859980361697959155126598284421792362843501361967548503757576918138895493498276658301936707818035503138088925361983300854592909022681075014994189523262500924039153521343614460622246152945716505290603455309333333560506091410274263241508522602811994582040578653226240563907254131889033343189265841619698442130035569880428826546382882121430886993470180883869383405219173399698928360778092640513571913940390199302310817294277155376000921294944591121246587133744
N = 523639805914061918270627443134741619704989339108811345591765650823383811679404400743730300288077320843234806116907796484315512386749183735427076044515394957782722144465236043561036957495670530886847413432636828661793513741180618385135095922719611444315861194066682307139969523206842728092440966461922557111209480112023032164065707216752568624317883094770784553451376502893748762652573604180632157059219119741129827017117558208565054860250853978397405747507844727903363351081745897472675235414693294079400158465019978970101063161094836772073302365997371679643083941089269169502839517043186914783290465318781726781533226599462066259256698885200843104424722505593942510854302401488139137362276492532699951880474157691347473741517183512613811731637427562990396497067805682564174185792379491573312640862381843195615293946630128509982267460922475624107750277459002662884836031305873522960659017891138316482378312004790485681371129328860344989214941450460756203906709954285455206483931555441550631622907560476932030275168094874500348941952385811045752980245084909805234648503736291123092594689494187215718382724496356220857628352007757197464098872772987476828030721472777531411032286344430474215475330008833588291692767417022829531866323051
h = 200972731730097636976827049698214756107439330058946586294810837394189769656758467301378455256704981506024979360358854939307759891385801491668590432728409172325924823845795802068569504027458509726942683684845099685005724309372842055251251103232234279320256975662933177657993600463290652464246399357992101963313348397652939723188131041888535203383479379782750484175239116419074864386243581748425119257869351582631464696880797553969260415636591522791709442079709586828716914705946883433533874750682958642851920347897328709815665287336267018234850211541263570668304013958387590188226346947851729783080697306777656948546082
g = 14511485561279877242490049924164262671564856980418706493772866848857612385453104346586350276227873984815502106112389832011566814347565705873657427101510533972939335373118027470906354834216983842099812965592939768854241417529908124711818216182341332507918374220901579987851767888710421089266081280013256600425746557269742268670300714949183260246617797156425767983027415373581836147225552931559016487193903056680274018867169067069164417868649729813464306199388375773268972224468436723728788928618254041886532217172217283880677562744928063668302190530092708676086756514664006766909499651097644447881334032649057611965077951245778537347658519214651268439995915614667939336569800565797702566887133370244643122543689011224353239395653153094885449557256699923700742653930928887024447374907536229536501931493386170594869542262576409686250950887746501725676758035668270309685358291271363775138099327895323451901829587908987436831617628346535627562925010698445652286450107659802164994355539623617745529876829000553355956755914526849056343372137493951531663650121127924626353148067965144997177441402726593083629261964699315644045714647617156724816370270635144953182744245498998992807987174252376199074131496163299914588620694929584594866873400406185502626180264465104468365933575409921644759774899908018217623256295871823903858740112075223018089096313796599554636163186830200265892525403238639070366999401808068998639590975305617369688731214141047568939908240058088089504343104889824160334560324387496383256518400827927341943755279126157377196722373876343583757261084975726106468397487366825775319965557539853162973895788663508023419482720093445137085452233528426725965549266605359644884153719762909553953900709890192728260024241748671796401590112629479273363064208874240854298225057415248756216847693518038319188675206377870041466557414694779134628404260587970
e = 65537

# g = d * (p - 0xdeadbeef)
p = gcd(powmod(c, e*g + 0xdeadbeef-1, N)-1, N)
q = N/p

print (p,q)

piN = (p-1)*(q-1)
d = invert(e, piN)
a = '%x' %  powmod(c, d, N)
b = [a[i:i+2] for i in range(0, len(a), 2)]
res = []
for i in b:
	res.append(chr(int(i,16)))

print ''.join(res)

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


Back to posts


comments powered by Disqus