[b01lers CTF] Clear the Mind - 암호학 / RSA / Python

 

쉬운 RSA 문제

 

2020CCE 대회가 끝나고 이 문제를 풀었는데

 

CCE 에서 나왔던 문제 유형과 아주 비슷한 문제여서 금방 풀었다.

(https://hackingstudypad.tistory.com/315)

 

반응형

 

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 = 102346477809188164149666237875831487276093753138581452189150581288274762371458335130208782251999067431416740623801548745068435494069196452555130488551392351521104832433338347876647247145940791496418976816678614449219476252610877509106424219285651012126290668046420434492850711642394317803367090778362049205437

c = 4458558515804625757984145622008292910146092770232527464448604606202639682157127059968851563875246010604577447368616002300477986613082254856311395681221546841526780960776842385163089662821

e = 3

 

문제에서 제공되는 clearthemind.txt 파일의 내용은 위와 같다.

 

딱 보자마자 느낀게

 

e 값이 3으로 매우 작다.

 

이럴 경우 낮은 지수 공격이 가능해진다.

 

보통 CTF에서 RSA 문제를 풀때 RsaCtfTool 이라는 도구를 많이 사용하지만

 

e 값이 작은 경우 해당 도구를 사용할 필요 없이

 

간단한 파이썬 코드만 짜면 된다.

 

from gmpy2 import *

c = 4458558515804625757984145622008292910146092770232527464448604606202639682157127059968851563875246010604577447368616002300477986613082254856311395681221546841526780960776842385163089662821

with local_context() as ctx:
	ctx.precision = 3000
	m = iroot(c,3)[0]
	
	print(bytes.fromhex('%x' % int(m)))

 

gmpy2 모듈을 이용해서 제곱근을 계산해주면 된다.

 

iroot(c, 3) 이라고 되어있는 부분은 c의 세제곱근을 계산하는 부분이다.

 

이렇게 하면 RsaCtfTool 을 쓰지 않고도 문제를 풀 수 있다.

 

 

코드를 실행시키면 플래그가 출력된다.

 

we need to go deeper... 더 어려운 문제가 나올거라는 암시인듯하다.