전 세계 연구기관과 기업들이 기존 컴퓨터로는 너무 복잡해 풀 수 없는 문제를 풀 수 있는 양자컴퓨터의 개발 경쟁을 벌이고 있다. 동시에 양자컴퓨터에 의한 암호해독에 맞서 ‘포스트 양자암호(PQC)’에 대한 개발 경쟁도 활발하다. 양자컴퓨터 시대를 대비해 알아두면 좋은 지식을 미국 국립표준기술연구소(NIST)가 정리했다. 요약, 소개한다.
◆ 양자컴퓨팅이란
양자컴퓨터는 고전적인 컴퓨터와는 다른 과학적 개념이 활용된 장치로 1비트의 데이터가 동시에 0과 1의 값을 취할 수 있는 직관에 반하는 양자의 특성을 이용해 기존 컴퓨터로는 어렵거나 불가능한 계산을 할 수 있다.
‘문제에 대한 많은 잠재적 해결책을 병행하여 계산하고 정답을 도출’하는 작업에는 ‘동시에 계산하고 걸러내’는 조작이 필요해 기존 컴퓨터로는 효율적으로 수행할 수 없다. 한편, 양자 컴퓨터라면 효율적으로 작업을 해 정답을 신속하게 도출할 수 있다.
◆ 포스트 양자암호화 알고리즘이란?
현행 암호화 알고리즘은 전자메일이나 메시지, 의료기록 등 기밀성이 높은 전자정보를 부정 열람자로부터 보호하는 것으로 오랜 세월에 걸쳐 암호를 깨려는 기존 컴퓨터의 공격으로부터 데이터를 지켜왔다. 그러나 양자 컴퓨터의 등장에 의해 그러한 종래의 알고리즘이 깨져 전자적인 비밀이 파헤쳐져 버릴 가능성이 있다.
이 위협에 대항하려면 기존 컴퓨터와 양자 컴퓨터 양쪽에 의한 사이버 공격을 저지할 수 있는 암호화 기술이 필요하다. 이것이 포스트 양자 암호 알고리즘이라고 불리는 기술이다.
◆ ‘포스트 양자암호’ vs ‘양자암호’
NIST에 따르면, 포스트 양자암호와 양자암호는 이름은 비슷하지만, 실제로는 전혀 다른 것이다. 포스트 양자암호는 양자컴퓨터에 의한 사이버 공격의 잠재적 위협에 대항하는 것을 염두에 둔 것으로, 타원곡선 등 고대 그리스 시대까지 거슬러 올라가는 매우 역사적인 수학적 기법을 기반으로 하고 있다.
한편, 양자암호는 20세기에 탄생한 양자 물리학을 기반으로 하고 있어, 양자 역학의 직감에 반하는 특성을 이용한 새롭고 안전한 암호화 기술의 실현을 목표로 하는 분야다. 포스트 양자 암호와 마찬가지로 양자 암호 또한 양자 컴퓨터에 의한 사이버 공격에 대한 대항책으로서 유망하지만 그 원리에는 큰 차이가 있다.
◆ 위험한 양자 컴퓨터는 왜 개발되고 있는가
사이버 공격에 악용되면 기존의 암호화 기술로 지켜진 다양한 시스템을 위험에 빠뜨려 버리는 양자 컴퓨터이지만, 유익한 용도도 많이 있다.
양자 컴퓨터에는 복잡한 변수의 상호작용을 수반하는 작업을 해결할 수 있는 가능성이 숨겨져 있다. 예를 들면 의약품의 개발, 복잡한 분자의 시뮬레이션, 복수의 목적지를 지나는 최적의 루트를 찾아내는 고전적인 ‘순회 세일즈맨 문제’의 해결 등에 크게 공헌할 것으로 기대되고 있다.
양자 컴퓨팅 분야는 아직 초기 단계에 있으며 강력한 양자 컴퓨터 구현에는 큰 기술적 장애물이 몇 가지 있다. 양자컴퓨터의 전모는 아직 미지수지만 강력한 양자컴퓨터가 등장할 가능성은 높은 것으로 보이며, 만약 그렇게 되면 현행 암호화 기술에 큰 영향이 미치기 때문에 세계는 그런 사태에 대비해야 한다고 NIST는 지적한다.
◆ 현행 암호화 기술과 양자컴퓨터 해독 구조
종래의 암호 알고리즘에서는 1과 그 자신으로 밖에 나눌 수 없는 매우 큰 소수를 2개 선택해, 그것을 곱해 큰 수를 만들고 있다. 소수를 곱하는 것 자체는 간단하지만, 반대로 어떤 소수가 곱이 되었는지를 알아내는 것은 매우 어렵고 시간이 걸린다. 이 두 수는 소인수라고 불리는데, 충분히 큰 수의 경우 기존 컴퓨터에서는 소인수를 산출하는 데 수십억 년이 걸릴 것으로 추정돼 왔다.
그런데 고성능 양자컴퓨터라면 소인수를 하나씩이 아닌 동시에 체에 걸러 지수함수적인 속도로 답에 도달할 수 있다. 이 디바이스는 ‘암호 해독 가능 양자컴퓨터(Cryptographically Relevant Quantum Computer, CRQC)’로 불리는데, CRQC라면 수십억 년은커녕 며칠, 혹은 몇 시간 만에 기존 암호를 해독해 버릴 가능성도 있기 때문에 국가 기밀에서 은행 계좌까지 모든 기밀 데이터가 위험에 처하게 된다.
◆ 포스트 양자암호는 어떻게 도움이 되나
NIST에 따르면, 양자 컴퓨터에 의한 공격이 행해지는 것을 막으려면, 온 세상의 시스템이 현행의 암호화 알고리즘을 폐지해, 종래의 컴퓨터에서도 양자 컴퓨터에서도 해독이 어려운 포스트 양자암호 알고리즘으로 전환하지 않으면 안 된다.
그 준비로서 NIST는 표준화해야 할 최초의 알고리즘을 4개 선택해, 그 개발에 관한 대처를 주도해 왔다. 4개의 알고리즘 중 3개는 구조 격자라고 불리는 수학 문제 군을 기반으로 하고, 나머지 1개는 해시함수라고 불리는 함수를 이용하고 있다. 이들 기술에서는 큰 수의 인수분해를 시키는 대신 양자컴퓨터든 기존 컴퓨터든 풀기 어렵다고 전문가들이 생각하는 다른 종류의 수학 문제가 사용되고 있다.
이러한 알고리즘은 퍼블릭 네트워크에서 주고받는 비밀번호의 정보를 보호하는 일반적인 암호화와 ID 인증에 사용되는 디지털 서명이라는 암호화가 자주 사용되는 두 가지 주요 작업을 위해 설계됐다. 또한 일반적인 암호화용으로 추가 알고리즘도 검토되고 있으며, 이 접근법에는 구조 격자나 해시함수가 사용되지 않는다.
NIST는 다양한 상황에 대응하거나 암호화에 다양한 접근법을 도입할 필요가 생기거나, 어느 하나의 알고리즘이 취약한 것으로 발각될 경우를 대비해 애플리케이션 종류별로 여러 알고리즘을 제공할 수 있도록 표준 책정을 추진하고 있다.
◆ 왜 지금부터 포스트 양자암호를 개발하나
충분한 성능을 가지는 암호 해독 가능 양자 컴퓨터는 아직 개발되지 않았고, 실용화까지 어느 정도의 시간이 걸리는지도 알려져 있지 않다. 다만, 여러 예측 중에는 “10년도 걸리지 않는다”는 것도 있다.
지금까지 새로운 알고리즘이 표준화되고 나서 그것이 보급되는 데는 10년에서 20년 정도가 걸렸기 때문에 양자컴퓨터의 등장에 의한 기존 암호의 해독이 가져올 위험성을 회피하려면 그 10년 이상 전부터 준비를 진행하지 않으면 안 된다.
◆ 포스트 양자암호의 향후 전개
2016년에 포스트 양자암호 프로젝트를 시작한 NIST는 세계 각국의 암호 전문가로부터 69개의 후보 알고리즘을 모집해, 그것들을 해독하도록 전문가에게 요청해, 투명성 있는 프로세스에 의해 후보수를 좁혀 갔다.
이후 2022년에는 4개의 알고리즘이 정식으로 채택되었고, 그 중 3개가 최초의 최종 표준으로 2024년 8월에 출시됐다. 남은 하나도 2024년 중에 출시될 예정이다.
NIST는 “우리의 사명 중 하나는 특정 기업이나 그룹뿐만 아니라 모든 사람에게 널리 도움이 되는 표준을 개발하는 것이다. 표준이 완성되는 대로 연방 정부 기관에 의해 채택되어 무료로 일반에 공개된다”고 밝혔다.
