앞의 포스트에서 디피-헬만 키 교환 알고리즘을 알아보았다.
디피-헬만 알고리즘은 송신자가 주체가 되어 송신자와 수신자 상호간의 암호키 전송없이 실제 송수신할 데이터의 암호화와 복호화를 할 수 있는 공통의 비밀키(대칭키)를 교환(실제로는 송신자와 수신자가 각자 생성)하는 키 교환 알고리즘이다. 그 이후의 데이터 암복호화는 생성된 대칭키(비밀키)를 이용하여 별도의 대칭키 암호화 알고리즘을 사용하면 된다. 그래서 디피-헬만 키 교환 알고리즘은 SSL(Secure Socket Layer) 통신 시 암호키를 생성하고 교환하는 목적으로 사용된다. 또한 SSL 통신 규약 상 주기적으로 암호키를 변경해야하기 때문에 디피헬만 키 교환 알고리즘은 주기적으로 호출된다.
즉, PKI(공개키 암호화 알고리즘)은 아니다.
PKI(Public Key Infrastructure) : 비대칭키 암호 시스템
PKI는 그대로 번역하면 “공개 키 기반구조” 쯤이 된다. 쉽게 “공개키 암호 시스템” 정도로 이해하면 된다. 하지만 이 이름에는 사실 중요한 단어가 빠졌다. “공개키/개인키 암호 시스템” 이 진짜~ 이름이 되겠다. 공개키 암호 시스템은 비대칭키 암호 시스템과 같은 용어다. 암호화 키와 복호화 키가 다르기 때문에 암호키가 비대칭이라는 의미다.
그래서 평문(데이터)를 공개키로 암호화하면 개인키로만 복호화가 되며 반대로 개인키로 암호화하면 공개키로만 복호화가 가능한 방식이다. 처음엔 어떻게 이런게 가능하지?라고 매우 신기하게 생각했다.
그리고 디피헬만 알고리즘과 같이 PKI에서도 키를 생성하는 과정은 필수다. 그리고 그 키는 두개가 된다. 주변에 공개할 즉, 유출되어도 상관없는 공개키와 나만이 갖고 있어야 하며 외부에 공개되어서는 안되는 개인키 두 개가 존재하게 된다. 그리고 이 공개키와 개인키를 담고 있으면서 소유자를 증명하는 것이 바로 PKI인증서다.
PKI인증서는 통신주체는 모두 갖고 있어야 한다. 만약 뽀로로와 패티가 안전하게 통신을 하고자 하면 적어도 둘 다 공개키와 개인키가 담겨져 있는 PKI인증서를 갖고 있어야 한다. (단순히 통신만 생각한다면 공개키와 개인키만 있으면 되겠지만)
기본적인 비대칭키 암호화알고리즘을 이용하여 암호화 통신을 수행하는 과정은 아래와 같다.
먼저 뽀로로와 패티는 서로의 공개키를 교환한다. 즉 뽀로로는 패티에게 , 패티는 뽀로로에게 자신의 공개키를 알려준다. 공개키는 원래 공개를 목적으로 하는 암호키다.뽀로로는 데이터를 패티의 공개키로 암호화하여 패티에게 보낸다.패티는 자신의 개인키로 데이터를 복호화한다.패티는 뽀로로에게서 받은 뽀로로의 공개키로 데이터를 암호하하여 뽀로로에게 보낸다.뽀로로는 자신의 개인키로 데이터를 복호화한다.
그렇다면 비대칭키 암호화 통신에서 사용되는 공개키와 개인키는 어떻게 만들어지는 것일까???
RSA (Ribest Shamir Adelman)
RSA의 세 글자는 RSA 알고리즘을 만든 세명의 이름 첫글자를 다온 알고리즘이다. RSA는 완전한 공개키기반구조(PKI)를 제공한다. 그리고 그 핵심은 PKI의 기본이 되는 공개키와 개인키를 만드는 키 생성 알고리즘이다.
RSA는 소인수분해의 어려움에 기반하며 공개되는 공개키를 가지고는 개인키를 유추하는 것이 어렵다. 아래에 RSA의 키 생성과정에서 최초 선택되는 두 소수 (P, Q)가 클 수록 공개키를 이용해 개인키를 유추하는 것이 어려우며 일정 크기를 넘어가면 현재 존재하는 컴퓨터로는 개인키를 해킹하는 것이 불가능에 가깝다고 한다.
다음은 RSA의 키 생성 과정을 설명해본다. 하지만 디피헬만보다 훨씬 어렵다. 수학에 소질이 있다면 이해가 쉬울 수도 있다.
뽀로로와 패티가 비밀연애를 위해 암호화된 연애편지를 주고 받으려 한다면…뽀로로는 서로 다른 두 소수 (P, Q)를 선택한다.P와 Q를 곱해 N 을 구한다. (N=PxQ)오일러 피 함수에 해당되는 φ(N) = (P-1)(Q-1)을 구한다.φ(N) 보다는 작으면서 φ(N)와 서로소인 정수 e를 찾는다. (1 < e < φ(N)) 확장된 유클리드 호제법을 이용해 (d x e)/φ(N) 일 때 나머지가 1인 정수 d 를 구한다. 처음에 선택한 두 소수 (P, Q)는 유출되면 안되므로 삭제한다.패티도 동일한 과정을 거친다.
위의 과정에서 등장하는 식을 만족하는 숫자들 중에 공개키와 개인키가 존재한다.
먼저 뽀로로의 공개키는 [N , e] 이고 개인키는 [N, d] 이다. 마찬가지로 패티도 패티의 공개키와 개인키를 만들었을 것이다.
뽀로로는 뽀로로의 공개키인 [N, e]를 패티에게 보내고 패티도 마찬가지로 패티의 공개키를 뽀로로에게 보낸다. 이후 두사람은 상대방에게 보낼 연애편지를 상대방에게서 받은 공개키를 이용해 암호화하여 보낸다. 암호화된 연애편지를 받은 뽀로로와 패티는 각자 자신의 개인키로 연애편지를 복호화하여 읽게 된다.
RSA의 암호화와 복호화
위에서 생성한 공개키를 이용해 암호화 할 때는 다음의 식에 따라 암호화 한다.
또한 개인키를 이용해 복호화 할 때는 다음의 식에 따라 복호화 한다.
RSA의 예제
위에 설명한 과정에 따라 키를 만들고 공개키로 암호화하고 개인키로 복호화하는 과정을 실습해보자.
먼저 키를 만든다.
두 소수는 P = 3, Q = 11 로 정한다. 따라서 N은 33 이다. ( P = 3, Q = 11, N = 33 )
φ(N)을 구하면 ( 3 – 1 ) x ( 11 – 1) 이므로 20 이다. ( φ(N) = 20 )
따라서 1 보다 크고 20보다 작으면서 20과는 서로소인 e를 구하면 몇개가 나오는데 그중에 7을 선택한다. ( e = 7 )
이젠 (d x e)/φ(N) 일 때 나머지가 1인 정수 d 를 구해야한다. 즉 (d x 7) / 20을 계산했을 때 나머지가 1 이어야 한다.
음… 수학에 소질이 없다보니 막 대입하는 방법밖엔 떠오르지 않는다. 막 대입하다 보니 3을 넣었을 때 나머지가 1이 나온다.
즉 d = 3 이다. ( d = 3 )
이제 키에 필요한 계산은 다 했다.
즉 공개키는 [ 33, 7 ] 이고 개인키는 [ 33, 3 ] 이다.
이제 공개키로 암호화를 해본다. 암호화 대상은 9 이라는 숫자다. ( M = 9 )
먼저 9를 공개키의 e승, 즉 7제곱하면 4782969 이고 4782969 mod 33 을 계산하면 15가 나온다.
즉 9를 RSA로 암호화하면 15가 나오는 것이다.
9는 평문(M : Message)이고 15는 암호문(C : Ciphertext)이다.
그럼 15를 RSA로 복호화 해본다.
일단 15의 d 승 즉 15의 3승을 계산하면 3375가 나온다.
다음은 3375 mod 33을 계산한다. 정확하게 처음 메시지인 9가 나온다.
그저 신기할 따름이다.