소수 p
공유 비밀
이브의 추측 횟수
모든 지수를 시도하는 데 걸리는 시간
앨리스
공개 (이브도 봄)
밥

표시

디피-헬먼 키 교환에 대해 더보기

디피-헬먼 키 교환

한 번도 만난 적 없는 두 사람이, 누군가 자신들의 말을 모두 엿듣고 있는 상황에서 어떻게 비밀 키를 정할 수 있을까요? 1976년 휫필드 디피와 마틴 헬먼이 그 답을 찾았고, 그 답은 지금 인터넷의 거의 모든 보안 연결을 지키고 있습니다. 앨리스와 밥을 따라 다섯 단계를 한 번은 물감 섞기로, 한 번은 실제 숫자로 거쳐 본 다음, 도청자 이브가 공격하게 해 보세요. 작은 수에서는 이브가 눈 깜짝할 새 이기지만, 실제로 쓰이는 크기에서는 우주의 나이보다 긴 시간이 필요합니다. ‘다음 단계’를 누르면 앨리스와 밥이 비밀을 정하는 과정을 따라갈 수 있습니다. 이브는 둘이 보내는 모든 것을 읽습니다. ‘이전’을 누르면 한 단계 뒤로 갑니다. 각 값은 물감과 숫자로 함께 표시됩니다. 잠긴 값은 주인을 절대 떠나지 않습니다. 오른쪽에서 더 큰 소수나 다른 비밀을 고르거나 ‘새 비밀’을 누르세요. 마지막 단계에서 ‘이브가 공격하게 하기’를 누르면 이브가 맞는 지수를 찾을 때까지 모든 지수를 시도합니다. 작은 소수에서는 쉽지만 실제로 쓰이는 소수에서는 가망이 없습니다.

작동 원리

  1. ‘다음 단계’를 눌러 공개 합의, 비밀, 메시지, 공유 결과로 이어지는 교환 과정을 따라가세요.
  2. 각 값을 물감과 숫자로 함께 보면서 어떤 값이 비공개로 남고 어떤 값을 이브가 읽을 수 있는지 확인하세요.
  3. 마지막 단계에서 ‘이브가 공격하게 하기’를 누른 다음, 더 큰 소수를 골라 이브의 가능성이 얼마나 빨리 사라지는지 보세요.

교환의 원리

앨리스와 밥은 먼저 소수 p와 수 g를 공개적으로 합의합니다. 그다음 각자 비밀 숫자를 하나씩 고르는데, 앨리스는 a, 밥은 b를 골라 자기만 알고 있습니다. 앨리스는 밥에게 A = gᵃ mod p를 보내고, 밥은 앨리스에게 B = gᵇ mod p를 보냅니다. 마지막으로 앨리스는 Bᵃ mod p를, 밥은 Aᵇ mod p를 계산합니다. 두 결과 모두 g의 a·b제곱 mod p와 같으므로, 둘은 이제 한 번도 회선을 지나간 적 없는 숫자를 공유하게 됩니다. p, g, A, B를 본 이브에게는 그런 지름길이 없습니다.

이브가 막히는 이유

gᵃ mod p는 반복 제곱법 덕분에 수백 자리 수라도 빠르게 계산할 수 있습니다. 거꾸로 결과에서 지수 a를 찾는 것은 이산 로그 문제이며, 잘 고른 소수에 대해서는 빠른 방법이 알려져 있지 않습니다. 이 데모의 작은 소수라면 이브는 모든 지수를 시도해 보기만 하면 됩니다. 앱은 이브의 추측 횟수를 세고 전체 탐색에 얼마나 걸릴지 추정합니다. 소수가 1비트 늘어날 때마다 작업량이 두 배가 되므로, 인터넷에서 쓰이는 2048비트 소수에서는 무차별 대입 탐색이 도저히 닿을 수 없는 일이 됩니다. 물감 버전도 같은 생각을 담고 있습니다. 색을 섞기는 쉽지만, 혼합색을 원래 색들로 다시 분리하는 것은 사실상 불가능합니다.

자주 묻는 질문

물감 비유는 왜 통하나요?

물감을 섞기는 쉽고 되돌릴 수 없습니다. g를 거듭제곱하고 mod p를 취하는 것이 하기는 쉽고 되돌리기는 어려운 것과 같습니다. 앨리스와 밥은 각자 공통의 색에 자기 비밀 색을 더하고 혼합색을 맞바꿉니다. 그런 다음 각자 받은 혼합색에 자기 비밀 색을 더합니다. 둘 다 공통의 색에 두 비밀 색이 더해진 색에 이르지만, 이브는 두 가지 색이 섞인 혼합색 두 개만 볼 뿐 이를 분리할 수 없습니다. 여기서는 물감을 같은 양씩 섞으므로 순서는 상관없습니다. (gᵃ)ᵇ = (gᵇ)ᵃ인 것과 마찬가지입니다.

g는 무엇이고 왜 원시근이어야 하나요?

g는 생성원입니다. g의 거듭제곱 g¹, g², …, g^(p−1) mod p는 1부터 p − 1까지의 모든 수를 거칩니다. 그래서 공개되는 값이 모든 가능성에 고루 퍼지고, 이브가 그로부터 얻는 정보는 가능한 한 적어집니다. 앱은 각 소수에 대해 그런 수 중 가장 작은 것을 고릅니다. 예를 들어 p = 23이면 g = 5입니다.

디피-헬먼이 제 메시지를 암호화하나요?

아니요. 공유 비밀을 정할 뿐입니다. 그 비밀은 AES 같은 빠른 대칭 암호의 키로 쓰이고, 실제 데이터는 그 암호가 암호화합니다. 모든 HTTPS 연결이 이렇게 동작합니다. 키 교환(보통 타원 곡선 사용) 뒤에 대칭 암호화가 이어집니다.

이브가 밥인 척할 수 있나요?

그 자체만으로는 가능합니다. 중간자가 앨리스와 한 번, 밥과 또 한 번 교환을 하고 모든 것을 중계할 수 있습니다. 실제 프로토콜은 서버가 디지털 서명과 인증서로 자신의 신원을 증명하게 하여 이를 막고, 교환이 인증되도록 합니다.

서버로 전송되는 것이 있나요?

아니요. 모든 숫자, 물감 섞기, 이브의 공격은 브라우저 안에서 계산되며, 설정은 이 브라우저의 로컬 저장소에 보관됩니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

편집기로 이동