키드 크립토(Kid Krypto)

컴퓨터 네트워크를 통해서 수신자만 제외하고 아무리 똑똑하고 열심히 노력하더라도 관계없이 그 누구도 해독할 수 없는 비밀 메시지를 보내려는 이유가 명확해졌다. 물론 만약 보내는 사람과 받는 사람이 비밀코드를 공유한다면 메시지를 교환할 수 있는 다양한 유형의 방법이 있다. 하지만, 공개키 암호화의 좀더 똑똑한 부문은 애미가 빌에게 비밀 메시지를 사전에 어떠한 비밀 약속도 없이 보낼 수 있다는 것이다. 단지 웹 페이지 같은 공공장소에서 자물쇠를 고르면 된다.

비밀성(secrecy)은 암호화의 단지 한 면에 불과하다. 또 다른 면은 인증(authentification)이다: 애미가 빌로부터 메시지를 받았을 때, 다른 사기꾼이 아니고 빌이 보냈다는 것을 어떻게 알 수 있을까? 누군가 다음과 같이 전자우편을 보냈다고 가정하자.

“자기야, 나 돈이 없어서 여기서 꼼짝할 수 없어. 내 계좌로 십만원만 넣어줘. 계좌 번호는 우리은행 0241-45-784329 이야. 사랑해, 빌.

애미는 정말 빌이 전자우편을 보낸 것인지 어떻게 알 수 있을까? 몇가지 공개키 암호시스템이 또한 사용될 수 있다. 애미가 빌에게 공개키로 메시지를 인코딩해서 메시지를 보냈듯이, 개인키로 메시지를 암호화해서 빌만 생성할 수 있는 메시지를 애미에게 보낼 수 있다. 만약 애미가 빌의 공개키로 암호를 풀 수 있다면, 메시지는 빌에서부터 온 것이 틀림없다. 물론, 키가 공개되었기 때문에 누군가 암호를 풀 수 있다. 하지만, 만약 메시지가 애미만을 위한 것이라면, 빌이 애미의 공개키로 두번 암호화할 수 있다. 이러한 이중 암호화는 공개키와 개인키 기법을 사용하여 비밀성과 인증을 모두를 제공한다.

이번 활동에 실제로 보여진 기법은 실제 산업에서 사용되는 공개키 암호화 시스템과 매우 유사하다는 것을 인정할 때가 지금이다. 실제 산업에서는 훨씬 더 커다란 지도가 사용되더라도, 사실 안전하지는 않다.

이유는 설사 임의 지도 위에 아이스크림 승합차를 배치할 최소 방법을 찾을 길이 없어서 이러한 관점에서 사실 이 기법이 안전하다. 보안을 뚫는 완전히 다른 방식이 있을 수 있다. 이 아이디어가 학교 학생, 최소한 고등학교 수준까지 생길 것 같지는 않다. 하지만 존재한다는 것은 최소한 알아야 한다. 지금까지 조사한 기법은 학교학생 안전한 방식이고, 수학자 안전한 방식은 아니다. 만약 수학에 관심이 없다면 다음을 무시하세요!

지도상에 교차점을 1, 2, 3, … 번호를 매긴다. 교차점에 원래 숫자를 b_1, b_2, b_3, … 을 대입하고, 실제 전송되는 숫자를 t_1, t_2, t_3, … 으로 표기한다. 교차점 1 이 교차점 2, 3, 4 와 연결되었다고 가정하자. 그렇다면, 해당 교차점에 전송되는 숫자는 다음과 같다.

t_1 = b_1 + b_2 + b_3 + b_4.

물론, 다른 모든 교차점에도 비슷한 방정식이 있다— 사실, 미지수 b_1, b_2, b_3, … 와 동일 갯수 방정식이 있다. 도청하는 사람은 공개지도와 전송되는 숫자 t_1, t_2, t_3, … 을 알고 있다. 따라서 방정식을 작성하고 방정식 푸는 컴퓨터 프로그램으로 문제를 풀 수 있다. 원래 숫자가 얻어지면, 메시지는 숫자 합이다— 사실 암호해독 지도를 찾을 필요도 없다. 가우스 소거법(Gaussian elimination)을 사용해서 방정식을 푸는데 드는 컴퓨터 노력은 방정식 갯수의 세제곱에 비례한다. 하지만, 방정식이 희소(sparse)하기 때문에— 계수 대부분은 0 — 좀더 효과적인 기법이 존재한다. 이 방법과 기하급수적 노력이 드는 것과 대조해보자. 누구나 알고 있지만, 최선의 노력은 암호해독 지도를 가져오는 것이다.

속았다는 느낌을 받지 않았으면 한다. 사실 실제 공개키 암호시스템에 관계된 절차는 살펴본 것과 암호화에 사용된 방식이 다르다는 것을 제외하고 거의 동일하다— 사실 손으로 계산하는 것은 가능하지 않다. 여전히 가장 안전한 방법중의 하나인 최초 공개키 방법은 큰 숫자를 소인수 분해하는 어려움에 기반한다.

9,412,343,607,359,262,946,971,172,136, 294,514,357,528,981,378,983,082,541,347,532,211,942,640,121,301,590,698,634,089, 611,468,911,681 백자리 숫자를 소인수 분해결과는 무엇일까? 너무 많은 시간을 쓰지 마세요.

정답은 86,759,222,313,428,390,812,218,077,095,850,708,048,977 과 108,488,104,853,637,470,612,961,399,842,972,948,409,834,611,525,790,577,216,753 이다. 다른 소인수는 없다: 두 숫자는 모두 소수다. 소수를 찾는 것은 엄청난 작업이다: 사실, 슈퍼컴퓨터로 7개월 프로젝트다.

지금 실제 공개키 암호시스템에서 빌이 공개키로 100 자리 숫자와 개인키로 두 소인수를 사용했다. 그런 키가 어려운 것은 아니다: 필요한 것은 큰 소수를 계산하는 방식이다. 충분히 큰 두 소수를 찾아서(어렵지 않다.), 둘을 곱하면, 매우 빠르게 공개키가 된다. 매우 큰 숫자를 곱하는 것은 컴퓨터에게 큰 작업이 아니다. 공개키가 주어진 상태에서, 슈퍼컴퓨터를 몇달 사용하지 않는다면, 개인키를 누구도 알아낼 수 없다. 그리고 만약 걱정이 된다면, 100자리 소수 대신에 200 자리 소수를 사용하라— 몇년더 걸릴 것이다. 주요점은 키를 해킹하는데 소요되는 비용이 해킹해서 얻는 정보의 가치보다 높다는 것이다. 실무에서 512 비트 혹은 좀더 큰 키가 보안 연결설정에 흔히 사용되는데, 십진수로 약 155 자리수 이상과 상응한다.

아직까지 소수기반 공개키를 사용하여 메시지를 암호화하는 방식을 학습하지 않아서 개인키 없이는 암호를 풀 수도 없다. 이것을 위해서, 실제는 앞에서 알아본 것처럼 간단하지 않다. 두 소수가 개인키로 두 소수의 곱이 공개키로 사용되는 것은 아니다. 대신에 두 소수에서 얻어진 숫자가 사용된다. 하지만 효과는 동일하다: 숫자를 소인수 분해해서 암호를 풀 수 있다. 어쨌든, 이런 어려운 점을 극복하고, 적절한 암호화 및 암호해독 알고리즘으로 개조하는 것은 어려운 것은 아니다. 하지만 여기서는 거기까지 상세히 다루지 않을 것이다. 이번 활동은 이미 충분한 학습이 되었다.

소수에 기반한 시스템은 얼마나 안전할까? 글쎄요, 큰 숫자를 인수분해하는 것은 수세기 동안 세상에서 가장 저명한 수학자의 관심을 끌어온 문제다. 모든 가능한 소인수를 시도하는 무작위 방법보다 훨씬 더 나은 방식이 발견되었지만, 아무도 정말 빠른 (즉, 다항시간) 알고리즘을 제시하고 있지는 못하다. (어느 누구도 아직 그런 알고리즘은 불가능하다는 것도 증명하지 못했다.) 그래서 기법이 학교학생-보안 뿐만 아니라 수학자-보안처럼 보인다. 하지만 주의하라: 우리 모두 조심해야 한다. 관광 마을 문제를 풀지 않고 빌의 암호를 해독하는 방식이 있듯이, 큰 숫자를 인수분해하지 않고도 소수 암호를 해킹할 수 있는 방법이 있는지도 모른다. 사람들이 이 문제에 대해서 주의깊이 점검했다. 괜찮아(OK) 보인다.

또다른 걱정이 만약 단지 몇개 가능한 메시지만 있다면, 침입자가 공개키를 사용해서 메시지를 순차적으로 암호화하고, 실제 메시지와 모든 경우의 수를 비교할 수 있다. 애미의 방법은 이것을 피할 수 있는데, 왜냐하면 무슨 숫자를 골라 코드 값을 더하는지에 따라 동일한 메시지를 암호화하는 방법이 많기 때문이다. 매우 빠른 컴퓨터의 도움을 받아도 시도해 보기에 너무나도 많은 메시지가 있도록 실무에서 사용되는 암호시스템은 설계된다.

소수 인수분해 문제를 푸는 빠른 방법이 존재하는지 알려져 있지 않다. 어느 누구도 방법을 고안하지도 못했지만, 빠른 방법이 불가능하다고 증명도 되지 않았다. 만약 이 문제에 대한 빠른 알고리즘이 발견된다면, 현재 사용되는 많은 암호화 시스템이 안전하지 않게 될 것이다. 제4부에서 NP-완전 문제를 토론했다. 함께 흥하고 함께 망한다: 만약 문제 중에 하나가 효율적으로 풀 수 있다면 다른 문제도 마찬가지로 풀 수 있어야 한다. 이 문제에 대한 빠른 알고리즘을 찾는데 너무나 많은 (성공하지 못한) 노력이 투여되었기 때문에, 안전한 암호화 시스템을 설계하는데 사용할 훌륭한 후보자처럼 보이다. 슬프게도, 이 계획에는 어려운 점이 있다. 지금까지 암호시스템 설계자는 사실 NP-완전 문제보다 풀기 쉬울 수 있는 (소인수 분해 같은), 어쩌면 훨씬 더 쉬운, 문제에 의지할 수 밖에 없었다. 지금까지 제기된 문제에 대한 해답은 산업계에 수십억원의 가치가 있고, 국가 안보에 극히 중요한 것으로 간주된다. 현재 암호화는 컴퓨터 과학에서 매우 역동적인 연구분야다.>

추가 읽기

Harel이 저술한 Algorithmics 책에서 공개키 암호화를 논의한다; 어떻게 매우 큰 소수를 사용해서 안전한 공개키 시스템을 만들어 내는지 설명한다. 암호화에 대한 표준 컴퓨터 과학 교과서는 Dorothy Denning이 저술한 Cryptography and data security이다. 반면에 좀더 실무적인 책은 Bruce Schneier가 저술한 Applied cryptography다. Dewdney가 저술한 Turing Omnibus에는 공개키 암호화하는 또다른 시스템을 기술하고 있다.