머클-디피-헬먼
1970년대 이전의 어떤 암호화 기법도 비보안 채널만 가지고 보안을 획득할 수 있는 방법을 제공하지 못했습니다. 비보안 채널에 보안을 부여하려면 반드시 다른 보안 채널(예를 들어 직접 만나서 암호표 주고받기)을 경유해야 한다는 것이 당시의 믿음이었습니다.
이것이 깨진 시점은 엄밀히 말하면 1973년입니다. 영국의 정보기관인 GCHQ에서 일하던 클리포드 콕스가 비밀리에 공개 키 암호학의 실용적 방법을 창안했습니다. 그러나 냉전 시대였고, 암호학이 국가적·군사적 기밀로 취급되던 시절이었고, 당시로서는 써먹기도 힘든 이론으로 취급되어 빛을 보지 못했습니다. 콕스의 업적은 기밀이 해제되는 1997년까지 공표되지 않았습니다.
아무튼 음지의 이야기는 없었던 셈치고, 양지에서는 윗필드 디피와 마틴 헬먼의 1976년 논문이 최초의 공개 키 암호학이라고 알려져 있습니다. 하지만 자세히 살펴 보면 디피와 헬먼 말고 다른 인물이 있었습니다.
랠프 머클은 1974년에 UC 버클리의 학생이었는데, CS244 ‘컴퓨터 보안’ 과목을 수강합니다. 이 과목은 1970년에 랜스 호프먼이 개설한 것으로, 컴퓨터 보안을 주제로 하는 최초의 정규 대학 강의였습니다. 머클은 암호학의 새로운 차원을 열어젖힐 획기적인 발상을 가지고 과제 제안서를 씁니다.
(전설의 시작.)
당초 머클의 의도는 기존의 믿음을 뒤엎으려는 것이 아니라 오히려 기존의 믿음을 증명하는 것이었습니다. 머클도 다른 수학자들과 마찬가지로 “비보안 채널로 통신해서 보안 채널을 구성하는 것은 불가능하다”라고 생각했던 것입니다. 이제 와서 보면 쉽게 알 수 있는 것이지만 그런 증명은 가능할 리가 없는데, 왜냐하면 실제로 오늘날 사방팔방에 깔려있는 웹 브라우저가 바로 “비보안 채널로 통신해서 보안 채널을 구성하는 기술”을 내장하고 있기 때문입니다.
그래서 증명은 계속 실패하고, 아무리 궁리해봐도 불가능성의 증명이 안 되니까 머클은 “불가능하다는 것을 증명하기가 이렇게 어렵다니, 혹시 가능한 것은 아닌가?“라는 의문을 갖게 됩니다. 그러다가 머클은 어려운 수학 문제를 이용해 통신 당사자와 공격자의 메시지 해독 난이도를 다르게 함으로써 통신이 노출된 채로도 정보를 효과적으로 숨길 수 있는 방법을 정말로 창안해버리고 마는데, 이것이 오늘날 ‘머클의 퍼즐’로 불리는 개념입니다. 다시 말해서
- 서로 만난 적이 없는 사람들의 통신을
- 처음부터 끝까지 도청했는데도
- 통신의 내용을 알 수 없다. (?!)
라는 놀라운 일이 가능해진 것입니다. 이것은 정보에 대한 인간의 믿음을 송두리째 뒤집어 놓은 실로 혁명적인 업적으로서, 1980년대 암호학의 르네상스 시기에 쏟아져나온 수많은 암호화 기법은 결국 이것을 여러 가지 수학 문제로 변주한 것입니다.
불행히도 호프먼은 머클의 발상을 알아보지 못했고 제안서는 거절당했습니다. 위의 제안서 원본을 보면 머클의 제안서에 대해 호프먼이 파란색 글씨로 남긴 평가를 볼 수 있습니다. 수강생은 과제 제안서 두 편을 제출하게 되어 있었는데, 머클은 첫째 과제로 “비보안 채널에서 보안 통신 구성하기”를 제출한 것이고, 호프먼은 “뭔 소린지 모르겠으니 둘째 과제가 낫겠다”라고 적은 것이죠.
머클은 호프먼에게 제안서를 수정해서 다시 제출해 보았지만 별 소득이 없었고 결국 이 과목을 그만두었습니다. 이후 머클은 미련을 버리지 못하고 다른 사람들에게 이 발상을 설명해 보지만 다들 그런 터무니없는 소리를 하는 머클이 미쳤다고 생각합니다.
When I talked with people they sort of looked at me in this very odd way, which said “What are you talking about? What do you mean communicate secretly over an open communications line? That doesn’t make any sense. How can you do that? You’re talking crazy talk here.”
(머클의 인터뷰.)
이듬해인 1975년 머클은 ACM에서 운영하는 〈Communications of the ACM〉에 글을 보냅니다. 하지만 CACM은 누구인지 알 수 없는 어떤 암호학 전문가의 의견을 근거로 머클의 글을 싣지 않습니다. 숙련된 암호학 전문가라는 사람이
- 주류 암호학적 사고에 부합하지 않는다.
- 노출된 채널로 키를 전송하는 것은 극히 위험하다는 것이 경험적으로 증명되어 있다.
라는데, 이제 와서 보면 어처구니가 없죠. 미적분의 창시자 아이작 뉴턴에게 “미적분은 수학적 사고에 부합하지 않는다” 운운하는 격입니다. 이 과정은 머클의 글 〈Publishing a new idea〉에 실려 있습니다.
마틴 헬먼의 2004년 인터뷰에 따르면, 디피와 헬먼은 머클과는 별도로 독자적인 공개 키 암호학 연구를 진행하고 있었으나, 시간상으로 머클의 퍼즐이 디피와 헬먼을 앞설 것으로 추정하고 있습니다. 머클은 1975년에 디피와 헬먼을 만났는데, 헬먼은 이 사건을 매우 긍정적으로 묘사하고 있고(“it was clear it was a meeting of the minds, again an intellectual soul mate.”), 1976년 논문 역시 머클의 발상을 크게 참고한 것이었습니다. 특히 키 교환 부분에 대해 헬먼은
… what’s called Diffie-Hellman key exchange is a public distribution system which is Merkle’s concept, not ours …
라고 말합니다. 그런데 정작 키 분배는 ‘디피-헬먼 키 교환’으로 알려져 있고, 이것은 헬먼이 인명을 쓸 거라면 머클의 이름이 들어가야 한다고 주장하는 이유가 됩니다.
수학·과학 분야에서 인명을 따서 붙이는 명명법은 그 사람이 인류의 지적 진보에 공헌한 바를 기리기 위한 것입니다. 이런 취지를 생각한다면 ‘머클-디피-헬먼’이 최초의 공개 키 암호학에 더 적절한 호칭일 것입니다. RSA처럼 MDH로 줄여 불러도 되겠죠.