[테크M=김광조 KAIST 전산학부·정보보호대학원 교수] 1980년 아날로그 신호를 0과 1 디지털 상태로 변환해 처리하는 반도체 기술 출현은 전자 부품이나 디지털 컴퓨터 분야에서 필요한 정보 처리와 저장 능력에 획기적인 진전을 가져왔다. 인텔을 창업한 무어(Moore)는 전자회로 선폭 간격을 1년 6개월마다 반으로 줄일 수 있다고 예측했다. 현재 반도체 선폭은 14nm(1나노미터 = 10-9)로 한계에 도달했다고 주장하는 학자도 있다.

반도체 소형화 기술은 작은 컴퓨터 같은 스마트폰 시대를 열었다. 또 스마트TV와 사물인터넷(IoT) 소자, 스마트 자동차, 드론, 로봇, 스마트가전에 초소형 반도체 기술을 활용해 생활에 엄청난 편의를 제공하고 있다.

반도체는 기본적으로 디지털 회로를 구성하는 트랜지스터를 켜고 끄는 신호를 제어해 0과 1이라는 디지털 정보를 표현한다. 이때 선폭이 14nm 이하인 전자회로에서 전자를 제어하는 기술은 현재 불가능하다. 이에 기존 체계와 달리 양자역학으로 전자보다 작은 양자 상태에서 이뤄지는 양자컴퓨터를 만들어야 할 필요성이 제기됐다.

소인수분해, 이산대수 문제에 기반한 현 암호체계

인터넷에서 카카오톡 같은 메시지를 이용하는 것을 채팅이라고 한다. 인터넷은 누구나 접근할 수 있어 제3자에 의한 불법 도청을 막으려면 둘만 아는 비밀 문자 같은 ‘보안 채팅’이 필요하다. 제3자가 알 수 없게 하려는 정보를 ‘평문’이라고 하면, 이 평문을 비밀키와 암호알고리즘으로 바꾼 걸 ‘암호문’이라고 한다.

송신자는 이 암호문을 인터넷으로 전달하고, 비밀키를 아는 수신자가 복호알고리즘으로 암호문을 평문으로 해석한다. 이때 암호와 복호알고리즘은 누구나 알 수 있다. 다만 정보를 잠그는 암호키와 정보를 푸는 복호키는 주고받는 두 사람만 아는 비밀로 해야 한다. 이게 ‘비밀키 암호시스템’이다. 복호알고리즘은 암호체계에서 수학적인 역함수를 의미한다.

비밀키 암호시스템에서 복호키를 아는 사람이 있으면 누구나 암호플 풀 수 있어 문제가 된다. 따라서 복호키 전달에 각별한 주의가 필요하다. 특히 송수신 상대방이 많으면 이 방식은 대단히 불편해진다.

이런 단점을 극복하려고 만든 것이 ‘공개키 암호방식’이다. 수학적으로 ‘개인키’를 입력하면 ‘공개키’ 출력이 쉽다. 하지만 반대로 출력에서 입력을 구하기는 매우 어려운 일방향 함수를 만들어 비밀키 암호방식이 지닌 단점을 해결했다. 상대에게 공개키로 암호화해 전송하면, 수신자만 알 수 있는 개인키로 평문을 복원하는 원리가 공개키 암호시스템이다. 이때 두 사람만 비밀키를 통신 전에 공유할 수 있어 안전하다. 또 송신자가 개인키로 문서를 암호화해 서명문을 만드는 ‘전자서명’을 할 수 있고, 누구든지 송신자 공개키로 문서 진위를 확인할 수 있다.

양자컴퓨터 이용한 새 소인수분해 알고리즘 개발

전자상거래와 전자결재, 웹 보안에 사용하는 공개키 암호시스템 중 세계에서 가장 널리 사용하는 건 ‘DH키공유방식’과 ‘RSA공개키 시스템’이다. 이들은 1970년대 중반에 설계돼 보안 통신에 필요한 비밀키 안전 전송, 전자문서 디지털 서명, 개인 식별, 부인 방지 같은 목적으로 국가망과 국방망, 금융망 같은 정보통신 전 분야에 걸쳐 널리 쓰이고 있다.

 RSA공개키와 DH키공유는 소인수분해나 이산대수 문제 안전성에 근간을 두고 있다. 1991년에 330비트 정수 소인수분해를 성공했고, 2005년에는 660비트 정수 소인수분해를 성공했다. 2018년 전문가들은 곧 1024비트 정수 소인수분해도 성공할 수 있을 것으로 예측하고 있다. 따라서 소인수분해를 하는데 걸리는 시간이 오래 걸린다는 사실에 기반한 RSA공개키가 안정성을 보장받으려면 최소 2048비트를 넘는 정수를 암호키로 사용해야 한다는 결론이 나온다.

한편 1994년 수학자 피터 쇼어는 양자컴퓨터를 이용한 새로운 소인수분해 알고리즘을 개발했다. 양자컴퓨터를 사용할 수 있다는 가정에서 문제 크기에 관계없이 빠른 시간에 소인수분해와 이산대수 문제를 해결할 수 있는 ‘쇼어 알고리즘’을 제시한 것이다. 당시에는 양자컴퓨터 구현이 어려워 이론적인 연구에 불과했다.

쇼어 알고리즘은 ‘양자푸리에 변환’ 방식을 이용해 소인수분해나 이산대수 문제를 푸는 시간을 혁신적으로 단축한다. 양자컴퓨터는 양자역학에서만 존재하는 큐비트가 지닌 ‘중첩’과 ‘얽힘’ 원리를 바탕으로 임의 함수 주기를 찾는 효율적인 알고리즘이다.

만약 양자컴퓨터가 등장해 쇼어 알고리즘을 사용한다면 RSA공개키와 DH키공유, 타원 곡선 암호시스템 같은 기존 암호체계가 손쉽게 해독될 것이다. 이는 현재 모든 곳에 보급된 보안시스템이 갑자기 통째로 붕괴되는 패닉 상황을 만들 것이다. 이미 세계 암호학자들은 이런 양자컴퓨터 공격에도 안전을 보장할 수 있는 양자 내성 암호인 ‘포스트 양자암호시스템’을 연구하고 있다.

암호화폐 안전성 위협하는 양자컴퓨터

지금까지 국가는 중앙은행에서 실물 화폐를 발행해 모든 사람이 신뢰할 수 있는 중앙집중 신뢰 구조로 화폐를 활용했다. 또 정부는 실물 통화에 대한 각종 통제력을 발휘할 수 있다. 외환 송금도 은행마다 송금 거래 업무를 담당하는 거래소를 통해 이뤄진다.

이런 실물 화폐를 대체할 수 있는 것으로 주목받고 있는 암호화폐는 사이버 세상에서 거래되는 가상화폐다. 암호화폐는 실물화폐가 지닌 중앙집중 신뢰 구조를 벗어나 구성원 모두가 거래 원장을 분산해 관리하고 책임지는 ‘분산 신뢰 구조’를 기반으로 한다. 이를 가능케 하는 것이 블록체인 기술이다.

중앙은행이 가진 발권 기능을 능가하는 블록체인 기술이 새롭게 경제 생태계를 만들어가고 있다. 블록체인을 이용한 암호화폐는 분산 환경에서 참가자 모두에게 동등한 권한과 계산력을 부여하는 것이 특징이다. 또 이를 바탕으로 P2P 통신망에서 거래 내역 무결성과 공정성을 보장하는 블록체인 기술은 4차산업혁명시대에 새 기술로 각광 받고 있다.

2008년 사토시 나카모토는 블록체인 기술을 기반으로 비트코인이라는 암호화폐를 세상에 내놓았다. 이후 이더리움과 리플, 라이트코인, 아이오타 같은 수많은 암호화폐가 등장해 세계에서 유통되며, 수백조원에 달하는 사이버 경제를 만들고 있다.

블록체인에서 통용되는 정보 보안성을 보장하는 핵심 암호 기술은 데이터를 일정한 크기로 압축하는 해시함수, 거래정보 무결성을 보장하는 타원곡선 전자서명기술(ECDSA), 이중지불이나 사용을 방지하는 작업증명이나 지분증명기술, 다자간 고장감내 암호프로토콜 등에 의존하고 있다.

비트코인과 이더리움, 리플 등은 타원곡선을 이용한 전자서명방식을 이용하고 있다. 이 방식은 일반 컴퓨터를 이용할 때는 안전성을 보장할 수 있으나 양자컴퓨터가 상용화가 되면 몇 분 안에 암호가 해독될 수 있다. 이에 따라 암호화폐 경제가 급속하게 몰락할 수 있다.

양자컴퓨터 상용화 대비한 포스트 양자암호

2015년 미국 국가안보국(NSA)은 양자컴퓨터 상용화를 대비해 정수론 기반 암호체계를 수용하는 ‘Suite B 암호시스템’ 사용 중지 결정을 내렸다. 이어 2016년 1월 미국 국립표준기준연구소(NIST)는 일본에서 개최한 ‘PQcrypt 2016 국제학술대회’에서 세계를 대상으로 포스트 양자암호체계를 공모한다고 발표했다. 공모는 2017년 11월 30일 마감됐다.

공모에는 격자(Lattice), 다변수 다항식, 해시함수, 아이소제니(Isogeny) 기반 양자 내성 암호 방식 82종류가 제안됐다. 1차 심사에서 62개 방식을 선정했다. NIST는 2019년 8월 2차 회의에서 암호 후보를 압축하고, 2021년까지 알고리즘 선정을 마칠 계획이다.

미국과 일본, 유럽 같은 암호 선진국에서는 10년 전부터 양자 내성 암호 연구를 진행해오고 있다. 2017년 구글은 크롬 카나리아(Chrome Canary) 브라우저에 양자컴퓨터 공격에도 안전한 격자기반 키공유 방식인 ‘뉴 호프(New Hope)’를 구현해 실험하고 있다.

현재까지 알려진 암호시스템 대부분은 유한한 키를 사용하므로 절대적으로 안전한 것은 존재하지 않는다고 말할 수 있다. 또 암호시스템 해독 능력은 설계 능력과 비교했을 때 두 배 이상 빠르게 진화하고 있다.

따라서 우리나라도 포스트 양자 암호체계에 대한 집중적인 연구 투자와 새로운 암호 인프라 구축을 서둘러야 한다. 범국가적으로 철저하게 대비해 양자 내성을 갖는 암호화폐와 안전한 4차산업혁명 인프라를 구축해야 한다.

김광조
현재 KAIST 전산학부 교수로 재임 중이며, IACR Fellow, IEEE, ACM, IEICE회원 및 한국정보보호학회 명예회장, IFIP-TC11 한국 대표, Cryptography Journal 주 편집자, J. of Mathematical Cryptography 편집자로 활동 중이다.

<이 기사는 테크M 제67호(2018년 11월)에 게재됐습니다.>