[2020CCE] Easy RSA - 암호학 / RsaCtfTool / Python

 

2020년에 진행되었던 국정원 주최 사이버공격방어대회

 

묵혀놨던 Write Up을 이제야 포스팅 해 본다.

 

반응형

 

이번에 풀이할 문제는 Easy RSA 문제이다.

 

문제 제목에 나온것 처럼 RSA 암호 알고리즘과 관련되어있다.

 

RSA는 지금까지도 아주 많이 사용하는 공개키 알고리즘의 이름이다.

 

개발자인 Rivest, Shamir, Adleman 세명의 이름 앞글자를 따서 RSA 라고 이름을 붙혔다.

 

엄청나게 큰 숫자일수록 소인수분해가 어렵다는것에 착안해서 설계되었다.

 

RSA의 원리는 아래와 같다.

 

1. 두 소수 p, q를 준비한다.

2. p-1, q-1과 각각 서로소(1외에는 공약수가 없는 수)인 정수 e를 준비한다.

3. ed를 (p-1)(q-1)으로 나눈 나머지가 1의 되도록 하는 d를 구한다.(d는 개인키로 공개하지 않는다)

4. n=pq를 계산한 후 n과 e를 공개한다.(이 둘이 공개키)

 

이 알고리즘을 이용해서 공개키-개인키 쌍을 만들고

 

공개키로 암호화했다면 개인키로만 풀 수 있고, 개인키로 암호화했다면 공개키로만 풀 수 있는 그런 알고리즘이다.

 

 

문제에서는 easy_rsa.zip 파일이 주어진다.

 

 

압축을 풀어보면 안에 이렇게

 

part1, part2, part3, part4 네 개의 폴더가 들어있다.

 

 

각각의 part* 폴더 안에는 이렇게 info.txt 파일이 하나씩 들어가 있다.

 

N = 17794978846042216050148931725595089651875311785077407238910164033527181138513768671294071284950705456989896700868062911364873892841737907936796932174364952004316793386397352563981251184830539963427817428792509765806272749528680955167527053314818839560297063410450582529920692028150778172790013910881512653189496979365607573637149899686561214163728480509433052951375430686495385806843227899098451707955002974765634324880758992939521150091217162343366705107016467497931584127232763833798489419633047145088150154808162195837036182705509102573431728754458189637264510940459295288262509486589513024806088805163268299478549
e = 8620489760843138811089147613664985387872458142889135797114151879030353568821851472032139305485073053172538861737539616609522302611682964688330279640455638198463330774387112709855821640629660306520056350625233302149956636582477049496831120026526157561762830688988870077260971692781568674574331103166166611908818543739297651202004510219426717586861979708034724218296030033905457242142637141746080427450401610454120624390617039918415976529578465809468367298106786113280667400010843541499562903598763820240992463566728346679653690890926546118178719006148959539350708863008221961156162381164809848959304544133385532678825
c = 15978626895575345942061366609913967164739556838499551075186726099145750722246631266677117338824732344285613619349431047176921581954476589798159703959540028417262514686106742038298385290368629286239321519121825476325910941332947394805669059863780985622339177969269472466347291240234631999207864239797531951932625187893059262232848933043486875693419910771276117215252707567050462887664359031135884573867038206672133655472872123842795104536331289870186252631460694391691037265388140038609414108115136764629190893548518028098851424197678414288999228317439873715288331468970387916065626597753114357613244162619511774628766

N = 1594143569557217399984075480720203827129877035942398682983020127597484080359905431995305536434658776918325557073348233286925190745163399637752520124105234970543312916953797725147236788194753028392315324443174570830615125671259032722623306377422715975845851680523950668625785918983223206026741725783938336177551639158879830414614871462138318140531932321841017463464628021089100932415123046370526284572036977341860036712378364039250868585426479833669689801482577147
e = 65537
c = 1420515665868581596940839803363950617909765271157014931946210051898436055113441042059150620385341022060755816183000424771452783690046953226457156301983913192455623601540481706661522862559348925062934344162580531535464528754543447377064964651190504954974380681579617753474952167222143347357809943679934361478600911873350650280141291550434021788309056194537934961289615617918196612413794338992167853525086525213136852210782909539899505364113978261766537134423857173

N = 5117449015452230507970530313700101221760938199059348789953180035854073852549869237
e = 65537
c = 4471662859088419438542536490278623560067760494869397330114565434335260201926586033

N = 10225510714134365745419812213979007923512416883701698031061631131554287928157995960851104254105614054632258188122757990066788697204246674743504813469672278819586346235964431069894126515023102676651504233586345045531392074918181461400729405678478540473487189095110959176658561602827509843158332908949439256858979316177175825765449250721290681382175781384493181850410616727290888261224714984055772604058787208758297883084448187449666077953042945572017173301807020723254156107829979748738614790293062886216723984316015105721698737941286722106566277452142682842200458457114015349935397336783973096521633106016356176360007
e = 23
c = 340367453566526244883416366790127360372520168777999761070900847701270609351400962281351434533034967316847055272775676939065383028659076554177750307491028686884533788664296203682181434792205639992309882796702809465905356563917406628983692069596031529856791681039538144770106671291836348496625243238930819952442684845581191075702475185206016200328470477746200079326823877615352496854633406849989425132712166830335768477614367877648666677

 

각각의 info.txt 파일의 내용은 위와 같다.

 

서로 다른 공개키로 암호화한 암호문이 들어가 있다.

 

총 네번 RSA를 풀어야 플래그를 찾을 수 있다.

 

진짜 악랄하게도 만들어 놨다..

 

문제를 풀기전에 도구를 먼저 준비해야 한다.

 

RSA 문제를 풀때 github에 보면 RsaCtfTool 이라는 좋은 도구가있다. 

 

 

git clone [github 주소] 명령어를 통해 다운로드 받을 수 있다.

 

다운로드 받고나서 cd RsaCtfTool 명령어로 해당 폴더에 들어가보면

 

RsaCtfTool.py 라는 파이썬 파일이 보이게 된다.

 

 

./RsaCtfTool.py 라고 입력하면 실행이 가능한데

 

이렇게 No module named 'Crytpo' 라는 에러가 나게되면

 

 

pip install pycrypto 명령어로 다운로드 받아주면 된다.

 

 

다운받으면 이렇게 잘 실행이 된다.

 

이제 옵션을 줘서 툴을 실행시키면 된다.

 

먼저 part1 의 info.txt 파일을 살펴보자.

 

여기서 봤을때 가장 큰 특징은

 

e 값이 어마무시하게 크다는 것이다.

 

RSA 암호에서 e 값이 이렇게 클 경우 Wiener Attack 이 가능해진다.

 

Wiener Attack 을 하게되면 개인키 d 값을 복구할 수 있게 되어

 

암호문을 해독할 수 있게 된다.

 

 

./RsaCtfTool.py -n n값 -e e값 --uncipher c값 으로 옵션을 넣어준 후에

 

--attack wiener 라고 명시해서 위너 공격을 해주면 된다.

 

잠시 기다리면 아래쪽에 플래그의 첫번째 부분인 CCE{Easy_P 가 나오는것을 볼 수 있다.

 

 

두번째로 part2 폴더의 info.txt 파일을 살펴보자.

 

사실 이건 바로 알아채진 못하고, 이것저것 시도해보다가 풀었다.

 

N과 c 값이 너무 커서 그냥 RsaCtfTool 에 돌렸더니 부하를 이기지 못하고 죽어버렸다.

 

결론적으로 이 부분은 Fermat's factorization 을 이용했다.

 

N = p * q 에서 p/q 가 비슷한 값(1에 근사하면) p 와 q 값을 구할 수 있는 방법이다.

 

from Crypto.Util.number import long_to_bytes
from gmpy2 import *
 
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 mul_inv(b, n):
    g, x, _ = xgcd(b, n)
    if g == 1:
        return x % n
    
def fermat_factor(n):
    assert n % 2 != 0
    
    a = isqrt(n)
    b2 = square(a) - n
    
    while not is_square(b2):
        a += 1
        b2 = square(a) - n
    p = a + isqrt(b2)
    q = a - isqrt(b2)
    
    return int(p), int(q)
    
 
n = 1594143569557217399984075480720203827129877035942398682983020127597484080359905431995305536434658776918325557073348233286925190745163399637752520124105234970543312916953797725147236788194753028392315324443174570830615125671259032722623306377422715975845851680523950668625785918983223206026741725783938336177551639158879830414614871462138318140531932321841017463464628021089100932415123046370526284572036977341860036712378364039250868585426479833669689801482577147
e = 65537
c = 1420515665868581596940839803363950617909765271157014931946210051898436055113441042059150620385341022060755816183000424771452783690046953226457156301983913192455623601540481706661522862559348925062934344162580531535464528754543447377064964651190504954974380681579617753474952167222143347357809943679934361478600911873350650280141291550434021788309056194537934961289615617918196612413794338992167853525086525213136852210782909539899505364113978261766537134423857173
 
p, q = fermat_factor(n)
phi = (p-1)*(q-1)
 
d = mul_inv(e, phi)
plain = pow(c, d, n)
 
print("p :" + str(p))
print("q :" + str(q))
print("p/q :" +str(p/float(q)))

 

Fermat's factorization 공격 코드는 구글 검색으로 쉽게 구할 수 있다.

 

n, e, c 부분만 바꿔서 코드를 실행시켜주면 된다.

 

 

코드를 실행시키면 이렇게 단숨에 p 와 q값을 구해준다.

 

두 값이 아주 근사한 것을 볼 수 있다.

 

 

p와 q값을 알아냈으니 이제

 

./RsaCtfTool.py -n n값 -e e값 --uncipher c값 -p p값 -q q값 으로 옵션을 줘서 도구를 실행시키면 된다.

 

바로 easy_Pr0b 라는 플래그의 두번째 부분이 나온다.

 

 

part3 의 info.txt 가 가장 쉽다.

 

n, e, c 세 값 모두 크지 않기 때문에

 

그냥 바로 RsaCtfTool 을 돌려버리면 된다.

 

 

./RsaCtfTool.py -n n값 -e e값 --uncipher c값 넣고 돌리면

 

_right?_ 라고 플래그의 세번째 부분이 나오게 된다.

 

출력되는 로그를 보면 factordb 방법을 이용해 공격이 성공했다고 한다.

 

 

마지막 part4의 info.txt 이다.

 

특징적으로 e 값이 다른 info.txt 에 비해 작은것을 알 수 있는데

 

e 값이 작으면 낮은 지수 공격이 가능하다.

 

from gmpy2 import *

c = 340367453566526244883416366790127360372520168777999761070900847701270609351400962281351434533034967316847055272775676939065383028659076554177750307491028686884533788664296203682181434792205639992309882796702809465905356563917406628983692069596031529856791681039538144770106671291836348496625243238930819952442684845581191075702475185206016200328470477746200079326823877615352496854633406849989425132712166830335768477614367877648666677

with local_context() as ctx:
	ctx.precision = 3000
	m = iroot(c,23)[0]
	
	print(bytes.fromhex('%x' % int(m)))

 

RsaCtfTool 을 안쓰고도 풀 수 있다.

 

gmpy2 모듈을 이용해서 제곱근을 계산해주면 된다.

 

iroot(c, 23) 이라고 되어있는 부분은 c의 23제곱근을 계산하는 부분이다.

 

사실 보통 낮은 지수 공격 문제가 나오면 e 값을 3정도로 주는데

 

혹시 23도 될까 싶어서 해봤더니 생각보다 빠르게 계산이 됐다.

 

 

코드를 실행시키면 left_gg} 라는 플래그의 마지막 부분을 얻을 수 있다.

 

지금까지 찾은 플래그를 모두 합친

 

CCE{Easy_Peasy_Pr0b_right?_left_gg} 이 이번문제의 플래그였다.