[DwagCTF] Left Foot Two Stomps - 암호학 / RSA

 

암호학 문제

 

대회가 끝나고 풀어서 캡쳐가 조금 부족하다.

 

n=960242069 e=347 c=346046109,295161774,616062960,790750242,259677897,945606673,321883599,625021022,731220302,556994500,118512782,843462311, 321883599,202294479,725148418,725148418,636253020,70699533,475241234,530533280,860892522,530533280,657690757,110489031,271790171,221180981,221180981,278854535,202294479,231979042,725148418,787183046,346046109,657690757,530533280,770057231,271790171,584652061,405302860,137112544,137112544,851931432,118512782,683778547,616062960,508395428,271790171,185391473,923405109,227720616,563542899,770121847,185391473,546341739,851931432,657690757,851931432,284629213,289862692,788320338,770057231,770121847

 

문제에서는 위처럼 숫자들이 주어지게 된다.

 

n, e, c 라는 변수에 각각 숫자들이 들어가 있는게 보이는데

 

CTF 문제에서 이렇게 n, e, c가 주어지면 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를 공개한다.(이 둘이 공개키)

 

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

 

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

 

CTF 문제를 풀때는 내가 직접 코딩해서 풀어도 좋지만

 

남이 만든거 가져와서 푸는게 빠르고 편리하다.

 

github에 보면 RsaCtfTool 이라는 좋은 도구가있다. 최근까지도 계속 업데이트 하고 있는듯 하다.

주소 : https://github.com/Ganapati/RsaCtfTool

 

 

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

 

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

 

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

 

 

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

 

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

 

 

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

 

 

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

 

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

 

python3 ./RsaCtfTool.py -n n값 -e e값 --uncipher c값들

 

 

툴을 실행시키면 이렇게 결과가 나오는데 

 

아래쪽 Unciphered data: 아래쪽이 해독된 데이터이다.

 

그런데 한글자씩 각각 디코딩을 해줘서 너무 가독성이 떨어진다.

 

저기 있는 출력값 종류중에 하나만 골라서 다 모아주기만 하면 된다.

 

utf-8로 모아서 풀어보자.

 

 

다시한번 실행시켜서 결과값을 output 이라는 파일로 모아준다.

 

f = open('output','r')

string = ''

for i in range(1000):
    line = f.readline()

    if 'utf-8' in line:
        string += line[16:17]

print(string)

 

파이썬으로 간단하게 utf-8 값을 추출할 수 있다.

 

open 으로 파일을 열어서 readline()으로 한줄씩 읽은 뒤에

 

utf-8 이라는 문자가 나올때마다 하나씩 글자를 모아주기만 하면 된다.

 

xhBQCUIcbPf7IN88AT9FDFsqEOOjNM8uxsFrEJZRRifKB1E=|key=visionary

 

코드를 실행시키면 이렇게 출력이 된다.

 

뭔가 인코딩된 값이 나오고, 뒤에는 key=visionary 라는 문자가 보인다.

 

visionary 발음이 뭔가 vigenere 와 비슷한거 같아서 

 

아마도 Vigenere 암호의 key를 의미하는게 아닐까 생각했다.

 

참고로 Vigenere 암호는 프랑스 외교관 블레즈 드 비제네르가 개발한 암호이다.

 

시저 암호보다 진화된 형태라고 생각하면 된다.

 

 

Cyberchef(https://gchq.github.io/CyberChef)에서 Vigenere 암호도 디코딩이 가능하다.

 

이렇게 visionary를 키로 입력해주면 출력값이 나오게 된다.

 

출력값 맨 뒤에 보면 '=' 이 있는걸 볼 수 있는데

 

= 이 있다면 base64로 인코딩 되었을 확률이 높다.

 

 

base64로 디코딩을 해본다.

 

출력값을 보면 이번에는 ROT 라는 문자가 보인다.

 

ROT 는 rotate의 줄임말로 시저 암호의 일종이라고 보면 된다.

 

ROT가 써있으니 ROT로 디코딩을 시도해본다.

 

 

ROT47을 이용해서 디코딩을 해보면 플래그가 나온다.