What are quantum-resistant algorithms—and why do we need them?

‘양자저항 알고리즘’이란 무엇이고, 우리에게 그것이 필요한 이유는?

양자컴퓨터가 강력해지면 현재 우리를 안전하게 보호하는 암호화 알고리즘을 깨뜨릴 수 있다. 이러한 상황에 대비하기 위해서 새로운 암호화 알고리즘을 찾는 작업이 추진되고 있다.

암호화 알고리즘은 온라인에서 우리의 사생활을 보호해주고, 안전한 정보 전송을 가능하게 해준다. 하지만 전문가들 중에서는 양자컴퓨터가 언젠가 이러한 암호화 알고리즘을 깨뜨려서 우리를 해커와 사기꾼들의 공격에 무방비로 당하게 만들까 봐 걱정하는 사람이 많다. 그리고 실제로 그러한 양자컴퓨터가 사람들이 생각하는 것보다 우리 곁에 더 가까이 다가와 있을지도 모른다.

우리가 이런 가장 강력한 성능의 양자컴퓨터에도 맞설 수 있는 새로운 유형의 알고리즘을 설계하기 위한 작업에 몰두하고 있는 이유가 이 때문이다.

암호화 알고리즘의 역할은?

암호화 알고리즘은 읽을 수 있는 데이터를 읽을 수 없는 비밀 형태로 변환하여 개방된 인터넷에서 안전하게 공유될 수 있게 해준다. 이러한 알고리즘은 웹사이트의 트래픽이나 이메일 콘텐츠 같은 모든 유형의 디지털 통신을 보호하는 데 사용되며, 웹의 기본 개인정보 보호, 신뢰, 보안에 필수적이다. 현재 널리 사용되는 표준 암호화 알고리즘에는 대칭키(symmetric-key)와 공개키(public-key) 알고리즘이 있다.

사람들이 일반적으로 암호화라고 생각하는 것이 바로 ‘대칭키 암호화(symmetric-key encryption)’다. 이것은 ‘키(key)’를 사용하여 데이터와 메시지를 암호화하므로 키가 없으면 아무도 암호화된 데이터를 해독할 수 없다. 이 방식은 데이터베이스나 하드디스크 드라이브에 저장된 민감한 데이터를 보호하는 데 사용된다. 민감한 이용자 정보로 가득 찬 데이터베이스를 손상시키는 데이터 침해(data breach)도 기본적인 데이터가 암호화되어 있으면 어느 정도 괜찮을 수 있다. 해커들이 암호화된 데이터를 손에 넣더라도 읽을 수 있는 방법이 없기 때문이다.

‘공개키 알고리즘’도 중요하다. 이 알고리즘은 대칭키 암호화의 근본적인 문제점을 해결하는 데 도움을 준다. 여기서 말하는 근본적인 문제란 애초에 대칭키를 공유할 수 있는 안전한 방법이 필요한 문제가 있다는 뜻이다. 공개키 알고리즘은 수신자가 개인적으로 가지고 있는 키와 공개되는 키로 이루어진 키 세트를 사용한다.

누구든 수신자의 공개키를 이용해 데이터를 암호화할 수 있고 이렇게 암호화된 데이터는 수신자만이 개인 키를 사용해서 해독할 수 있다. 이 방법은 대칭키를 전송하는 데 사용될 수 있고 반대로 디지털 서명에도 사용될 수 있다. 수신자마다 고유한 개인 키를 가지고 있기 때문에 이러한 개인 키를 이용해 자신의 신원을 입증할 수 있는 것이다.

암호화 알고리즘이 양자 저항성을 가져야 하는 이유는?

암호화 알고리즘은 수학적으로 해독하기가 어렵기 때문에 데이터를 비밀로 유지할 수 있다. 조합 가능한 모든 문자열을 무차별적으로 하나씩 대입해보는 브루트포스(brute force) 방식을 사용해서 암호화 키 한 세트를 풀어내려면 현대 컴퓨터로는 수조 년이 걸릴 것이다.

그러나 양자컴퓨터가 진지하게 논의되기도 전인 1990년대에 수학자 피터 쇼어(Peter Shor)는 이론적인 양자컴퓨터가 작동하는 방식이 특히 공개키 암호화에 사용되는 종류의 수학을 푸는 데 적합하다는 것을 발견했다.

당시에 양자컴퓨터는 존재하지 않았지만 다른 수학자들은 이러한 ‘쇼어 알고리즘(Shor’s Algorithm)’이 양자컴퓨터로 공개키 암호화를 푸는 데 이론적으로 사용될 수 있다는 것을 확인할 수 있었다. 이제 충분한 처리 능력을 가진 양자컴퓨터가 만들어지면 오늘날 우리가 공개키 암호화를 위해 의존하고 있는 알고리즘은 쉽게 깨질 수 있다는 것이 널리 받아들여지고 있다. 미국 국립표준기술연구소(National Institute of Standards and Technology, NIST)는 불과 10~20년 후면 이러한 작업을 수행할 수 있는 양자컴퓨터가 준비될 것으로 전망한다.

다행히도 대칭키 암호화 방식은 매우 다르게 작동하고 사용하는 키의 크기를 늘리는 것만으로도 보안을 유지할 수 있기 때문에 위험하지 않다. 하지만 이것도 수학자들이 양자컴퓨터로 대칭키 암호화를 해독하는 방법을 알아낼 수 없을 때만 유효한 얘기다. 그러나 키 크기를 늘린다고 해도 현재 공개키 암호화 알고리즘을 양자컴퓨터로부터 보호할 수는 없다. 따라서 새로운 알고리즘이 필요하다.

우리가 현재 사용하고 있는 암호화를 양자컴퓨터가 푼다면?

일단 좋지 않다. 대체할 방법이 없는 상황에서 공개키 암호화가 갑자기 풀리면 디지털 보안이 심각하게 손상될 수 있다. 예를 들어 웹사이트들은 인터넷 연결을 안전하게 유지하기 위해 공개키 암호화를 사용하므로 공개키 암호화가 사라지면 웹사이트를 통해 민감한 정보를 보내는 것이 더는 안전하지 않을 것이다. 암호화폐 역시 기반에 있는 블록체인(blockchain) 기술을 보호하는 데 공개키 암호화 방식을 사용하므로 블록체인 장부의 데이터도 더는 신뢰할 수 없게 될 것이다.

또한 해커나 국가가 현재는 해독할 수 없는 매우 민감한 데이터를 가지고 있다가 나중에 양자컴퓨터를 사용할 수 있게 되면 해독할지도 모른다는 우려도 있다.

양자저항 알고리즘(quantum-resistant algorithm) 작업의 진행 상황은?

미국에서 국립표준기술연구소(NIST)는 양자컴퓨터의 공격에도 견딜 수 있는 새로운 알고리즘을 찾고 있다. NIST는 2016년에 공개 제출을 받기 시작했고 지금까지 4개의 최종 후보와 3개의 백업 알고리즘으로 후보가 좁혀졌다. 이러한 새로운 알고리즘은 쇼어 알고리즘을 사용하는 양자컴퓨터의 공격을 견딜 수 있는 기술을 사용한다.

프로젝트 책임자 더스틴 무디(Dustin Moody)는 NIST가 새로운 알고리즘이 올바르고 안전하게 사용되도록 하기 위한 지침을 만드는 것을 포함해 2024년까지 네 개의 최종 후보에 대한 표준화를 완료할 예정이라고 말했다. 나머지 세 개의 알고리즘에 대한 표준화는 2028년까지 이루어질 것으로 예상된다.

새로운 표준을 위해 후보들을 검토하는 일은 주로 대학과 연구기관 소속 수학자들과 암호학자들이 담당한다. 이들은 포스트 양자 암호 체계에 대한 제안서를 제출하고 그것들을 공격할 방법을 모색하며 논문을 발표하고 서로 다른 공격 방식을 구축하여 결과를 공유한다.

이런 방식으로 그들은 제대로 공격당하거나 알고리즘에 약점이 있는 것으로 보이는 후보를 하나씩 제거한다. 우리가 현재 암호화에 사용하는 표준을 만들 때도 비슷한 방법이 사용됐다.

그러나 이러한 새로운 알고리즘을 깨뜨릴 수 있는 새로운 유형의 양자 공격이나 심지어 기존 방식의 공격이 언젠가 발견되지 않을 것이라는 보장은 없다.

암호학자 토머스 데크루(Thomas Decru)는 “암호화 알고리즘이 깨지지 않을 것임을 증명하는 것은 불가능하다”며 “하지만 “암호화의 세계에서 어떤 것이 ‘시간의 시험’을 견뎌낸다면 신뢰가 커질 수 있을 것”이라고 말했다. (By Tammy Xu)

미리보기 2회1회

MIT Technology Review 구독을 시작하시면 모든 기사를 제한 없이 이용할 수 있습니다.