[CTFlearn] RSA Twins! - 암호학 / RsaCtfTool

 

CTFlearn의 예순 일곱번째 문제

 

이번엔 암호학 카테고리의 RSA 문제이다.

 

Hard 로 분류되어 있어서 살짝 쫄았는데 그렇게 어렵지 않게 풀 수 있다.

 

반응형

 

문제 제목에 나온것 처럼 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 = 14783703403657671882600600446061886156235531325852194800287001788765221084107631153330658325830443132164971084137462046607458019775851952933254941568056899

e = 65537

c = 684151956678815994103733261966890872908254340972007896833477109225858676207046453897176861126186570268646592844185948487733725335274498844684380516667587

 

문제에서 주어지는 값은 위와 같다.

 

RSA 문제를 풀때 github에 보면 RsaCtfTool 이라는 좋은 도구가있다. 

 

 

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

 

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

 

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

 

 

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

 

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

 

 

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

 

 

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

 

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

 

 

./RsaCtfTool.py -n n값 -e e값 --uncipher c값 으로 옵션을 넣어주면

 

툴이 계산을 시작한다.

 

 

잠시 기다리면 평문으로 된 플래그를 찾을 수 있다.

 

 

리눅스 환경이 불편하다면 Dcode(https://www.dcode.fr/rsa-cipher) 사이트에서도 가능하다.

 

이렇게 주어진 입력값을 넣고 DECRYPT 버튼을 눌러주면

 

 

플래그를 찾을 수 있다.