RSA 암호와 그 원리

RSA 암호와 그 원리

샤미르, 리베스트,

  '암호학(Cryptography)의 모든 것' 에서 RSA 암호에 대해 간략하게 설명한 바 있다. RSA 암호는 공개키 암호(Public-key cryptography) 의 한 종류로 '큰 정수의 소인수분해의 난해성' 을 기초로 한 암호다.  이 암호는 1977년에 MIT 에서 리베스트(Ronald Rivest), 샤미르(Adi Shamir), 애들만(Leonard Adleman) 이 개발하였으며 그들 이름의 머리글자를 따서 RSA 암호라 이름 붙였다. 원래 영국 정보통신 사령부(GCHQ) 에 소속된 콕스(Clifford Cocks) 가 1973년에 동일한 시스템을 개발하였으나 이를 계산할만한 컴퓨터가 없어서 비록 주목은 받았으나 이용되지는 못하였다. 콕스의 발견은 1997년 까지 일급 기밀에 속해 있어서 세상에 알려지지 못하였다.

  RSA 암호는 2개의 키를 필요로 한다. 하나는 공개키 이고 하나는 개인키 인데, 메세지는 공개키를 통해 암호화 되고 오직 개인키를 통해 복호화 될 수 있다. RSA 알고리즘을 통한 키 생성은 다음과 같다.

•   먼저, 무작위로 큰 두 소수 p 와 q 를 고른다.

•   이 때, 를 통해 n 값을 계산한다.
•   또한, n 이하의 n 과 서로소인 수들의 개수 인 를  계산한다.
•   세번째로, 1 < e < φ(n), 이고 e 와 φ(n) 가 서로소인 e 를 선택한다.
•   마지막으로 를 만족하는 d 를 계산한다. 즉, 임의의   정수   k 에 대해서 다음을 만족할 것이다. de = 1 + kφ(n)

  이제 부호화 할 준비는 끝났다. 이 때 (n,e) 는 공개키 이고, d 는 개인키 이다. 또한 숫자 p,q 도 매우 중요하기 때문에 공개키와 개인키의 생성이 끝난다면 곧바로 지워버리는 것이 상책이다.

부호화 과정

  만약 앨리스(Alice)가 밥(Bob)에게 어떠한 메세지 M 을 보내려고 한다고 하자. 그렇다면 앨리스와 밥이 서로 알고있는 변환법(Padding scheme) 을 통해 M 을 m<n 인 m 으로 변환한다. 또한 밥은 앨리스에게 공개키인 n 과 e 를 알려준다. (이 공개키는 제 3자가 가로채도 안전하다.) 이 때 앨리스는 다음을 계산한 c 를 보내면 된다.

복호화 과정

 밥은 앨리스로 부터 c 를 받았다. 이 때 밥은 그 만이 알고있는 개인키 d 를 이용해 다음과 같은 작업을 통해 c 로 부터 m 을 해독해 낼 수 있다.

이 때, m 으로 부터 변환법에 따라 역으로 해준다면 M 을 알 수 있을 것이다.
여기서 위의 식이 성립하는 이유는 다음과 같다.
일단 위의 식에서

가 된다. 또한

이므로,

로 분해 가능하다. 위 식을 변형시킨다면,

로 나타낼 수 있다. 이 때, m 이 p 의 배수가 아니라면 m 과 p 는 서로소 이다. 왜냐하면 p 가 소수이기 때문이다. 따라서 페르마 소정리의 의해 다음이 성립한다.

 

따라서 원래 식은 다음과 같이 바뀔 수 있다.

참고로 만약 m 이 p 의 배수여도 위 식이 성립한다. 왜냐하면

 

이기 때문이다.
똑같은 방법으로 q 에 대해서도 보일 수 있다.

이 때, p 와 q 는 모두 소수이고 p, q 각각 m^ed − m 을 나누기 때문에 다음과 같은 결론을 내릴 수 있다.

따라서

가 성립한다.

실제로 RSA 암호를 이용해 보자.

• 두 소수 p=61, q=53 으로 정한다.
  
• 에서 n = 61 * 53 = 3233 으로 계산한다.
  
• 또한 n 이하의  n 과 서로소인 수들의 개수인 φ(n) 을  계산한다.
  
  

• 3120 과 서로소인 e 를 고른다. 이 때 e=17 이라 하자.
• 마지막으로  아래 식을 만족하는 d 를 계산하자.  이  때, d=2753 이라 하자.
  

이 때 m=123 을 암호화 하기 위해 n 과 e 를 이용해 계산해 보면

이 때 c 를 받은 밥은 비밀키 d=2753을 통해 해독할 수 있다.

  만약 제 3자가 n 을 알고있더라 해도 n 을 소인수분해 하지 못한다면 p,q 를 알 수 없다. 따라서 비밀키 d  는 안전하게 보관될 수 있다. 그러나 p,q 를 알아낸다면 d 를 손쉽게 알아 낼 수 있으므로 곧 암호는 뚤리게 된다. 따라서 보통 RSA 암호 키는 1024비트(2진수로 나타냈을 때, 1024자리란 뜻) 정도의 길이를 가지며 이를 푸는데는 수십년은 족히 걸린다.

  1994년에 쇼어(Peter Shor) 가 쇼어의 알고리즘을 통해서 양자컴퓨터는 정수의 소인수분해를 다항시간 내에(polynomial time, 문제를 해결하는데 걸리는 시간함수가 다항함수 이하로 정해지는 경우) 할 수 있어 RSA 암호를 무용지물화 만들 수 있음을 보였다. 그러나 양자 컴퓨터는 아직 개발단계(2001년 IBM 서 15 의 소인수분해를 할 정도)에 머물러 있으며 실용화 되려도 오랜 시간이 걸릴 것으로 보인다.