CCE 2020 예선 #Crypto - [중]easy rsa

2020 사이버공격방어대회 예선 09.26_9:00-24:00

 

[그림1. 문제]

 

• 압축파일을 풀면 part1~4폴더에 info.txt파일이 각각 한개씩 들어있다.
• defenit.kr/2019/09/24/Crypto/%E3%84%B4%20Research/RSA_for_CTF/를 참고해서 문제를 풀었다.

 

• "part1"의 txt파일을 보면 n,e,c 모두 아주 큰 숫자이다.
• 위너공격기법으로 문제를 풀었다. github.com/pablocelayes/rsa-wiener-attack

pablocelayes/rsa-wiener-attack

 

• git clone https://github.com/pablocelayes/rsa-wiener-attack.git 명령으로 위너 공격 코드를 다운 받은 후  RSAwienerHacker.py 하단에 아래와 같이 수정했다.

#part1
if __name__ == "__main__":
    n = 17794978846042216050148931725595089651875311785077407238910164033527181138513768671294071284950705456989896700868062911364873892841737907936796932174364952004316793386397352563981251184830539963427817428792509765806272749528680955167527053314818839560297063410450582529920692028150778172790013910881512653189496979365607573637149899686561214163728480509433052951375430686495385806843227899098451707955002974765634324880758992939521150091217162343366705107016467497931584127232763833798489419633047145088150154808162195837036182705509102573431728754458189637264510940459295288262509486589513024806088805163268299478549
    e = 8620489760843138811089147613664985387872458142889135797114151879030353568821851472032139305485073053172538861737539616609522302611682964688330279640455638198463330774387112709855821640629660306520056350625233302149956636582477049496831120026526157561762830688988870077260971692781568674574331103166166611908818543739297651202004510219426717586861979708034724218296030033905457242142637141746080427450401610454120624390617039918415976529578465809468367298106786113280667400010843541499562903598763820240992463566728346679653690890926546118178719006148959539350708863008221961156162381164809848959304544133385532678825
    c = 15978626895575345942061366609913967164739556838499551075186726099145750722246631266677117338824732344285613619349431047176921581954476589798159703959540028417262514686106742038298385290368629286239321519121825476325910941332947394805669059863780985622339177969269472466347291240234631999207864239797531951932625187893059262232848933043486875693419910771276117215252707567050462887664359031135884573867038206672133655472872123842795104536331289870186252631460694391691037265388140038609414108115136764629190893548518028098851424197678414288999228317439873715288331468970387916065626597753114357613244162619511774628766

    d = hack_RSA(e, n)

    print ('%x' % pow(c, d, n))

 

• 출력결과 4343457b456173795f50 헥스값이 나온다. ascii값으로 변환해보면 'CCE{Easy_P' 가 나오는 걸로 보아 part1~4를 합치면 플래그가 될 것 같다.

 

• "part2" txt파일을 보면 n이 엄청나게 크고, e는 65537이다. 

part2.py

0.00MB

#part2
import gmpy2

n = 1594143569557217399984075480720203827129877035942398682983020127597484080359905431995305536434658776918325557073348233286925190745163399637752520124105234970543312916953797725147236788194753028392315324443174570830615125671259032722623306377422715975845851680523950668625785918983223206026741725783938336177551639158879830414614871462138318140531932321841017463464628021089100932415123046370526284572036977341860036712378364039250868585426479833669689801482577147

a = gmpy2.isqrt(n) + 1
b2 = a * a - n

while not gmpy2.is_square(b2):
       a = a + 1
       b2 = a * a - n

b = gmpy2.isqrt(b2)

p = a + b
q = a - b

print("p =", p)
print("q =", q)

 

gmpy2설치방법

sudo apt-get install libgmp3-dev

sudo apt-get install libmpfr-dev

 

sudo apt-get install libmpc-dev

 

sudo pip install gmpy

sudo pip install gmpy2

 

• 구글링을 해보면 소인수분해할 수 있는 사이트가 나온다. factordb.com/ 
• 하지만, part2의 n은 너무 커서 소인수분해가 되지 않아 gmpy2모듈을 이용하면 빠르게 나온다.

 

 

[그림2. part2 p, q]

 

• p,q를 구했으면 평문을 구하는건 쉽다.

 

#part2
from Crypto.Util.number import inverse

n = 1594143569557217399984075480720203827129877035942398682983020127597484080359905431995305536434658776918325557073348233286925190745163399637752520124105234970543312916953797725147236788194753028392315324443174570830615125671259032722623306377422715975845851680523950668625785918983223206026741725783938336177551639158879830414614871462138318140531932321841017463464628021089100932415123046370526284572036977341860036712378364039250868585426479833669689801482577147
e = 65537
c = 1420515665868581596940839803363950617909765271157014931946210051898436055113441042059150620385341022060755816183000424771452783690046953226457156301983913192455623601540481706661522862559348925062934344162580531535464528754543447377064964651190504954974380681579617753474952167222143347357809943679934361478600911873350650280141291550434021788309056194537934961289615617918196612413794338992167853525086525213136852210782909539899505364113978261766537134423857173

p=1262593984445204538447202200381392552597147745306036473849541248751288765803533895226113614239165361220690474232436980944403732140418010970263615510025838222108529930009862561709482706431208722619561714020792620327341723824167049519
q=1262593984445204538447202200381392552597147745306036473849541248751288765803533895226113614239165361220690474232759762179164595714125000866763991994317051446212182869113694981277063659183313871948267383180809849256829620320760538613

phi=(p-1)*(q-1)
d=inverse(e,phi)
m=hex(pow(c,d,n))
print(m)

 

• 출력값은 656173795f50723062이다. 값을 변환하면 'easy_Pr0b'가 나온다.

 

• "part3" txt파일을 보면  아까에 비해 n이 조금 짧다. factordb.com/ 에서 값을 넣으면 쉽게 p, q를 구할 수 있다.

#part3
from Crypto.Util.number import inverse

n = 5117449015452230507970530313700101221760938199059348789953180035854073852549869237
e = 65537
c = 4471662859088419438542536490278623560067760494869397330114565434335260201926586033

p=64117314142720457036484283602724109205821
q=79813839426604222178879904625111308372697

phi=(p-1)*(q-1)
d=inverse(e,phi)
m=hex(pow(c,d,n))
print(m)

 

• 출력값은 5f72696768743f5f이고 변환 값은 '_right?_'이다. 

 

• "part4" txt파일을 보면 n이 엄청 크고, e가 굉장히 짧다.
• 낮은 지수 공격기법을 활용하면 된다.

 

#part4
from gmpy2 import *
from Crypto.Util.number import inverse
import time 
n = 10225510714134365745419812213979007923512416883701698031061631131554287928157995960851104254105614054632258188122757990066788697204246674743504813469672278819586346235964431069894126515023102676651504233586345045531392074918181461400729405678478540473487189095110959176658561602827509843158332908949439256858979316177175825765449250721290681382175781384493181850410616727290888261224714984055772604058787208758297883084448187449666077953042945572017173301807020723254156107829979748738614790293062886216723984316015105721698737941286722106566277452142682842200458457114015349935397336783973096521633106016356176360007
c = 340367453566526244883416366790127360372520168777999761070900847701270609351400962281351434533034967316847055272775676939065383028659076554177750307491028686884533788664296203682181434792205639992309882796702809465905356563917406628983692069596031529856791681039538144770106671291836348496625243238930819952442684845581191075702475185206016200328470477746200079326823877615352496854633406849989425132712166830335768477614367877648666677
e = 23


with local_context() as ctx:
    ctx.precision=3000
    m=iroot(c,e)[0]

    print(m)

 

• 출력결과 7810761778746845053-> 6c6566745f67677d 변환해보면 left_gg}가 나온다.
• Flag : CCE{Easy_Peasy_Pr0b_right?_left_gg} (뒤 늦게 해결... 이게 플래그가 맞나....?)