공개 키 암호화 (public crytography)
공개 키 암호화 (public cryptography)
네트워크가 발달하면서 컴퓨터로 친구와 대화도 할 수 있고, 쇼핑을 할 수도 있고, 은행에 가지 않아도 은행업무를 볼 수도 있습니다. 이처럼 컴퓨터 간에 통신으로 많은 일들을 쉽게 할 수 있게 됐습니다.
컴퓨터로 다른 컴퓨터와 비밀통신을 해야만 하는 경우가 있습니다. 예를 들면 은행에서 돈을 출금하고 싶을 때, 내 계좌번호와 비밀번호를 보내면 은행에서 확인한 후에 출금처리를 해주겠지요. 하지만, 인터넷 상에서는 라우터(router)라 불리는 수많은 컴퓨터를 돌아다니기 때문에 라우터에 접근만 하면 이 계좌번호와 비밀번호를 쉽게 볼 수 있게 됩니다.
이렇게 컴퓨터가 인터넷을 통해 통신을 하게 되면 정보들이 전부 공개가 됩니다. 비밀통신을 하는데 모르는 사람이 이를 쉽게 알아 낼 수 있다면 컴퓨터는 계산기, 데이터창고로 전락하겠지요.
공개 키 암호화 (public cryptography), 공개된 정보를 암호화시켜 보내고자 하는 특정 컴퓨터에게만 정보를 주는 방법입니다. 이 방법으로 컴퓨터 간에 비밀통신이 가능합니다.
컴퓨터 간의 통신방법이 바뀌지 않는 이상은 완벽한 방법은 없겠지만, 공개 키 암호화는 컴퓨터에 있어서 아주 중요한 알고리즘입니다.
공유비밀(shared secret) 암호화
이 방법의 핵심은 간단합니다. 보내는 사람과 받는 사람이 둘만이 알고 있는 공유비밀인 키를 이용하는 것입니다.
A, B, C 세사람이 있습니다. A는 C에게 인터넷상으로 통장비밀번호를 몰래 알려주고 싶습니다. A가 C에게 ‘내 통장비밀번호는 8282야’ 라고 인터넷 상에서 메시지를 보내면 B도 알게 됩니다. 하지만 C의 전화번호 뒤 4자리가 5050 이라는 것을 A만 알고 있다고 가정합니다.
그렇다면 A는 ‘내 통장비밀번호는 너의 전화번호 뒤 4자리에 3232를 더한 거야’ 라고 메시지를 보내면 A와 C는 인터넷상에서 통장비밀번호를 무사히 알려줄 수 있습니다.
위에서는 shared secret인 key가 5050입니다. 하지만, B가 A의 비밀번호를 알고 싶어서 1000부터 9999까지를 한번 씩 모두 더 해보면 이를 쉽게 복호화(decrypt)를 할 수 있습니다.
그래서 key의 자리수를 늘려 ‘128비트 암호화’로 128비트 (38자리수 숫자)인 키를 이용하여 컴퓨터를 이용하여도 모든 가능성을 시도하더라도 수십억년이 걸리는 안전한 방법을 이용합니다. 또, 위처럼 단순한 덧셈트릭을 이용하면 암호화된 메시지 분석을 통해 키를 구해낼 수 도 있기 때문에 오늘날에는 블록 암호(block cipher) 라는 변형된 덧셈 트릭을 이용합니다.
우선 긴 메시지를 작은 블록으로 쪼갠 다음 메시지와 키를 복잡한 규칙에 의해 섞어 통계적인 분석을 할 수 없도록 어렵게 합니다. 오늘날에 가장 많이 쓰이는 block cipher는 Advanced Encryption Standard (AES) 이라고 합니다.
하지만 공유비밀 암호화에서는 둘만이 아는 공유비밀이 있어야 한다고 가정하였습니다.
공유비밀이 없는 모르는 사람과 비밀통신을 하고자 할 때, 어떻게 해야할까요?
공유비밀(shared secret) 공개 설정
공유비밀이 없으면서도 (엄연히 말하면, 공유비밀을 암호화시켜 공개하는데 정보를 받는 사람은 공유비밀을 알 수 있도록) 비밀통신을 하는 방법은 Diffie-Hellman key exchange(디피-헬먼 키 교환)이 있습니다.
여기서도 한 가지 중요한 점이 있습니다. 그것은 one-way action (일방향 행위) 이 필요하다는 사실입니다. one-way action은 수행을 할 수는 있지만 원상태로 되돌릴 수 없는 행위를 말합니다.
Diffie-Hellman key exchange (디피-헬먼 키 교환)
디피-헬먼 키 교환은 다음과 같은 방법으로 진행합니다.
2. 그리고 A, C 중 한명이 ‘공개 수’를 공개한다.
3. A와 C는 각각 ‘개인수’와 ‘공개수’를 one-way action 한다.
4. A와 C가 각각 ‘개인-공개 one-way action 수’를 공개한다.
5. A는 C의 ‘개인-공개 one-way action 수’ 와 개인수를 one-way action을 한다.
C는 A의 '개인-공개 one-way action 수' 와 개인수를 one-way action을 한다.
6. A와 C는 같은 수를 갖게 된다. (공유 비밀을 갖게 된다.)
이 과정을 먼저 이해하기 쉽게 곱셈 연산을 one-way action이라고 가정합니다. (나눗셈 이라는 연산이 없다고 가정)
1. A와 C는 각각 ‘개인수’ 2, 9를 선택한다.
2. A 또는 C가 ‘공개수’ 4를 공개 한다.
3. A와 C는 각각 ‘개인수’와 ‘공개수’를 곱셈한다. A는 8 (2x4)를 C는 36 (9x4)를 얻는다.
4. A와 C가 각각 ‘개인-공개 곱셈 수’를 공개한다.
5. A는 C의 ‘개인-공개 곱셈 수’ 36 과 자신의 개인수 2를 곱하여 72를 얻는다.
C는 A의 ‘개인-공개 곱셈 수’ 8 과 자신의 개인수 9를 곱하여 72를 얻는다.
6. A와 C는 72 라는 공유비밀을 얻을 수 있다.
이렇게 one-way action을 이용하면 공개 수를 이용하고도 모르는 사람과 공유비밀을 갖을 수 있게 됩니다. 위에서는 나눗셈이 없다고 가정하고 곱셈을 one-way action이라고 했는데, 그렇다면 실제로 one-way action은 어떻게 가능할까요?
one-way action
컴퓨터가 어떤 연산을 한 후, 다시 원 상태로 되돌리는 연산을 할 수 없는 방법이 있을까요?
이산누승법(discrete exponentiation)이라는 혼합 계산방법이 있습니다. 이를 원상태로 되돌리는 연산은 이산로그(discrete logarithm) 이라는 연산입니다. 컴퓨터는 이산누승법을 할 수 있지만, 이산 로그를 효율적으로 계산할 방법이 없기에 one-way action의 종류가 될 수 있겠습니다.
이산누승법은 거듭제곱과 나머지연산을 이용한 연산인데, 이산누승법은 이렇게 진행합니다.
이산누승법을 이용하여 Diffie-Hellman key exchange를 다시 진행해보면,
1. A와 C가 각각 8과 9를 선택한다.
2. A또는 C가 시계크기 11, 기저수 2를 공개한다.
3. A와 C가 각각 PPN을 구한다. A는 3 (2^8%11) C는 6 (2^9%11)를 얻게 된다.
4. A와 C가 각각 PPN을 공개한다.
5. A는 C의 PPN을 이용하여 두번째 연산을 통해 key를 구한다. 6^8 % 11 = 4
C는 A의 PPN을 이용하여 두번째 연산을 통해 key를 구한다.. 3^9 % 11 = 4
6. A와 C는 4라는 공유비밀을 갖게 된다.
실제 공개 키 암호화 방식에서는 이렇게 작은 시계크기를 사용하지 않습니다. 시계크기보다 작은 개인수를 이용할 수 밖에 없으므로 가능한 개인수도 줄어 모든 가능한 개인수를 대입하여 공유비밀을 알 수 있기 때문입니다. 따라서 수백만 자리의 시계크기를 이용합니다. 그 다음에는 아래와 같은 수학적 속성이 올바르도록 공개 수도 주의 깊게 선택돼야 합니다.
1. 시계 크기가 소수 (prime number) 여야 한다.
2. 기저수가 시계 크기의 원시근 (primitive root) 이여야 한다.
기저수의 제곱수가 결국 시계에서 가능한 모든 값을 따라 순환해야 한다는 말이다.
시계크기 11에서의 거듭제곱표를 보면 2와 6은 11의 원시근이지만, 3은 아니다.
3의 제곱수는 3,9,5,4,1 을 순환하고 2,6,7,8,10은 지나치기 때문이다.
이와 같이 컴퓨터로 보내는 정보들은 공개될 수 밖에 없으나, 네트워크 상에서 공개 키 암호화 방식을 통해 원하는 사람과 아주 중요한 비밀정보들을 안전하게 통신할 수 있도록 할 수 있는 계기가 됐습니다.
<참고문헌>
미래를 바꾼 아홉가지 알고리즘 - 존 맥코믹 저, 민병교 역
