RSA 암호

최근에 읽은 책중에 <침팬지도 이해하는 5분 수학>(? 제목이 정확하진 않지만 비슷할 것같다.)이 있다. 여러가지 수학에 관한 짧은 칼럼들을 모아놓은 것인데 그 중에 RSA 암호 체계에 관한 글이 있었다. 간단히 설명하면, 현재의 대분의 공개키 암호체계의 기본이 되는 것으로 페르마의 소정리를 이용하는 것이다.

일단, 페르마의 소정리란
(1) n 이 소수이고, 1<k<n-1 인 k 에 대해,
 
     k^{n-1} mod n =1
 
     이다.
     ( 비슷하게 k^n mod n =k )
     예를 들어 n=7, k=5 라면,  5^{7-1} mod 7 = 1

(2) 한 단계 더 일반화 시키면,
     임의의 정수 n 에 대해, 1<k<n 이고 n 과 서로소인 k 가 있을 때,
     n 보다 작으면서 1 또는 n과  서로소인 수의 개수를 phi(n) 이라고 하면,
   
     k^(phi(n)) mod n =1

     이다.
     n 이 소수이면 phi(n)=n-1  이 되어 (1) 과 같아진다.
     예를 들어 n=10, k=7 , phi(10)=4 (즉, 9,7,3,1) 이고
        7^4 mod 10 =  1

 이제 RSA 암호를 보자.  이 경우 등장하는 수는 p, q, L, n, k 인데, 각각은
   p, q : 서로다른 큰 소수
   n     : p, q의 곱 n=p * q
   k , L  : 다음 관계를 만족하는 두 수
            (k*L) mod phi(n)=1
            여기서, phi(n)=(p-1)*(q-1) 이다.
   이 중  p, q , L은 비밀로 하고 n과 k는 공개한다.
(1) 암호화 : 먼저 메세지를 숫자 m 이라고 하자. 그러면, 암호문은
                 r= m^k mod n
                 으로 구해진다. 즉, 이 경우 알려진 n과 k를 이용하므로
                 누구나 암호화할 수 있다.

(2) 해독 : 받은 암호문으로 부터
               r^L mod n =m
               을 계산하여 메세지 m 을 얻는다.

               이 과정이 페르마의 소정리를 이용한 것이다.
                 r^L mod n = (m^k)^L mod n = m^(k*L) mod n
                                 = m^( s*phi(n)+1 ) mod n
                                 = m* (m^phi(n))^s mod n
                                 = m mod n = m

               따라서, 해독은 L 을 알아야만 할 수 있다. ( p, q 자체는 몰라도 됨.)
           
만약  누군가가 알려진 n 과 k 로부터 L을 계산할 수 있다면,
암호가 풀리게 된다.

쉬울까?
예를 들어 n=2773, k=17 이 알려져 있다고 하자. 이 경우 해야 할 일은
먼저 2773과 서로소인 수의 개수 phi(2773) 을 구하고 (이 부분이 어렵다),
17*L mod phi(2773) =1 이 되는 수 L을 구하는 것이다.
문제는 이미 p=47, q=59를 알고 있는 경우에는 phi(2773)=2668 임을 알 수 있지만,
p와 q를 모를 경우 phi(2773)을 구하기는
쉽지 않다는 것이다. 특히 만약 n 이 수백자리수가 되면 더욱 어려울 것이다.