네트워크 보안 - 4 | 공개키 암호

공개키 암호

현대의 암호체계를 크게 대칭키 암호체계, 공개키 암호체계, 해시함수로 나눌 수 있다고 했는데, 이번에는 공개키 암호방식에 대해 알아보고자 한다.

 

이전에 알아본 대칭키 암호체계의 경우 암호화와 복호화에 필요한 키가 서로 같은 암호방식이었다. 암호화와 복호화의 속도가 빠르고, 비교적 간단한 방식으로 설계가 가능하기 때문에 과거에서부터 현대에 이르기까지 널리 쓰이는 암호방식이지만, 송신자와 수신자가 같은 키를 공유해야 한다는 것 자체가 가장 큰 어려움이라고 볼 수 있었다.

 

이를 해결할 수 있는 방법이 바로 공개키 암호체계이다. 공개키 암호체계에서는 암호화에 사용되는 키와 복호화에 사용되는 키가 서로 다른데, 이 중 암호화에 사용되는 키는 모두에게 공개를 할 수 있다. 왜 공개를 해야 하고, 키를 공개해도 어떻게 보안상의 문제가 없는지, 그리고 이러한 방식으로 어떻게 대칭키를 서로 공유할 수 있는지를 이제 알아보도록 하자.

공개키 암호체계의 작동

암호화에 필요한 키와 복호화에 필요한 키가 서로 다르고, 그중 암호화에 필요한 키는 공개를 한다는 것은 처음 듣는 사람에게는 꽤나 이상하게 다가올 수 있다. 하지만 조금만 생각해 보면, 이런 방식의 암호체계가 충분히 근거 있는 방법이고, 또 대칭키 암호체계에서는 불가능하던 부분까지 실현 가능하다는 점을 알 수 있을 것이다.

 

먼저 모두에게 공개되는 공개키는 어떤 메시지를 암호화만 할 수 있다. 따라서 모두가 해당 공개키를 가지고 암호화는 가능하지만, 이미 암호화된 메시지의 경우 복호화를 할 수 없다. 이때 복호화에 필요한 개인키는 해당 키의 주인만이 가지고 있으며, 따라서 개인키를 가지고 있는 사람만이 암호화된 메시지들을 확인할 수 있다.

 

따라서 대칭키 암호체계에서 필요한 대칭키의 교환 역시 공개키 암호체계를 이용하면 간단하게 구현할 수 있다. 예를 들어 A와 B가 서로 암호통신을 시작하려고 한다. 이때 대칭키 암호방식을 사용하려고 하는데, 그전에 먼저 A와 B가 같은 대칭키를 공유하고자 한다. 이를 위해 공개키 암호를 이용한다고 할 때, 다음과 같은 절차를 이용하기로 했다.

1. 먼저 A가 자신의 개인키와 공개키 쌍을 생성한다.
2. 이후 B에게 생성된 공개키를 전송한다. (모두가 봐도 상관없으므로 그대로 전송)
3. 공개키를 받은 B는 A와의 통신에 사용할 대칭키를 받은 공개키로 암호화하여 전송한다.
4. 이렇게 전송된 대칭키는 A만이 자신의 개인키로 복호화할 수 있다.
5. 서로 같은 대칭키를 공유했으므로, 이후로는 대칭키 방식으로 암호통신을 진행한다.

이와 같은 방식을 사용한다면, 굉장히 논리적이면서도 간단하게 대칭키를 서로 교환할 수 있다. 대칭키 방식의 가장 큰 걸림돌이 공개키 방식으로 단번에 해결되는 것이다.

 

물론 공개키 암호체계가 이러한 대칭키 교환에만 사용되는 것은 아니다. 전자 사인과 같은 특수한 방식도 구현할 수 있고, 통상적인 암호로도 사용할 수 있다. 중요한 것은 위의 예시를 통해 공개키가 어떤 식으로 작동하는지만 이해하면 되는 것이다.

 

여기서 가장 핵심이 되는 부분은 개인키와 공개키 쌍을 생성하는 작업이다. 공개키로 암호화된 값이 개인키로만 복호화되도록 하는 키 쌍을 생성하기 위해서는 특별한 수학적인 구조가 필요하다. 따라서 지금부터는 어떤 종류의 공개키 암호방식이 있는지 알아보고, 각 방식이 어떤 수학적인 원리로 개인키와 공개키 쌍을 생성하는지를 가볍게 살펴보도록 하겠다.

---

배낭 암호

보통의 공개키 암호의 경우, 대칭키 암호와 달리 매우 특별한 수학적인 구조를 기반으로 하기 때문에 그 원리를 자세히 이해하기란 매우 어렵다. 전문적으로 암호를 공부하는 수학자들이 아닌, 암호를 공학적으로 사용하기 위한 입장에서는 공개키 암호 방식의 원리를 완벽하게 이해하기 어려울 것이다.

 

하지만 그럼에도 이러한 공개키 암호 방식이 어떻게 공개키와 개인키 쌍을 생성하는지 대충이라도 확인하기 위해 배낭 암호라는 공개키 암호체계를 먼저 살펴보고자 한다. 자세한 수학적 원리를 파고들지만 않는다면, 나름 쉽게 이해할 수 있을 것이다.

일반적인 배낭 문제

먼저 배낭 문제란, 배낭에 담을 수 있는 전체 무게가 정해져 있을 때, 각각 다른 무게를 가진 물건들을 얼마나 배낭에 담아서 무게를 맞추냐에 대한 문제이다. 이를 식으로 나타내면 다음과 같다.

$S=a_{0}W_{0}+a{1}W_{1}+ ... + a_{n-1}W_{n-1}$
$S$는 전체 무게, $a_{i}$는 0 또는 1, $W_{i}$는 서로 다른 개별적인 무게

식으로는 이해하기 힘들 수 있으니 간단한 예시를 들어보면 다음과 같다.

예를 들어, 배낭 무게가 다음과 같이 주어졌다고 가정하자.

85, 13, 9, 7, 47, 27, 99, 86

이때 요구되는 전체 무게가 $S=172$라면, 필요한 무게는 85, 13, 47, 27이다.

따라서 이 문제에 대한 해답은 11001100이다. (위에 제시된 무게 순서에 맞춰, 필요한 무게를 1로 배치)

 

중요한 것은 해당 문제를 풀기 위한 특별한 쉬운 방법이 존재하지 않는다는 점이다. 그저 숫자를 하나씩 넣어보면서 해당 무게들을 넣었을 때 전체 무게 S가 구해지는지를 확인하는 방법밖에 존재하지 않는다. 따라서 위의 예시에서는 사람이 조금만 노력한다면 풀 수 있는 문제지만, 경우의 수가 많아지면 많아질수록 컴퓨터라고 하더라도 시간이 아주 오래 걸리는 문제라고 할 수 있다.

수퍼증가 배낭 문제

반면 특수한 상황에서는 이러한 배낭 문제가 아주 쉽게 풀리는 경우가 있다. 바로 각 무게가 작은 수에서 큰 수로 차례대로 정리되고, 각 무게는 그 앞의 무게를 전부 합한 무게보다 더 큰 경우이다. 이렇게 특수한 경우를 수퍼증가 배낭 문제라고 한다. 이렇게 특수한 상황에서는 배낭 문제를 푸는 방법에 지름길이 생긴다.

 

예를 들어 다음과 같은 무게가 주어졌다고 가정하자.

3, 6, 11, 25, 46, 95, 200, 411

이때 요구되는 전체 무게가 $S=309$라고 한다면, 답을 구하기 위해 가장 큰 무게부터 작은 순서로 순차적으로 찾아가면 된다. 이런 방식으로 찾는 방식을 순서대로 나타내면 아래와 같다.

1. 411은 전체 무게를 초과하므로 넣을 수 없다.
2. 200은 넣을 수 있으므로, 묻지도 따지지도 않고 일단 넣는다.
3. 200을 넣었으므로 남은 전체 무게는 109이다.
4. 95는 109안에 들어가므로 넣을 수 있다.
5. 남은 전체 무게는 14이다.
6. 그다음으로 들어가는 건 11이다.
7. 남은 전체 무게는 3이다.
8. 마지막으로 들어가는 건 3이다.
9. 정답은 10100110이다.

이와 같이 무거운 순서대로 넣기 시작하면서, 일단 전체 무게에 들어가기만 하면 무조건 넣는 식으로 답을 찾을 수 있다. 즉, 모든 경우의 수를 계산해야 하는 일반 배낭 문제와 달리, 이러한 특수한 상황에서는 아주 빠르게 답을 찾을 수 있다.

 

그리고 이렇게 일반 배낭 문제와 수퍼증가 배낭 문제를 이용해 공개키 암호체계를 구현할 수 있다.

배낭 암호 구현

그렇다면 이런 일반 배낭 문제와 수퍼증가 배낭 문제를 이용해 실제 암호체계, 즉 공개키와 개인키 쌍은 어떻게 생성한다는 것일까? 다시 한번 말하지만 수학적으로 어떤 원리에 의해서 이러한 것이 가능한지는 여기서 설명하지 않는다. 이를 유의하여 키의 생성 방법을 간단하게 살펴보면 다음과 같다.

1. 수퍼증가 배낭을 생성한다.
2. 수퍼증가 배낭을 일반 배낭으로 변환한다.
3. 일반 배낭을 공개키로 사용한다.
4. 수퍼증가 배낭과 변환 값을 개인키로 사용한다.

지금까지 살펴본 바에 의하면, 일반 배낭 문제를 푸는 데에는 특별한 지름길이 없어 아주 오랜 시간이 걸린다는 것을 알 수 있었다. 반면 수퍼증가 배낭 문제의 경우 굉장히 빠르게 문제를 풀어낼 수 있었다. 따라서 일반 배낭 문제를 공개키로, 수퍼증가 배낭을 개인키로 사용한다면, 개인키를 가진 사람만 문제를 빠르게 풀어낼 수 있을 것이다.

 

여기서 핵심은 수퍼증가 배낭을 일반 배낭으로 변환하는 과정이다. 아무런 일반 배낭을 하나 만드는 것이 아니라, 기존의 수퍼증가 배낭을 일반 배낭으로 변환하는 것이다. 이러한 수학적인 방법은 다음과 같다.

1. 수퍼증가 배낭을 생성한다.
2. 서로소인 m과 n을 선정한다. 이때 n은 수퍼증가 배낭의 모든 요소의 합보다 커야 한다.
3. 각 수퍼증가 배낭 요소를 $E_{i}$라고 할 때, 아래와 같은 방식으로 각 요소를 변화시킨다.

$ (E_{i} \times m) mod n $

이때 mod연산은 나머지 연산을 의미한다. 예를 들어 5 mod 3은 2이다.

배낭 암호 예시

위에서 살펴본 방법대로 실제 배낭 암호를 이용하는 예시를 알아보자.

 

1. 수퍼증가 배낭 선택

(2, 3, 7, 14, 30, 57, 120, 251)

 

2. 수퍼증가 배낭을 일반 배낭으로 변환 (공개키 생성)

$m=41$, $n=491$로 정했다고 가정하고, 위의 수퍼증가 배낭을 일반 배낭으로 변환한다.

• $ (2 \times 41) mod 491 = 82 $
• $ (3 \times 41) mod 491 = 123 $
• $ (7 \times 41) mod 491 = 287 $
• $ (14 \times 41) mod 491 = 83 $
• $ (30 \times 41) mod 491 = 248 $
• $ (57 \times 41) mod 491 = 373 $
• $ (120 \times 41) mod 491 = 10 $
• $ (251 \times 41) mod 491 = 471 $

따라서 위의 과정을 거쳐 만들어진 일반 배낭은 다음과 같고, 이는 공개키로 사용된다.

공개키: (82, 123, 287, 83, 248, 373, 10, 471)

 

3. 개인키 생성

개인키의 경우 처음에 생성한 수퍼증가 배낭이 곧 개인키이다. 하지만 추가로 필요한 것이 하나 더 있는데, 이는 수퍼증가 배낭을 일반 배낭으로 변환하기 위해 사용한 변환 값 m과 n이다. 이때 m과 n을 그대로 사용하는 것은 아니고 m의 역 모듈로 값을 이용한다.

 

$m$의 역 모듈로 값인 $m^{-1}$을 구하는 방법은 다음의 식을 만족하는 $m^{-1}$을 알아내는 것이다.

$ (m \times m^{-1} ) mod n = 1$

해당 예시에서 m은 41, n은 491이므로, $ (41 \ times x) mod 491 = 1$인 $x$값을 찾는다고 하면, $x=12$임을 알 수 있다. 따라서 해당 키를 생성한 본인이 가지고 있어야 하는 개인키의 경우 아래와 같다.

개인키: (2, 3, 7, 14, 30, 57, 120, 251), $m^{-1} = 12$, $n=491$

 

4. 공개키를 이용한 암호화

키의 주인이 공개키를 모두에게 뿌렸다고 하자. 이때 개인키를 가지고 있는 키의 주인에게 특정 메시지를 암호화해서 보내고 싶은 사람의 경우, 자신이 받은 공개키를 이용해 다음과 같이 암호화를 진행할 수 있다.

 

먼저 보내고자 하는 메시지를 이진화한다. 이번 예시에서는 간단하게 150이라는 수를 암호화한다고 하자. 이때 150을 이진화한다면 10010110을 얻을 수 있을 것이다. 그리고 자신이 가진 공개키를 이용해 일반 배낭에서 비트 값이 1로 표시된 요소를 모두 더해 암호문을 생성한다.

공개키	82	123	287	83	248	373	10	471
이진수	1	0	0	1	0	1	1	0

따라서 암호문은 82 + 83 + 373 +10 = 548이다.

이번 예시에서는 경우의 수가 적어 꽤 풀만해 보이지만, 사용하는 비트수가 늘어나면 늘어날수록 경우의 수는 기하급수적으로 늘어나기 때문에, 단순히 저 548이라는 암호문과 공개키만 보고, 어떤 이진수를 사용했는지 복호화하는 것은 불가능에 가깝다.

 

5. 개인키를 이용한 복호화

이렇게 만들어진 548과 같은 암호문의 경우에는 개인키를 가지고 있는 키의 주인만이 복호화를 할 수 있다. 이때 암호문을 복호화하기 위해 먼저 548과 같은 암호문을 수퍼증가 배낭 문제에서 풀 수 있는 수로 변환해야 한다.

 

이를 위해 암호문 $C$를 다음과 같은 연산을 이용해 변환한다.

$ (C \times m^{-1}) mod n = (548 \times 12) mod 491 = 193 $

이후 이렇게 만들어진 193을 전체 무게로 하여 수퍼증가 배낭 문제를 푼다.

개인키	2	3	7	14	30	57	120	251
이진수	1	0	0	1	0	1	1	0

전체 무게 193을 만들기 위해서는 120 + 57 + 14 + 2 = 193이므로, 위와 같이 이진수를 얻을 수 있다. 그리고 이때 얻어지는 이진수 10010110은 공개키를 이용해 암호화하기 전의 바로 그 메시지의 이진수와 동일한 것을 확인할 수 있다. 따라서 이를 다시 십진수로 변환하면 평문 150을 구해낼 수 있다.

배낭 암호 결론

따라서 배낭 암호에서는 문제를 수퍼배낭 암호로는 쉽게 풀 수 있지만, 일반 배낭 암호로는 쉽게 풀 수 없다는 점을 이용해 개인키와 공개키를 생성할 수 있었다. 물론 이런 배낭 암호는 실제로 보안성이 없기 때문에 사용할 수는 없다. 특수한 방법을 이용하면 충분히 해독이 가능하기 때문이다. 하지만 이를 공부하면서 공개키 암호체계가 어떤 식으로 구성되는지를 간단하게라도 이해할 수 있었다.

---

RSA

배낭 암호를 이용해서 간단한 형태의 공개키 암호를 알아봤으니, 이번에는 실제 사용되는 유명한 공개키 암호인 RSA에 대해 알아보고자 한다. RSA는 해당 암호체계를 발명한 리베스트, 샤미르, 애들맨의 이름을 딴 것으로, 큰 수의 인수분해가 매우 어렵다는 사실을 근거로 한 암호체계이다.

 

실제로 우리가 어떤 수를 인수 분해하기 위해서 사용하는 특별한 공식이 존재하지 않는다. 그저 맞는 수를 찾을 때까지 반복하는 방법밖에 없는데, 만약 인수분해를 굉장히 쉽게 하는 방법이 발견된다면, RSA는 더 이상 암호로써의 역할을 하지 못할 것이다.

RSA의 동작

RSA의 공개키와 개인키 쌍을 생성하기 위해서는 다음과 같은 방법을 사용한다.

1. 두 개의 큰 소수인 p와 q를 선택하고, 그 둘의 곱 N = pq를 계산한다.
2. (p - 1)(q - 1)에 서로소인 e를 선택한다.
3. 이때 (N, e)를 공개키로 사용한다.
4. ed mod (p - 1)(q - 1) = 1인 d를 계산한다.
5. 이때 d를 개인키로 사용한다.

이렇게 공개키와 개인키 쌍을 생성했다면, 이를 이용해 암호화와 복호화를 진행하는 방법은 다음과 같다.

암호화: $C=M^{e}modN$

복호화: $M=C^{d}modN$

RSA 예시

이번에는 위의 내용을 참고하여 실제 RSA를 이용해 암호화와 복호화를 진행하는 예시를 살펴보고자 한다.

먼저 p와 q를 각각 p = 11, q = 3으로 정한다. 그러면 N = 33이다. 다음으로 e = 3으로 정한다. 마지막으로 d를 계산하면, $3d mod 20 = 1$을 만족해야 하므로, d = 7이다.

 

따라서 최종적으로 생성된 키쌍은 다음과 같다.

공개키: (N, e) = (33, 3)
개인키: d = 7

이를 이용해 메시지 M = 15를 암호화한다고 가정하면, $C=M^{e}modN=15^{3}mod33=9$이다. 따라서 C = 9로 암호화할 수 있다.

 

반대로 C = 9라는 것을 개인키를 이용해 복호화하려면, $M=C^{d}modN=9^{7}mod33=15$이다. 따라서 원래 메시지인 15를 정확하게 복원한 것을 확인할 수 있다.

RSA 동작 증명

위의 예시에서 직접 알아봤듯이 RSA는 실제로 잘 동작한다. 이번에는 이러한 RSA의 동작을 수학적으로 증명하고자 한다. 해당 증명에는 오일러 정리가 사용되는데, 수학적인 원리는 잠시 내려놓고, 그 식만을 이용하도록 하자.

오일러 정리: $x$와 $n$이 서로소이면, $x^{\phi(n)}mod \ n=1$이다.
이때 $\phi(n)은 1부터 n까지의 수 중에서 n과의 서로소의 개수이다.

먼저 $C=M^{e}modN$이고, $M=C^{d}modN$이므로, 이때의 $M$이 서로 같은지를 증명할 수 있다면, RSA의 동작을 수학적으로 증명할 수 있다.

 

따라서 $M=C^{d}modN$식에서의 $C$를 $C=M^{e}modN$로 치환하면, $M=(M^{e}modN)^{d}modN$로 나타낼 수 있다. 이때 나머지 성질에 따라 $a^{b}modN=(a mod N)^{b}modN$이므로, $M=(M^{e}modN)^{d}modN=M^{ed}modN$이다.

 

그리고 $ed mod (p - 1)(q - 1) = 1$이므로, $ed = k(p - 1)(q - 1) + 1$이라고 할 수 있다. 이때 $k$는 정수이다.

여기서 오일러 정리를 사용하면, $\phi(N) = (p-1)(q-1)$로 나타낼 수 있다. 따라서 $ed=k\phi(N)+1$이다.

 

이를 정리하면 $M^{ed}modN=M^{k\phi(N)+1}modN$이고, 이 식을 풀어나가면 다음과 같다.

$M^{ed}modN=M^{k\phi(N)+1}modN$

$=M \bullet M^{k\phi(N)}modN$

$=(MmodN)(M^{k\phi(N)}modN)modN$

$=(M \bullet 1^{k})modN$

$=MmodN$

$=M$

 

정확한 내용은 아래의 블로그 글을 참조하기 바란다.

RSA 암호화 - RSA의 작동 원리

RSA 계산의 효율

RSA의 계산은 지수 계산과 모듈로 계산(mod)이 함께 존재하는데, 실제 데이터를 암호화하는 과정에서는 이러한 계산 과정에서 매우 큰 수가 나올 수 있다. 따라서 최대한 계산의 효율을 좋게 하기 위해 모듈로 거듭제곱법이라는 방식을 사용한다.

 

예를 들어 $5^{117}mod19$라는 값을 계산해야 한다고 하자. 그렇다면 분명 이 수를 계산하는 과정에서 큰 수가 발생하게 될 것이다. 지금은 M = 5임을 가정하였기 때문에 단순 계산으로도 컴퓨터가 계산할 수 있지만, 실제 암호화를 진행할 메시지의 경우 단순한 숫자가 아님을 기억하자. 분명 컴퓨터가 계산하지 못할 정도의 크기일 것이다.

 

따라서 이러한 큰 숫자가 중간에 생기지 않고 계산하는 방법이 필요하다. 따라서 $5^{117}mod19$을 다음과 같은 방법으로 계산한다.

 

1. 지수를 2의 거듭제곱으로 분해

지수인 117을 1 + 4 + 16 + 32 + 64와 같이 2의 거듭제곱의 합으로 나타낸다. 이는 십진수를 이진수로 변환하는 과정과 동일하다.

 

2. 분해된 거듭제곱 수 중 가장 큰 거듭제곱까지 모듈로 계산을 진행

1) $5^{1}mod19=5$

2) $5^{2}mod19=(5^{1} \times 5^{1})mod19=(5^{1}mod19 \times 5^{1}mod19)mod19=(5 \times 5)mod19=6$

3) $5^{4}mod19=(5^{2} \times 5^{2})mod19=(5^{2}mod19 \times 5^{2}mod19)mod19=(6 \times 6)mod19=17$

4) $5^{8}mod19=(5^{4} \times 5^{4})mod19=(5^{4}mod19 \times 5^{4}mod19)mod19=(17 \times 17)mod19=4$

5) $5^{16}mod19=(5^{8} \times 5^{8})mod19=(5^{8}mod19 \times 5^{8}mod19)mod19=(4 \times 4)mod19=16$

6) $5^{32}mod19=(5^{16} \times 5^{16})mod19=(5^{16}mod19 \times 5^{16}mod19)mod19=(16 \times 16)mod19=9$

7) $5^{64}mod19=(5^{32} \times 5^{32})mod19=(5^{32}mod19 \times 5^{32}mod19)mod19=(9 \times 9)mod19=5$

 

3. 모듈로 곱셈 성질을 이용하여 원래 값 계산

$5^{117}mod19=(5^{1} \times 5^{4} \times 5^{16} \times 5^{32} \times 5^{64})mod19$

$=(5^{1}mod19 \times 5^{4}mod19 \times5^{16}mod19 \times5^{32}mod19 \times5^{64}mod19)mod19$

$=(5 \times 17 \times 16 \times 9 \times 5)mod19$

$=61200 mod 19$

$=1$

 

따라서 위와 같이 이전의 제곱 값을 계속해서 이용하는 방식으로 큰 수의 모듈로 거듭제곱을 진행할 수 있다.

---

디피-헬먼

디피-헬먼(DH) 키 교환 알고리즘은 대칭키 암호를 공유하는 데 일반적으로 사용되기 때문에 키 교환 알고리즘이라고 한다. 이러한 DH의 보안성은 인수분해를 사용하는 RSA와 달리 이산 로그 문제의 계산 난이도에 의존한다.

 

양의 정수인 g와 k, 소수인 p가 $g^{k}mod \ p=x$와 같은 식을 만족한다고 할 때, g, p, x의 값을 알고 있다면, k를 알 수 있다는 점을 이용한다.

 

먼저 p의 값과 g의 값은 공개되어 있다. 그리고 키를 서로 교환할 앨리스와 밥은 각각 자신의 비밀 지수인 a와 b를 생성한다. 이후 앨리스는 밥에게 $g^{a}mod \ p$를 계산해서 보내고, 밥은 앨리스에게 $g^{b}mod \ p$를 계산해서 보낸다.

 

이때 앨리스는 밥으로부터 받은 값을 자신의 비밀 지수 a를 이용하여 다음과 같이 계산할 수 있다.

$(g^{b}mod \ p)^{a} mod \ p = g^{ab} mod \ p$

마찬가지로 밥 역시 앨리스로 받은 값을 자신의 비밀 지수 b를 이용해서 다음과 같이 계산할 수 있다.

$(g^{a}mod \ p)^{b} mod \ p = g^{ab} mod \ p$

 

따라서 $g^{ab} mod \ p$가 서로 공유한 비밀이 되어 통상적인 대칭키로 사용될 수 있다. 공격자는 $g^{a}mod \ p$와 $g^{b}mod \ p$를 훔쳐볼 수 있지만, 비밀 지수인 a 또는 b가 없다면 $g^{ab} mod \ p$를 알 수는 없다.

중간자 공격

이러한 DH 알고리즘은 중간자 공격에 민감하다. (DH 알고리즘 뿐 아니라 모든 공개키 암호방식이 중간자 공격의 대상이 될 수 있다.)

중간자 공격이란, 공격자가 정보를 주고받는 앨리스와 밥 사이에 서서 오가는 메시지를 가로채는 방식이다. DH 교환에서의 중간자 공격은 다음과 같은 방식으로 이루어진다.

1. 앨리스가 밥에게 $g^{a}mod \ p$를 계산해서 보낸다.
2. 중간에 위치한 공격자는 이를 자신이 가지고, 밥에게는 $g^{t}mod \ p$를 계산해서 보낸다.
3. 밥은 앨리스에게 $g^{b}mod \ p$를 계산해서 보낸다.
4. 공격자는 이 역시 가로챈 다음, 앨리스에게는 $g^{t}mod \ p$를 계산해서 보낸다.
5. 앨리스는 $g^{at} mod \ p$를, 밥은 $g^{bt} mod \ p$를 대칭키로 인지한 상태이다.
6. 공격자는 자신의 비밀 지수인 t를 이용해 $g^{at} mod \ p$와 $g^{bt} mod \ p$를 계산할 수 있다.
7. 각 대칭키를 이용해 양쪽의 정보 교환이 일어날 때마다, 공격자는 해당 정보를 읽고 변경할 수 있다.

그렇다면 이러한 중간자 공격을 막을 수 있는 방법은 무엇일까? 여러 가지 방법이 있지만, 그중에서 가장 대표적으로 전자서명을 하는 방법이 있다. 전자서명의 경우 개인키를 가지고 있는 본인만 서명할 수 있는 방법이기 때문에, 중간에 누군가가 정보를 변경하는 것을 방지할 수 있다.

 

이러한 전자서명 역시 공개키 암호체계를 이용하면 간단하게 구현할 수 있다.

전자서명

공개키 암호체계에서는 모두에게 공개하는 공개키와, 자신만 알고 있는 개인키가 있다. 보통 공개키는 데이터를 암호화하는 데 사용하고, 개인키는 이를 복호화하는 데 사용한다.

 

하지만 만약에 개인키를 이용해 데이터를 암호화하게 된다면 어떻게 될까? 이때는 반대로 공개키를 이용해 복호화를 진행할 수 있다. 하지만 자신이 암호화해 둔 데이터를 모두가 알고 있는 공개키로 복호화가 가능하다면, 이는 과연 의미가 있는 행동일까?

 

놀랍게도 이런 방식을 이용해 현실에서 싸인이나 도장을 찍는 것과 같은 기능을 구현할 수 있다. 이러한 서명은 자기 자신이 해당 문서나 데이터를 보증한다는 뜻을 가지고 있는데, 공개키 암호체계에서 개인키는 자기 자신만이 가지고 있는 키이기 때문에, 이를 이용해서 데이터를 암호화한다는 것은 자신이 해당 데이터를 보증한다는 서명의 개념과 같게 된다.

 

즉, 공개키를 가지고 있는 모든 사람들은 해당 서명을 언제든 복호화해서 확인할 수 있지만, 이 서명자체를 만들 수 있는 주체는 개인키를 가지고 있는 사람만이 가능한 것이다. 따라서 이러한 방식으로 간단하게 전자서명을 구현할 수 있다.

---

타원곡선 암호(ECC)

타원곡선은 특정한 암호체계가 아니다. 보통 공개키 암호체계에서는 복잡한 수학 연산을 요구하는데, 이때 사용할 수 있는 또 하나의 방법이라고 생각하면 된다. 예를 들어 타원곡선을 디피-헬먼에 적용하면 디피-헬먼의 타원곡선 버전이 되는 식이다.

 

우선 타원곡선 암호는 타원곡선 방식을 사용하지 않는 다른 암호방식과 비교했을 때, 같은 수준의 보안성을 위해 필요한 비트 수가 더 적다는 장점이 있다. 따라서 이러한 ECC방식은 휴대용 장비와 같이 자원이 제한되는 환경에서 특히 더 자주 사용된다.

 

타원곡선 E는 아래와 같은 함수로 나타낼 수 있다.

$$ E: \ y^{2}=x^{3}+ax+b$$

 

그리고 이러한 함수를 실제 그래프로 그려보면 다음과 같은 형태를 가진다.

타원곡선

(타원곡선에 대한 내용은 완벽하게 이해가 되지 않아 우선은 접어둔 상태로 유지하도록 하겠습니다.)

---

공개키 암호 용도

기본적으로 대칭키 암호가 할 수 있는 일은 모두 공개키 암호로 수행할 수 있다. 다만 대칭키 암호 방식에 비해 속도가 훨씬 느리다는 것이 문제이다. 따라서 대부분의 공개키 암호는 대칭키 암호를 사용하기 이전에 안전하지 않은 채널을 안전하게 만드는 역할을 한다.

 

간단히 말하자면 속도가 빠른 대칭키 암호방식을 사용하기 위해서는 반드시 송수신자 간에 같은 대칭키를 가지고 있어야 하는데, 서로 키를 나눠가지지 않은 안전하지 않은 상태에서 키를 나눠가질 수 있는 방법으로 공개키 암호 방식을 사용한다는 것이다. 그리고 키를 나눠가진 이후에는 속도가 빠른 대칭키 방식으로 실제 전달할 데이터들을 암호화한다.

 

이처럼 공유키가 불필요하지만 속도가 느린 공개키 방식과 공유키를 설정해야 하지만 속도가 빠른 대칭키 방식을 서로 결합하여 사용하는 방식을 합성 암호체계라고 한다.

전자서명과 부인봉쇄

공개키 암호 방식은 전자서명으로도 사용이 가능하다. 기존의 공개키 암호 방식을 거꾸로 하여, 서명하는 대상이 비밀키를 가지고 암호화를 한다. 그렇다면 다른 모든 사람이 공개된 공개키를 이용해 해당 서명을 복호화해서 확인할 수 있을 것이다. 중요한 건 비밀키를 가지고 있지 않은 사람은 그 사람의 서명을 할 수 없다는 것이다.

 

이러한 전자서명은 부인봉쇄라는 기능을 수행할 수 있다.

 

예를 들어 앨리스가 인터넷 쇼핑몰에서 어떤 물건을 주문했다고 하자. 이때 앨리스와 쇼핑몰은 해당 주문의 무결성을 보장하기 위해 대칭키 K를 이용해 MAC을 계산하고 서로 확인하였다. 하지만 앨리스가 갑자기 마음이 변심해서 해당 주문들을 자신이 주문한 게 아니라고 따질 수 있다. 쇼핑몰의 입장에서는 당황스럽지만 이를 반박할 수 있는 증거가 전혀 없다. 쇼핑몰 역시 앨리스와 공유하는 대칭키 K를 가지고 있기 때문에 이론적으로는 앨리스가 주문한 것처럼 주문서를 위조할 수 있기 때문이다.

 

즉, MAC이 제공하는 무결성은 제삼자로부터 무결성이 훼손되는 것을 방지한다. 서로 공유 대칭키를 가지고 있는 한쪽에서 받은 내용을 변경하는 것은 막지 못한다. 따라서 앨리스는 쇼핑몰이 자신의 주문서를 변경했다고 우길 수 있는 것이다.

 

하지만 만약 MAC 대신 전자서명을 사용한다면 어떨까?

MAC과 마찬가지로 전자서명 역시 무결성을 보장한다. 앨리스가 주문서를 보내면서 해당 주문서를 자신의 비밀키로 암호화한 서명을 함께 보낸다고 하자. 그렇다면 중간에 주문서의 내용이 변조되더라도 쇼핑몰은 앨리스의 서명을 공개키로 풀어보아 해당 주문서가 변조된 것인지 확인할 수 있다.

 

중요한 것은 MAC과 달리 전자서명은 무결성뿐 아니라 부인봉쇄도 제공한다는 것이다. 한마디로 앨리스가 이전처럼 자신이 주문서를 작성한 것이 아니라고 부인하는 것을 사전에 봉쇄할 수 있다. 왜냐하면 해당 전자서명은 앨리스 본인의 개인키로 서명된 것이기 때문에 쇼핑몰을 포함한 제삼자가 변조할 수 없기 때문이다.

전자서명과 암호화의 순서

앨리스가 메시지 M을 밥에게 보낸다고 가정하자. 이때 앨리스는 보안을 중요시 여겨서 비밀성과 부인봉쇄를 모두 원한다. 따라서 앨리스는 암호화와 서명을 동시에 해야 한다. 이때 전자서명을 먼저 하고 암호화를 하는 게 좋을까? 아니면 암호화를 한 다음에 전자서명을 하는 게 좋을까?

 

이에 앞서 먼저 공개키의 암호화, 복호화, 서명의 표기법을 간단히 설명하고자 한다.

• 앨리스의 공개키로 메시지 M을 암호화: $C=\{M\}_{Alice}$
• 앨리스의 개인키로 암호문 C를 복호화: $M=[C]_{Alice}$
• 앨리스가 메시지 M을 서명: $S=[M]_{Alice}$ (서명은 복호화와 같은 연산)

이를 통해 다음의 두 가지 시나리오에 대해 알아보자.

 

선서명 후암호화

앨리스가 밥에게 돈을 갚으라는 메시지 M을 보낸다고 하자. 이를 선서명 후암호화를 이용해 보낸다면 다음과 같은 방식으로 밥에게 전달될 것이다.

$$ \{[M]_{Alice}\}_{Bob}$$

 

먼저 앨리스는 자신의 비밀키로 서명을 한 다음, 밥의 공개키로 서명한 메시지를 암호화하였다. 이를 받아본 밥은 자신의 개인키로 해당 암호를 복호화한 다음, 앨리스의 공개키로 서명을 열어보아 앨리스가 쓴 메시지를 확인할 수 있을 것이다.

 

이때 밥은 돈을 갚으라는 메시지를 보고 화가 났다고 하자. 그래서 앨리스의 서명을 그대로 놔두고, 관련이 없는 트루디의 개인키를 이용해 암호화하여 트루디에게 메시지를 보낸다고 하자. 따라서 트루디에게는 다음과 같은 방식으로 전달될 것이다.

$$ \{[M]_{Alice}\}_{Trudy}$$

 

이를 받아본 트루디는 자신의 개인키로 해당 암호문을 열어볼 것이다. 그리고 안에 앨리스의 서명이 되어있는 메시지를 발견할 것이고, 이를 앨리스의 공개키를 이용해 그 내용을 확인할 수 있을 것이다. 트루디는 앨리스에게 돈을 빌린 적이 없지만 돈을 갚으라는 말을 듣게 되었다. 자신의 공개키를 이용해 암호화했으니 자신에게 보낸 메시지도 맞을 것이고, 그 내용이 앨리스의 개인키로 서명되어 있으니 앨리스가 직접 쓴 내용도 틀림없이 맞을 것이다.

 

따라서 앨리스는 밥의 심술궂은 행동으로 인해 괜히 트루디에게 오해를 사고 말았다.

 

선암호화 후서명

연구원인 앨리스는 연구를 거듭한 끝에 새로운 신약을 개발하였다. 따라서 이를 자신의 상급자인 밥에게 보고하려고 한다. 이때 앨리스는 선암호화 후서명을 이용해 다음과 같은 형태로 메시지를 밥에게 전달하였다.

$$ [\{M\}_{Bob}]_{Alice}$$

 

하지만 동료 연구원인 트루디가 나쁜 마음을 품고 중간 공격자가 되어 해당 메시지를 중간에 가로채었다. 앨리스의 서명은 누구에게나 공개된 공개키로 풀 수 있으므로, 트루디는 앨리스의 서명을 풀어버리고 자신의 서명으로 암호화를 하였다.

$$ [\{M\}_{Bob}]_{Trudy}$$

 

따라서 이를 전달받은 밥은 트루디의 서명이 있는 것을 확인하고, 그 안의 메시지를 자신의 개인키로 복호화하여 살펴본다. 이후 해당 내용이 매우 만족스러웠던 밥은 트루디에게 보너스를 지급할 것이다.

 

이를 통해 알 수 있듯이, 선서명 후암호화를 하든 선암호화 후서명을 하든 모두 문제가 생길 수 있다. 그렇다면 도대체 어떤 방식을 사용해야 공개키를 사용한 암호화와 전자서명을 동시에 안전하게 사용할 수 있을까?

 

이에 대한 내용들은 이후 프로토콜에서 다시 자세히 알아보도록 하자.

---

공개키 기반구조(PKI)

(추후에 내용을 추가할 예정입니다)