[CTFlearn] RSA Noob - 암호학

 

CTFlearn 의 서른두번째 문제

 

이번엔 암호학 문제이다.

 

문제 제목처럼 RSA 암호 알고리즘에 관한 문제인데

 

풀어보면 이게 무슨 RSA 문제인가.. 싶을정도로 황당하다.

 

반응형

 

 

문제에서 주어진 주소로 접속하면 텍스트 파일을 하나 받을 수 있다.

 

e: 1
c:9327565722767258308650643213344542404592011161659991421
n: 245841236512478852752909734912575581815967630033049838269083

 

텍스트 파일의 내용은 위와 같다.

 

보통 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를 공개한다.(이 둘이 공개키)

 

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

 

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

 

이 문제에서는 n과 e가 공개키 쌍이고, c는 암호문이다.

 

그런데 보면 e값이 1로 아주 작은 값이다.

 

RSA 암호 알고리즘에서 e값이 작을 경우 낮은 지수 공격이 가능하다.

 

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

 

여긴 더 쉽게 그냥 1로 줘버렸다..

 

e값이 1이라는건 그냥 평문이라는 뜻이다..

 

c = 9327565722767258308650643213344542404592011161659991421
print ('%x' % int(c))

 

문제 푸는데 복잡한 코드도 필요없다.

 

이렇게 파이썬으로 딱 두줄만 쓰면 된다.

 

암호문 값인 c를 가져와서 16진수로 출력시켜주면 끝이다.

 

 

실행시키면 이렇게 16진수 값이 출력되는데

 

 

출력된 값을 CyberChef(https://gchq.github.io/CyberChef)에서 Hex 디코딩해주면 플래그가 나온다.