LG CNS 자세히보기

IT Solutions

[보안동향] 코앞으로 다가온 양자 컴퓨터, 포스트 양자암호를 찾아라!

LG CNS 2021. 12. 16. 09:30

 

현재 우리는 0과 1로 구성된 디지털 컴퓨터를 사용하고 있습니다. 그러나 최근 양자 역학의 발전으로 양자 컴퓨터의 발명이 코앞으로 다가왔습니다. 구글, IBM 등 여러 회사에서 양자 컴퓨터 개발을 위한 연구에 힘을 쏟고 있는데요. 10년 안에 개발하는 것을 목표로 힘쓰면서 암호도 양자 컴퓨팅 시대에 맞춰 준비 중입니다. 

양자 컴퓨터에 대비하기 위해, 양자 컴퓨터에서 큐비트(qubit)를 이용한 양자 암호와 기존의 컴퓨터에서 사용할 포스트 양자 암호(Post Quantum Cryptography), 두 가지에 대한 연구가 활발하게 진행되고 있습니다. 양자 컴퓨터가 개발돼도 현재 사용하고 있는 기존의 컴퓨터를 대체하는 것이 아니기 때문인데요. 양자 컴퓨터가 슈퍼컴퓨터와 같이 특정 목적의 컴퓨터로 사용될 확률이 높기 때문에 암호도 양자 컴퓨터와 기존의 컴퓨터 두 가지 경우를 대비하는 것입니다.

 

 

여기서 양자 컴퓨터에서 사용하기 위해 암호에 대한 연구를 진행하는 것은 당연한 흐름으로 보일 것입니다. 그런데 양자 컴퓨터의 개발 때문에 기존 컴퓨터의 암호를 새로 연구하는 것은 바로 이해가 되지 않으실 겁니다. 그 이유는 바로 양자 컴퓨터가 기존의 컴퓨터의 암호 체계를 무너뜨릴 수 있기 때문입니다. 

양자 컴퓨터를 이용하면 현재 사용하는 암호가 기반으로 하는 난수를 빠르게 풀어내는 쇼어 알고리즘(Shor's algorithm)을 구현할 수 있게 됩니다. 그렇게 되면 현재 사용하는 RSA, ECC 형식의 암호들은 더는 안전하지 않은 암호가 되죠. 이를 대비하기 위해 미리 포스트 양자 암호에 대한 연구를 진행하는 것입니다.

이를 위해 NIST(National Institute of Standards and Technology, 미국표준기술연구소)에서는 2016년 ‘Post Quantum Conference’를 주최했습니다. 이 콘퍼런스는 총 3개의 라운드로 가장 안전하고 빠른 양자 암호의 표준을 정하는 것을 목표로 합니다. 

이와 같은 절차를 통해 표준화된 암호로는 현재 활발히 사용되는 AES가 있습니다. 현재 전 세계에서 널리 사용되고 있는 AES 표준을 발표했던 만큼, 포스트 양자 암호 관련한 연구의 중심에 이 콘퍼런스가 있다고 할 수 있죠. 이 콘퍼런스에 수많은 포스트 양자 암호 후보가 올라왔으며, 이에 꼬리를 물고 각 암호를 분석하고, 속도를 높이기 위한 최적화 기법 등 암호 알고리즘을 대상으로 한 연구들도 활발히 이뤄졌습니다.

NIST 콘퍼런스에서 올라온 후보는 크게 격자기반 암호(Lattice-based Cryptography), 다변수기반 암호(Multivariate-based Cryptography), 코드기반 암호(Code-based Cryptography), 해시기반 암호(Hash-based Cryptography), SIDH 암호(Supersingular Isogeny Diffie-Hellman Cryptography), 기타 카테고리로 나눌 수 있습니다. 

각각의 암호가 기반하고 있는 난제가 이렇게 나누는 기준이 됩니다. 기존의 RSA(Rivest–Shamir–Adleman)가 기반하던 난제인 큰 수의 소인수 분해 문제는 곱셈과 나눗셈 개념으로도 충분히 이해할 수 있었는데요. 새로 연구되는 암호의 난제는 더 복잡하지만 양자 컴퓨팅에는 안전하다고 알려진 난제입니다. 

이에 속하는 암호 중에는 예전부터 존재하던 암호들도 있습니다. 그동안은 RSA(Rivest–Shamir–Adleman), ECC(Elliptic Curve Cryptography)와 비교했을 때 키 사이즈가 너무 크다든지, 난제의 안정성 증명에 대한 문제 등으로 경쟁에서 밀려 사용되지 않았습니다. 하지만 RSA, ECC의 위치가 위협받는 지금, 다시 수면에 위로 올라와 연구되기 시작했습니다.

이렇게 시작된 첫 번째 라운드에서 총 82개의 암호가 제출됐습니다. 이 중에서 64개의 알고리즘이 선정돼 다음 라운드까지 분석과 최적화 과정을 거쳤습니다. 이 결과 2라운드에서는 총 26개의 알고리즘이 선정됐습니다.

 

 

위의 표에서 볼 수 있는 것처럼 격자 기반 암호와 코드 기반 암호의 수가 가장 많았는데요. 이 암호들이 아무래도 오래 연구됐고, 다른 분야에서 사용되고 있는 알고리즘이 존재하기 때문이라고 추측할 수 있습니다.

2020년 7월, 수많은 석학의 논쟁 끝에 3라운드에서 총 7개(키 교환 메커니즘 - 4개, 서명- 3개)의 최종 후보가 선정됐고, 8개(키 교환 메커니즘 - 5개, 서명- 3개)의 대체 후보가 선정됐습니다. 최종 3라운드는 보안을 중점으로 보면서 다양한 카테고리의 암호들을 선정했다고 하였고, 보안 이슈가 있었던 알고리즘들은 모두 제외됐다고 합니다.

최종 후보 중 키 교환 메커니즘에 속하는 Kyber, NTRU, SABER은 structured Lattice에 기반하고, Classic McEliece는 Code 기반 암호입니다. 키 교환 메커니즘의 대체 후보로는 NTURprime, FrodoKEM이 격자기반 암호이고, BIKE, HQC 가 structured code 기반 암호, 타원곡선의 아이소제니(Isogenies)에 기반한 SIKE가 있습니다. 서명 후보는 structured Lattice에 기반한 Dilithium, Falcon, 다변수 문제에 기반한 Rainbow가 있고, 대체 후보로 다변수 문제에 기반한 GeMSS, symmetric primitives에 기반한 Picnic, 해시 함수의 안전성에 기반한 SPHINCS+가 있습니다.

치열한 경쟁을 뚫고 선정된 후보들은 2020년 10월 NIST에 최종본을 제출한 상태입니다. NIST는 2022년에서 2024년 사이에 표준을 발표할 예정이라고 밝혔는데요. AES 때와는 다르게 표준을 단일로 선정하지 않을 수 있다고 가능성을 열어두었습니다. 분야별로 골고루 최종과 대체 후보를 선정한 점으로 보아 폭넓게 고려해 선정할 것으로 보입니다.

 

위에서 살펴본 것과 같이, 적어도 3년 안에 NIST에서 새로운 공개키 암호의 표준을 발표할 것입니다. 이렇게 새로운 암호의 발표에 앞서 앞으로의 변화에 대비해야 합니다. 암호가 사용되고 있는 수많은 분야에서 대대적인 알고리즘 교체가 일어날 수 있기 때문인데요. 그에 따른 충격을 완화하기 위해 차분히 변화를 준비해야 합니다.


글 ㅣ LG CNS RED팀 안수정 선임

 

*해당 콘텐츠는 저작권법에 의해 보호받는 저작물로 LG CNS 블로그에 저작권이 있습니다.
*해당 콘텐츠는 사전 동의없이 2차 가공 및 영리적인 이용을 금하고 있습니다.