[퍼즐] 잘못된 주소 또는 엉뚱한 모자 문제

여기에 5개의 목적지가 다른 편지와 각각의 주소가 적힌 편지 봉투 5개가 있다.
실수로 모든 편지를 잘못된 주소로 보낼 경우의 수는 몇인가?

변형된 다른 문제는 7개의 모자와 7명의 모자 주인이 있는데, 모든 모자 주인들이
엉뚱한 모자를 가져갈 경우의 수는 몇인가?

이 문제를 처음 접한 지는 꽤 되었는데,
이것에 교란순열(derangement)이라는 수학용어가 있었다.
(예를 들어 n개가 모두 잘못된 위치로 놓이는 방법은 !n 으로  쓴다.)

이 문제의 답을 스스로 생각해 내는 것은 항상 헷갈린다.

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 이 수백자리수가 되면 더욱 어려울 것이다.