현대 암호 체계를 무력화하는 양자 알고리즘

지난해 8월, 양자 기술 기반 IoT 보안 전문 기업 노르마가 ‘2023 아시아 양자 정보 과학 컨퍼런스(AQIS, Asian Quantum Information Science Conference)’에서 양자 컴퓨터를 이용한 현대 암호 풀이 논문을 발표했다. 해당 논문은 공인인증서 등에 널리 쓰이는 현대 암호 ‘RSA’와 같은 공개키 암호도 양자 알고리즘으로 빠르게 해독될 수 있음을 보여준다. 정현철 노르마 대표는 “이번 연구 사례는 양자 컴퓨터가 현재 암호 시스템에 심각한 위협이 된다는 점을 실제로 확인했다는 점에서 의의가 크다”라며 “양자 컴퓨터를 본격적으로 사용하기 전까지는 보안 위협을 대비한 생태계 구축이 중요하다”라고 강조했다. 

대표적인 양자 알고리즘

<미국 컴퓨터 과학자 피터 쇼어, 제공. MIT News>

피터 쇼어는 1996년 ‘소인수분해 알고리즘’(Shor’s algorithm)을 발견했다. 쇼어 알고리즘은 합성수 N이 주어졌을 때, N을 소수의 곱으로 나타내는 것을 목표로 한다. 자연수가 이 두 개의 소수의 곱으로 이루어져 있다고 가정해 보면, 쇼어 알고리즘은 빠른 시간 안에 소인수분해 값을 구해 소수 p, q를 알아내는 것이다.

쇼어는 주기함수를 활용해 빠른 소인수분해 알고리즘을 찾아냈다. 예를 들어 뒤집힌 15개의 숫자 카드가 손에 있고, 이 중 두 개의 소수 카드를 골라서 곱하면 15가 나오도록 하는 것을 목표로 가정해 보자. 여기서 15는 합성수 N이고 두 개의 카드는 15의 소수이다. 고전적인 컴퓨터는 15개의 카드 중에서 하나씩 카드를 뒤집어 가능한 조합을 찾아야 하며, 숫자가 클수록 시간이 오래 걸린다. 

반면, 쇼어는 양자 컴퓨터를 통해 빠르게 두 카드의 조합을 찾을 수 있다고 가정했다. 고전 컴퓨터의 비트가 0과 1만을 사용하여 한 번에 한 카드씩만 뒤집어 조합할 때, 양자 컴퓨터는 큐비트의 중첩(superposition) 상태를 활용해 모든 카드를 동시에 뒤집을 수 있다. 다시 말해, 양자 컴퓨터는 계산을 병렬적으로 수행해 어떤 숫자 조합이 주기를 형성하는지 빠르게 찾아내고 정답을 구할 수 있다. RSA 암호의 안전성은 Ν의 자릿수가 클수록 두 소인수를 찾는 것이 매우 어렵다는 것에 기반한다. 양자 컴퓨터는 기존 컴퓨터에 비해 특정 계산 문제를 훨씬 빠르게 해결할 수 있기 때문에 RSA와 같은 현대 암호화 방식의 안전성을 위협할 수 있다.

그로버의 알고리즘은 그로버(Lov Grover)가 쇼어의 소인수 분해 알고리즘에 자극을 받아 양자 알고리즘에 대한 연구를 시작하면서 탄생했다. 표지가 없는 100권의 책 중에 원하는 책 1권을 찾아야 할 때, 최악의 경우 100개의 책을 모두 펼쳐봐야 원하는 책을 찾을 수 있을 것이다. 하지만 그로버 알고리즘을 사용하면 책장 전체를 한 번에 살펴보고 원하는 책이 어디 있는지 바로 알 수 있다. 책과 같은 거시적인 물체는 이런 효과를 기대하기 어렵지만 양자의 중첩 상태로는 가능하다. 기존 컴퓨터 알고리즘이 1~100권의 책을 펼쳐야 할 때, 그로버의 알고리즘을 이용한 양자 컴퓨터상에서는 대략 ∼Ν ‾‾√번의 연산으로 계산할 수 있어 정렬되지 않은 데이터베이스에서 특정 표시된 상태를 찾기 위해 실행 가능한 모든 입력을 검색하기 위한 검색 속도 향상을 위해 쓰인다.

양자 알고리즘의 응용

<127-큐비트 양자 프로세서 ‘이글(Eagle)’, 제공. IBM>

많은 산업체, 금융기관, 정부 기관에서는 최적의 결정을 내리기 위해 상당한 시간과 자원을 투입하고 있다. 특히 방대한 데이터와 다수의 결정 요인이 산재하는 현대 사회에서는 최선의 결정을 내리기가 더욱 어려워졌다. 이렇게 여러 경우의 수 중에서 최대의 효율이나 이익을 내는 방법을 찾는 문제를 '최적화 문제'라고 한다. 최적화 문제에 있어서 양자 컴퓨터는 기존 컴퓨터보다 적은 연산량으로 동일한 최적화 값을 도출할 수 있다. 

미국의 대표적인 컴퓨터 산업 기술 기업 IBM은 2021년 127-큐비트 프로세서 '이글(Eagle)'을 공개했다. 이글은 4개 레이어가 차곡차곡 쌓여 연결된 형태로, 최하단에는 절대영도(영하 273도)를 유지하는 시스템이다. IBM은 2025년까지 4000-큐비트 이상의 양자 시스템을 목표로 하고 있다. IBM은 2017년부터 양자 컴퓨팅 활용을 위한 핵심 소프트웨어 개발 키트(SDK)인 '퀴스킷(Qiskit)'을 오픈소스 형식으로 개발해 배포하고 있다. 한국 IBM 사업본부장 표창희 상무는 올해 6월 퀀텀 코리아 2024 행사장에서 “IBM은 조만간 기존 양자 컴퓨터가 가지고 있는 에러 완화 기술도 발표할 예정”이라며 “이 기술을 활용하면 기존에 풀기 어려웠던 난제, 미적분, 인수분해, 분자 구조 분석 등을 훨씬 간편하게 해결할 수 있을 것”이라고 밝혔다.

세계 최초의 양자 통신 위성인 중국의 ‘묵자(墨子, Micius)’호는 2018년 중국 베이징 인근에서 약 7,600㎞ 떨어진 오스트리아 빈까지 양자로 암호화된 사진 파일을 안전하게 주고받는 데 성공했다. 위성을 활용한 무선 양자 통신은 우주 공간을 통하기 때문에 손실이나 간섭 등의 문제가 없으며 위성의 이동성을 활용할 수도 있다. 이 프로젝트를 주도한 판 젠웨이 중국과학원(CAS) 중국과학기술대 교수는 “같은 거리에서도 유선보다 무선이 더 안정적인 것으로 나타났다”며 “이번 연구 결과로 양자 인터넷을 실현할 최장 거리의 글로벌 양자 네트워크를 구현하는 효율적인 방법을 제안했다”고 밝혔다. 이 연구는 양자 통신 기술의 실질적 가능성을 입증하며, 글로벌 통신 네트워크의 보안과 효율성을 혁신적으로 향상할 전망이다. 

올해 1월, 한국과학기술연구원의 임향택 연구팀은 적은 광자 수로도 기존 센서보다도 높은 정밀도로 넓은 영역에 분산된 여러 변수를 측정할 수 있는 분산형 양자 센싱 시스템을 개발했다. 양자 시계, 자기장, MRI 이미징, 온도 및 압력 센서 등에서 고전 물리학 기반의 센서를 능가하는 정밀도를 보여주는 양자 센싱 기술은, 암세포 등의 질병 진단, 지진 감지, 자기장 측정을 위한 센서로도 활용될 수 있다. 임 책임연구원은 “적은 자원으로도 표준 양자 한계를 뛰어넘는 측정이 가능한 분산형 양자 센싱 핵심 원천기술을 선점해 세계 시간 동기화, 초미세 암 발견 등의 실용적인 기술로 발전하기를 기대한다”라고 밝혔다. 이 연구는 양자 센싱 기술의 잠재력을 실질적으로 입증하며, 다양한 산업 분야에서 혁신적인 응용 가능성을 제시하고 있다.

양자 기술 시장의 전망

유형정 KISTEP 전략기술정책단 부연구위원은 ‘양자과학기술의 현 동향과 전망’ 저널에서 “양자 과학기술은 광범위한 산업 안보적 파급력을 가진 파괴적 혁신 기술이며 미래 기술의 핵심”이며 “현재 양자 산업에 대한 전 세계 투자 규모는 최고치에 달했고, 기술의 발전은 그에 비해 느리지만 점진적으로 이뤄지고 있으며 인재 격차는 다소 좁혀지는 추세”라고 전했다. 양 연구위원은 한국은 최근 양자법이 제정되어 양자 시스템 플랫폼, 국제 협력, 표준화 상용화 방안 등을 포함하는 양자 종합계획 수립에 필요한 토대는 갖춰졌다고 평가하면서, 양자과학기술이 국가전략기술로 선정된 만큼 전문인력과 기술 양성을 위한 중 장기적 지원과 논의, 연구 주제, 양자 시스템 플랫폼 등 적절한 방향성에 대한 합의가 필요하다고 전했다. 

[기사]

노르마, AQIS에서 ‘양자 알고리즘으로 공인인증서 해킹 가능’ 논문 발표 https://m.boannews.com/html/detail.html?tab_type=1&idx=121590

적은 광자 수로 민감도 최대치 '양자센싱' 기술 개발

https://m.dongascience.com/news.php?idx=63367

IBM 퀀텀, 양자컴퓨팅 시대의 새로운 미래 제시하다

https://m.boannews.com/html/detail.html?tab_type=1&idx=130833

우주로 날아간 묵자(墨子)...중국, 세계 최초 양자통신 위성 '묵자호' 발사 성공

https://www.khan.co.kr/world/china/article/201608161528001

[참고자료]

한국정보통신기술협회 TTA저널 197호(2021.09.) 특집: [Special Report] 양자

김한영. (2020.06). ‘양자 알고리즘의 세계’. KIAS고등과학원. https://horizon.kias.re.kr/14565/

[참고문헌]

TTA저널 210 호. (2023.11). “양자로 다시 쓰는 ICT”.

양자과학기술의 현 동향과 전망. 유형정. KISTEP 전략기술정책단 부연구위원