<전경택 박사, 그는 세계적인 양자컴퓨팅 기술 전문가이고, 현재 큐토모㈜의 대표로서, 최첨단 양자컴퓨팅 응용기술을 선도하고 있습니다.>
[투데이타임즈 기획연재] 전경택 박사와 함께하는 “양자 시대의 개막” 기획 시리즈 그 두 번째 시간입니다. 지난 1편에서는 양자컴퓨팅의 기초와 그 잠재력을 살펴보았다면, 이번 편에서는 현대 디지털 보안의 핵심인 RSA 암호 체계가 양자 알고리즘에 의해 어떻게 도전받고 있는지, 그리고 그 중심에 서 있는 전경택 박사의 연구 성과를 집중 조명합니다.
디지털 세계를 지키는 거대한 수의 장벽, RSA
RSA cryptosystem은 큰 수의 소인수분해가 어렵다는 성질을 이용한 대표적인 공개키 암호 방식입니다. RSA 이름은 개발자인 Rivest, Shamir, Adleman의 앞글자에서 따왔습니다. 두 큰 소수 p,q를 곱해서 N=pq를 만드는 것은 쉽지만, N만 보고 다시 p,q를 찾아내는 것은 매우 어렵습니다.
오늘날 우리가 사용하는 HTTPS 인증서, 전자서명, 금융기관의 공동인증서 등은 모두 RSA 공개키 암호 방식에 기반하고 있습니다.
RSA의 보안성은 '매우 큰 수의 소인수분해는 현실적으로 불가능하다'는 수학적 난제에 뿌리를 둡니다. 예를 들어, 1024비트의 RSA-1024를 현재의 고성능 PC로 단순 계산으로 해독하려면 백만 년 이상 걸리는 것으로 예상되며, 아직 성공한 사례가 없습니다.
쇼어(Shor) 알고리즘과 범용 양자 컴퓨터의 한계
하지만 1994년 피터 쇼어(Peter Shor)가 발표한 쇼어 알고리즘은 이 견고한 성벽에 균열을 냈습니다. 쇼어 알고리즘은 이론적으로 소인수분해를 다항 시간 안에 해결할 수 있어 기존 컴퓨터보다 기하급수적으로 빠른 속도를 자랑합니다. 그러나 현실의 벽은 높았습니다. 현재의 범용 양자 컴퓨터는 노이즈 문제, 오류 보정 비용, 하드웨어 부족 등으로 인해 아직 의미 있는 수준의 큰 수를 분해하는 데 성공하지 못했습니다.
양자 어닐러와 QUBO : 소인수분해의 새로운 접근법
전경택 박사는 이 지점에서 양자 어닐러(Quantum Annealer)와 QUBO(Quadratic Unconstrained Binary Optimization) 모델에 주목했습니다. QUBO 모델은 선형항과 이차항으로 이루어지며 선형항은 큐비트의 바이어스에 해당하며 이차항은 큐비트간의 커플러에 해당합니다. QUBO 모델은 해당 큐비트가 특정 값을 취할 때 발생하는 에너지 패널티나 보상을 결정합니다. 이는 범용 양자 컴퓨터에서 양자 근사 최적화 알고리즘(QAOA: Quantum Approximate Optimization Algorithm)을 통해 계산되거나 양자 어닐러에서 중첩과 터널링 현상을 활용해 계산됩니다. 최근에는 양자-고전 하이브리드 컴퓨팅이 주를 이루고 있으며, 현재 수준의 범용 양자 컴퓨터의 하이브리드 솔버를 이용할 때는 수십 큐비트 연산에 특화된 반면, 양자 어닐러의 하이브리드 솔버는 수만 큐비트 연산까지 가능합니다. 양자 어닐러는 최적화 계산에 특화되어 있지만, 양자 최적화 모델에서 11자리 또는 그 이상의 정확도까지 계산 가능합니다.
<그림은 전경택 박사가 연구한 양자 어닐링 QUBO 기반의 소인수분해 모델을 AI를 활용하여 시각화한 자료입니다. 각 그림이 나타내는 핵심 내용은 다음과 같습니다. 이 모델은 수학적으로 명쾌하여 모든 수에 적용 가능하지만, 계산 과정에서 4차식(HUBO)이 발생하여 이를 2차식(QUBO)으로 변환할 때 추가적인 큐비트가 많이 소모되는 특성이 있습니다.>
QUBO는 복잡한 최적화 문제를 0 또는 1의 이진 변수들의 2차식 최소화 문제로 변환하는 방식입니다. 전 박사는 소인수분해 문제(N=pq)를 QUBO 관점에서 에너지 최적화 문제로 재정의했습니다. 그 결과, 2023년 당시 세계 최고 기록이었던 1,630,729를 넘어 최대 N=1,000,070,001,221까지 소인수분해하는 데 성공하며 세계를 놀라게 했습니다. 이는 범용 양자 컴퓨터가 아닌 양자 어닐러의 하이브리드 솔버를 활용해 얻은 획기적인 결과였습니다.
'Binary Carry Propagation'으로 한계를 돌파하다
기존의 QUBO 모델은 숫자가 커질수록 계산해야 할 2차항의 자릿수가 양자 하드웨어의 물리적 한계에 부딪히는 문제가 있었습니다. 전경택 박사는 이를 극복하기 위해 전체 식을 한 번에 계산하는 대신 각 자릿수의 에너지 모델을 만들고 이들을 결합하는 '이진 캐리 전파(Binary Carry Propagation)' 기반의 새로운 모델을 개발했습니다.
이 혁신적인 알고리즘을 통해 2025년, 전 박사팀은 약 60비트 수준인 N=1,152,921,423,002,469,787의 계산에 성공하여 관련 논문을 제출했습니다.
최근에는 D-Wave 시스템의 최신 양자 어닐러를 통해 최대 100비트까지 계산이 가능함을 확인하며, 양자 컴퓨팅을 통한 실질적인 암호 해독의 가능성을 한 단계 더 끌어올렸습니다.
성벽은 무너질 것인가: 양자 보안의 미래
물론 100비트 수준의 소인수분해가 당장 RSA-2048과 같은 상용 암호를 위협하는 것은 아닙니다. 하지만 전경택 박사의 연구는 양자 하드웨어의 발전과 함께 이 모델이 더 큰 정수 분해 문제로 확장될 수 있음을 증명했다는 점에서 매우 중요한 의의를 가집니다.
수백 년이 걸릴 계산을 단 몇 초 만에 해결하는 양자 컴퓨터의 시대는 더 이상 먼 미래의 이야기가 아닙니다. 전경택 박사가 이끄는 이 여정은 우리 삶을 바꿀 양자 혁명의 현주소를 여실히 보여주고 있습니다.
다음 회차 예고 [양자 시대의 개막 ③] 수백만 년의 계산을 수십초 단위로, '양자 선형 시스템'의 혁신이 시작된다.
){kind=small}
){kind=small}
){kind=small}
){kind=small}