기존 암호체계 치명적 위험…양자컴도 못 뚫는 '양자내성암호' 필수

"인터넷 암호 기술 더 이상 안전하지 않다"

암호 기술은 늘 '암호를 만드는 사람'과 '암호를 푸는 사람' 사이의 끝없는 대결 속에서 발전해왔다. 더 강한 암호를 설계하면, 이를 깨려는 시도가 뒤따르고, 다시 그보다 강력한 암호가 등장하는 식이다. 이 치열한 공방 속에서, 최근 가장 뜨거운 화두가 되고 있는 것이 바로 '양자내성암호(Post-Quantum Cryptography·PQC)'다.

이 분야의 권위자인 심경아 국가수리과학연구소(수리연) 공공기반연구본부장은 암호 연구의 본질을 이렇게 설명한다. 2020년, 그녀가 연구팀을 이끌며 '양자 컴퓨터로도 뚫리지 않는 고속 암호 기술'을 개발한 것은 국내 암호 기술이 세계적으로 인정받는 계기가 됐다.

픽사베이 제공

국제연합(UN)은 2025년을 '세계 양자 과학의 해'로 지정했다. 과학계에서는 이를 디지털 기술이 중심이었던 시대에서, 양자 기술이 주도하는 시대로 전환하는 원년으로 보고 있다. 그리고 이 변화 속에서 가장 바쁜 사람들은 바로 암호 연구자들이다.

양자 컴퓨터의 등장이 머지않았기 때문이다. 지금 우리가 쓰는 암호 기술은 현재의 컴퓨터로는 풀기 어려운 수학적 문제를 기반으로 보안을 유지한다. 하지만 양자 컴퓨터가 충분히 발전하면, 기존 암호 체계는 빠르게 무력화될 수 있다.

1994년 '쇼어 알고리즘' 외면, 30년 뒤 치명적 위협 노출

김광조 한국과학기술원(KAIST) 명예교수는 이 문제를 오래전부터 경고해왔다. 그는 "1994년, 수학자 피터 쇼어가 기존 암호의 핵심 원리를 무너뜨릴 수 있는 '쇼어 알고리즘'을 발표했을 때만 해도, 양자 컴퓨터는 먼 미래의 기술로 여겨졌다. 하지만 불과 30년 만에, 현재 우리가 사용하는 암호 기술은 치명적인 위협에 노출됐다"고 지적했다.

김 교수는 한국 최초로 국제암호학회(IACR) 석학회원으로 선정된 이 분야 최고 권위자다. 그는 2021년, 미국 국립표준기술연구소(NIST)에서 기존 방식보다 뛰어난 성능을 갖춘 양자내성 전자서명 '솔매(SOLMAE)'를 개발했고, 올해는 이를 한국 표준으로 지정하기 위한 작업을 추진하고 있다.

김광조 한국과학기술원(KAIST) 명예교수.

심경아 본부장도 같은 우려를 표했다. "양자 컴퓨터가 등장하면, 지금 우리가 인터넷에서 사용하는 암호 기술은 더 이상 안전하지 않을 가능성이 높다"면서 "미래에도 안전한 통신과 데이터 보호를 위해, 암호 체계를 '양자내성암호(PQC)'로 바꾸는 것이 필수적"이라고 강조했다.

PQC는 양자 컴퓨터로도 쉽게 풀리지 않는 암호 기술이다. 지금 사용되는 암호는 특정한 수학 문제를 푸는 것이 어렵다는 점을 이용해 보안을 유지하지만, 만약 이 문제가 해결된다면 암호도 함께 깨지게 된다. PQC는 이러한 위험을 피하기 위해, 양자 컴퓨터가 발전해도 풀기 어려운 새로운 방식을 적용한 암호 체계다. 두 전문가의 의견은 하나로 모인다. "PQC로의 전환을 서둘러야 한다."

PQC로의 전환 서둘러야

PQC는 지금 우리가 쓰는 일반적인 컴퓨터뿐만 아니라, 미래에 나올 강력한 양자 컴퓨터로도 쉽게 풀 수 없는 방식으로 정보를 보호하는 암호 기술이다. 이 기술은 특정한 수학 문제를 풀기 어렵다는 원리를 이용해 보안을 유지한다. 그런데 만약 이 수학 문제가 풀리면, 그 암호도 안전하지 않은 것이다.

우리가 많이 사용하는 암호 기술 중 하나가 RSA라는 방식이다. 이 기술은 1978년에 로널드 리베스트, 아디 샤미르, 레오나드 애들먼이라는 세 사람이 개발했다. RSA는 두 개의 매우 큰 소수를 곱해서 만든 숫자는 쉽게 계산할 수 있지만, 반대로 그 숫자를 원래의 두 소수로 되돌리는 과정(소인수분해)은 극도로 어렵다는 수학적 원리를 이용한다.

심경아 국가수리과학연구소 공공기반연구본부장.

일반적인 컴퓨터로는 이 계산을 푸는 데 엄청난 시간이 걸리기 때문에 RSA 암호가 안전하게 사용될 수 있었다. 하지만 '쇼어 알고리즘'이라는 새로운 계산 방법이 등장하면서, 양자 컴퓨터가 이 소인수분해 문제를 매우 빠르게 해결할 수 있다는 사실이 알려졌다. 이 때문에 RSA를 포함한 기존 암호 방식이 더 이상 안전하지 않다는 가능성이 제기된 것이다.

이런 문제를 해결하기 위해 등장한 것이 바로 PQC다. PQC에는 여러 가지 암호 방식이 포함되는데, 대표적으로 격자 기반 암호(Lattice-based cryptography), 다변수 다항식 암호(Multivariate polynomial cryptography), 해시 기반 암호(Hash-based cryptography) 등이 있다. 이 중에서도 특히 격자 기반 암호는 현재까지 알려진 양자 알고리즘으로도 쉽게 풀리지 않는 것으로 평가되며, 가장 안전한 방식으로 주목받고 있다.

격자 기반 암호, '컴퓨터 연산량 2의 n 제곱'으로 폭발적 증가

격자(Lattice)는 쉽게 말해 바둑판 위의 교차점처럼 규칙적으로 배열된 점들의 집합이다. 어떤 한 점에서 출발해 특정 방향으로 같은 거리만큼 이동하면 항상 다른 점에 도달하는 구조를 갖는다. 이렇게 점과 선으로 이루어진 격자는 2차원 공간에서 쉽게 시각화할 수 있지만, 실제 암호 기술에서는 이를 훨씬 높은 차원(n 차원)으로 확장해서 사용한다.

차원이 커질수록 가능한 점의 개수가 기하급수적으로 증가하며, 컴퓨터가 이를 계산하는 데 필요한 연산량도 2의 n 제곱(2의 n 승)에 비례해 폭발적으로 늘어난다. 이 때문에 높은 차원의 격자 문제는 양자 컴퓨터로도 쉽게 풀기 어려운 암호 기술의 기반이 된다.

여기서 중요한 점은 격자 기반 암호가 절대 풀리지 않는 것이 아니라, 기존의 알고리즘으로는 풀기가 극도로 어렵다는 점이다. 과학자들은 현재 사용 가능한 암호 기술 중 격자 기반 방식이 가장 강력하다고 평가하며, 양자 컴퓨터가 계속 발전하더라도 최소한 10년 정도는 안전할 가능성이 높다고 보고 있다. 이는 양자 컴퓨터가 실용화된 이후에도 격자 기반 암호가 일정 기간 보안성을 유지할 수 있을 것이라는 의미다.

심 본부장은 "격자는 n-차원 공간에서 정수 선형 결합으로 표현되는 점들의 집합인 만큼 차원이 높을수록 공격이 어려워지지만, 차원이 너무 높으면 계산량이 커져 속도가 느려질 수 있다"면서 "현재는 풀기 어렵겠지만, 향후 효율적 공격 방법이 개발될 수 있어 공격에 대응하기 위해서는 차원 등 키 길이를 늘여야 한다"고 진단했다.

실제로 2022년 5월, 한국전자통신연구원 연구진이 세계 최초로 '분할-정복 전략'을 활용해 PQC를 공략할 수 있는 양자 알고리즘을 개발해 화제가 됐다. 아직 학술적 검증이 더 필요하지만, PQC도 언젠가 뚫릴 수 있다는 가능성을 보여준 사례다.

픽사베이 제공

양자 컴퓨터 등장 "빠르면 5년, 늦어도 20년"

양자 컴퓨터 등장도 초읽기에 들어간 것으로 보인다. 김 교수는 "무어의 법칙을 기준으로 보면 1년 반이 지나면 연산 능력이 배가 되고, 이를 양자에 적용하면 100 큐비트는 10년 뒤 10만 큐비트가 된다"면서 "10년 뒤에는 10만 큐비트 양자 컴퓨터로 현재 암호체계는 쉽게 해킹이 될 것"이라고 예상했다. 이어 그는 "빠르면 5년 내, 아무리 늦어도 20년은 넘기지 않을 것으로 본다"고 덧붙였다.

심 본부장에 따르면, 구조화된 격자의 잠재적 취약점을 보완하고 암호 방식의 다양성을 확보하기 위해 미국 국립표준기술연구소(NIST)는 지난해 6월 새로운 전자서명 알고리즘을 다시 공모했다.

마찬가지로 우리 정부도 2035년 PQC 체제 전환을 대비해 발 빠르게 움직이고 있다. 지난 1월, 격자 기반 알고리즘을 활용한 '한국형 양자내성암호(KpqC)' 선정을 마무리했으며, 이를 적용한 PQC 시범 전환 지원 사업을 추진하고 있다.

과학기술정보통신부 관계자는 "각국의 보안 수준이 달라지면 문제가 발생할 수 있기 때문에, 양자 컴퓨터 상용화 시점을 고려해 주요 국가들이 2035년까지 PQC 전환을 추진하고 있다"면서 "선정된 알고리즘을 실생활에 적용하는 시범 사업을 통해 각 분야에서 제대로 작동하는지 검증하고, 2035년 전환이 차질 없이 이뤄지도록 하겠다"고 말했다.

김종화 기자 justin@asiae.co.kr