[CTFlearn] CoppeRSA Lattice - 암호학 / RsaCtfTool

 

CTFlearn 의 여든한번째 문제

 

이번엔 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 과 c 를 생성하는 파이썬 코드가 같이 주어진다.

 

문제 제목에 있는 coppe 라는 단어에 힌트를 얻어서 구글에 검색해보니

 

RSA Coppersmith's attack 가 있다는 것을 알아냈다.

 

 

ChatGPT 에게 Coppersimth's attack 가 뭔지 물어봤다.

 

결론적으로 n = pq 에서 p와 q의 차이가 작을경우

 

c = m^e mod n 에서 m 을 찾을 수 있다는 것이다.

 

문제 코드를 다시한번 보자

 

base = random.getrandbits(2048)
p = next_prime(base + random.getrandbits(256))
q = next_prime(base + random.getrandbits(256))

 

 

 

p 와 q 를 생성할때 랜덤한 값으로 생성을 하는데

 

base 라는것을 2048 비트를 똑같이 두고, 

 

그 뒤에 256 비트만 랜덤으로 다시 생성해 추가하여 차이를 만든다.

 

이 부분에서 p 와 q 의 차이가 작다는 것을 알 수 있다.

 

c = power_mod(m, e, n)

 

이 부분이 방금 ChatCPT 에서 언급한

 

c = m^e mod n 를 의미한다.

 

이러면 이제 대충 Coppersimth's attack 을 할 수 있을것 같다.

 

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값 으로 옵션을 넣어주면

 

툴이 계산을 시작한다.

 

잠시 기다리면 아래 플래그가 나온다.

 

어.. 근데 출력된 문구를 보면 Coppersimth's attack 가 아니라

 

factordb method 로 공격을 성공했다고 한다.

 

 

factordb 는 이런것이다.