키 배송 문제(key distribution problem)

키 배송 문제

대칭 키 암호 사용 시 키를 상대에게 보내지 않으면 수신자는 복호화할 수 없고, 키를 보내면 도청자가 이를 복호화할 수 있는 '키 배송 문제'가 발생할 수 있다.

---

키 배송 문제 해결방법

키의 사전 배포

• 사전에 안전한 방법으로 키를 건네주는 방식으로 기본적으로 모든 사용자 사이에 안전한 통로가 필요하다.
• 사용자가 많은 경우에는 그만큼 많은 키를 관리해야 하는 문제점이 있다.
  이 때문에 매우 복잡하고 관리 비용이 많이 지불된다.
• 공격자가 도중에 가로챌 위험이 존재한다.

키 배포 센터(KDC, key distribution center)

• 암호 통신이 필요해질 때마다 통신용 키를 키 배포 센터라는 신뢰받는 3자에 의뢰해 개인과 키 배포 센터 사이에서만 키를 사전에 공유하는 방식이다.
• 사용자가 많아질수록 키 배포 센터의 부하가 커지며, 시스템에 문제가 생겼을 때 전체의 암호 통신이 마비된다.
• 공격자가 키 배포 센터를 공격할 경우, 모든 키가 쓸모없게 된다.

키 배포 센터 사용 절차

1. 앨리스는 밥과의 통신을 신청한다.
2. KDC는 의사 난수 생성기를 사용하여 세션 키($k$)를 만든다. 이것은 이번 통신만을 위한 일시적인 키다.
3. KDC는 데이터베이스에서 앨리스의 키($ka$)와 밥의 키 ($kb$)를 꺼낸다.
4. KDC는 앨리스의 키를 사용하여 세션 키를 암호화($C_a=E_{ka}(k)$)해서 앨리스에게 보낸다.
5. KDC는 밥의 키를 사용하여 세션 키를 암호화($C_b=E_{kb}(k)$)해서 밥에게 보낸다.
6. 앨리스는 KDC에서 온 세션 키 (앨리스의 키로 암호화되어 있는 키)를 복호화($K=D_{ka}(C_a)$) 해서 세션 키를 얻는다.
7. 앨리스는 세션 키를 사용하여 밥에게 보낼 메일을 암호화($C=E_k(M)$)해 보낸다.
8. 밥은 KDC에서 온 세션 키(밥의 키로 암호화되어 있는 키)를 복호화($K=D_{kb}(C_b)$)해서 세션 키를 얻는다.
9. 밥은 세션키를 사용하여 앨리스에게서 온 암호문을 복호화($M=D_k(C)$)한다.
10.  앨리스와 밥은 세션키를 삭제한다.

Diffie-Hellman 키 교환

• Whitfield Diffie와 Martin Hellman이 제안한 최초의 비밀키 교환 알고리즘이다.
• 공개 키 암호방식의 개념을 이용하여 두 사용자 간에 공통의 암호화 키를 안전하게 공유할 수 있는 방법을 제시하였으며, 많은 키 분배 방식에 관한 연구의 기본이 되었다.
• 대칭 키 방식이 '키는 이미 정해져 있고 이를 어떻게 공유할까?' 라면,
  Diffie Hellman 키 교환 방식은 '정해진 키 값은 없고, 특정 변수를 받아 각자 계산해 비밀키를 만들어내는 것'이다.
• 대칭 키를 만들기 전에 양쪽은 두 개의 수 $p$와 $g$를 선택하며 p는 안전을 위해 10진수 수백~수천 자리 크기의 큰 소수를 사용한다.^[각주:1]
• Diffie-Hellman key agreement(키 합의)로 부르기도 한다.

Diffie-Hellman 키 교환 절차

1. 먼저 앨리스가 매우 큰 소수 $p$와, $1$과 $p-1$사이의 정수 $g$를 선택한다. ($1≤g≤p-1$)
2. 앨리스는 $p$와 $g$를 밥과 공유한다. 이때 $p$와 $g$는 누가 알아도 상관없다.
3. 앨리스가 정수 $a$를 선택한다. 이 정수는 앨리스만 알고 있다.
4. 앨리스가 $A=g^a mod p$, 즉 $g^a$를 $p$로 나눈 나머지 $A$값을 구한다.
5. 밥이 마찬가지로 정수 $b$를 선택해 $B=g^b mod p$를 계산한다.
6. 앨리스와 밥이 결괏값인 $A, B$를 서로에게 전송한다.
7. 앨리스는 $B^a mod p$를 계산하고 밥은 $A^b mod p$를 계산한다.
8. $B^a mod p = (g^b)^a mod p = g^{ab} mod p$ / $A^b mode p = (g^a)^b mod p = g^{ab} mod p $
   를 만족하기 때문에 서로는 $g^ab mode p$라는 공통된 비밀키를 얻는 것이다.
   
   

앨리스와 밥 이외의 인물은 $a$와 $b$를 알 수 없으며, $g$, $p$, $g^amodp$, $g^bmodp$를 알 수 있다.

 

Diffie-Hellman 키 교환 예

쉬운 설명을 위해 작은 크기의 소수를 사용하지만, 원래는 안전을 위해 아주 수백~수천 자리 크기의 큰 소수를 사용한다.

공개된 정보 - 파란색 / 비밀 정보 - 빨간색

1. 앨리스와 밥은 p=23, g=5를 사용하기로 합의한다.
2. 앨리스가 비밀 정보를 전송하기 위해 임의의 정수 a=6을 고른 후, 밥에게 $A=g^amodp$ 을 전송한다.
   - B = 5^6 mod 23
   - B = 15,625 mod 23
   - B = 8
3. 밥은 임의의 정수 b=15를 고르고, 앨리스에게 $B =g^bmodp$ 를 전송한다.
   - B = 5^15 mod 23
   - B = 30,517,578,125 mod 23
   - B = 19
4. 앨리스는 밥에게서 받은 B를 바탕으로$s = B^amodp$ 를 계산한다.
   - s = 19^6 mod 23
   - s = 47,045,881 mod 23
   - s = 2
5. 밥은 앨리스에게서 받은 A를 바탕으로 $s=A^bmodp$ 를 계산한다.
   - s = 8^15 mod 23
   - s = 35,184,372,088,832 mod 23
   - s = 2
6. 앨리스와 밥은 이제 비밀 키 s = 2를 공유하게 되었다.

 

Diffie-Hellman 키 교환의 안정성

• $p$가 충분히 클 경우, 외부에서 비밀 키를 알아내기 위해 도청을 하는 공격자는 $g^a$나 $g^b$를 통해 $s$를 알아낼 수 없다.
• 앨리스와 밥은 두 사람 만이 아는 비밀 키 $s$를 갖게 되었으므로, 대칭 키 암호를 이용해 이후의 통신을 암호화할 수 있다.
• $p$나 $a$, $b$가 너무 작을 경우, 도청자는 가능한 모든 조합을 다 계산해보는 방식으로 $p, a, b$를 알아낼 수 있다.
• 만약 $p$가 최소 300자리의 소수이고, $a$와 $b$가 각각 100자리 이상의 정수일 경우, 현재 인류가 보유한 모든 컴퓨터를 동원해도 공개된 정보로부터 비밀 키를 알아낼 수 없다
• 도중 인증 단계가 없기 때문에 중간자 공격(man-in-the-middle attack)에 취약하다.
  이러한 공격은 전자 서명과 공개키 인증서 등을 이용해야 한다.

공개 키 암호화

• 암호화/복호화에 키가 같은 대칭 키 암호와는 달리 암호화/복호화 키가 서로 다른 방식이다.
• 복호화 키를 전달할 필요가 없기 때문에 중요한 정보가 도청될 걱정이 없다.

공개 키 암호화 절차

1. 수신자는 미리 암호화 키를 송신자에게 알려준다. 이 암호화 키는 도청당해도 아무 문제없다.
2. 송신자는 받은 암호화 키로 암호화하여 수신자에게 보낸다.

이 암호화 키로 암호화된 데이터를 복호화할 수 있는 사람은 오직복호화 키를 가진 수신자뿐이다.

1. $p$와 $g$자체는 비밀로 할 필요 없다. 공격자에게 알려져도 아무 문제없다. [본문으로]