디피-헬먼 키 교환 해설
수천 년 동안 비밀 메시지를 보내려면 먼저 비밀 키를 직접 만나서 또는 전령을 통해 공유해야 했습니다. 1976년 스탠퍼드의 두 연구자는 누구나 볼 수 있는 곳에서 메시지를 주고받는 것만으로 두 당사자가 무에서 공유 키를 만들어 낼 수 있음을 보였습니다. 이 아이디어는 공개 키 암호의 시대를 열었고, 브라우저에 자물쇠가 표시될 때마다 지금도 작동하고 있습니다.
키 분배 문제
AES 같은 암호는 키만큼만 안전하며, 양쪽 모두 같은 키가 필요합니다. 1976년 이전에는 키를 비밀리에 전달해야 했습니다. 외교 행낭, 믿을 만한 전령, 또는 미리 인쇄한 암호책을 통해서였습니다. 지금 당장 안전하게 대화하고 싶은 낯선 두 사람, 예를 들어 인터넷의 상점과 고객에게는 불가능한 일입니다. 휫필드 디피와 마틴 헬먼의 논문 〈New Directions in Cryptography〉(암호학의 새로운 방향)는 사전에 공유한 비밀이 전혀 필요 없는 방법으로 이 문제를 해결했습니다.
시계 위의 산술
이 교환은 모듈러 연산을 사용합니다. p시간짜리 시계 위에서 계산하는 것으로, p는 큰 소수입니다. 이 시계 위에서 거듭제곱은 놀라운 방식으로 움직입니다. g가 원시근이면 g, g², g³, … mod p는 여기저기 뛰어다니며, 반복되기 전에 1부터 p − 1까지의 모든 시각을 무작위처럼 보이는 순서로 방문합니다. gᵃ mod p를 계산하는 것은 빠르며, a의 이진 자릿수 정도의 곱셈이면 됩니다. 이를 되돌리는 것은 그렇지 않습니다.
단계별 교환 과정
앨리스와 밥은 p와 g를 공개적으로 합의합니다. 앨리스는 비밀 a를 골라 A = gᵃ mod p를 보내고, 밥은 비밀 b를 골라 B = gᵇ mod p를 보냅니다. 앨리스는 Bᵃ = (gᵇ)ᵃ를, 밥은 Aᵇ = (gᵃ)ᵇ를 계산하며, 둘 다 mod p로 계산합니다. 지수의 순서는 상관없으므로 둘 다 g^(ab) mod p를 얻습니다. 고전적인 작은 예인 p = 23, g = 5, a = 6, b = 15에서 앨리스는 8을, 밥은 19를 보내고, 둘 다 공유 비밀 2에 이릅니다.
이산 로그 문제
이브는 p, g, A, B를 봅니다. A = gᵃ mod p에서 a를 찾을 수 있다면 앨리스와 똑같이 비밀을 계산할 수 있습니다. 이것이 이산 로그 문제입니다. 수체 체와 같이 알려진 가장 좋은 고전 알고리즘은 모든 지수를 시도하는 것보다 훨씬 빠르지만, 여전히 자릿수의 어떤 거듭제곱보다도 빠르게 늘어나는 시간이 필요합니다. 2048비트 소수에서는 현존하는 어떤 컴퓨터로도 이 문제를 풀 수 없습니다. 더 빠른 방법이 가능한지는 알려져 있지 않으며, 교환의 안전성은 그 믿음에 기대고 있습니다.
중간자
디피-헬먼은 엿듣는 사람으로부터는 보호해 주지만 사칭하는 사람으로부터는 보호해 주지 못합니다. 앨리스와 밥 사이에 자리 잡은 맬러리는 두 사람 각각과 교환을 한 번씩 하고 메시지를 전달하면서 모든 것을 읽을 수 있습니다. 방어책은 인증입니다. HTTPS에서는 서버가 신뢰할 수 있는 기관이 인증한 키로 교환의 자기 몫에 서명하므로, 브라우저는 자신이 정말로 올바른 사이트와 통신하고 있음을 알 수 있습니다. 키 교환과 서명은 늘 함께합니다.
누가 발명했을까?
디피와 헬먼은 1976년에 발표했으며, 이는 랠프 머클의 아이디어를 바탕으로 한 것이었고 헬먼은 나중에 머클의 공로도 인정해 달라고 요청했습니다. 1997년 영국 정보기관 GCHQ는 자신들의 수학자들이 먼저 도달했다는 사실을 공개했습니다. 제임스 엘리스는 1970년에 공개 키 암호의 아이디어를 떠올렸고, 클리퍼드 콕스는 1973년에 RSA와 비슷한 체계를 찾아냈으며, 맬컴 윌리엄슨은 1974년에 같은 키 교환을 발견했지만, 모두 20년 넘게 비밀로 유지되었습니다.
오늘날의 디피-헬먼
현대의 연결은 대부분 타원 곡선 디피-헬먼을 사용합니다. 훨씬 짧은 숫자로 같은 안전성을 제공하며, 예를 들어 TLS 1.3, Signal, WhatsApp에서 쓰이는 X25519 곡선이 있습니다. 연결마다 새로운 비밀 쌍을 사용하면 전방향 안전성을 얻습니다. 나중에 서버의 장기 키가 도난당하더라도 과거의 대화는 안전하게 남습니다. 약한 매개변수는 여전히 위험 요소로, 2015년의 Logjam 공격이 오래된 512비트 소수에서 이를 보여 주었습니다. 또한 쇼어 알고리즘을 실행하는 대형 양자 컴퓨터는 고전적인 디피-헬먼과 타원 곡선 디피-헬먼을 모두 깨뜨릴 수 있으며, 그래서 지금 양자 내성 키 교환이 이들과 함께 도입되고 있습니다.
직접 살펴보기
디피-헬먼 시각화 도구를 열어 앨리스, 공개 채널, 밥이 아는 것을 보여 주는 보드에서 다섯 단계를 물감과 숫자로 따라가 보세요. 23부터 2,147,483,647까지의 소수를 고르고, 비밀을 직접 정하고, 이브가 모든 지수를 시도해 공격하게 해 보세요. 작은 소수에서는 이브가 즉시 성공하는 것을 지켜보고, 소수가 길어질수록 예상 탐색 시간이 어떻게 늘어나는지 확인할 수 있습니다.
자주 묻는 질문
디피-헬먼은 RSA와 같은가요?
아니요. 둘 다 1970년대의 공개 키 방식이긴 합니다. 1977년에 발표된 RSA는 공개 키와 개인 키로 암호화와 서명을 할 수 있으며, 큰 수를 소인수분해하기 어렵다는 점에 기반합니다. 디피-헬먼은 공유 비밀을 정할 뿐이며 이산 로그 문제에 기반합니다.
실제로 쓰이는 숫자는 얼마나 큰가요?
고전적인 디피-헬먼은 최소 2048비트, 즉 십진수로 약 617자리인 소수를 사용하며, 3072비트나 4096비트도 자주 씁니다. 타원 곡선 방식은 256비트 정도의 키로 비슷한 안전성을 얻습니다.
왜 1비트 늘어날 때마다 이브의 작업량이 두 배가 되나요?
1비트 더 긴 소수는 약 두 배 크므로 시도해야 할 지수도 약 두 배가 됩니다. 실제 공격은 모든 지수를 시도하는 것보다 영리하지만, 그 비용은 여전히 소수의 크기에 따라 매우 빠르게 늘어납니다.
앨리스와 밥에게 왜 소수가 필요한가요?
법이 소수이면 1부터 p − 1까지의 모든 수에 역원이 있고 원시근이 존재하므로, g의 거듭제곱이 모든 가능성을 덮습니다. p − 1의 작은 인수를 이용하는 지름길을 막기 위해 (p − 1)/2도 소수인 안전 소수를 고르는 경우가 많습니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
디피-헬먼 시각화 도구 열기