HSOC 교내 해킹방어대회 문제 출제 후기 및 50점 문제 writeup

저저번주 금요일(9/23)에 교내 해킹방어대회가 열렸다. hsoc 동아리 부원들이 문제를 출제하고 운영하는 대회이며 나같은 경우 이번에 씨텦 문제도 첨 만들어봐서 어려움을 좀 겪었다. 현재 hsoc의 암호학 분야에 속해있기 때문에 총 3문제를 만들었고 50, 100, 200점으로 최대한 다양하게 만들었다.
 
솔직히 문제를 만들기 전에는 3일 정도면 문제를 다 만들고도 남을줄 알았다..ㅎ 어림도 없었다. 생각보다 문제를 만드는데 처음에 내가 만들고자 했던것과 다르게 흘러가는 경우가 많았고 만들고보니까 너무 쉽게 만들어진 경우가 많아서 몇번을 갈아엎었는지 모르겠다.
안그래도 시간이 없는데 계속 갈아엎고 다시 만드느라 나중에는 라잇업이랑 열려있는 대회 사이트 여기저기에 다 들어가보면서 새로운 문제 유형을 계속 찾아봤던 것 같다. 그래서 아마 문제들을 보면 다른 대회에서 한번쯤은 나온 유형의 문제다,, 교외대회가 아닌 교내대회라 그나마 다행이라 해야할까... 암튼 좀 질좋은 문제를 만들어보고싶었는데 그닥 만족스럽지는 않다.
 
근데 당일날 대회를 진행하다보니 50, 100점 문제를 푼 사람이 많이 없어서 150, 200점 문제는 공개하지도 못했다.
그래도 이번에 문제를 출제하면서 새로운 문제 유형도 진짜 많이 보고 심도있게 공부할 수 있어서 유익하고 좋았다. 다음에 중학생 대상으로 하는 교외대회에서는 기간을 좀 넉넉하게 잡고 문제를 푸는분들이 알차고 질좋다고 느낄만한 문제를 출제하고싶다. 또 시간이 좀 남는다면 크립토 외에 다른 분야 문제도 공부해보고 출제해보고 싶다. 
 
마지막으로 평일날 학교 끝나고 짧은시간 동안 진행했던 대회인데도 불구하고 끝까지 열심히 풀어주신 참가자분들께 너무 감사하고 계속 학교에 남아서 같이 문제를 출제했던 동아리 부원분들과 외부 강사님들께도 진짜 감사하다는 말씀드리고싶다. (특히 대회의 전반적인 부분들을 진행/운영해주신 선배님들 넘 감사드리고 존경합니다..)
 

easy RSA - 50점

대표적인 공개키 알고리즘인 RSA를 활용한 문제이다.

<시나리오>
한세가 비밀 문서를 보기 위해 잠금을 해제하려고 노력하고 있다. 노트북에 e, c, p, q 4개의 파일이 있다.
파일을 보니 안에 알 수 없는 숫자들이 있어서 메모장에 메모를 해 놓았다. 이 메모를 활용하여 잠금을 해제할 수 있을 것 같다.

from Crypto.Util.number import *

e = 257

p = getPrime(1024) 
q = getPrime(1024) 
n = p * q

flag = b"HSOC{????????????}"
c = pow(bytes_to_long(flag), e, n)

print(f"e = {e}")
print(f"c = {c}")
print(f"p = {p}")
print(f"q = {q}")

e = 257
c = 5170614309301223184388980439033937972958595751713320965808860175588790115219381694288306180451949710261512480304973718112228889626940113529439227149734487012037630024859786546305225093967154391890149077265714446582747768706411436149671496479109814775690406008776885497246411111989054712865047658076549493437166223452452855195649368804859350881162375200684571102147323943146082552216356213851098024600173550937621944196190441066471923633389014705391050788386027507663015531178749441167149946800122899769099206880827114130951143393000212588720045757847160070434793928195140628142207776720680351969286852634379093267395
p = 121082940632566084365045468274080389844245747988255783680486430339285622475938449072789554464746638386992904689290579744213300917014736134613903560443148772127353839823710670680986528534128280877375044770611360109829049475842435278969303947209412658556907276581778492754960030258658453902050691012787944153029
q = 93773260875800805924403007041088524372825300383500367049104233796459989047050929611151854646094506486446127494624906576319038878918384371070507039400233234869045356878874646585055502928435133167377331216852702026481058788799943840756755689058510106076276525924408876911194766461521214272472920976958554265097

위처럼 python 파일 하나와 txt 파일을 문제파일로 제공해주었다.
 
1. 문제를 보면 e, c, p, q 4개의 값이 주어졌는데 이는 각각 공개키, 암호문, 두 소수를 나타낸다.
우리가 구하고자 하는것은 플래그값인 M(평문)인데, 이를 구하기 위해서는 개인키인 d와 N이 필요하다.
참고로 마지막 식에서 N이 아닌 Φ(N)을 법으로 둔 이유는 지수들이 Zn*의 원소 자체가 아니고 원소의 색인으로 작용하기 때문이라 한다. (이제부터 Φ(N)을 phi라 하겠음)
위 식에 따라서 phi를 아는 공격자는 e의 역원을 계산해서 d를 쉽게 유도할 수 있고 그렇게 때문에 p와 q가 노출되면 안된다.
phi = (p-1)*(q-1)이기 때문이다.
 
2. 주어진 문제에서는 p와 q가 주어졌기 때문에 이 값을 통해서 phi를 구할 수 있다. 주어진 p, q를 통해 N 또한 구할 수 있다.
구한 phi와 주어진 e를 이용하여 mod의 역원을 계산하여 d를 구할 수 있다.
M을 구하는데 필요한 요소인 c, d, n을 통해 평문을 얻어낼 수 있다.
 
3. 최종적으로 코드를 작성해보면 아래와 같다.

from gmpy2 import *

p = 121082940632566084365045468274080389844245747988255783680486430339285622475938449072789554464746638386992904689290579744213300917014736134613903560443148772127353839823710670680986528534128280877375044770611360109829049475842435278969303947209412658556907276581778492754960030258658453902050691012787944153029
q = 93773260875800805924403007041088524372825300383500367049104233796459989047050929611151854646094506486446127494624906576319038878918384371070507039400233234869045356878874646585055502928435133167377331216852702026481058788799943840756755689058510106076276525924408876911194766461521214272472920976958554265097
e = 257
c = 5170614309301223184388980439033937972958595751713320965808860175588790115219381694288306180451949710261512480304973718112228889626940113529439227149734487012037630024859786546305225093967154391890149077265714446582747768706411436149671496479109814775690406008776885497246411111989054712865047658076549493437166223452452855195649368804859350881162375200684571102147323943146082552216356213851098024600173550937621944196190441066471923633389014705391050788386027507663015531178749441167149946800122899769099206880827114130951143393000212588720045757847160070434793928195140628142207776720680351969286852634379093267395

n = p * q
phi = (p-1) * (q-1)
d = invert(e, phi) # d = divm(1, e, phi)

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

#출력결과: 48534f437b495f406d5f68756e6772797d

m = '48534f437b495f406d5f68756e6772797d'
print(bytes.fromhex(m))

#출력결과: HSOC{I_@m_hungry}

구한 요소들을 RSA 복호화 사이트에 넣어도 평문이 정상적으로 나온다.
flag: HSOC{I_@m_hungry}