[UMDCTF] Low Effort Required - 암호학 / RSA

 

 

RSA와 관련된 암호학 문제였다.

 

사우스 보스턴에 있는 어느 레스토랑에서 public key와 ciphertext를 발견했는데

 

해독할 수 있냐고 물어본다.

 

 

반응형

 

문제파일로 ciphertext, public_key 그리고 encrypt.py 파일이 주어진다.

 

40030182544273856015788999062464973403472186630147528555052489762516210821795493031619376345647069575950526306492922573846162431037037824967074058132327917359025595463728944947118480605422897682821384491771926743103021286982319660969379132360886299787840185308892024028684314873509707776

 

먼저 ciphertext 파일을 열어보면 이런 값이 들어있다.

 

105764039675765007162224197946041421610988226034822789741202355465038405474039844301402146302908742536731331641437484787719599778194205333004482617077526529379473501342486898353691458150850096153562792549383987722885036435071184194348535804171098527517150958992100793020614109813938620093243709325590796177891:5

 

다음으로 public_key의 내용이다.

 

맨 뒤쪽에 보면 :5 라고 써있는데 이건 encrypt.py 파일을 열어보면 무슨뜻인지 알 수 있다.

 

from Crypto.PublicKey import RSA

def encrypt_flag(plaintext_bytes):
    RSAkey = RSA.generate(1024)
    n = getattr(RSAkey.key, 'n')
    e = 5
    plaintext_bytes += b'\x00'
    plaintext = int.from_bytes(plaintext_bytes, 'big')
    ciphertext = pow(plaintext, e, n)
    open('ciphertext', 'w').write(str(ciphertext))
    public_key = str(n) + ":" + str(e)
    open('public_key', 'w').write(public_key)

 

주어진 encrypt.py 파일을 열어보면

 

e 라는 변수에 5라는 값이 들어있는걸 알 수 있다.

 

CTF에서 n, e, c가 주어지면 RSA 문제라고 보면 된다.

 

이 문제의 경우 n은 public_key 파일에서 :5 앞부분, e는 5,  c는 ciphertext 파일의 내용이 된다.

 

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 이라는 좋은 도구가있다. 

 

 

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값

 

 

툴을 실행시키면 이렇게 플래그를 찾을 수 있다.