키 사전 분배

키 사전 분배(Key Predistribution)는 통신을 시작하기 전에 신뢰기관(키 분배 센터, KDC)이 사용자들에게 키나 키를 계산할 비밀 정보를 미리 나눠 주어, 나중에 두 사용자가 따로 키를 주고받지 않고 서로의 세션 키를 만들게 하는 키 분배 방식이다.

개요

대칭키 암호는 통신하는 두 사람이 같은 키를 미리 가지고 있어야 쓸 수 있다. 이 키를 어떻게 안전하게 나눠 갖느냐가 키 배송 문제이고, 푸는 방법은 크게 셋이다.

방식	키가 정해지는 때	신뢰기관의 역할	예
키 사전 분배	통신 전에 미리	처음에 한 번 비밀 정보를 나눠 주고, 통신할 때는 필요 없다	Blom 방식, Diffie-Hellman 키 사전 분배
온라인 키 분배	통신할 때마다	키 배포 센터가 그때그때 세션 키를 만들어 나눠 준다	커버로스, 니덤-슈로더 프로토콜
공개키를 이용한 분배	통신할 때	필요 없다(공개키가 진짜인지는 PKI가 확인)	상대 공개키로 세션 키를 암호화해 보내기, 디피-헬먼 키 교환

가장 단순한 사전 분배는 KDC 가 모든 사용자 쌍에 서로 다른 키를 하나씩 만들어 주는 것이다. n 명이면 키가 n(n-1)/2 개 필요하고, 사용자마다 n-1 개를 보관해야 해서 사용자가 늘면 감당하기 어렵다. Blom 방식과 Diffie-Hellman 키 사전 분배는 사용자가 작은 비밀 정보 하나만 보관하고 상대마다 다른 키를 계산해 내게 해 이 문제를 줄인다.

Blom 방식

1984년 롤프 블롬(Rolf Blom)이 제안한 방식이다. 키 분배 센터가 두 노드에게 비밀 함수의 값을 미리 보내 두면, 두 노드는 받은 정보와 상대의 공개 정보만으로 둘 사이의 세션 키를 각자 계산한다.

KDC 는 큰 소수 p 위에서 (k+1)×(k+1) 크기의 대칭 비밀 행렬 D 를 고른다. 사용자 i 마다 서로 다른 공개 값 r_i 를 정하고 공개 벡터 g_i = (1, r_i, r_i², …, r_i^k) 를 만든다
KDC 는 사용자 i 에게 비밀 벡터 a_i = D·g_i 를 안전한 방법으로 미리 전달한다. 이것이 사용자가 보관하는 유일한 비밀이다
사용자 i 와 j 가 통신할 때 i 는 K_ij = a_i·g_j, j 는 K_ji = a_j·g_i 를 계산한다. D 가 대칭 행렬이라 두 값이 같다(K_ij = g_i^TDg_j = K_ji)

통신할 때 KDC 와 연락할 필요가 없고 키를 주고받는 메시지도 없다
k 명까지는 서로 짜고 비밀을 모아도 다른 사용자 쌍의 키를 알아낼 수 없다. k+1 명이 모이면 D 를 복원할 수 있으므로 k 를 예상 공모 규모보다 크게 잡는다
노드끼리 미리 키를 가져야 하는 무선 센서 네트워크의 키 관리에서 많이 다룬다

Diffie-Hellman 키 사전 분배

디피-헬먼 키 교환의 원리를 사전 분배에 쓴 것으로, 이산대수 문제의 어려움에 기댄다.

키 분배 센터(신뢰기관)는 큰 소수 p 를 정하고 Z_p 위에서 원시근 g 를 찾아 공개한다
가입자 A 는 개인키 x_A 를 정하고 공개키 y_A = g^x_A mod p 를 계산해 공개한다(인증서나 공개 디렉터리에 둔다). B 도 같은 방법으로 x_B, y_B 를 만든다
A 는 K = y_B^x_A mod p, B 는 K = y_A^x_B mod p 를 계산한다. 둘 다 g^x_Ax_B mod p 로 같다

개인키를 먼저 고르고 그것으로 공개키를 계산한다. 공개키에서 개인키를 거꾸로 구하는 것이 이산대수 문제라 어렵다
소인수분해 문제에 기대는 것은 RSA 이고, Diffie-Hellman 은 소인수분해가 아니라 이산대수 문제를 바탕으로 한다

키 로밍과의 구분

키 로밍(key roaming)은 사용자의 전자서명용 개인키를 안전한 서버에 맡겨 두고 다른 컴퓨터·기기에서도 내려받아 쓰게 하는 서비스다. 개인키를 들고 다니기 어려운 문제를 푸는 것이지, 두 노드 사이에 세션 키를 나눠 주는 분배 방식이 아니다 → 공개키 기반 구조

같이 보기