양자 컴퓨터 공격에도 안전한 양자 암호의 이해
양자 컴퓨터 공격에도 안전한 양자 암호의 이해
  • 김광조 교수 / 카이스트 전산학부 정보보호대학원
  • 승인 2017.03.01 19:57
  • 댓글 0
이 기사를 공유합니다

21세기에 들어와서 종래의 유·무선 정보 시스템에 클라우드 및 SNS 등의 새로운 정보 시스템이 보급되어 사이버 공간상에 상호 의사 전달과 연결의 편리성이 증대했지만, 이에 대한 공격과 보안 위협은 복잡화·지능화·조직화되고 있다. 현재 사용 중인 암호와 인증방식은, 새로운 해독 기술의 진전으로 공격이 성공하면 일반적으로 안전성을 강화하기 위하여 키의 크기 등과 같이 비도 변수를 단순 증가하여 사용하는 사후 약방문식 대응 기술이다.
인류는 기원전 300년 시저시대 이래 현재까지 멀리 있는 상대방에게 효과적이고 비밀리에 메시지를 보내려고 노력했다. 지금도 우리는 인터넷이라는 사이버 공간을 통하여 카카오톡과 같은 문자 통신 서비스를 이용하여 친구에게 쉽게 보낼 수 있지만(일반 채팅), 사이버 공간상에 누구나 접속할 수 있으므로 제 3자에 의한 정보 누설이 이루어지지 않고 통신 상대방 간에만 비밀 문자를 보낼(보안 채팅) 필요가 있다. 이러한 과정은 어떻게 이루어지는 것일까? 아파트 출입구에 열쇠를 가지고 우리가 문을 채우면 열쇠를 가지고 있지 않은 사람은 들어갈 수가 없다. 디지털화되어 있는 정보도 마찬가지로, 기계적인 열쇠와 같은 체계를 만들 수 있다면 암호화가 가능할 것이다.
우리는 제 3자가 알 수 없는 변환을 해야 하는 정보를 평문이라고 하면 평문을 비밀키와 암호 체계(알고리즘)에 동작한 결과를 암호문이라 한다. 암호화 체계의 수학적인 역함수를 우리는 복호알고리즘이라고 하면 송신자는 암호문이 공개된 공간(인터넷)을 통하여 전달하고 비밀 키를 알고 있는 수신자는 복호알고리즘으로 평문을 복구한다. 여기서 암호 및 복호 알고리즘은 누구나 알 수 있게 하고 두 사람만이 정보를 채우는 비밀 키 정보를 푸는 복호 키를 비밀로 하여야 한다. 여기서 두 개의 키가 동일한 비밀 정보이어야 하므로 비밀 키 암호 시스템(<그림 1>)이라고 한다.
비밀 키 암호 시스템에서 사용하는 키는 가용 공간에서 하나를 비밀로 선택하여 사용하게 되는 데, 가용 공간의 크기를 무한대로 하는 것은 불가능하여 한정된 유한 공간의 크기상에 있는 비밀 키 정보를 슈퍼 또는 가용할 수 있는 최대 크기의 컴퓨터로 탐색할 수 없게 설계되어 있다. 이런 비밀 키 암호로는 우리나라 표준으로 SEED, ARIA, LEA가 있으며 전 세계 표준으로는 AES가 있고 비밀 키의 크기는 128비트에서 256비트까지 사용할 수 있다.
비밀 키 암호 시스템은 송수신 상대방이 사전에 결정된 비밀 키를 공유할 수 있다면 동작이 수월하나, 송수신 상대방이 많아지고 비밀 통신을 하기 전에 비밀 키를 공유할 수 없다면 대단히 불편해진다.
 수학적으로 입력(개인 키)이 주어지면 출력(공개 키)을 쉽게 연산할 수 있으나 출력으로부터 입력을 구하기가 어려운 일방향 함수를 만들 수가 있다면 이 문제는 쉽게 해결할 수 있다. 
<그림 2>와 같이 수신 상대방의 공개 키를 암호화하여 전송하면 수신자만이 알 수 있는 개인키로만 원래의 평문을 복원할 수 있는 공개 키 암호 시스템이 구성될 수 있다. 이를 통하여 두 사람만이 비밀 키 암호 시스템에서 사용하는 비밀 키를 암호 통신 전에 공유할 수 있게 된다. <그림 2>에서와같이 송신자가 개인 키로 문서를 암호화하여 서명문(전자 서명)을 만들면 누구든지 송신자의 공개 키로 문서의 진위를 확인할 수 있다.   
현재 우리가 전자 상거래, 전자 결재, 웹 보안 등에 사용되는 암호 시스템 중 전 세계에 가장 널리 사용되는 공개 키 암호 시스템으로 DH(Diffie Hellman) 키 공유 방식 및 RSA(Rivest, Shamir, Adlemann) 공개 키 시스템이 대단히 널리 사용되고 있다. 이 방식은 1970년대 중반에 설계되어 송·수신자간의 보안 통신에 요구되는 비밀 키의 안전한 전송, 전자 문서의 디지털 서명, 개인 식별, 부인 방지 등의 목적으로 국가망, 국방망, 금융망 등 정보통신 전 분야에 걸쳐 널리 쓰이고 있다. 이러한 RSA 공개 키 암호, DH 방식, 타원곡선 암호 등은 문제의 크기에 준지수적(sub-exponential) 계산 시간을 소요하는 소인수분해 문제 또는 이산대수 문제에 암호학적 안전성의 근간을 두고 있다.
그러나, 소인수분해 및 이산대수 알고리즘의 개선과 컴퓨터 성능이 1년 반마다 2배씩 빨라진다는 무어의 법칙에 의한 디지털 컴퓨터 계산 능력의 급속한 향상으로, 1991년 330비트 정수의 소인수분해가 성공하였고, 2005년에는 660비트 정수의 소인수분해가 성공하여, 향후 2018년에는 1,024비트 정수가 소인수분해가 성공될 것으로 예측하고 있어, 현재 키의 크기가 2,048비트 이상의 정수를 사용하여야 RSA의 암호학적 안전성을 보장받을 수 있다.
한편, 1984년 Shor는 이러한 정수론적 문제에 근간을 둔 공개 키 암호 방식은 양자컴퓨터를 사용할 수 있다는 가정하에 문제의 크기와 관계없이 이른 시간 내에 소인수 분해 및 이산대수 문제를 해결할 수 있는 알고리즘을 제시하였다.
양자 컴퓨터는 0과 1만을 취급하는 2진 디지털 컴퓨터와 달리 그림 3과 같이 구(球)의 원점에서 3차원 공간에 있는 벡터 성분이라 할 수 있는 양자 비트(quantum bit)를  qubit로 간단히 표현하고 90도 벡터 성분을 “1”로, 270도 벡터 성분을 “0”으로 처리하면 1-qubit 양자 컴퓨터를 구성할 수 있을 것이다. 이 방향 성분을 구에서 직교 되도록 확장할 수 있다면 1-qubit에서  n-qubit 양자 컴퓨터를 구성할 수 있을 것이다.
당시에는 양자컴퓨터의 구현이 어려워 Shor의 주장은 이론적인 연구에 불과하였지만, 2014년 캐나다의 D-Wave사는 그림 4와 같이 세계 최초로 512-qubit 양자컴퓨터를 제작하여 Google, NASA 등에 판매하여 양자컴퓨터의 상용화가 거의 목전에 다가와 있는 것이 현실이고 혹자는 양자 컴퓨터의 상용화는 향후 15년간 수십억 불을 투자하면 가능할 것이라는 예측도 있다.
이러한 양자컴퓨터가 현실화된다면, Shor 알고리즘을 이용하여 RSA 공개 키, DH 키 분배 방식 및 타원 곡선 암호 시스템 등이 손쉽게 해독되어 현재 널리 보급되고 있는 보안 시스템이 갑자기 붕괴하는 패닉 상황이 발생할 수 있다. 따라서 전 세계 암호학자들은 양자컴퓨터를 이용한 공격에도 안전성을 보장할 수 있는 새로운 포스트 양자 암호 시스템을 연구하여 기존의 암호 시스템을 대체하고 다양한 시스템에 암호와 인증 체계를 준비하여야 한다고 주장하고 있다.
다행히 이러한 양자 컴퓨터 공격에도 안전한 암호 체계는 종래의 정수론적 어려움이 아닌 다른 대수학적 구조를 갖는 격자(Lattice) 문제, 다변수 다항식 문제, 해시 함수, 부호 이론 등을 근간으로 한 새로운 공개 키 암호 및 인증 기술이 과거 10년 전부터 미국, 일본, 유럽 등에서 이론적인 연구가 진행 중이다.
그러나 점차 가시화 대고 있는 양자 컴퓨터의 상용화에 대비로 2015년 미국의 NSA는 이러한 정수론적 문제 기반의 암호 체계를 수용하는 Suite B 암호 시스템의 사용 중지라는 결정을 내렸으며, 2016년 1월 일본에서 개최된 PQcrypt2016 국제 학술 대회에서 미국 표준 기구인 NIST는 각종 포스트 양자 암호 체계를 2016년 가을에 전 세계에 공모 예정이라고 발표하였으며 향후 5년 동안 제안된 포스트 양자 암호 체계의 안전성과 성능 평가를 통하여 표준안을 작성한다는 계획을 발표하였다.
우리나라도 선진국의 이러한 선행 연구에 대비에 대하여 포스트 양자 암호 체계에 대한 집중적인 연구 투자와 새로운 암호 인프라 구축에 최대한 서둘러야 하며, 국회에서도 양자 통신 진흥에 관한 특별법 제정을 서두르고 있는 현 시점에 국내에 정보통신 젊은 후속 세대들의 관심과 도전을 기대하여 본다.