국가암호공모전 2018 (II-A)분야 10번 문제 풀이

TL;DR

N이 103 decimal digits 로 충분히 작으므로, msieve등의 라이브러리를 이용해 소인수분해하면 풀린다.

 

 

2018년에 국가암호공모전 II-A 암호 문제 풀이 분야에 2명의 학교 후배들과 참가했었다.

그 때 참 많은 일들이 있었지...

 

어쨌든 이 문제는 놀랍게도 우리 팀이 6번(타원 곡선 문제)을 제외한 모든 문제를 풀어갈 때 까지도 감을 못잡았던 문제였다.

문제는 다음과 같다:

1. RSA 암호에 대한 설명

2. 공개키 쌍 N,e 와 암호문 c를 아래 사진과 같이 알려줌

10번 문제에서 제시한 N,e,c

아무튼 이런 문제가 나오면.. 대부분 특정한 취약점을 이용해서 d(개인키)를 구한 이후에 평문을 복구하는 것이 목표가 된다. 

해킹 대회를 하는 사람이면 알겠지만, RSA 관련된 문제는 기존 해킹대회(ctf)에서도 많이 나왔던 형식이다. 예를 들어서 암호문을 RSA 방식을 이용해 encrypt 하는 코드를 적절히 censor해서 첨부하거나, 아니면 그냥 N,e,c 던져주고 응 해독해~ 이런 식이었다.

 

내가 ctf에서 풀었던 문제는 주로 RSA를 이용해 암호화할 때, 특정 parameter를 잘못 선정해 생긴 취약점을 이용하는 방식으로 푸는 것이 많았다. 예를 들어 Wiener's attack이 있다. 이 공격은 e 값이 매우 클 때 사용할 수 있고(근데 e가 N^(1.5)보다 크면 사용할 수 없어요), d가 1/3*N^(0.25) 보다 작을때 공격자가 d를 easy하게 뽑아낼 수 있다.

아? 그런데 지금 보니 문제에서 주어진 e가 매우 크다. 그럼 해당 공격을 쓸 수 있지 않을까? ㅎㅎ

 

하지만 아쉽게도 실패했다. 생각보다 d가 큰가보다. 해당 공격을 시작으로 RSA에서 사용할 수 있는 다양한 공격들을 시도해봤지만 모두 실패하였다. 뭔가 딱봐도 쉬워보이는데 도저히 안풀려서 꽤 오랫동안 답답한 기억이 있다.

계속 노력해도 풀리지 않아서.. 초심으로 돌아가 영문 wikipedia에서 RSA에 대한 설명을 읽던 중 해당 글을 발견했다. 그냥 RSA factoring challenge가 있고 작은 숫자들에 대해서는 factor가 진행되었다. 이게 주 내용이었는데, 문득 생각해보니 N이 엄청 짧았던 것 같다..?! 그래서 N을 다시 제대로 보니 103 decimal digits, 340 bit였던 것이다. 아... 대체 무슨 삽질을?

 

결론적으로, msieve 라는 라이브러리를 이용해 소인수 분해를 진행하였다. 해당 라이브러리는 GMP-ECM, Pollard p-1, William p+1, ECM, Pollard Rho, Quadratic sieve 알고리즘 등을 적용해 자연수에 대해 소인수분해를 하는 기능을 가지고 있다. 

어쨌든 내 2015년형 맥북 에어에서 소인수분해를 돌려놓고 잠들었고, 아침에 일어나서 소인수분해 된 p와 q를 확인할 수 있었다. 해당 값을 이용해 평문 m을 hexdecode한 값을 구하면 "PlainText" 라는 심플한 값이 나온다.

 

RSA에 대한 다른 여러 공격을 찾고 싶으신 분은 구글에 RSA attack이라고 치면 수많은 공격 방법들을 확인하실 수 있습니다. 추가로 msieve에서 소인수분해를 돌린 output 파일을 첨부하였습니다.

msieve.txt

0.01MB

 

 

오늘 글은 여기서 끝!