RSA 암호화는 공개 키 암호화 방식의 대표적인 예로, 수학적으로 큰 숫자의 소인수분해가 어려움을 기반으로 만들어 졌다.
그러므로 큰 수의 소인수분해를 획기적으로 빠르게 할 수 있는 알고리즘이 발견된다면 이 암호 체계는 가치가 떨어질 것이다. 실제로 양자컴퓨터는 다항 시간 내에 소인수 분해를 진행할 수 있다. 만약 양자컴퓨터가 본격적으로 실용화 된다면 RSA 알고리즘은 무용지물이 될 것이다.
RSA 방식
RSA는 두개의 키를 사용한다. 일반적으로 많은 공개키 알고리즘의 공개키(public key)는 모두에게 알려져 있으며 메시지를 암호화(encrypt)하는데 쓰이며, 암호화된 메시지는 개인키(private key)를 가진 자만이 복호화(decrypt)하여 열어볼 수 있다.
키의 생성
p와 q라고 하는 두개의 서로다른 소수를 고른다 ( p != q )
-
두 수를 곱하여 N = pq를 구한다.
-
phi(N) = (p - 1) * (q - 1) 을 구한다.
-
phi(N) 보다 작고, phi(N)과 서로소인 정수 e를 찾는다.
-
( d * e ) % phi(N) = 1 인 정수 d를 구한다.
암호화
암호 메시지 C = m^e mod N 이다.
이때 m은 메시지(평문) 이고, C는 암호문 이다.
복호화
만약 위의 C와 N 과 d를 알고 있다면, 식을 통해 m을 찾을 수 있다.
m = c^d mod N이다.
워게임 문제 및 풀이 ( safeprime )
문제 파일이 주어진다.
RSA의 알고리즘이 담겨있고, p는 정해져 있어, 누구나 알 수 있는 상태이다. 즉 p를 통해 q를 계산해낼 수 있다.
주어진 것은 N 과 e, 그리고 FLAG1_enc이다.
여기서 우리가 구해야 하는 것은 FLAG이다.
FLAG는 M(평문) 이고, FLAG_enc는 C(암호문)이다.
복호화를 위해 C^d mod N 을 구해아 하며, 이 떄 키의 생성과정에서 d가 필요하다.
d를 구하기 위해서는 p와 q를 알아야 한다.
이제 복호화를 진행해 보겠다.
복호화 코드를 작성하였다.
p1, q1을 계산해내고, (p-1)*(q-1) 을 계산하여 phi(N)을 구한다.
그리고 우리가 알아야 하는 d는 확장 유클리드 호제법을 이용하여 모듈로 역원을 통해 구한다. 라이브러리의 inverse 함수를 이용하였다.
d를 계산해냈으면 이제 복호화 과정을 수행한다.
결과는 다음과 같고 합쳐서 FLAG를 구하였다.
DH{50aca6c6db15b053c23987a46746afff79cd09cbc77e6ce4a645e46b84d76cf2}
