소수를 이용한 RSA 암호화 방식 간단한 소개

1999-7-24

소수(Prime Number)를 이용한 암호화 방식

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

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

 

Ron Rivest, Adi Shamir, Len Adleman

 

여기서 잠깐 소수에 대해서 살펴 봅시다. 소수는 1과 자기 자신을 제외하고는 나누어 지지 않는 숫자입니다. 소수는 무한히 많은 것으로 알려졌는데, 소수라는 공통점을 제외하고는 어떤 정형화된 패턴도 따르지 않는 것으로 생각되고 있습니다.

 

두개의 소수를 곱하면 당연히 처음에 곱했던 두 개의 소수로 나누어 지는 숫자를 얻게 됩니다. 예를 들어, 소수인 7과 소수인 5을 곱하면, 35를 얻게 되고, 이 35는 7과 5으로 나누어질 수 있지요.

 

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

 

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

 

 

RSA - 129

그런데, Public Key Encryption을 창안해낸 세 명의 과학자는 얼마 지나지 않아서 비판을 받게 됩니다. Public Key Encryption이 정말로 안전한가의 여부는 아무도 알 수 없는 것 아니냐는 문제제기가 일어나지요. 그래서 세 명의 과학자들은 팩토링하는데 수백만 년이 걸릴 것이라며 간단한 129자리 숫자를 제시했습니다. 그들은 자신들의 생각이 옳았음을 증명하기 위해 전 세계를 상대로 이 129자리 소수를 두개의 소수로 나눠보라고 도전장을 던졌던 겁니다. RSA-129란 그  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은 무용지물이 될 지도 모릅니다. 현재까지는 소수가 고갈 되진 않을까라는 고민은 할 필요가 없습니다. 이 우주에 존재하는 원자만큼이나 많은 소수가 있으니까요.