양자 암호론

 

암호는 정보를 특정 집단이 공유하고 집단 이외의 구성원은 정보의 내용을 알 수 없게 하기 위한 기호체계이다. 암호가 제 기능을 하기 위해서는 암호를 공유한 집단은 암호의 정확한 해독이 가능하나 이외의 집단에게는 암호의 해독이 불가능해야 한다. 이러한 목적을 달성하기 위한 대표적인 방법으로 RSA PUBLIC KEY를 이용한 암호 체계와 ONE-TIME PAD를 이용한 암호 체계 등이 있다. 두 방식 모두 뚜껑함수(Trapdoor Function)를 이용한 방법이다. 뚜껑함수란 특별한 열쇠(Key)를 모르면 역변환의 계산이 매우 어려워지는 수리적 과정이다. 이를 이용하면 열쇠를 가진 측만이 쉽게 암호를 해독할 수 있게 되는 것이다.

ONE-TIME PAD를 이용한 암호체계

이 암호에서 암호를 전송하는 측(이하 갑돌이라 부르겠다.)은 뚜껑함수를 이용해서 정보를 암호화한다. 전송받는 측(이하 갑순이라 부르겠다.)은 열쇠를 이용해서 암호를 해독한다. 이 암호의 작성과 해독은 다음과 같다.

1) 갑돌이와 갑순이는 사전에 몇 개의 숫자열들을 공유한다. 한 숫자열의 숫자들은 각각이 서로 다른 한 문자에 대응된다. 이러한 숫자열을 PAD라 하고 이는 다음과 같은 수열이다.

(한편 암호체계에서 이용되는 문자의 개수는 L개라 하자.)

2) 이제 갑돌이는 보내려는 정보의 각 문자들을 정수로 부호화한다(이를테면 A를 1에 대응시키고 B를 2에 대응시키고 ,,,). 이 상태에서 정수를 문자로 바꾸는 것은 쉽다. 부호화된 정보는 다음과 같은 수열이 된다.

3) 갑돌이는 갑순이와 공유한 여러 PAD들 중 하나의 PAD를 고른다. 이제 2)에서 부호화한 각각의 숫자를 다음과 같은 수열로 변환한다.

즉 PAD내의 각 숫자를 더해서 L로 나눈 나머지가 부호화된 숫자를 대치한다. 이렇게 만들어진 수열이 암호화된 정보이고 이를 전송하면 된다.

4) 갑순이는 정보를 전송받은 후 자신이 공유한 PAD중 하나를 선택하고 다음과 같이 변환한다.

즉 전송받은 각 숫자에서 PAD내의 각 숫자들을 빼서 L로 나눈 나머지를 구한다. 이렇게 구한 숫자열을 문자로 바꾸어 본다. 갑순이가 고른 PAD가 갑돌이가 암호를 만들때 쓴 PAD와 일치할 때 암호는 해독된다.

이 방법은 PAD의 수열을 모르면 해독이 될 때까지 임의의 수열을 가정해서 암호를 풀어야 하므로 해독이 거의 불가능하다. 이 암호체계로 암호를 작성하려면 반드시 PAD를 공유해야 한다. 그러나 많은 사람이 PAD를 안전하게 공유하기가 쉽지 않다. 그러므로 많은 사람이 사용하는 암호로는 적합하지 않은 방법이다.

RSA PUBLIC KEY를 이용한 암호체계

RSA PUBLIC KEY를 이용한 암호체계는 전자상거래시 정보의 보안을 위해 사용되고 있는 방법으로 암호의 열쇠가 외부로 유출될 가능성이 매우 적다. 이 암호체계는 정보를 전송하는 측(갑돌이)에게 공유된 두개의 숫자 n, e 와 공유되지 않은 두 개의 숫자 m, d 로 이루어진다. 갑돌이는 공유된 숫자 n, e 를 통해 정보를 암호화한다. 암호화된 정보는 공유되지 않은 숫자 m, d 를 통해 쉽게 해독이 가능하나 m, d 를 모른 상태로는 해독이 쉽지 않다. 정보를 전송받는 집단(갑순이)이 m, d의 보안을 유지하면 이 암호는 깨지지 않는다. 이 암호는 n, e가 공유된 모든 집단이 이용할 수 있는 만큼 전자 상거래와 같은 많은 구성원이 암호화를 필요로 하는 경우에도 쓰일 수 있는 안전한 암호체계이다. 이 암호체계를 사용한 암호의 작성과 해독은 아래의 과정과 같다.

1) 먼저 n은 두개의 매우 큰 소수 p , q의 곱으로 이루어진 자연수이다. 이때 n의 소인수분해는 매우 어렵다.

2) m은 (p-1)*(q-1)이 되는데 n을 소인수분해하지 않고 m을 구할 수는 없다.

3) d는 m과 서로소인 자연수이면 된다.

4) e는 e*d가 m으로 나눈 나머지가 1인 자연수이다.즉 아래와 같다.

5) e, n 은 암호로 정보를 작성하고자 하는 모든 이에게 공개되며 m, d 는 암호를 해독하는 측만 공유한다.

6) 갑돌이는 먼저 자신의 정보를 정수의 수열로 부호화한다. 이때 다음의 수열이 얻어진다.

7) 정보가 부호화된 각 숫자를 다음과 같이 변환한다. 이때 변환된 숫자의 열들이 암호가 되고 전송된다.

8) 갑순이는 전송받은 수열을 다음과 같이 변환한다.

이때 변환된 숫자는 암호화하기 전의 숫자가 되는데 그 이유는 아래와 같은 오일러의 정리 때문이다.

9) 이제 숫자들을 문자로 바꾸는 것은 과정 6)을 반대로 시행한 것이 되고 암호는 해독된다.

이러한 과정이 암호로서 성공할 수 있는 이유는 큰 정수를 소인수분해하기가 매우 힘들기 때문이다. 그 결과 주어진 n과 e로부터 암호를 풀기 위해 반드시 필요한 m과 d를 계산하는 것이 기존의 컴퓨터로서는 영원히 불가능하게 여겨질 정도로 어렵게 된다. 위의 과정에서 알 수 있듯이 RSA PUBLIC KEY를 이용한 암호는 암호를 만들어 전송하는 구성원이 많더라도 안전하게 사용될 수 있는 방법이다. 그러나 양자컴퓨터가 구현되면 큰 수의 소인수분해가 가능해지고 주어진 n, e 를 통해 m, d 를 계산할 수 있게 되므로 이 암호는 깨진다.

양자암호론

앞에서 논의한 암호체계는 모두 암호를 전송받는 측이 가진 비밀열쇠(secret key)를 바탕으로 성립하는 것으로 열쇠가 공개되면 암호는 쉽게 해독된다. 그러나 열쇠가 공개되지 않은 상태에서 열쇠를 계산하는 것은 현재의 컴퓨터로 거의(전혀) 불가능하다. 그러므로 KEY의 보안이 중요하고 이것이 현재의 암호방식의 한계이기도 하다. 더구나 양자컴퓨터가 구현되면 KEY의 보안이 보다 수월한 RSA PUBLIC KEY 암호체계는 깨지고 만다. 그러므로 정보의 보안이 더욱 용이한 암호체계를 연구할 필요가 있다. 여기서는 Bennett과 Brassard가 고안한 안전한 정보 수송법을 살펴본다. 이 방법을 이용하면 ONE-TIME PAD를 이용한 암호체계에서 PAD를 안전하게 공유할 수 있다.

정보의 부호화는 여러 가지 방식으로 이루어질 수 있지만 일단 문자를 0과 1을 사용한 2진 부호로 부호화 한다고 하자. 2진 부호를 물리적으로 구현하는 방법은 여러 가지가 있으나 여기서는 서로 수직한 선형 편광된 광자를 각각 1과 0으로 부호화 한다. 수직 편광된 광자(|로 표시한다.)와 45'' 선형편광인 광자(/로 표시한다.)은 0을 나타내고 수평 편광된 광자(-로 표시한다.)와 -45'' 선형편광인 광자(\로 표시한다.)는 1을 나타낸다.

갑돌이가 보낸 정보를 갑순이가 받는다고 하자. 갑돌이는 자기가 가진 수열에서 1은 -과 \을 이용하고 0은 |과 /을 이용하여 구현한다. 그림 1)은 이를 나타낸 것이다. 그림의 첫째줄은 갑돌이가 가진 수열이고 둘째 줄은 갑돌이가 +편광기와 x편광기 중 하나를 써서 정보를 전송함을 나타낸다. (즉 전송신호로 |, -을 사용할 것인지 /, \를 사용할 것인지를 나타낸 것이다.) 셋째 줄은 물리적으로 구현된 부호이다. 갑돌이는 이렇게 만들어진 광자의 열들(|, -, /, \)을 갑순이에게 보낸다.

1 1 1 1 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1
X + X X X X X + X X + + + + X X + + X + + X X + + X X + X X
\ - \ \ \ / / - / \ | | | | \ / | | / - | / / | | / \ | \ \


그림 1)

갑돌이가 보낸 광자가 중간에서 누설되지 않고 바로 갑순이에게 갔다고 하자. 이때 갑순이는 +편광기로 측정할 수도 있고 x편광기로 측정할 수도 있다. 그림 2)의 첫째 줄은 갑순이가 받은 광자들의 상태를 나타내고 둘째 줄은 갑순이가 선택한 편광기의 상태이다. 셋째 줄은 그 결과 갑순이가 얻은 수열을 나타낸다. 이 수열과 갑돌이가 가진 수열은 갑돌이가 선택한 편광기와 갑순이가 선택한 편광기가 같은 경우에는 완전히 일치하나 둘이 선택한 편광기가 다른 경우에는 1/2의 확률로 다를 수 있다.

\ - \ \ \ / / - / \ | | | | \ / | | / - | / / | | / \ | \ \
+ + X + X X + X + X + + X X + X X + X + X + + + X + X + X +
0 1 1 1 1 0 0 0 1 1 0 0 0 1 0 0 0 0 0 1 1 1 1 0 1 1 1 0 1 0


그림 2)

이제 갑돌이와 갑순이는 서로 특정한 위치의 편광기의 상태와 그때의 수열값을 교환한다. 이때의 교환은 공개되어도 무방하다. 누설이 없다면 교환된 수열 중 편광기의 상태가 같은 경우에는 완전히 일치할 것이다. 그림 3)은 편광기의상태가 같은 경우 갑돌이와 갑순이가 가진 수열이 일치함을 보여준다. 교환된 수열중 편광기의 상태가 같은 한 비트를 조사하여 두 값이 일치할 경우 누설이 없을 확률은 1/4이 된다. 만일 편광기의 상태가 같은 N 비트의 수열을 조사하여 각 수열이 같은 경우 누설이 없을 확률은 다음과 같다.

즉 조사한 비트의 수가 많을수록 그리고 그 결과가 일치할수록 광자의 누설이 없을 확률은 매우 빠르게 1에 접근한다. 만일 누설이 있다면 조사한 비트들은 4개 중 1개 꼴로 다른 값을 갖게 될 것이다. 이와 같이 하여 누설의 유무를 판단할 수 있다.

   1 1       0          1    0          0    0    1                   1 0      
  + X     X       X   +       X   +   +             X +    
  + X     X       X   +       X   +   +             X +    
  1 1     0       1   0       0   0   1             1 0    


그림 3)

누설이 없었다고 판단되면 갑돌이와 갑순이는 각자의 편광기의 상태만을 완전히 교환한다. 이 때 편광기의 상태가 같은 경우만을 보면 두 사람은 같은 수열을 얻을 것이고 이렇게 얻은 수열은 오직 갑돌이와 갑순이만 공유한 것이다. 그림 4)의 마지막 줄은 이렇게 얻어진 수열을 나타낸다.


그림4)

이렇게 얻은 수열을 PAD를 만드는 데 이용할 수 있다. 이러한 PAD의 교환은 기존의 방법보다 훨씬 안전한 것이 되어 보안된 ONE-TIME PAD를 이용한 암호체계는 매우 강력한 암호체계가 될 수 있다. 이 체계에서는 PAD의 보안이 RSA PUBLIC KEY를 이용한 암호 체계에 준하게 되고 일단 PAD가 보안되면 이 암호체계는 깨지지 않는 암호체계가 된다.

[ Prev | Return | Next ]