[퀀텀 컴퓨터로 RSA 암호를 깨보자(1)] 8비트 RSA 해독에 2시간 반이 걸린 이유

안녕하세요. 베네타리저브(VENETA Reserve)의 이현주입니다.

지난 에세이에서 리처드 파인만이 남긴 "자연은 고전적이지 않다"는 경고와 함께, 고전 컴퓨터가 양자역학을 흉내 낼 때 발생하는 논리적 모순('음의 확률')을 다뤘습니다. 하지만 엔지니어에게 가장 확실한 증명은 직접 코드를 돌려보고 결과값을 확인하는 것입니다.

오늘은 직접 양자 프로그래밍 코드를 짜서 '고전 컴퓨터가 양자 회로를 시뮬레이션할 때 어떻게 붕괴하는가'를 확인해 보려 합니다. 목표는 가장 단순한 형태의 RSA 암호 해독, 즉 쇼어 알고리즘(Shor's Algorithm)을 이용한 소인수분해입니다.

타겟 숫자는 143 (11 x 13). 8비트(bit) 수준의 RSA Toy 버전의 암호입니다.

1. 프롤로그: Qiskit의 의존성 지옥(Dependency Hell)

처음엔 아주 우아하고 쉽게 가려고 했습니다. IBM의 양자 프로그래밍 프레임워크인 Qiskit에 내장된 Shor 모듈로 코딩하면 금방 끝날 줄 알았어요.

그런데 웬걸, 최신 Qiskit(1.0 이상) 환경에서 Shor 모듈을 찾을 수 없다는 에러가 났습니다. 확인해 보니 IBM이 최근 업데이트에서 이 범용 소인수분해 모듈 자체를 폐기했더라구요. 숫자가 조금만 커져도 양자 게이트의 수가 수만 개로 폭발해 최신 시뮬레이터조차 감당하지 못하고 뻗어버리는 문제가 있었기 때문입니다.

재미있는 점은, 이 '게이트 수 폭발' 현상이 현재 양자 컴퓨터 하드웨어 진영의 패권 다툼과도 직결된다는 것입니다. 양자 컴퓨터는 크게 '게이트 방식'과 '어닐링 방식'으로 나뉩니다.

IBM, 리게티(초전도체)나 아이온큐(이온트랩)가 주도하는 게이트 방식은 범용성은 뛰어나지만, 이번 코드에서 보듯 연산이 복잡해지면 게이트가 수만 개로 폭발해 오류 제어가 힘들다는 치명적인 단점이 있습니다. 반면 디웨이브(D-Wave)가 대표적인 어닐링 방식은, 게이트를 거치지 않고 자연의 에너지 안정화 원리를 이용해 한 번에 답을 찾기 때문에 이런 게이트 폭발 문제에서 자유롭다는 점을 자신들의 장점으로 내세우고 있습니다.

어쨌든, 오기가 생겨 모듈이 살아있던 과거 안정화 버전(0.43.3)으로 다운그레이드를 시도했습니다. 하지만 이번엔 제가 사용하는 Python 3.12 환경이 구버전 qiskit-aer(0.12.2)의 설치를 거부했어요. Resolution Impossible 즉, 의존성 충돌 에러 때문이었습니다.

2. 직접 짜자

그래서 고민 후 최신 Qiskit 환경에서 양자 회로를 처음부터 직접 설계하고 코드를 짜보았습니다.

$N=143$ 을 쪼개기 위해 총 20개의 큐비트(카운팅 큐비트 12개 + 타깃 연산 큐비트 8개)를 배치하고, 아다마르(Hadamard) 게이트로 중첩을 만든 뒤, 모듈러 거듭제곱 게이트와 역 양자 푸리에 변환(IQFT)을 통해 파동의 간섭을 유도하는 코드입니다. (힌트: 용어가 낯선데요. 제 에세이들을 보시거나 계속 하다보면 익숙해집니다. 그냥 무작적 따라서 하다보면 결국 익숙해지니 의문 생겨도 그냥 무작정 따라오세요)

# Qiskit 1.0+ 호환 Shor 알고리즘 (N=143)
import numpy as np
from qiskit import QuantumCircuit, transpile
from qiskit_aer import AerSimulator
from qiskit.circuit.library import QFT, UnitaryGate
import math
import time

# 타깃 숫자 세팅 (8비트 토이 RSA)
N = 143  # 11 * 13
a = 2    

print(f"🎯 [극한 실험] N={N} (Base a={a}) 범용 양자 회로 연산 시작...")
start_time = time.time()

n_target = math.ceil(math.log2(N)) 
n_count = 12 # 큐비트 수 증가 (메모리 사용량 폭발할걸~)

# a^x mod N 모듈성 지수연산을 수행하는 범용 행렬(Unitary Matrix) 생성
def c_amodN(a, power, N, n_target):
    U = np.zeros((2**n_target, 2**n_target))
    for i in range(2**n_target):
        if i < N:
            U[(i * (a**power)) % N, i] = 1
        else:
            U[i, i] = 1
    return UnitaryGate(U).control()

# 양자 회로 설계 (총 20 큐비트)
qc = QuantumCircuit(n_count + n_target, n_count)

for q in range(n_count): qc.h(q)
qc.x(n_count + n_target - 1)

for q in range(n_count):
    gate = c_amodN(a, 2**q, N, n_target)
    qc.append(gate, [q] + list(range(n_count, n_count + n_target)))

qc.append(QFT(n_count, inverse=True).to_gate(), range(n_count))
qc.measure(range(n_count), range(n_count))

# 시뮬레이터 실행 (트랜스파일링 병목 구간)
simulator = AerSimulator()
compiled_circuit = transpile(qc, simulator) 
job = simulator.run(compiled_circuit, shots=1024)
counts = job.result().get_counts()

# (고전적 후처리 코드는 지면상 생략: 위상을 분석해 GCD로 소인수 도출, 나중에 깃허브에 다 올리겠음)
# ...

end_time = time.time()
print(f"🔥 최종 분해된 소인수: {list(factors)}")
print(f"⏱️ 소요 시간: {end_time - start_time:.4f} 초")

위 코드 실행 결과값은 아래 캡처를 참고하세요.

3. 9132초의 고군분투: 시뮬레이터는 왜이리 오래 걸렸나

처음엔 더 작은 수의 RSA 암호를 해독을 금방 끝내고 위 코드를 짠 뒤 실행 후 한참 기다렸습니다. 그런데 런타임이 끝날 기미를 보이지 않았습니다. 결국 화면에 최종 분해된 소인수: [11, 13]이라는 정답이 찍히기까지 걸린 시간은 9132.3477초. 2시간 32분 12초였습니다.
고작 20개의 큐비트가 엮였을 뿐인데, 고전 컴퓨터는 이를 시뮬레이션하기 위해 $2^{20}$ (약 104만 개)의 복소수를 담은 거대한 행렬을 메모리에 밀어 넣어야 했습니다. 그리고 그 거대한 행렬들을 12번이나 곱하며 파동 간섭을 순차적으로 시뮬레이션 하느라 CPU와 RAM이 연산 한계에 부딪혀 병목(Bottleneck)을 겪은 것입니다.

4. "그냥 고전 알고리즘으로 풀면 금방 되잖아요?"

네, 맞습니다. 파이썬으로 단순한 나눗셈 코드 (143 % 11 == 0)를 짜면 0.0001초 만에 답이 나옵니다. 아마 많은 엔지니어들이 "거 봐, 양자 시뮬레이터가 2시간 반이나 걸린 건 고전 컴퓨터한테 양자 흉내를 내게 만들었기 때문이잖아!" 라고 비판하실지도 모릅니다.

정확한 지적입니다. 하지만 바로 그곳에 '진짜 한계'가 숨어 있습니다.

고전 알고리즘은 숫자가 작을 땐 빠르지만, 우리의 디지탈 라이프 전반에서 알게모르게 다 사용하고 있는 RSA2048 규격의 암호처럼 수백 자리의 숫자로 커지는 순간에는 우주의 나이보다 긴 '시간'이 필요해집니다. 이 시간의 장벽을 부수기 위해 만들어진 것이 바로 쇼어 알고리즘입니다.

하지만 우리가 방금 증명했듯, 고전 컴퓨터로 이 양자 연산을 흉내(시뮬레이션) 내는 것은 불가능에 가깝습니다. 고작 20 큐비트를 흉내 내는 데 2시간 반이 걸렸습니다. 만약 고전 컴퓨터에서 RSA2048을 깨기 위해 수천 개의 큐비트를 시뮬레이션한다면 어떨까요? 전 우주의 원자 수를 모두 합친 것보다 많은 '메모리(RAM)' 공간이 필요합니다.

즉, 고전 컴퓨터는 정면 돌파를 시도하면 '시간의 폭발'에 갇히고, 양자를 흉내 내려 하면 '메모리의 폭발'에 갇혀 완전히 붕괴합니다. 이것이 바로 논리적 한계를 명확히 보여주는 대목입니다.

이 '시간과 공간의 한계'를 가볍게 무시하고, 물리적인 파동의 간섭 현상 그 자체를 이용해 순식간에 답을 내놓는 기계. 그것이 바로 진짜 양자 컴퓨터(QPU)입니다.

5. 엔터프라이즈 데이터 인프라의 다가올 미래

지금 해커들이 암호화된 기업 데이터를 무작위로 긁어모으는 SNDL(Store Now, Decrypt Later) 전략을 취하는 이유가 바로 이것입니다. 언젠가 물리적인 QPU가 상용화되는 날, 2차원의 논리로 짜인 현재의 방어막은 3차원의 양자 파동 앞에서는 무력화될 수밖에 없습니다.

베네타리저브(VENETA Reserve)팀은 기업의 모든 정보가 날것 그대로 담긴(raw data의 보고) "백업(Backup) 시스템"을 이용해 단순한 장애 리커버리를 위한 단순한 스토리지가 아닌, AI와 퀀텀 컴퓨팅을 위한 데이터 프로비저닝(Provisioning) 인프라로 완전히 재설계하려는 이유가 바로 여기에 있습니다. 엔터프라이즈 컴퓨팅의 미래는 HPC, GPU, QPU가 함께 작동하는 하이브리드 아키텍처 입니다. 이미 미국, 일본, 유럽에서는 이런 아키텍처로 시작했어요. 베네타리저브는 이 미래에 기여하는 주역이 되고자 합니다.

감사합니다.

• 다음주부터는 IBM 퀀텀, 아이온큐, 리게티 등의 퀀텀 컴퓨팅 환경에서 더 높은 수준의 RSA 암호 Toy 버전을 더 큰 게이트를 할당하여 해독한 결과를 올릴 예정입니다. 가능하면 이스라엘 기업, Classiq의 Qmod(Quantum Modeling Laguage)로 코드짜서 실제로 어느 정도로 빨라지는지도 확인할 거에요.

이현주 드림
Founder & CEO of VENETA Reserve
a UWS Company | IYF Group
hjlee@veneta.ai