By choirish | February 17, 2018

Codegate2018 RSAbaby 출제자 Writeup

안녕하세요, choirish 입니다 :)
이번 예선에 제가 출제한 문제는 RSAbaby 입니다.

Challenge Name : RSAbaby

Category : Crypto

Downloaded Files : RSAbaby.py / Result.txt

RSA 암호를 주제로 문제를 만들어보고 싶어서 이것 저것 찾아보며 고민을 해보았는데…
준비 시간도 길지 않고, 머리도 굳어서…. 하… \^-\^a
제 마음에 드는 재미있는 문제를 만들지 못해서 조금 아쉬웠습니다 :(

어찌저찌 알려진 방법들을 조합하여 문제를 만들었는데…!
어려운 문제는 아니였기 때문에 많은 분들이 풀어주셨고, 그것 또한 보람찬 일이었다고 생각합니다 :D

RSAbaby.py

#!/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()

함수 설명

xgcd(b,n) : 확장 유클리드 호제법을 이용하는 함수
mulinv(b,n) : mod 연산에서의 역원을 구하는 함수
GenerateN(randomST) : 2048bit 이하의 랜덤 수를 기반으로 큰 소수 p,q를 생성하는 함수
GenerateKeys(p,q) : 공개키 e,n과 비밀키 간의 관계식에 대한 결과값 h,g를 생성하는 함수
EncryptMsg() : 공개키를 이용하여 Flag를 암호화하고, Encrypted Data, N, h, g를 출력하는 함수

Result.txt

[*] Encrypted Data : 380838525806255337893946743050327173947433371586247814759050430578204300094635270877953690129762202769875996939276197842147224857220372679703619497806927398399795108952962442891905146440202908075035070979097412854358636621348531277713225298087614167276769631514565642627640343771883615641654535423058064397195504442204533423747451626752470200734177912209703945585196661670059908372263823148356525332391696830864610833871912286943309315368473809329884078356658600058695228563250424729883958206468130236010169302227516477051342268478958591705205358855157076547042386496593253499052139707216013118968009859098636706611794339780312391554420587540660796607687910531233690474314728367495027785278881971814489961127141923005420385579115964806930701533734013794866357390109761177291603859980361697959155126598284421792362843501361967548503757576918138895493498276658301936707818035503138088925361983300854592909022681075014994189523262500924039153521343614460622246152945716505290603455309333333560506091410274263241508522602811994582040578653226240563907254131889033343189265841619698442130035569880428826546382882121430886993470180883869383405219173399698928360778092640513571913940390199302310817294277155376000921294944591121246587133744

[*] N : 523639805914061918270627443134741619704989339108811345591765650823383811679404400743730300288077320843234806116907796484315512386749183735427076044515394957782722144465236043561036957495670530886847413432636828661793513741180618385135095922719611444315861194066682307139969523206842728092440966461922557111209480112023032164065707216752568624317883094770784553451376502893748762652573604180632157059219119741129827017117558208565054860250853978397405747507844727903363351081745897472675235414693294079400158465019978970101063161094836772073302365997371679643083941089269169502839517043186914783290465318781726781533226599462066259256698885200843104424722505593942510854302401488139137362276492532699951880474157691347473741517183512613811731637427562990396497067805682564174185792379491573312640862381843195615293946630128509982267460922475624107750277459002662884836031305873522960659017891138316482378312004790485681371129328860344989214941450460756203906709954285455206483931555441550631622907560476932030275168094874500348941952385811045752980245084909805234648503736291123092594689494187215718382724496356220857628352007757197464098872772987476828030721472777531411032286344430474215475330008833588291692767417022829531866323051

[*] h : 200972731730097636976827049698214756107439330058946586294810837394189769656758467301378455256704981506024979360358854939307759891385801491668590432728409172325924823845795802068569504027458509726942683684845099685005724309372842055251251103232234279320256975662933177657993600463290652464246399357992101963313348397652939723188131041888535203383479379782750484175239116419074864386243581748425119257869351582631464696880797553969260415636591522791709442079709586828716914705946883433533874750682958642851920347897328709815665287336267018234850211541263570668304013958387590188226346947851729783080697306777656948546082

[*] g : 14511485561279877242490049924164262671564856980418706493772866848857612385453104346586350276227873984815502106112389832011566814347565705873657427101510533972939335373118027470906354834216983842099812965592939768854241417529908124711818216182341332507918374220901579987851767888710421089266081280013256600425746557269742268670300714949183260246617797156425767983027415373581836147225552931559016487193903056680274018867169067069164417868649729813464306199388375773268972224468436723728788928618254041886532217172217283880677562744928063668302190530092708676086756514664006766909499651097644447881334032649057611965077951245778537347658519214651268439995915614667939336569800565797702566887133370244643122543689011224353239395653153094885449557256699923700742653930928887024447374907536229536501931493386170594869542262576409686250950887746501725676758035668270309685358291271363775138099327895323451901829587908987436831617628346535627562925010698445652286450107659802164994355539623617745529876829000553355956755914526849056343372137493951531663650121127924626353148067965144997177441402726593083629261964699315644045714647617156724816370270635144953182744245498998992807987174252376199074131496163299914588620694929584594866873400406185502626180264465104468365933575409921644759774899908018217623256295871823903858740112075223018089096313796599554636163186830200265892525403238639070366999401808068998639590975305617369688731214141047568939908240058088089504343104889824160334560324387496383256518400827927341943755279126157377196722373876343583757261084975726106468397487366825775319965557539853162973895788663508023419482720093445137085452233528426725965549266605359644884153719762909553953900709890192728260024241748671796401590112629479273363064208874240854298225057415248756216847693518038319188675206377870041466557414694779134628404260587970

Result.txt 파일의 결과를 기준으로 p, q, Flag를 구하면 된다.

How to Solve

본래 출제자의 의도는…

h = (d+p)\^(d-p)
- p가 2048bit라고 했을 때 h는 d와 p의 XOR 연산 결과값으로, 대략 2048bit의 값입니다.
- 즉, h는 d의 하위 2048bit와 p의 XOR 연산에 대한 결과값입니다.
g = d*(p-0xdeadbeef)
- d와 p의 곱셈 연산에 대한 결과값입니다.

대부분의 참가자들께서는 h값은 도대체 왜 준건가.. 어디 쓰라는 거냐.. 하면서 의문을 가지셨을 텐데요 :)
사실 h는 xor 관계식을 통하여 1bit씩 brute-force attack으로 d와 p의 값을 유추해낼 수 있는 관계식입니다.

이 아이디어는 HXP CTF 2018 - flea 라는 문제에서 따온 것입니다 ㅎㅎ

HXP CTF 2017 - flea

처음 문제를 보고서도 “우와 이건 무슨 관계식이지?” 궁금했는데
풀이를 보고서 참 재미있는 문제라고 생각하여 이를 활용해서 d와 p에 대한 관계식으로 구성해보았습니다.

따라서, flea 문제의 풀이 방법을 참고하여
d의 하위 비트(대략 p-bit && d-bit/2 보다 많은 비트)를 알아내고,
Coppersmith's attack으로 d의 나머지 상위 비트를 알아내는 것이 본래 의도였습니다 :D

본선 진출 팀의 write-up을 확인해보니, flea 문제를 풀었던 LCBC 팀만 본래 의도로 풀었고
나머지 팀들은 g(= d*(p-0xdeadbeef))만을 이용해서 문제를 풀었다고 합니다 ㅎㅎ

다른 풀이는…

저는 CTFtime.org에 올라온 DoubleSigma 팀의 풀이를 을 참고하였는데, Fermat Littlel Theorem을 통해 g 값을 이용하여 비밀키 p를 구하는 방법을 잘 설명해 두었습니다.

DoubleSigma - Codegate2018 RSAbaby Writeup

비밀키 d의 하위 비트를 복구하기 위해서는 d와 p에 대한 관계식이 하나 더 필요해서
g 관계식을 추가한 것이었는데.. 이렇게 이용될 수 있다는 걸 고려하지 못한 게 아쉽네요…

그래도 이걸 통해서 또 한 가지 배우게 되어 좋은 경험이 되었습니다.

문제 풀어주신 모든 분들, 감사합니다! :)