천천히.. 느리게.. 될때까지.. |

RSA 암호와 그 원리

샤미르, 리베스트,

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

$m = c^d \mod{n}.$

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

$c^d \equiv (m^e)^d \equiv m^{ed}\pmod{n}$

가 된다. 또한

$e d \equiv 1\pmod{(p - 1)(q - 1)}$

이므로,

$e d \equiv 1\pmod{p - 1}\,$; $e d \equiv 1\pmod{q - 1}\,$
로 분해 가능하다. 위 식을 변형시킨다면,: $e d = k (p - 1) + 1\,$; $e d = h (q - 1) + 1\,$

로 나타낼 수 있다. 이 때, m 이 p 의 배수가 아니라면 m 과 p 는 서로소 이다. 왜냐하면 p 가 소수이기 때문이다. 따라서 페르마 소정리의 의해 다음이 성립한다.
: $m^{(p-1)} \equiv 1 \pmod{p}$
따라서 원래 식은 다음과 같이 바뀔 수 있다.: $m^{ed} = m^{k (p-1) + 1} = (m^{p-1})^k m \equiv {1}^k m = m \pmod{p}\,$

참고로 만약 m 이 p 의 배수여도 위 식이 성립한다. 왜냐하면
$m^{ed} \equiv 0^{ed} = 0 \equiv m \pmod{p}$

이기 때문이다. 똑같은 방법으로 q 에 대해서도 보일 수 있다.: $m^{ed} \equiv m \pmod{q}\,$

이 때, p 와 q 는 모두 소수이고 p, q 각각 $m e d - m$ 을 나누기 때문에 다음과 같은 결론을 내릴 수 있다.: $m^{ed} \equiv m \pmod{pq}$

따라서: $c^d \equiv m \pmod{n}$

가 성립한다.

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

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

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

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

$c = 123^{17}\mod {3233} = 855.$

이 때 c 를 받은 밥은 비밀키 d=2753을 통해 해독할 수 있다.: $m = 855^{2753}\mod {3233} = 123$

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

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

티스토리 툴바