Shor 알고리즘 — RSA 암호가 깨지는 날
지금 이 순간에도 당신의 은행 계좌, 이메일, 신용카드 정보는 RSA라는 암호로 보호받고 있습니다. 이 암호 체계가 얼마나 견고한지는 한 가지 단순한 수학 문제에서 비롯됩니다. 두 개의 거대한 소수를 곱하는 것은 쉽지만, 그 결과인 큰 수를 다시 원래의 소수로 분해하는 것은 거의 불가능하다는 원리입니다. 고전 컴퓨터로는 2048비트 RSA를 깨려면 우주의 나이보다 더 오래 걸립니다. 하지만 1994년 피터 쇼어(Peter Shor)가 발표한 한 가지 알고리즘이 이 모든 가정을 뒤흔들어 놓았습니다. 양자 컴퓨터라면 같은 문제를 몇 시간 안에 풀 수 있다는 것입니다. 지난 시리즈에서 Grover 알고리즘으로 암호 위협의 첫 번째 신호탄을 올렸다면, 이제 Shor 알고리즘은 인터넷 보안의 기초를 흔드는 본격적인 위기입니다.
RSA 암호의 원리: 쉬운 곱셈, 어려운 분해
RSA 암호의 강력함은 이 비대칭성에서 비롯됩니다. 은행이 당신에게 공개 키(n)를 알려줍니다. 당신은 이것을 이용해 돈을 암호화해서 보냅니다. 은행만 비밀 키(p와 q)를 알고 있으므로 복호화할 수 있습니다. 해커가 공개된 n을 가지고 있어도 p와 q를 찾아내지 못하면 아무것도 할 수 없다는 것이 핵심입니다.
구체적으로 생각해봅시다. RSA-2048이라는 현재 표준 암호는 약 617자리의 십진수입니다. 고전 컴퓨터의 가장 빠른 소인수 분해 알고리즘(일반 수체 체(General Number Field Sieve))을 써도 이를 깨려면 약 300조 년이 필요합니다. 우주의 나이가 138억 년이니 비교가 안 됩니다. 이것이 우리가 RSA를 믿고 인터넷 거래를 하는 이유입니다.
Shor 알고리즘: 주기 찾기로 소인수를 구하다
Shor 알고리즘의 천재성은 소인수 분해 문제를 전혀 다른 문제로 변환한다는 점입니다. "이 큰 수를 인수분해해"라는 어려운 질문을 "이 수열의 주기가 몇인가?"라는 다른 질문으로 바꾸는 것입니다.
어떻게 이런 변환이 가능할까요? 핵심은 모듈로 연산(mod)의 주기성입니다. 예를 들어 n = 15이고 a = 2라고 합시다. 2^1 mod 15 = 2, 2^2 mod 15 = 4, 2^3 mod 15 = 8, 2^4 mod 15 = 1, 2^5 mod 15 = 2... 이렇게 주기 4로 반복됩니다. 만약 이 주기 r을 알면, 2^(r/2) = 2^2 = 4이고, 2^(r/2) - 1 = 3, 2^(r/2) + 1 = 5입니다. 15의 인수인 3과 5가 나타났습니다!
고전 컴퓨터로 이 주기를 찾으려면 최악의 경우 n번 계산해야 합니다. 하지만 양자 컴퓨터는 다릅니다. 양자 중첩을 이용해 모든 가능한 x 값을 동시에 계산하고, 양자 푸리에 변환(Quantum Fourier Transform, QFT)으로 주기 정보를 증폭시킵니다. 이것이 바로 Grover 알고리즘에서 본 "양자 간섭"의 또 다른 형태입니다. 정답에 해당하는 진폭은 커지고, 오답의 진폭은 상쇄되어 사라집니다.
양자 푸리에 변환: 주기를 빛으로 드러내다
양자 푸리에 변환은 고전 푸리에 변환과 같은 수학이지만, 양자 중첩 상태에 작용하면 지수적으로 빠릅니다.
푸리에 변환은 신호를 주파수 성분으로 분해하는 수학 도구입니다. 음악을 예로 들면, 복잡한 소리를 여러 음정(주파수)의 합으로 표현합니다. 양자 푸리에 변환도 같은 원리인데, 양자 상태에 적용됩니다.
Shor 알고리즘에서는 a^x mod n의 주기 r을 찾기 위해 QFT를 씁니다. 양자 레지스터에 0부터 N-1까지의 모든 x를 중첩 상태로 준비하고, 각각에 대해 a^x mod n을 계산합니다. 그 결과는 주기적인 패턴을 이루는데, QFT가 이 패턴의 주파수(즉, 주기의 역수)를 추출합니다. 측정하면 주기에 관련된 정수가 나오고, 고전 후처리로 정확한 r을 복원합니다.
고전 푸리에 변환은 N개의 데이터 포인트에 O(N log N) 시간이 필요합니다. 양자 푸리에 변환은 O(log^2 N) 시간에 끝납니다. 이것이 바로 Shor 알고리즘이 지수 가속을 이루는 이유입니다. 양자 중첩으로 N개 상태를 동시에 처리하고, QFT로 주기 정보를 효율적으로 추출하기 때문입니다.
RSA-2048을 깨려면 몇 개의 큐비트가 필요한가
이론과 현실의 간격은 엄청납니다. 2012년 논문에 따르면 RSA-2048을 Shor 알고리즘으로 깨려면 약 2,330개의 논리 큐비트(logic qubit)가 필요합니다. 논리 큐비트란 오류 없이 완벽하게 작동하는 이상적인 큐비트를 의미합니다.
하지만 현재의 양자 컴퓨터는 NISQ(Noisy Intermediate-Scale Quantum) 시대에 있습니다. 물리 큐비트는 잡음과 오류에 시달립니다. 양자 오류 정정을 적용하려면 1개의 논리 큐비트마다 수백 개에서 수천 개의 물리 큐비트가 필요합니다. 즉, RSA-2048을 깨려면 수백만 개 이상의 물리 큐비트가 필요합니다.
2024년 현재, IBM의 가장 강력한 양자 컴퓨터는 약 1,000개의 물리 큐비트를 가지고 있습니다. Google의 Willow 칩도 비슷한 규모입니다. IonQ 같은 갇힌 이온 방식은 더 적은 물리 큐비트로도 높은 정확도를 자랑하지만, 여전히 수백 개 수준입니다. 우리가 RSA-2048을 깨는 양자 컴퓨터를 보려면 최소 10년, 현실적으로는 20~30년이 필요할 것으로 예상됩니다.
그렇다면 지금 당장 위협은 없을까요? 아닙니다. "수확 지금, 복호화 나중(Harvest Now, Decrypt Later)" 공격이 이미 시작되었습니다. 해커들이 지금 암호화된 통신을 몽땅 저장해 두었다가, 10년 뒤 양자 컴퓨터가 나오면 그때 복호화하려는 전략입니다. 당신의 의료 기록, 금융 정보, 국가 기밀이 지금 이 순간 "미래의 양자 공격"을 기다리며 저장되어 있을 수 있습니다.
양자 내성 암호: 미래를 향한 준비
NIST(미국 국립표준기술원)는 2022년 양자 내성 암호 표준을 최종 확정했습니다. ML-KEM(격자 기반 키 캡슐화), ML-DSA(격자 기반 디지털 서명), SLH-DSA(해시 기반 서명) 등이 새로운 표준입니다.
격자 기반 암호의 핵심은 "최단 벡터 문제(Shortest Vector Problem)"입니다. 고차원 격자에서 가장 짧은 벡터를 찾는 것은 고전 컴퓨터로도, 양자 컴퓨터로도 지수 시간이 필요합니다. Shor 알고리즘도 이 문제를 풀 수 없습니다. 해시 기반 암호는 SHA-256 같은 해시 함수의 안전성에 의존하는데, Grover 알고리즘으로도 겨우 제곱근 가속만 가능해 여전히 안전합니다(256비트 해시는 Grover로도 2^128 시간 필요).
미국, 유럽, 한국을 포함한 주요국들이 2024년부터 양자 내성 암호로의 이행을 추진 중입니다. Google은 이미 Chrome 브라우저에 양자 내성 키 교환을 테스트 중이고, Apple도 iMessage에 PQC(Post-Quantum Cryptography)를 적용할 계획입니다. 금융권도 SWIFT, 은행 간 통신에 양자 내성 암호 도입을 검토 중입니다.
Shor 알고리즘이 남긴 교훈
Shor 알고리즘은 단순히 "양자 컴퓨터가 빠르다"는 것을 보여준 게 아니라, 문제를 다르게 변환하면 어려운 것도 쉬워질 수 있다는 통찰을 제시했습니다.
1994년 Shor가 이 알고리즘을 발표했을 때, 양자 컴퓨터는 아직 실험 단계였습니다. 하지만 그의 이론적 발견은 양자 컴퓨팅 산업 전체를 깨웠습니다. 정부와 기업들이 대규모 투자를 시작했고, 30년이 지난 지금도 여전히 가장 강력한 양자 알고리즘입니다.
Shor 알고리즘의 진정한 가치는 속도 그 자체보다 패러다임 전환에 있습니다. 고전적 사고로는 "소인수 분해는 어렵다"고 믿었습니다. 하지만 양자적 사고로 "주기 찾기로 변환하면 쉬워진다"고 본 것입니다. 이것은 Grover 알고리즘의 진폭 증폭과는 다른 종류의 가속입니다. Grover는 "모든 경우를 동시에 확인하되, 정답만 증폭"하는 방식이라면, Shor는 "문제의 수학적 구조를 이용해 본질적으로 다른 계산으로 변환"하는 방식입니다.
현실적으로, RSA-2048을 깨는 양자 컴퓨터는 아직 10년 이상 떨어져 있습니다. 하지만 그 시간 동안 우리가 할 일은 명확합니다. 이미 암호화된 민감한 정보들을 양자 내성 암호로 다시 암호화하고, 새로운 통신 표준을 도입하고, 양자 위협에 대비한 기술 인프라를 구축하는 것입니다. Shor 알고리즘은 미래의 위협을 정확히 예측했고, 우리는 그 예측에 답하는 준비를 해야 합니다.
📚 관련 글
Shor 알고리즘은 양자 컴퓨터가 얼마나 빠른지를 보여준 것이 아니라, 어떻게 생각하느냐에 따라 불가능한 문제도 가능해질 수 있다는 것을 증명했습니다.
슈로 🐾