소수를 이용한 암호화 방식

간단하게 암호기술이 어떻게 변천되어 왔는지 조금 얘기해 보겠습니다.

PGP 같은 애플리케이션에서 사용하는 Public Key Encryption은 Whitfield Diffie 와 Martin Hellman에 의해서 1977년에 창안 되었습니다. 그 뒤 일단의 컴퓨터 과학자들은 이 시스템을 더욱 발전시켜서 소인수 분해 방식(prime number factorisation) 하에서 적용 가능하게 만들었고, 이름을 RSA Cryptography System 으로 바꾸었는데, RSA는 세명의 과학자의 성을 딴 것입니다. RSA 암호화 시스템은 순식간에 소수를 이용한 암호기술의 대표로 떠오르게 됩니다.

여기서 잠깐 소수에 대해서 살펴 봅시다. 소수는 1과 자기 자신을 제외하고는 나누어 지지 않는 숫자 입니다. 소수는 무한히 많은데, 그들은 소수라는 공통점을 제외하고는 어떤 정형화된 패턴도 따르지 않습니다. 두개의 소수를 곱하면 당연히 처음에 곱했던 두 개의 소수로 나누어 지는 숫자를 얻게 됩니다. 예를 들어 소수인 7과 소수인 5을 곱하면, 35를 얻게 되고, 이 35는 7과 5으로 나누어질 수 있지요.

그런데 이렇게 두개의 소수를 곱하는 것은 아무것도 아니지만 거꾸로 하는 것, 즉 어떤 소수의 곱으로 이뤄진 숫자에서 곱한 소수를 찾는 것은 매우 매우 어렵습니다. 소수 11927 x 소수 20903 = 249310081 으로 쉽게 계산할 수 있지만 거꾸로 249310081을 처음의 두 소수로 다시 쪼개는 건 정말 정말 까다롭습니다. 바로 이것이 가장 강력하고, 가장 발달되고 또 훌륭한 암호기술인 RSA 방식의 기초가 됩니다. 큰 숫자를 소수의 곱으로 분리하는 것은 세상에서 제일 강력한 컴퓨터로도 엄청나게 긴 세월동안 작업해야 하거든요 . 현재까지 알려진 가장 큰 소수가 895932자리에 이른다는 점을 감안해보면 소수를 이용한 암호화 기술을 깨는것은 매우 어렵다는 것을 잘 아실 수 있을 겁니다.

Public Key Encryption은 위의 원리를 이용해서 두개의 다른 해독 키(key)를 만들어 내는 것입니다. 하나는 메씨지를 암호화 하는데 쓰고, 다른 하나는 해독하는데 쓰게 됩니다. 암호화에 쓰는 쪽은 두 소수를 곱해서 만들어지는 수를 기반으로 만들게 되고, 해독하는 키는 소수 그 자체를 기반으로 만들어 집니다. 컴퓨터를 이용하면 쉽게 키를 만들 수 있구요.

RSA - 129

그런데, Public Key Encryption을 창안해낸 세 명의 과학자는 얼마지나지 않아서 비평가들로부터 공격을 받게 됩니다. 비평가들은 Public Key Encryption이 정말로 안전한가의 여부는 아무도 알 수 없는것 아니냐고 문제제기를 합니다. 그래서 세 명의 과학자들은 팩토링 하는데 '수 백만년'이 걸릴것이라며 '간단한' 129자리 숫자를 제시했습니다. 이것만이라도 한 번 깨보라면서요.

그들은 자신의 생각이 옳았음을 증명하기 위해서, 전 세계를 상대로 이 129자리 소수를 두개의 소수로 나눠보라고 도전장을 던졌던 겁니다. "RSA-129"란 바로 그 숫자를 가르키는 말이었습니다. 그리고 그 숫자는,

(한줄임) 11438162575788886766923577997614661201 0218296721242362562561842935706935245733897830597123 563958705058989075147599290026879543541

그 세명의 과학자들은 위의 소수를 이용해서 암호화 시켜놓은 메씨지를 해독하는것이 불가능 할것이라 확신했고, 그들의 메씨지는 영원히 안전할거라 호언장담 했습니다. 그런데 1993년 전세계 약 600여명의 학자와 관심있는 사람이 모여서 인터넷을 통한 공동작업으로 이 129자리 숫자를 공격해 보자는 프로젝트를 시작하게 됩니다. 그리고, 그 프로젝트가 시작된지 일 년도 못되어서 문제의 두개의 소수를 알아내게 됩니다. 하나는 64자리 수였고, 다른 하나는 65자리 수였죠.

그들은 즉시 세 과학자가 암호화 시켜둔 메씨지를 해독했고, 해독된 메씨지는,

"The magic words are squeamish and ossifrage."

이 사건이 있고나서 129자리 키는 정말 중요한 정보를 암호화 하기엔 부족하다는 사실을 모두다 알게 되었습니다. 하지만 단지 몇 자리만 키를 더 늘려도 그 키를 깨는것은 매우 매우 더 어려워진다는 것은 여전히 흔들리지 않는 사실 입니다.

수학자들은 우리가 예측한 대로 컴퓨팅 파워가 발전해 간다고 하더라도 250자리 소수를 팩토링 하는데는 수 백만년 이상이 걸릴거라고 얘기하곤 합니다. 그리고 그 얘기는 결코 과장이 아닙니다. 그런데, 1995년 암호화 기술 컨설턴트를 하고 있던 Paul Kocher라는 사람이 "Brute force factorising" (가능한 모든 조합을 계속 테스트 해보는것)을 쓰지 않고도 Public Key Encryption 중 몇 몇을 깰 수있다고 주장 합니다. 그는 어떤 종류의 public key들을 컴퓨터로 깨는데 걸리는 시간을 산출해 낸 다음, 그걸 이용해서 public keys를 팩토링 해보기 시작했죠. 단지 몇 백번 정도만에 그는 컴퓨터의 계산 시간을 측정하는 방법으로 암호화에 사용된 숫자를 찾아냈고 그때 걸린 시간을 숫자로 전환하는 방법으로 깨버립니다.

그래서, Public Key Encryption이 위와 같은 방법으로 깨질 수 있는 것을 막기 위해 업데이트를 하게 되었고, 그 방법은 암호화/해독 시간을 일정하게 정하는 식이 된것입니다. 하지만 누가 알겠습니까? 또다른 천재가 불쑥 나타나서 미래의 Public Key Encryption을 또 다시 위험에 빠뜨리게 될지. 우리가 도저히 생각해 낼 수 없는 방법으로 깨뜨려 버릴 수도 있는 것입니다. 또한 현재 여러 수학자들이 n번째 소수를 알아낼 수 있는 공식을 연구하고 있기 때문에 만약에 그 방법이 발견되면 Public Key Encryption은 무용지물이 되버립니다. 하지만 현재로는 소수가 고갈 되진 않을까라는 고민은 할 필요가 없습니다. 이 우주에 존재하는 원자 만큼이나 많은 소수가 있으니까요. 그러므로 지금까지 찾아낸 소수를 몇 배로 늘린다든지 또는 표를 만든다든지 하는 방법은 별로 의미가 없습니다.