이번에 RSA를 공부해 볼 일이 생겨서 Short RSA를 깨는 방법에 대해서 찾아봤다.
시작하기 전에 용어에 대해서 잠깐만 짚고 가자면
p, q : 두 소수
n : p * q
phi : (p - 1) * (q - 1)
e : phi와 서로소인 수
d : e * d % phi가 1인 값
m : 원문
c : 암호문
이렇게 된다. m에서 c로 암호화 하는 과정은 c = m ** e % n이고 c에서 m으로 복호화하는 과정은 m = c ** e % n이 된다.
여기서 우리는 먼저 n과 e가 주어져야 한다. 그리고 n을 소인수분해하여 두 소수 p, q를 구해내야 한다. 이 과정이 되지 않으면 절대 다음 과정으로 넘어갈 수 없다.
p, q를 구하는 과정은 대체적으로 먼저 n의 제곱근을 구한 후에 그 제곱근 근처의 소수들로 구할 수 있다. 물론 대체적으로 이런 것이지 이러한 방식으로 되지 않을 때는 브루트포싱을 하면 된다.
쨌든 구한 p, q로 phi를 구하고 난 뒤에 d를 구해야 한다. d는
d = e ** -1 % phi 로 구할 수 있으며 이 원리에 대해서는 공부를 좀 더 해야 알 것 같다. 이렇게 구한 d를 이용하여 최종적으로 암호문 c를 복호화하여 m을 구할 수 있다.
더 다양한 자료는 http://www.members.tripod.com/irish_ronan/rsa/attacks.html