[angstromCTF] Reasonably Strong Algorithm - 암호학 / RSA

암호학 문제이다. 

 

문제 이름이 Reasonably Strong Algorithm 인데 맨 앞글자만 따면 R S A 가 된다.

 

RSA는 지금까지도 아주 많이 사용하는 공개키 알고리즘의 이름이다. 

 

개발자인 Rivest, Shamir, Adleman 세명의 이름 앞글자를 따서 RSA 라고 이름을 붙인 알고리즘이다.

 

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 라는 변수에 각각 숫자가 들어있는것을 볼 수 있다.

 

여기서 n, e 는 위에서 본것처럼 공개키를 의미한다.

 

c는 cipher text의 약자로 암호문이다. 아마 위에있는 공개키로 어떤 문자열을 암호화한 값일 것이다.

 

원래는 개인키로만 이것을 해독할 수 있지만, n의 크기가 작은것을 보니 crack 할 수 있을듯 하다.

 

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

 

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

 

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

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

 

사용법은 아주 간단한다.

 

python RsaCtfTool.py -n n값 -e e값 --uncipher c값

 

이렇게 옵션을 줘서 해당하는 값들을 넣어주면 된다.

 

그럼 아래쪽에 Clear text : 라고하면서 해독된 플래그가 보이게 된다.