By AMIT KATWALA, WIRED UK

1994년, 벨 연구소(Bell Labs) 소속 수학자 피터 쇼어(Peter Shor)가 무한한 잠재성을 지닌 알고리즘을 개발했다. 15를 5와 3으로 줄이는 등 곱셈 값을 줄이는 방식으로 큰 숫자가 필요한 연산 자원을 대거 줄인 쇼어의 알고리즘은 암호화 분야에서 가장 큰 인기를 얻은 여러 방식을 뒤집을 것이라는 위협을 제기했다.

다행히도 RSA 암호화나 타원 곡선 암호 방식(elliptic curve cryptography)과 같이 요소 기반 암호화 방식을 사용하는 이메일 공급사와 웹사이트 등 기타 보안 서비스 수천 곳에는 쇼어가 개발한 알고리즘을 실행할 컴퓨터가 존재하지 않았다.

쇼어는 1990년대 중반, 과학자가 언젠가 복잡한 하위 문제를 처리하는 데 기존 컴퓨터의 성능을 뛰어넘기를 바란 기기이면서 거의 이론적으로 존재한 기기였던 양자 컴퓨터를 실행했다.

그리고 수십 년 뒤 실용적인 양자 컴퓨터 개발 성과 측면에서 크나큰 발전이 이루어졌다. 정부와 민간 연구 기관 모두 양자 컴퓨터의 힘에 저항할 새로운 양자 증명 알고리즘 개발 경쟁을 펼쳐왔다. 지난 6년간 미국 상무부 산하 기관인 미국 국립표준기술연구소(NIST)는 양자 컴퓨터로부터 데이터를 보호하기를 바라며, 알고리즘 발견 경연을 운영해왔다. 그리고 2022년 7월, NIST가 경연 결과를 공식 발표했다.

NIST는 전 세계 수백 개의 암호화 알고리즘을 일반 암호화를 위한 ‘CRYSTALS-Kyber’와 신원 검증 디지털 문서 사용 시 사용하는 디지털 서명을 위한 ‘CRYSTALS-Dilithium’, ‘FALCON’, ‘SPHINCS’ 등 총 네 가지로 줄였다. NIST에서 포스트 양자 암호화 프로젝트를 이끈 더스틴 무디(Dustin Moody) 박사는 “양자 컴퓨터가 암호화에 제기하는 위협을 이해해야 한다. 보안 수준이 취약한 알고리즘을 대체하고 표준화를 위한 첫 단계로 나아가야 한다”라고 말했다.

RSA 암호화가 매우 큰 수를 형성할 때의 어려움에 의존하듯이 NIST가 새로 공개한 알고리즘 4가지 중 3가지는 양자 컴퓨터도 처리하기 어려울 것으로 보이는 복잡한 수학 문제를 사용한다. 구조화된 격자는 단축된 방식을 알 때를 제외하고 해결하기 매우 어려운 추상적인 다차원 알고리즘 그리드(abstract multi-dimensional grid)이다. RSA와 마찬가지로 구조화된 패턴 암호화에서 메시지 발송자는 수신자의 공개 키를 사용해 콘텐츠를 암호화한다. 그러나 수신자만 암호화 해제 키를 보유할 것이다. RSA 암호화 방식의 핵심은 두 개의 큰 소수를 함께 곱하기는 쉽지만, 거꾸로 작업해야 하는지 확인하기 어려운 요인이다. 이러한 양자 후 암호화 알고리즘에서 키는 벡터이며 구조화된 격자의 미로를 통과하는 방향이다.
 
알고리즘 방식이 최종 형태로 표준화되려면 몇 년이 걸릴 것이다. 하지만 지금 당장은 매우 중요한 성과를 거두었다. FALCON 알고리즘 작업에 참여한 양자 보안 기업 PQShield CEO인 알리 엘 카파라니(Ali El Kaafarani)는 “양자 위협에 맞서 무언가 성과를 거둔 것은 이번이 처음이다”라고 말했다.

양자 위협 부문에서 여전히 수십 년이 뒤처졌으나 다수 보안 전문가는 ‘지금 최대한 이용하고 나중에 암호화를 해제하는’ 공격을 경고한다. 해커 세력이 결과적으로 접근할 수 있는 양자 컴퓨터를 보유할 것이라는 기대와 함께 암호화 데이터 캐시를 제거하기 때문이다. 양자 증명 암호화를 구축하는 시간이 오래 걸릴수록 보안이 취약해지는 데이터가 증가할 것이다. 하지만 랭커스터대학교 양자 연구원인 롭 영(Rob Young)은 현재 마구 이용하는 민감 데이터 상당수가 시간이 매우 중요하다고 지적했다. 오늘 사용하는 신용카드 번호가 15년 뒤면 무효가 된다는 점을 예시로 생각할 수 있다.

엘 카파라니는 “연구 기관이 가장 먼저 할 일은 암호화 기술을 사용하는 곳과 방식, 사용 이유를 이해하는 것이다. 시스템 영역 중 전환이 필요한 부분을 평가하기 시작하고, 가장 취약한 부분에서 포스트 양자 암호로의 전환을 구축해야 한다”라고 말했다.

그러나 양자 컴퓨터는 불확실한 요소가 넘쳐난다. 실제 양자 컴퓨터의 역량이나 대규모 설치 입증 가능성 등을 아는 이는 없다. 지금도 구글, IBM 등 양자 컴퓨터를 개발하는 테크 업계 대기업은 특정한 특수 설계 작업에서 기존 컴퓨터를 능가하는 성능 입증 단계에서 시작한다. 그러나 양자 컴퓨터를 대규모로 개발하는 일은 기술적으로 어려우며, 쇼어가 개발한 알고리즘을 의미 있는 방식으로 활용할 양자 컴퓨터가 등장하기까지는 오랜 시간이 걸릴 것이다. 영은 “가장 큰 문제는 기존 컴퓨터와 양자 컴퓨터의 미래 역량을 이해한 채로 추측해야 하는 것이다. 지금은 양자 컴퓨터의 보안을 보장할 수 없다”라고 설명했다.

새로운 알고리즘의 복잡함은 실질적으로 얼마나 훌륭한 성과를 거둘지 평가하기 어렵도록 만든다. 옥스퍼드대학교 양자물리학 교수인 아터 에카르트(Artur Ekert) 교수는 “보통 보안 평가는 문제를 쫓는 동시에 또 다른 문제가 보안을 우회하는 과정이 반복한다. 암호화 기반 격자는 수학적 관점에서 매우 간편한 방식이다”라고 말했다.

NIST가 지원하는 알고리즘을 개발한 여러 연구팀은 양자 컴퓨터가 문제를 푸는 데 걸리는 시간을 효율적으로 시뮬레이션할 수 있다고 말한다. CRYSTALS-Dilithium 개발 작업에 참여한 IBM 연구원 바딤 류바셰프스키(Vadim Lyubashevsky)는 “양자 컴퓨터가 없어도 양자 프로그램을 작성하고 양자 컴퓨터로 실행하는 것을 알 수 있다”라고 전했다. 그러나 새로운 양자 알고리즘이 앞으로 어떤 방식으로 실행될 지는 아무도 모른다.

실제로 NIST가 단축한 양자 알고리즘 최종 목록 중 하나이자 ‘레인보우(Rainbow)’라는 이름으로 알려진 구조화된 격자는 IBM 연구원 와드 불렌스(Ward Beullens)가 ‘노트북으로 일주일 만에 레인보우 분해하기(Breaking Rainbow Takes a Weekend on a Laptop)’라는 제목의 논문을 게재할 당시 경연에서 탈락했다. 영은 NIST의 발표는 전체 프로젝트를 저하할 수 있는 구조화된 격자의 코드 분해에 대한 관심 집중으로 이어질 것이라고 주장했다.

에카르트 교수는 보안과 효율성 간의 신중한 균형이 필요하다고 말했다. 기본 조건에서 암호화 키를 더 오래 사용하도록 제작한다면, 해독이 더 어려워질 것이다. 그와 동시에 더 강력한 연산 처리 능력이 필요하기도 하다. 포스트 양자 암호가 RSA만큼 널리 배포된다면, 매우 심각한 환경 영향이 발생할 수 있음을 의미한다.

영은 NIST가 약간 무지한 사고를 지녔다고 비난했다. 반면, 에카르트 교수는 더 자세한 보안 분석이 필요하다는 견해를 전했다. 그러나 보안 분석 능력에 필요한 양자학과 암호학 지식이 모두 풍부한 전문가는 전 세계를 통틀어 보더라도 극소수에 불과하다.

앞으로 2년간 NIST는 표준 초안을 발행하고 전문가의 의견을 요청한 뒤 전 세계가 채택하기를 바라면서 양자 증명 암호화의 새로운 형태를 최종 발표할 것이다. 무디 박사는 이후 기존 구축 사항에 따라 기업이 새로운 표준을 실제로 활용하는 데 10~15년 걸릴 전망이지만, 보안이 취약해질 수 있다고 예측한다. 엘 카파라니는 “지금 당장 시작해야 한다. 의료 기록이나 지식 재산권, 개인 정보 등을 철저한 보안 수준과 함께 보호하고자 한다면, 지금 당장 새로운 표준 변화를 시작해야 한다”라고 주장했다.

** 위 기사는 와이어드UK(WIRED.co.uk)에 게재된 것을 와이어드코리아(WIRED.kr)가 번역한 것입니다. (번역 : 고다솔 에디터)

<기사원문>
Will These Algorithms Save You From Quantum Threats?