양자컴퓨터가 RSA 암호화를 단 10초 만에 깨뜨린다고? 우리가 지금 당장 알아야 할 것들
지금 이 순간에도 누군가는 당신의 암호화된 데이터를 조용히 저장하고 있을지 모른다. 해독하기 위해서가 아니라, 나중에 해독하기 위해서.
시작하기 전에: 왜 이게 지금 당신 문제인가
솔직히 말해서, 양자컴퓨터 얘기가 나오면 대부분의 사람들은 눈이 흐릿해진다. "어디선가 들어봤는데, 아직 멀었겠지." 그런데 2026년 현재, 이 판단이 틀렸을 가능성이 꽤 높아졌다.
구글은 최근 2029년까지 자사 시스템 전체를 양자 내성 암호화로 전환하겠다고 발표했다 [1]. 정부 권고안보다 몇 년 앞선 일정이다. 이건 단순한 보여주기가 아니다. 구글의 양자 연구팀이 직접 내놓은 자원 추정치들이 이 결정의 배경에 있다 [2].
RSA-2048 — 지금 이 순간 인터넷 뱅킹, 이메일, 온라인 쇼핑을 보호하고 있는 암호화 방식이다. 완벽한 양자컴퓨터가 등장한다면, 이걸 깨는 데 걸리는 시간은 약 10초다 [3]. 지금은 그런 컴퓨터가 없다. 하지만 문제는, 있어야 그 시점부터 걱정하면 된다는 게 아니라는 것이다.
큐비트란 뭔가 — 아주 쉽게
고전 컴퓨터는 비트(bit)로 작동한다. 비트는 0이거나 1이다. 무조건. 반면 양자컴퓨터의 기본 단위인 큐비트(qubit)는 0과 1을 동시에 가질 수 있다. 이걸 중첩(superposition)이라고 부른다 [3].
어떻게 그게 가능하냐고? 동전을 던지는 순간을 생각해보자. 공중에 떠 있는 동전은 앞면도 뒷면도 아니다. 그 둘 다다. 측정하는 순간 한쪽이 정해지는 것처럼, 큐비트도 관측하기 전까지는 두 상태를 동시에 유지한다.
여기다 얽힘(entanglement)이라는 현상을 더하면 상황이 더 흥미로워진다. 큐비트들이 서로 연결되면, 큐비트 수가 늘어날수록 처리할 수 있는 연산의 규모가 기하급수적으로 커진다 [3]. 10개의 고전 비트가 1024가지 경우를 순서대로 처리하는 동안, 10개의 큐비트는 이론적으로 그 1024가지를 동시에 탐색할 수 있다 [4].
구글의 Willow 칩은 최근 연산 중 오류를 줄이는 데서 유의미한 진전을 보였다 [3]. 이게 왜 중요한지는 잠시 후 오류 정정 부분에서 이야기하겠다.
Caption: 그림 1. 양자 알고리즘 기반 RSA 공격 및 오류 정정 기술과 차세대 암호 체계 전환 로드맵. Shor 알고리즘은 정수 인수분해를 기하급수적으로 가속화하여 기존 RSA 암호 체계를 무력화하며 , 이를 실현하기 위한 연산 신뢰성은 물리 큐비트를 논리 큐비트로 인코딩하고 표면 코드 등을 통해 토폴로지적 보호를 수행하는 양자 오류 정정(QEC) 기술로 확보된다. 이에 대응하여 격자 기반 암호와 같은 양자 내성 알고리즘(PQC)을 도입하고 기존 암호체계와 병행하는 하이브리드 배포 전략을 통해 보안 가용성을 유지하며 단계적인 암호 자산 식별 및 소프트웨어 업데이트를 수행해야 한다.
RSA는 어떻게 작동하고, 왜 지금껏 안전했나
RSA는 1977년에 개발됐다. 원리는 간단하다. 두 개의 거대한 소수를 곱하면 아주 큰 수가 나온다. 이 곱셈은 쉽다. 하지만 결과값만 보고 원래의 두 소수를 찾아내는 것은? 고전 컴퓨터로는 사실상 불가능에 가까울 만큼 오래 걸린다 [5].
구체적으로는 이런 식이다. 두 소수 P와 Q를 골라 N = P × Q를 계산한다. 여기서 N과 특정 지수 e가 공개 키가 되고, 이로부터 유도되는 d가 비밀 키가 된다 [6]. 공개 키로 암호화된 데이터는 비밀 키 없이는 해독할 수 없다. RSA-2048에서 N은 2048비트 길이, 즉 약 617자리 숫자다.
- RSA-2048: 현재 가장 널리 쓰이는 표준
- RSA-4096: 더 강력하지만 속도가 느림
- 양자 내성: 둘 다 양자 공격 앞에서는 동등하게 취약 [5, 7]
고전 컴퓨터로 RSA-2048을 깨려면? 현재 기술로 수백만 년이 걸린다. 그래서 안전하다고 믿어왔다. 문제는, 양자컴퓨터에는 다른 규칙이 적용된다는 것이다.
쇼어 알고리즘: 게임의 판이 바뀌다
1994년, 수학자 피터 쇼어가 쇼어 알고리즘(Shor's Algorithm)을 발표했다. 이 알고리즘은 양자컴퓨터가 큰 수의 소인수분해를 다항식 시간 안에 해결할 수 있도록 한다 [8]. 고전 컴퓨터는 수의 크기가 커질수록 지수함수적으로 느려지는데, 쇼어 알고리즘은 이 벽을 허문다.
이게 얼마나 큰 차이인지 느낌이 오지 않는다면 이렇게 생각해보자. 고전 컴퓨터로 RSA-2048을 깨는 건 지구에서 안드로메다 은하까지 걸어가는 것과 비슷하다. 쇼어 알고리즘을 쓰는 양자컴퓨터로는, 집 앞 편의점 다녀오는 수준이다.
2025년 기준으로, RSA-2048을 실제로 깨뜨리기 위해서는 10만 ~ 2천만 개의 물리 큐비트가 필요하다는 추정이 나와 있다. 이 범위가 넓은 이유는 오류율과 사용하는 아키텍처에 따라 다르기 때문이다 [9, 8, 10].
흥미로운 건, 이 숫자가 빠르게 줄어들고 있다는 점이다.
시드니의 Iceberg Quantum 연구팀이 2026년 2월 발표한 논문에서는, LDPC 코드라는 새로운 오류 정정 기법을 사용하면 10만 개의 물리 큐비트로도 가능하다는 주장이 나왔다 [11, 12]. 스콧 애런슨은 이에 대해 "완전히 타당한 주장처럼 보인다"고 평가했다 [12]. 구글 연구팀은 100만 개의 잡음 있는 큐비트면 충분할 수 있다는 결과를 2025년에 내놨다 [2].
방향은 분명하다. 필요한 큐비트 수는 줄어들고 있고, 실제 하드웨어의 큐비트 수는 늘어나고 있다.
비대칭 암호화가 위협받는 동안, 대칭 암호화 방식인 AES는 어떨까? 여기엔 그로버 알고리즘(Grover's Algorithm)이 등장한다. 이건 비구조적 탐색 문제에서 제곱근 배의 속도 향상을 주는 알고리즘이다 [7]. AES-128의 실질적 보안 강도가 64비트로 반토막난다는 의미다. 때문에 AES-256이 양자 시대의 안전한 대칭 암호로 권장된다 [7].
"지금 훔치고, 나중에 해독한다"는 전략
이 부분이 기술 전문가가 아닌 일반인도 당장 신경 써야 하는 이유다.
"지금 수확하고, 나중에 해독한다(Harvest Now, Decrypt Later)" 전략은 이미 현실이다 [5]. 적대적 국가나 정교한 해커 집단이 지금 암호화된 데이터를 수집해두고, 양자컴퓨터가 상용화되는 시점에 해독한다는 계획이다.
오늘 당신이 주고받는 이메일, 의료 기록, 금융 거래. 지금은 안전하게 암호화되어 있다. 하지만 누군가가 그것을 저장해뒀다면, 2029년이나 2035년에 열 수 있을지도 모른다 [5, 7].
구글의 보안 담당 부사장 Heather Adkins는 이 위협이 미래형이 아니라 현재진행형임을 명확히 했다 [25].
양자 오류 정정: 양자컴퓨터가 실용화되려면 반드시 넘어야 할 벽
여기서 기술적으로 조금 더 들어가야 한다. 걱정 말고 따라오면 된다.
큐비트는 본질적으로 불안정하다. 외부 진동, 온도 변화, 전자기 간섭 — 이런 것들이 큐비트를 탈결맞음(decoherence) 상태로 만들고, 오류가 발생한다 [15]. 현재 최신 양자컴퓨터의 오류율은 게이트 연산당 약 0.1~1% 수준이다 [17]. 고전 컴퓨터에서 10억 번에 1번 꼴로 오류가 나는 것에 비하면, 엄청나게 높은 오류율이다.
쇼어 알고리즘처럼 수백만 번의 연산이 필요한 작업을 하려면, 이 오류를 실시간으로 탐지하고 수정해야 한다. 이게 양자 오류 정정(Quantum Error Correction, QEC)의 존재 이유다 [15, 16].
- 안정화 코드(Stabilizer Codes): 측정을 통해 오류를 감지하고 고전 논리로 수정. 쇼어 코드, 스틴 코드가 대표적 [4].
- 표면 코드(Surface Codes): 2차원 격자 형태로 물리 큐비트들을 배열해 위상학적으로 보호받는 논리 큐비트를 만든다. 격자 전체에 오류가 퍼지더라도 논리 큐비트의 상태를 유지할 수 있다 [4].
비유하자면, 중요한 문서를 10군데에 복사해 보관하는 것과 비슷하다. 몇 곳이 손상돼도 나머지로 원본을 복구한다.
문제는 이 과정이 엄청난 자원을 요구한다는 것이다. 하나의 논리 큐비트를 만들기 위해 수백에서 수천 개의 물리 큐비트가 필요하다. LDPC 코드와 같은 새로운 접근법은 이 오버헤드를 줄이려는 시도다 [11, 20].
또 다른 도전은 디코딩 속도다. 오류를 실시간으로 수정하려면, 디코더가 아주 빠르게 작동해야 한다. 이건 양자 연산과 고전 연산의 긴밀한 통합이 필요한 공학 문제이기도 하다 [21, 22].
구글의 Willow 칩이 이 분야에서 주목받는 이유가 바로 이 오류 정정 성능의 향상 때문이다 [3]. 아직 쇼어 알고리즘을 실제 규모로 실행할 수준은 아니다. 하지만 방향은 맞다.
RSA에 대한 현재의 양자 위협: 진짜 상황은?
중요한 것은 균형감이다. 지금 당장 RSA-2048이 깨진 것처럼 공황 상태가 될 필요는 없다. 2026년 현재, 아무도 비밀리에 RSA-2048이나 RSA-4096을 깨지 못했다 [23].
가장 크게 인수분해에 성공한 고전 컴퓨터 기록은 829비트 수준이다. RSA-2048의 절반도 안 된다 [23]. 양자컴퓨터로는 훨씬 작은 수만 인수분해됐다.
하지만 이것이 위협이 없다는 의미는 아니다. 방향은 분명하다. 필요한 큐비트 수는 계속 줄어드는 추세이고 [12, 11], 구글은 2029년이라는 구체적인 기한을 제시했다 [1, 2]. 이 기한은 "RSA가 반드시 2029년에 깨진다"는 의미가 아니라, "우리는 그전에 준비를 완료하겠다"는 선언이다.
에너지 측면도 생각해봐야 한다. RSA-2048을 깰 수 있는 수준의 양자컴퓨터를 운용하는 데 드는 에너지와 인프라 비용은 어마어마하다. 엄청난 냉각 시스템과 물리적 인프라가 필요하다 [13]. 이 때문에 양자 암호해독은 경제적 타당성의 문제가 될 수 있다. 가능하지만, 극히 고가값의 표적에만 동원될 것이라는 시나리오다 [13, 14].
그림 2. 양자 컴퓨팅 하드웨어 고도화에 따른 암호화 보안 영향도 및 기술적 대응 체계. 쇼어 알고리즘(Shor’s Algorithm) 기반의 양자 컴퓨터는 정수 인수분해 성능의 비약적 향상을 통해 기존 RSA-2048 암호 체계를 무력화하며, 이를 위해 10만에서 2,000만 개 사이의 물리적 큐비트 확보와 논리적 큐비트 구현을 위한 양자 오류 수정(QEC) 기술이 전제되어야 한다. 공격자의 '선 수집 후 복호화(Harvest Now, Decrypt Later)' 전략에 대응하기 위해 조직은 격자 기반 암호 체계인 NIST 포스트 양자 암호(PQC) 표준으로의 이행과 고전 암호 및 양자 알고리즘을 병행하는 하이브리드 배포 전략을 수립해야 한다.
우리는 무엇을 해야 하나: 양자 내성 암호화로의 전환
다행히 전 세계가 이 문제를 진지하게 받아들이고 있다.
미국 국립표준기술연구소(NIST)는 포스트 양자 암호화(PQC) 표준을 2024년에 최종 확정했다. ML-KEM, ML-DSA, SLH-DSA 세 알고리즘이 핵심이다 [18]. 2025년 3월에는 HQC가 ML-KEM의 백업으로 추가 선정됐다. 이 알고리즘들은 격자 기반 수학 문제나 해시 함수 등 양자컴퓨터로도 쉽게 깰 수 없는 기반 위에 세워졌다 [19, 9].
전문가들이 권장하는 전략은 하이브리드 배포다 [18]. RSA 같은 고전 알고리즘과 PQC 알고리즘을 병행하여, 하위 호환성을 유지하면서 점진적으로 전환한다. TLS 프로토콜에서 이 방식이 우선적으로 적용되고 있다 [18].
- 지금 해야 할 일들:
- 조직 내 어떤 시스템이 RSA, ECC, 디피-헬만 등을 사용하는지 인벤토리 작성
- 장기간 기밀 유지가 필요한 데이터 우선순위 설정
- NIST 표준 PQC 알고리즘 파일럿 구현 시작
- 암호화 민첩성(crypto-agility) — 알고리즘을 빠르게 교체할 수 있는 아키텍처 — 설계에 반영
텔레콤 분야에서는 3GPP, ETSI 같은 규제 기관의 불확실성이 중소 사업자에게 부담이 되고 있다 [18]. 소규모 사업자들에게는 하드웨어 전면 교체보다 소프트웨어 업데이트 방식이 현실적이다 [18].
백악관은 이미 "Q-Day" 대비 준비태세를 강조한 바 있다 [12]. 2035년을 연방 기관의 PQC 전환 완료 목표로 제시했으며, 일부 시스템은 2030~2031년 더 이른 마감이 적용된다 [1].
토론: 우리가 아직 모르는 것들
양자 위협 타임라인에 관해 가장 불편한 진실 하나. 아무도 정확한 날짜를 모른다는 것이다.
구글의 2029년 선언 [1]은 주목할 만하지만, 그것은 구글이 대비하겠다는 날짜이지, 양자컴퓨터가 실제로 등장한다는 날짜가 아니다. 과거를 돌아보면, 이 분야의 예측은 항상 오차가 컸다. 2012년에는 RSA-2048을 깨는 데 10억 개의 큐비트가 필요하다고 했다. 지금은 100만 개, 심지어 10만 개라는 추정까지 나온다 [12, 11]. 방향은 분명하지만 속도는 여전히 불확실하다.
이런 맥락에서, NIST의 PQC 표준화 작업은 그 어떤 개별 기업의 선언보다 실질적인 의미가 있다 [7, 9]. 2024년 세 개의 FIPS 표준이 나왔고, 2025년에 HQC가 추가됐다. 그런데 이 표준들이 실제 시스템에 통합되려면 수년의 개발과 검증이 필요하다. 특히 임베디드 장치, 산업용 제어 시스템, 레거시 인프라 분야에서 이 전환은 더디고 비용이 많이 든다 [8].
흥미로운 긴장 지점이 있다. NIST는 공식 입장으로 '순수 PQC' 전환을 권장하고 있는데, 구글을 비롯한 많은 엔지니어링 팀은 하이브리드 방식을 사용하고 있다 [24]. 두 접근법 모두 합리적인 근거가 있다. 하이브리드는 현실적이지만, 두 시스템을 동시에 유지하면 공격 표면(attack surface)이 늘어날 수 있다. 순수 PQC는 깔끔하지만, 아직 PQC 알고리즘에 예상치 못한 취약점이 발견될 가능성을 완전히 배제할 수 없다.
2019년 SIKE 알고리즘이 NIST 4라운드까지 살아남았다가 2022년 고전 컴퓨터 공격으로 하루 만에 깨진 사례를 기억해야 한다. 새로운 수학적 기반 위에 세운 알고리즘은, 수십 년의 검증을 거친 RSA와 달리, 아직 충분히 시험되지 않았다는 점에서 구조적 취약성을 안고 있다.
또 하나의 미해결 질문: 양자 암호해독의 비대칭성이다. 양자컴퓨터를 만들 수 있는 주체는 극히 일부다 — 지금으로서는 대형 테크 기업이나 국가 수준의 행위자들. 이 비대칭성이 오히려 암호화 붕괴보다 더 위험한 권력 집중 문제를 낳을 수 있지 않을까? 누군가는 RSA를 깰 수 있는 기계를 가지고 있고, 나머지는 모르는 채로 데이터를 계속 주고받는 미래를 상상해보라.
무엇보다, 기술 전환의 역사는 항상 같은 패턴을 보여준다. 준비 완료 선언은 항상 실제 배포보다 훨씬 빠르다. NIST의 표준이 나왔다고 해서, 지금 당신의 은행, 병원, 정부 시스템이 내일 당장 업데이트되지는 않는다. 그 격차의 시간이 가장 위험한 구간이다. 그리고 그 구간이 바로, 지금일 수 있다.
References
[1] Adkins, H., & Schmieg, S. (2026, March). Google's timeline for PQC migration. Google. https://blog.google/innovation-and-ai/technology/safety-security/cryptography-migration-timeline/
[2] The Quantum Insider. (2026, March 31). Q-Day just got closer: Three papers in three months are rewriting the quantum threat timeline. https://thequantuminsider.com/2026/03/31/q-day-just-got-closer-three-papers-in-three-months-are-rewriting-the-quantum-threat-timeline/
[3] Van Impe, S. (2025, January 7). 10 seconds to break: Preparing for quantum security threats. Unisys. https://www.unisys.com/blog-post/cis/10-seconds-to-break-preparing-for-quantum-security-threats/
[4] Hollebeek, T. (2025, February 26). Why quantum computers can break RSA but not lattice cryptography. LinkedIn. https://www.linkedin.com/pulse/why-quantum-computers-can-break-rsa-lattice-timothy-hollebeek-vi8re
[5] Deegan, C., & Nugent, D. (2025, February 20). The risk of quantum to classical cryptography. Project Eleven. https://blog.projecteleven.com/posts/the-risk-of-quantum-to-classical-cryptography
[6] Arharbi, A. (2025, February 1). Breaking RSA: Understanding the algorithm and exploring vulnerabilities and the quantum threat. Medium. https://medium.com/@aa.adnane/breaking-rsa-understanding-the-algorithm-and-exploring-vulnerabilities-and-the-quantum-threat-cbd148ee7f3a
[7] Braunstein, A. (2024, December 19). Q-Day and the impact of breaking RSA2048. IonQ. https://www.ionq.com/blog/q-day-and-the-impact-of-breaking-rsa2048
[8] Strilanc, C. (2017, August 28). Shor's quantum factoring algorithm. Algorithmic Assertions. https://algassert.com/post/1718
[9] Scrivano, A. (2025, June 6). A comparative study of classical and post-quantum cryptographic algorithms in the era of quantum computing. arXiv:2508.00832v1. https://arxiv.org/html/2508.00832v1
[10] Meegle. (2024, December 29). Quantum error correction. https://www.meegle.com/en_us/topics/quantum-computing/quantum-error-correction
[11] Webster, P., Berent, L., Chandra, O., Hockings, E. T., Baspin, N., Thomsen, F., Smith, S. C., & Cohen, L. Z. (2026, February 12). The Pinnacle Architecture: Reducing the cost of breaking RSA-2048 to 100,000 physical qubits using quantum LDPC codes. arXiv:2602.11457v1. https://arxiv.org/html/2602.11457v1
[12] Aaronson, S. (2026). On reducing the cost of breaking RSA-2048 to 100,000 physical qubits. Shtetl-Optimized. https://scottaaronson.blog/?p=9564
[13] Ivezic, M. (2025, April 24). The enormous energy cost of breaking RSA-2048 with quantum computers. PostQuantum.com. https://postquantum.com/post-quantum/energy-cost-rsa-2048-quantum/
[14] Gascuel, J. (2023, November 12). Quantum computing RSA encryption: a threat and a solution. Freemindtronic. https://freemindtronic.com/quantum-computing-rsa-encryption-freemindtronic-nfc-technology/
[15] Li, S., Chen, Y., Chen, L., Liao, J., Kuang, C., Li, K., Liang, W., & Xiong, N. (2023). Post-quantum security: Opportunities and challenges. Sensors (Basel), 23(21), 8744. https://doi.org/10.3390/s23218744
[16] Bamford, A. (2026, March 2). Assessing quantum's risk on critical infrastructure. Bloomsbury Intelligence and Security Institute (BISI). https://bisi.org.uk/reports/assessing-quantums-risk-on-critical-infrastructure
[17] Microsoft Quantum. (n.d.). Quantum error correction. https://quantum.microsoft.com/en-us/insights/education/concepts/quantum-error-correction
[18] Singh, S., & Sakk, E. (2024, January 8). Implementation and analysis of Shor's algorithm to break RSA cryptosystem security. TechRxiv. https://doi.org/10.36227/techrxiv.170259160.05374043/v2
[19] Rehman, M. U. (2026, April 6). Understanding quantum error correction: Will quantum computers overcome their biggest challenge? The Quantum Insider. https://thequantuminsider.com/2026/03/16/understanding-quantum-error-correction-physical-logical-qubits/
[20] QuEra Computing. (n.d.). What is quantum error correction (QEC). https://www.quera.com/glossary/quantum-error-correction
[21] Mishan, L. (2025, June 17). Scalable quantum error correction: Breaking bottlenecks in quantum computing. Quantum Machines. https://www.quantum-machines.co/blog/scalable-quantum-error-correction/
[22] Netlas. (2026). Post-quantum now: From AES & RSA to ML-KEM hybrids. https://netlas.io/blog/post_quantum_cryptography/
[23] Ivezic, M. (2026, March 6). No one has secretly broken RSA-2048 or RSA-4096 — Here's the science. PostQuantum.com. https://postquantum.com/post-quantum/no-broken-rsa-2048-4096/
[24] SDxCentral. (2026, March). Google sets 2029 for quantum apocalypse. https://www.sdxcentral.com/news/google-sets-2029-for-quantum-apocalypse/
[25] CyberScoop. (2026, March). Google moves post-quantum encryption timeline up to 2029. https://cyberscoop.com/google-moves-post-quantum-encryption-timeline-to-2029/
본 글은 공개된 연구를 바탕으로 정보 제공 목적으로 작성되었으며, 전문적인 판단을 대신하거나 의학적 진단이나 치료를 위한 근거로 사용될 수 없습니다.
댓글
댓글 쓰기