열쇠와 자물쇠, 전부 수학이다
[책을 읽고] 이언 스튜어트, <수학의 이유> (1/2)
리디에서 밀리로 건너오니, 이언 스튜어트 책이 3권이나 있다. (<우주를 계산하다>가 없다는 것은 함정.)
이 책은 현대 사회를 지탱하는 수많은 기술들 뒤에 숨겨진 수학을 소개한다. 포인트는 이중 많은 것들이 원래 발견자가 생각도 하지 못했던 분야에서 활용되고 있다는 점이다. 실제로 존재하지 않는다는 의미로 이름 지은 허수(imaginary number)가 실제 세계를 지배하는 법칙인 양자역학의 발견으로 이어질지 상상이나 했겠는가.
그 양자역학이 가능케 한 반도체와 컴퓨터의 발명으로, 예전에는 도저히 할 수 없었던 단순 반복 계산이 가능해졌고, 이에 따라 새롭게 등장한 수학적 기법(예컨대 몬테 카를로 시뮬레이션)도 있으니, 준 만큼 받기도 한 셈이다.
P/NP 문제에서 자율주행은 위험하다는 결론이라니
이언 스튜어트는 통찰력이 뛰어난 학자이고, (비교적) 쉽게 이해할 수 있는 교양서를 쓰는 작가지만, 언제나 명쾌한 설명에 성공하는 것은 아니다. 예컨대 P/NP 문제 설명은 헷갈리기 딱 좋게 서술해 놨다. 이 파트를 읽느니 나무위키의 해당 항목을 읽는 편이 이해가 쉽다.
앞뒤 다 자르고 말하자면, P문제는 쉽게 계산 가능한 문제이고, NP문제는 쉽게 검산 가능한 문제다. P<>NP인게 당연해 보이지만, 혹시 같으면 어쩌나 하는 걱정이 드는 것도 사실이다. P=NP라면, 세상 모든 암호는 무용지물이라는 얘기다.
앞서 말한 컴퓨터의 도움이 가능해지자, 일부 학자들은 대화형 증명(interactive proof)이라는 방식을 고안해 냈다. 컴퓨터(알고리즘)끼리 증명을 제시하고 반증을 내놓는 식의 증명법이다. 딥러닝 알고리즘 중에 적대적생성망(GAN)과 유사한 방식이다. 이 방법으로 P/NP 문제가 해결된다면, 물론 좋은 일이겠지만 많은 사람들이 실망할 것이다. 4색 문제가 컴퓨터 계산으로 증명되었을 때, (히가시노 게이고를 포함한) 많은 사람들이 그랬듯 말이다.
현대 수학계의 거장, 히가시노 게이고저자는 수학의 유용성을 가늠하는 척도 중 하나로 무려 "아름다움"을 제시한다. 오일러 등식을 바라보면, 아름다움이란 요소는 수학의 필연적인 면모라는 생각도 든다. 그러나, 간결하고 아름다운 코드는 이미 옛날 이야기이고, 파이썬은 길게 늘어지고 중복이 난무하는 표현이 결국 승리한다는 사실을 보여주는 역사적 증인이다. 마찬가지의 일이 수학에서도 일어나고 만다.
이런 방법들이 확립되고 나니 명확성과 간결함을 추구할 때는 피하게 되는 특성을 컴퓨터를 통해서는 가능하다는 사실을 깨달았다. 바로 중복성redundancy이다. 논리적 증명을 훨씬 더 긴 형태로 고쳐 적을 수 있게 되었다. 이것은 만약 오류가 하나 있으면 그 오류가 거의 모든 곳에 중복해서 나타난다는 의미이기도 하다 (88쪽)
공교롭게도, 이 흥미로운 제3장은 다소 억지스러운 주장으로 끝난다. 단지 몇 픽셀만 바꿈으로써 AI의 이미지 감별을 속일 수 있다. 따라서 자율주행을 AI에게 맡기는 것은 곤란하다고 단정한다.
책에 나오는 고양이 사진의 사례는 물론 사실일 것이다. (무려 인셉션 v3를 속였다고 한다.) 그러나 '헤밍 거리'로 설명되는 이 속임수는 AI가 아직 그런 이미지를 학습하지 못했을 때나 가능한 것이다. 헤밍 거리를 조작한 속임수 이미지 10개만 던져주면, AI는 그 속임수를 간파하는 방법을 금방 배워버린다. 이런 뻔한 사실을 이언 스튜어트씩이나 되는 대학자가 간과했다는 점은 놀라울 뿐이다.
RSA와 그 적들 (그리고 대체 후보들)
인터넷 뱅킹을 포함한 컴퓨터 암호에 널리 사용되는 RSA 알고리즘은 기본적으로 페르마의 소정리에 기반한다. 소수를 두 개만 쓰는 이유는, 소수를 세 개 이상 곱했을 때 오히려 소인수 분해가 쉽기 때문이다.
RSA 암호는 너무 느리기 때문에 문장 전체를 암호화하는 데 쓰기에는 무리가 있다. 그래서 암호키 정도를 암호화하는 데 사용한다. 문제는 RSA 암호가 근본적으로 깰 수 있는 구조라는 데 있다. 충분한 평문과 암호 조합을 확보하면, 이론적으로 가능할 뿐 아니라 실제로도 가능하다는 점을 한 해커 집단이 증명했다.
2012년에 아르젠 렌스트라Arjen Lenstra가 이끄는 집단이 인터넷에서 추출한 공개 암호키 수백만 개를 가지고 시도해봤더니 500개 중 하나는 암호를 깰 수 있었다. (143쪽)
양자 컴퓨터는 RSA 암호를 단박에 무력화시킬 무기로 흔히 소개된다. 병렬 연산이 가능하니 당연한 얘기인데, 사실 컴퓨터 연산 능력이 대폭 빨라지는 어떤 방법이라도 RSA 체계를 무력화할 수 있다. 컴퓨터 연산 능력이 향상됨에 따라, 은행들은 RSA 알고리즘에 쓰는 소수의 길이를 늘리는 방법으로 대응해 왔다.
저자는 RSA 암호 체계의 대안으로 타원 곡선을 제시한다. 이는 결투 천재 갈루아의 군론을 바탕으로 한 것인데, 간단히 말해 유한군 내에서 역산이 어려운 점을 이용한 것이다. 자세한 설명은 (내가 모르니) 생략한다.
장점은 크기가 작은 군으로도 훨씬 큰 소수를 기반으로 만든 RSA 암호만큼이나 보안이 좋은 암호를 만들 수 있다는 것이다. (150쪽)
이번에는 양자 컴퓨팅에 관해 말해보자. 양자 컴퓨팅은 양자 중첩 상태를 이용한 것인데, 양자 중첩 상태는 관측, 즉 간섭만으로 깨지기 때문에 그 어떤 상호작용도 없는 상태를 유지해야 한다. 절대 온도 0도에 가깝게 냉각하는 이유가 바로 이거다. 문제는 이런 극한 상황에서조차 간섭이 아예 없을 수는 없다는 점이다. 그래서 간섭에 따른 오류를 보정해야 하는데, 여기에는 당연히 비용이 따른다. 큐비트를 더 써야 하는 것이다. 그런데 큐비트는 초저온 냉각 때문에 매우 비싸다. 게다가 오류 수정에 필요한 계산에도 시간이 소요된다.
양자 컴퓨터의 모습은 어딘가 진공관스럽다 - Copyright: Forschungszentrum Jülich / Sascha Kreklau사실 나는 양자 컴퓨팅의 기본 원리도 잘 이해하지 못하지만, 양자 컴퓨팅이 근시일 내에 가능할 것이라 생각하지 않는다. 양자 컴퓨팅보다 일반 인공지능이 먼저 올 것 같다. 물리학자 미하일 디아코노프도 같은 생각이다.
일부는 과연 만들 수 있을지 아직도 확신하지 못하고 있다. 물리학자 미하일 디아코노프Mikhail Dyakonov는 이렇게 적었다.
주어진 어느 한 순간에 한 유용한 양자 컴퓨터의 상태를 기술하는 연속 매개 변수의 수는 분명 10^300 정도는 된다. 우리가 이런 시스템의 양자 상태를 정의하는 10^300개의 연속적인 가변 매개 변수를 통제하는 법을 배울 수 있을까? 내 대답은 간단하다. 안 된다. 절대 불가능하다. (158쪽)
그러나, 만약 양자 컴퓨팅이 가능해진다고 해도, 현재의 암호 체계가 무너지지는 않는다. 양자 컴퓨팅은 병렬 연산이 강점이니, 암호화 계산도 더 복잡하게 할 수 있다. 간단히 말해, 암호화 과정에서 일련의 계산을 더 길고 지리멸렬하게 하면 된다.
암호 체계를 무너뜨릴 진정한 악당은 P=NP다. (그럴 리가 없겠지만.)
