증명할 수 없는 수학이 암호를 더 안전하게 만든다고?

수학과 암호의 오래된 관계

현대 암호학은 수학 위에 세워진 학문이에요. RSA는 "큰 수를 소인수분해하기 어렵다"는 가정 위에 서 있고, 타원곡선 암호는 "이산로그 문제를 풀기 어렵다"는 가정 위에 서 있죠. "어렵다"는 게 핵심이에요. 그런데 여기서 어려움이라는 게 정확히 뭘 의미할까요? 그리고 이번에 등장한 흥미로운 아이디어는, 수학에서 "증명할 수 없는 명제"를 암호의 안전성 근거로 삼자는 거예요.

이게 무슨 소린지 한 번에 와닿지 않을 수 있어요. 차근차근 풀어볼게요.

괴델의 불완전성 정리, 그리고 "알 수 없는 명제"

수학에는 괴델의 불완전성 정리라는 유명한 결과가 있어요. 1931년에 쿠르트 괴델이 증명한 건데, 한마디로 "충분히 강한 모든 수학 체계 안에는 참인데 그 체계 안에서는 증명할 수 없는 명제가 반드시 존재한다"는 정리예요. 즉, 어떤 수학 명제는 참인지 거짓인지 영원히 결정될 수 없는 상태로 남아 있을 수 있다는 거죠.

예를 들어 어떤 수학 명제 P가 있는데, 현재 우리가 사용하는 수학 공리들로는 P가 참이라고도, 거짓이라고도 증명할 수 없어요. 이런 명제를 결정 불가능한(undecidable) 명제라고 불러요. 유명한 예로는 연속체 가설이 있는데, 표준 집합론(ZFC) 안에서는 참인지 거짓인지 증명할 수 없다는 게 코헨에 의해 밝혀졌어요.

이번 아이디어의 핵심은 이거예요. "공격자가 비밀을 알아내려면 결정 불가능한 명제를 풀어야 하도록 설계한다면, 그 비밀은 수학적으로 절대 깨질 수 없지 않을까?" 라는 발상이에요.

기존 암호의 안전성 가정과 뭐가 다른가

지금 우리가 쓰는 암호들의 안전성은 사실 "증명되지 않은" 가정에 기대고 있어요. 예를 들어 RSA의 안전성은 "소인수분해가 다항 시간 안에 풀리지 않는다"는 가정에 의존하는데, 이게 진짜로 어려운지는 아무도 수학적으로 증명하지 못했어요. 만약 누군가 천재적인 알고리즘을 발견하면 한순간에 무너질 수도 있는 거죠. 양자컴퓨터의 쇼어 알고리즘이 바로 그런 위협이고요.

그런데 결정 불가능성에 기반한 암호는 차원이 달라요. "이 문제는 풀기 어렵다"가 아니라 "이 문제는 풀이가 존재할 수 없다" 는 거니까요. 어떤 알고리즘도, 어떤 컴퓨터 성능도, 어떤 양자컴퓨터도 결정 불가능한 명제를 결정해줄 수는 없어요. 이건 계산 자원의 문제가 아니라 논리 체계 자체의 한계거든요.

그럼 어떻게 실제 암호로 만들까

여기서부터가 진짜 어려운 부분이에요. 결정 불가능한 명제를 어떻게 "비밀을 숨기는 자물쇠"로 바꿀 수 있을까요? 한 가지 접근은 튜링 머신 정지 문제나 디오판토스 방정식의 해 존재 여부 같은 결정 불가능한 문제를 변형해서 비밀과 연결하는 거예요. 비밀을 아는 사람은 특정한 "빠른 길"을 알기 때문에 답을 낼 수 있지만, 그 길을 모르는 공격자는 결정 불가능한 일반 문제와 마주하게 되는 구조죠.

물론 이게 실용적인 암호 시스템이 되려면 풀어야 할 문제가 많아요. 정상 사용자가 합리적인 시간 안에 암호화/복호화를 할 수 있어야 하고, 키 생성도 효율적이어야 하고, 공격자에게 노출되는 정보가 정말로 결정 불가능한 영역에만 갇혀 있어야 해요. 이론적으로는 매력적이지만 실제 구현으로 가는 길은 험난하다는 게 현재 상황이에요.

양자내성암호와의 관계

요즘 암호학계의 화두는 양자내성암호(Post-Quantum Cryptography, PQC) 예요. 양자컴퓨터가 RSA와 ECC를 깰 수 있기 때문에, 격자 기반(lattice), 코드 기반, 다변수 다항식 기반 같은 새로운 수학적 어려움 위에 암호를 다시 세우고 있어요. 미국 NIST가 작년부터 표준을 확정하고 있고, Kyber, Dilithium 같은 알고리즘이 채택됐죠.

결정 불가능성 기반 암호는 이 흐름의 "한 걸음 더 멀리" 같은 거예요. PQC도 결국은 "양자컴퓨터로도 어렵다"는 가정에 의존하는데, 결정 불가능성 기반은 그 가정조차 넘어서서 "논리적으로 불가능하다" 는 더 강한 토대를 추구해요. 다만 현실 구현 가능성에서는 PQC가 훨씬 앞서 있어요.

한국 개발자에게 주는 의미

실무에 당장 영향을 주진 않아요. 한국 기업들이 결정 불가능성 암호를 쓸 일은 가까운 미래에 없을 거예요. 그래도 알아두면 좋은 이유는 두 가지예요.

첫째, 암호의 안전성이 무엇에 의존하고 있는지에 대한 감각을 키울 수 있어요. "이 라이브러리가 안전하다"는 말이 실제로 어떤 가정 위에 서 있는지 이해하면, 보안 설계 결정을 내릴 때 훨씬 신중해질 수 있어요. 둘째, PQC 전환은 곧 한국 기업들에게도 현실 과제가 됩니다. 금융, 통신, 공공 분야는 이미 양자내성 마이그레이션 로드맵을 검토 중이거든요. 이런 큰 흐름의 끝자락에 어떤 이론적 가능성이 있는지 알아두면 장기적인 기술 안목에 도움이 돼요.

마무리

핵심 한 줄로 정리하면, "증명할 수 없음" 자체가 비밀의 가장 강력한 자물쇠가 될 수 있다는, 수학과 암호학이 만나는 가장 흥미로운 경계에 대한 이야기예요.

여러분은 "수학적으로 어려운 문제"와 "논리적으로 결정 불가능한 문제" 중 어느 쪽이 더 안전한 토대라고 느끼시나요? 그리고 양자컴퓨터 시대를 대비해서 지금 어떤 암호 기술을 공부해두면 좋을까요?