[암호학] 비대칭키 암호 - 키 배송 문제
비대칭키(공개키) 암호
키 배송 문제
1. 개요
- 대칭암호에서는 양측이 안전하게 통신을 하기 위해서 비밀키를 공유하는 것이 핵심이다.
- 하지만, 대칭키 암호를 사용하려고 하면 키 배송 문제가 발생한다 => 비대칭키 기법이 해결
- 키를 보내지 않으면 수신자는 수신한 암호문을 복호화할 수 없다. 그렇다고 암호화되지 않은 키를 보내면 도청자가 복호화할 수 있다. 키를 보내지 않으면 안되는데 키를 보내서도 안된다. 이것이 대칭키 암호의 키 배송 문제이다.
- 키 배송 문제를 해결하기 위한 방법에는 몇 가지가 있다.
① 키의 사전 공유에 의한 해결
② 키배포 센터에 의한 해결(온라인 키 분배)
③ Diffie-Hellman 키 교환에 의한 해결
④ 공개키 암호에 의한 해결
2. 키 사전 공유에 의한 해결
- 키 사전 분배란 키 관리기관(TA, Trusted Authority)이 사전에 임의의 두 사용자 (A,B)에게 비밀 경로를 통하여 임의 키 K(A,B) = K(B,A)를 선택하여 전달하는 방법
2.1 키 사전 공유의 문제
- 이 방법은 일반적으로 TA와 네트워크 상의 모든 사용자 사이에 안전한 통로가 필요하다.
- 사용자가 많은 경우에 TA는 물론 사용자들도 많은 키를 관리해야 하는 문제점이 있다 => n(n-1) / 2
3. 키배포 센터에 의한 해결(온라인 키 분배)
(1) 개요
- 암호 통신이 필요해질 때마다 통신용 키를 키배포 센터(KDC, Key distribution center)라는 신뢰받는 제3자에 의뢰해서 개인과 키배포 센터 사이에서만 키를 사전에 공유하는 것이다. (TA가 네트워크 상의 모든 사용자와 필요할 때마다 키를 공유하는 방법이다)
- 회사 안에 키배포 센터의 역할을 하는 컴퓨터를 지정해 둔다. n명의 사원이 있다면 n개의 키를 컴퓨터 데이터베이스에 저장한다.
(2) 단계별 순서
① 송신자는 키배포 센터에 수신자와 통신하고 싶다고 신청한다.
② 키배포 센터는 의사난수 생성기를 사용하여 세션키(K)를 만든다. 이것은 송신자와 수신자의 이번 통신만을 위한 일시적인 키이다.
③ 키배포 센터는 데이터베이스에서 송신자의 키(KA)와 수신자의 키(KB)를 꺼낸다.
④ 키배포 센터는 수신자의 키를 사용하여 세션키를 암호화해서 수신자에게 보낸다.
⑤ 키배포 센터는 송신자의 키를 사용하여 세션키를 암호화해서 송신자에게 보낸다.
⑥ 송신자는 키배포 센터에서 온 세션키를 복호화해서 세션키를 얻는다.
⑦ 송신자는 세션키를 사용하여 수신자에게 보낼 메일을 암호화한다.
⑧ 송신자는 수신자에게 암호문을 보낸다.
⑨ 수신자는 키배포 센터에서 온 세션키를 복호화해서 세션키를 얻는다.
⑩ 수신자는 세션키를 사용하여 송신자에게 온 암호문을 복호화 한다.
※ 송신자와 수신자는 키분배 센터로부터 암호화 복호화에 사용할 세션키를 얻는 것이다.
4. Diffie-Hellman 키 교환에 의한 해결
(1) 개요
- Diffie-Hellman 키 교환은 1976년 공개키 암호방식을 최초로 제안한 디피(Diffie)와 헬먼(Hellman)이 발명한 알고리즘이다.
- 공개키 암호방식의 개념을 이용하여 두 사용자 간에 공통의 암호화키를 안전하게 공유할 수 있는 방법을 제시하였으며, 많은 키 분배 방식에 관한 연구의 기본이 되었다.
- Diffie-Hellman 프로토콜 방법에서는 양쪽 통신주체가 KDC없이 대칭 세션키를 생성한다. 대칭키를 만들기 전에 양쪽은 두 개의 수 p 와 g 를 선택해야 한다. 여기서 p는 매우 큰 소수로서 300자리가 넘는 십진수(1024비트)이다.
- 소수 p와 g는 비밀로 할 필요는 없고, 도청자에게 알려져도 문제 없다.
- "키 교환" 이라는 이름이 붙어 있지만 실제로는 키를 교환하는 것이 아니라 공유할 키를 계산하여 만들어 내는 것이다.
- 이산대수 문제를 풀기 어렵다는 것을 근거로 만들어졌다.
(2) 절차
(2-1) 예제
- 위 과정이 도저히 이해가 안가, 많은 설명을 찾은 끝에 가장 쉬운 방법을 설명한 글을 찾았다.
- 실제 숫자를 통해 예를 들어 설명한다.
- 여기서는 설명을 위해 작은 크기의 소수를 사용하지만, 실제 응용에서는 안전을 위해 아주 큰 소수를 사용한다.
- 공개된 정보는 파란색으로, 비밀 정보는 빨간색 굵은 글씨로 표시한다.
① 송신자와 수신자는 p=23, g=5를 사용하기로 합의한다. (23과 5는 소수이다)
② 송신자가 비밀 정보를 전송하기 위해 임의의 정수 a=6 을 고른 후, 수신자에게 A=g^a mod p 를 전송한다.
- A = 5^6 mod 23
- A = 15,625 mod 23
- A = 8
③ 수신자는 임의의 정수 b=15 를 고르고, 수신자에게 B=g^b mod p 를 전송한다.
- B = 5^15 mod 23
- B = 30,517,578,125 mod 23
- B = 19
④ 송신자는 수신자에게서 받은 B 를 바탕으로 s = B^a mod p 를 계산한다.
- s = 19^6 mod 23
- s = 47,045,881 mod 23
- s = 2
⑤ 수신자는 송신자에게서 받은 A 를 바탕으로 s = A^b mod p 를 계산한다.
- s = 8^15 mod 23
- s = 35,184,372,088,832 mod 23
- s = 2
⑥ 송신자와 수신자는 비밀키 s = 2 를 공유하게 되었다.
⑦ s 는 세션키에 사용될 대칭키이다.
※ 위 글이 이해가 안되시는 분을 위하여 좀 더 쉬운 설명을 하겠습니다.
1. 송신자와 수신자는 알려진(소수) - p=3, g=5 을 사용하기로 서로 합의함
[송신자]
비밀(정수) - a:2 선택
[수신자]
비밀(정수) - b:3 선택
---------------------------------------------------------------------
[송신자]
A=5^2 mod 3
A=1
[수신자]
B=5^3 mod 3
B=2
---------------------------------------------------------------------
송신자는 A=1 값을 수신자에게 전달
수신자는 B=2 값을 송신자에게 전달
---------------------------------------------------------------------
[송신자]
s=2^2 mod 3
s=1
[수신자]
s=1^3 mod 3
s=1
송신자와 수신자는 s=1 값을 서로 공유한다.
여기서의 s는 세션에 사용될 대칭키 이다.
(3) Diffie-Hellman의 안전성
① 이상대수 공격
- 키 교환의 안전성은 이산대수 문제를 풀기 어렵다는데 기반을 두고 있다.
② 서비스 거부 공격(Dos, Denial of Service) 취약점
- Diffie-Hellman 기법은 지수 함수에 기초하고 있으므로 계산이 복잡하여 많은 수의 장치와 동시에 통신을 하는 경우 비밀키 생성에 큰 지연 시간이 발생할 수 있다.
- 따라서 Diffie-Hellman 기법은 제3자에 의한 Dos 공격에 대한 취약점을 가지고 있다. 즉, 악의적인 제3자가 공격 대상 서버에 대해 IP 스푸핑 등을 통해 위조한 키 생성 요청을 동시에 다수 요청함으로써 키 생성 부담으로 서비가 마비되도록 공격할 수 있다.
③ 중간자 공격(man-in-the-middle attack, MITM)에 취약
- 중간자 공격은 네트워크 통신을 조작하여 통신 내용을 도청하거나 조작하는 공격 기법이다. 중간자 공격은 통신을 연결하는 두 사람 사이에 중간자가 침입하여, 두 사람은 상대방에게 연결했다고 생각하지만 실제로는 두 사람은 중간자에게 연결되어 있으며 중간자가 한쪽에서 전달된 정보를 도청 및 조작한 후 다른 쪽으로 전달한다.
- 많은 암호 프로토콜은 중간자 공격을 막기 위하여 전자서명과 공개키 인증서 등을 사용한다.
- 예를 들어, TLS/SSL 프로토콜은 공개 키를 기반으로 한 인증을 사용한다.
(4) Diffie-Hellman 알고리즘의 응용
- 중간자 공격 취약점 문제는 세션키를 생성하는 통신 당사자 A와 B가 교환하는 메시지에 대한 인증을 통해 해결할 수 있고, IP 스푸핑을 통한 Dos 공격은 키 생성 요청자를 확인하기 위한 쿠키를 사용함으로써 방지할 수 있다.
- 현재 Diffie-Hellman 기법 기반의 대칭키 분배는 중간자 공격와 DoS 공격 취약점을 보완하여 IPSec, SSL 등 다양한 인터넷 보안 프로토콜에 광범위하게 적용되고 있다.
5. 공개키 암호에 의한 해결
(1) 개요
- 대칭키 암호에서 "암호화키"와 "복호화키"는 같은 것이다. 그러나 공개키 암호에서는 "암호화키"와 "복호화키"는 다른 것이다.
- 수신자는 미리 "암호화키"를 송신자에게 알려 준다. 이 "암호화키"는 도청자에게 알려져도 괜찮다. 송신자는 "암호화키"로 암호화하여 수신자에게 보낸다.
- 복호화할 수 잇는 것은 "복호화키"를 가지고 있는 사람(수신자)뿐이다. 이렇게 하면 "복호화키"를 수신자에게 배송할 필요가 없어진다.
(2) 암호화 키와 복호화 키의 구별
- 송신자가 필요한 것은 암호화 키뿐이다.
- 수신자가 필요한 것은 복호화 키뿐이다.
- 도청자에게 알려지면 곤란한 것은 복호화 키이다.
- 암호화 키는 도청자에게 알려져도 괜찮다.
(3) 공개키
- 공개키 암호에서 암호화 키는 일반에게 공개할 수 있다.
- 공개해도 상관이 없으므로 이 키를 공개키라 부른다.
(4) 개인키(private key)
- 복호화 키는 절대로 공개해서는 안된다.
- 이 키는 당신만이 사용하는 것이다. 그러므로 이 키를 개인키(private key)라 부른다.
- 개인키는 다른 사람에게 보이거나, 건네주거나 해서는 안되고 자신의 통신 상대에게도 보여서는 안된다.
(5) 대칭암호의 비밀키와 개인키
- 대칭 암호에서 사용하는 키는 비밀키(secret key) 라고 일컬어 진다.
- 공개키 암호에서 사용되는 두 개의 키는 공개키(Public key)와 개인키(private key)라고 한다.
- 항상 개인키는 비밀로 해야 하지만 비밀키라고 부르지 않고 개인키라고 부르기로 한다. (대칭암호에서 사용하는 비밀키와 혼동하지 않도록 하기 위함)
(6) 키 쌍(key pair)
- 공개 키와 개인 키는 둘이 한 쌍이 된다. 이 쌍을 가리켜 키 쌍(Key pair)라고 부른다.
- 공개 키로 암호화한 암호문은 그 공개 키와 쌍이 되는 개인키가 아니면 복호화할 수 없다.
- 키 쌍을 이루고 있는 2개의 키는 서로 밀접한 관계(수학적인)가 있다. (공개키와 개인키를 별개로 만들 수는 없다)
※ 마지막 중요 체크
★ 키 배송 문제 해결
- 키의 사전 공유에 의한 해결
- 키배포 센터에 의한 해결
- Diffie-Hellman 키 교환에 의한 해결
- 공개키 암호에 의한 해결