[System32.kr] RSA101

RSA101

#Crypto #RSA Algorithm #Inverse

---

System32.kr 워게임의 메인컨텐츠로 보이는 Crypto 문제의 서막이다.
RSA 문제 시리즈가 여러가지가 있는데 그에 대한 첫 단추를 꿸 수 있는 문제로 보인다.

이와 동시에 RSA공부도 시작할 수 있을 것 같다.

RSA에 대한 것은 따로 정리하고 문제풀이에 관해서만 핵심적으로 정리하겠다.

우선 문제파일은 paste bin에 올라온 이 텍스트 파일이다.

RSA에 필요한 서로소인 수 p,q 와 공개키 e, 그리고 암호화 된 데이터 c가 들어있다.

여기서 개인키 d를 추출해서 복호화 하면 될 것 같다.

참고로 원래 데이터인 M은 이러한 구조로 복호화 가능하다.

문제풀이를 위해 파이썬 Crypto 모듈을 이용했다. 모듈러 연산 시, 역원을 구하기 위함이다.

from Crypto.Util.number import *
'''
<RSA에서의 KEY>
1. 임의의 두 소수 p,q
2. 1<e<phi && phi와 서로소 관계인 e
3. e*d를 phi로 나눈 나머지가 1이 되는 d
4. n=p*q
공개키 : (n,e)
개인키 : (n,d)
'''
p=11820547749265118607908336189140061659994883367758644383099900753008997316272341754974105712436833864387373302687964986221522289414610698068230842231006759
q=2076478388690715447644222392295584753007140199740835763821170999934221864895193172716587341806099928941239417181782165665806324184552950128351328886814107
e=65537
c=15175007508230661949213125841853820919948368859221761481847700530363990883761097704372435675552656459480039957857925187102590466676354015036181849182155680399350099015532296504916485091012255771133872737687990897080899160898509685794777509104691093814282101492973637294053730555124794841034604131492169339102
# ==== previous condition =======
n=p*q
phi=(p-1)*(q-1)
d=inverse(e,phi)
# e*d mod phi = 1 이 되는 역 d를 구하자.
# 이는 일반적인 대입법 또는 확장된 유클리드 알고리즘으로 도출가능
flag=pow(c,d,n)
# flag = C^d mod n
print(long_to_bytes(flag).decode())

긴 설명 필요없이 결론은 이게 끝이다. 실행시켜보면 플래그가 나올 것이다.

.
.
.
.
contact : a42873410@gmail.com