정수론 4강. RSA: 정수론이 지키는 인터넷
잠그는 열쇠와 여는 열쇠를 분리해 보세요. 그 순간 한 번도 만난 적 없는 두 사람이 비밀을 나눌 수 있습니다.
풀고 시작
자물쇠와 열쇠를 분리하다
암호의 오랜 딜레마는 열쇠 전달이었습니다. 암호문을 주고받으려면 먼저 열쇠를 공유해야 하는데, 그 열쇠는 무엇으로 안전하게 보낼까요? 수천 년간 답이 없던 이 문제에 1976년 디피(Whitfield Diffie)와 헬만(Martin Hellman)이 발상의 전환을 제안했습니다. 잠그는 열쇠와 여는 열쇠를 분리하자. 잠그는 열쇠(공개키)는 전 세계에 공개하고, 여는 열쇠(개인키)만 혼자 간직합니다. 누구나 내 자물쇠로 상자를 잠가 보낼 수 있지만, 여는 것은 나뿐이죠. 열쇠를 몰래 전달할 필요가 아예 사라집니다.
남은 과제는 이 아이디어를 실현할 수학이었습니다. 공개키에서 개인키를 역산할 수 없어야 합니다. 즉 한쪽 방향으로는 쉽고 반대 방향으로는 사실상 불가능한 연산이 필요했죠.
곱하기는 쉽고 쪼개기는 어렵다
정수론이 바로 그런 연산을 갖고 있었습니다. 소인수분해의 비대칭성이죠. 300자리 소수 두 개를 곱하는 일은 컴퓨터에게 순간의 일입니다. 그러나 그렇게 나온 600자리 합성수를 받아 원래의 두 소수를 찾는 일은 전혀 다릅니다. 알려진 최선의 알고리즘으로도 자릿수가 커지면 계산 시간이 폭발적으로 늘어나, 충분히 큰 수는 슈퍼컴퓨터를 동원해도 사실상 분해할 수 없습니다. 계산이 한 방향으로만 쉽게 흐르는 이 언덕이 암호의 재료가 됩니다. 1강에서 본 것처럼 소수는 무한히 많고 밀도도 알려져 있으므로, 큰 소수를 새로 구하는 일은 어렵지 않죠. 재료는 무한하고 조립은 쉬운데 역설계만 어려운 셈입니다.
1977년 MIT의 리베스트(Rivest), 샤미르(Shamir), 애들먼(Adleman)은 이 비대칭성 위에 실제 암호 체계를 세웠고, 세 사람의 머리글자를 따 RSA라 불립니다. 흥미로운 후일담이 있습니다. 영국 정보기관 GCHQ의 클리퍼드 콕스(Clifford Cocks)가 1973년 사실상 같은 체계를 먼저 고안했으나 기밀로 묶여 있다가 1997년에야 공개됐죠.
페르마와 오일러가 심장에 있다
RSA의 뼈대는 3강의 정리들로 조립됩니다. 개념 수준에서 따라가 봅시다. 큰 소수 p와 q를 골라 n = p × q를 만들고, n과 암호화 지수 e를 공개합니다. 암호화는 메시지를 수 m으로 보고 m^e을 n으로 나눈 나머지를 취하는 것입니다. 복호화 지수 d는 e와 짝을 이루어, 암호문을 d제곱하면 원래 m이 돌아오도록 정하죠.
왜 돌아올까요? 오일러의 정리 때문입니다. mod n의 세계에서 거듭제곱은 φ(n) = (p - 1) × (q - 1) 걸음마다 제자리로 돌아오는 주기 운동을 합니다. e와 d를 곱이 이 주기와 맞물리도록(정확히는 e × d를 φ(n)으로 나눈 나머지가 1이 되도록) 골라 두면, e제곱으로 갔다가 d제곱으로 돌아오는 여정이 정확히 출발점에 착지합니다. 관건은 φ(n)입니다. p와 q를 아는 사람은 φ(n)을 즉시 계산해 d를 만들 수 있지만, n만 아는 도청자는 φ(n)을 구하려면 n을 소인수분해해야 합니다. 비밀은 숨겨진 것이 아니라 계산적으로 봉인된 것이죠.
쓸모없던 수학, 문명의 기둥이 되다
3강에서 하디가 정수론의 쓸모없음을 자랑했다고 했습니다. 그로부터 40년도 지나지 않아 페르마와 오일러의 정리는 온라인 뱅킹, 전자상거래, 메신저 보안의 기반이 되었습니다. 브라우저 주소창의 자물쇠 아이콘 뒤에서 공개키 암호가 매일 작동하고 있죠. 순수한 호기심이 수백 년 뒤 문명의 인프라가 된 이 역설은, 기초 학문의 가치를 말할 때 가장 자주 소환되는 사례입니다.
다만 이 봉인은 영원하지 않을 수 있습니다. 1994년 피터 쇼어(Peter Shor)는 충분히 큰 양자컴퓨터가 있다면 소인수분해를 빠르게 해낼 수 있음을 보였습니다. 그런 컴퓨터는 아직 없지만, 세계는 이미 격자 문제 등 다른 어려운 수학에 기반한 양자내성암호로의 이행을 준비하고 있죠. 암호의 역사는 결국 어려운 수학 문제를 갈아 끼우는 역사입니다. 다음 과목인 이산수학에서는 이런 계산의 세계를 떠받치는 또 다른 기둥, 세는 기술을 다룹니다.
인출 문제
생각해볼 질문 (정답 없음)
- RSA의 안전성은 "소인수분해가 어렵다"는 증명되지 않은 믿음 위에 서 있습니다. 문명의 인프라가 미해결 문제 위에 세워져 있다는 사실을 어떻게 받아들여야 할까요?
- 하디의 역설이 보여 주듯 어떤 수학이 언제 쓸모를 얻을지는 예측할 수 없습니다. 그렇다면 연구 지원은 무엇을 기준으로 배분해야 할까요?