Shor 알고리즘은 왜 RSA와 ECC를 위협할까? 원리와 현실적 한계

Shor 알고리즘의 의미는 큰 수의 소인수분해와 이산로그 문제를 양자컴퓨터에서 효율적으로 해결할 수 있는 알고리즘을 제시했다는 데 있습니다.

하지만 '현재 양자컴퓨터가 RSA를 바로 해독할 수 있다'는 의미는 아닙니다. 실제 대규모 암호를 공격하려면 매우 낮은 오류율로 긴 회로를 실행할 수 있는 fault-tolerant quantum computer가 필요합니다.

쇼어 알고리즘은 ‘어렵다고 믿어온 수학 문제’를
양자컴퓨터에서 ‘다항시간’에 풀 수 있음을 증명했다.
그 결과 RSA·Diffie‑Hellman·ECC 기반 공개키 암호는
충분히 큰 양자컴퓨터 앞에서 근본적으로 붕괴한다. 

1️⃣ 현대 공개키 암호는 무엇을 믿고 있을까?

오늘날 인터넷 보안의 핵심(HTTPS, 인증서, 전자서명)은 아래 가정을 전제로 합니다.

RSA	큰 수의 소인수분해
Diffie‑Hellman	이산 로그 문제
ECC(ECDSA/Ed25519)	타원곡선 이산 로그 문제

• 곱하기는 쉽고, 되돌리기는 어렵다는 비대칭성
• 고전 컴퓨터로는 수명이 우주보다 김

2️⃣ 쇼어 알고리즘은 무엇이 다른가?

1994년 피터 쇼어는 다음을 보였습니다.

✅ 정수 소인수분해·이산 로그 문제를
양자컴퓨터에서 다항시간(polynomial time)에 해결 가능

핵심은 문제 환원입니다.

• 소인수분해/이산로그 → 주기 찾기(period finding)
• 주기 찾기 → **양자 푸리에 변환(QFT)**로 효율적 추출

이는 “조금 빠름”이 아니라 차원이 다른 가속입니다.
(고전: 아득한 시간 → 양자: 현실적 시간)

 

Shor 알고리즘은 양자회로에서 주기성을 찾는 문제로 소인수분해를 변환하고 Quantum Fourier Transform 등을 이용해 그 주기 정보를 추출합니다.

이 관점에서 보면 '양자컴퓨터가 모든 수를 동시에 나눠본다'는 흔한 설명보다 알고리즘의 실제 구조를 더 정확하게 이해할 수 있습니다.

3️⃣ 왜 “키 길이를 늘리면” 해결이 안 되나?

고전 보안은 키 길이 확장으로 버텼습니다.
하지만 쇼어 알고리즘에서는:

• 계산량이 비트 수의 다항식으로 증가
• 키를 키워도 본질적으로 안전해지지 않음

즉,

“더 큰 RSA”라는 방어는 없다.

4️⃣ 무엇이 실제로 깨지나? (그리고 무엇은 아니다)

✅ 취약 (근본적으로)

• RSA
• Diffie‑Hellman
• ECC 계열 전부 (ECDSA, Ed25519 등)

⛔ 상대적으로 안전

• 대칭키(AES): 그로버 알고리즘의 제곱근 가속만 영향
• → 키 길이 증대(AES‑256)로 대응 가능

5️⃣ “지금은 아직 안전한데, 왜 지금 준비하나?”

이유 1) Harvest Now, Decrypt Later

• 오늘 암호화된 데이터를 지금 수집
• 미래의 양자컴퓨터로 나중에 복호화 가능

이유 2) 이행 시간

• PKI·TLS·임베디드·하드웨어 교체: 수년 단위
• 암호는 “즉시 교체”가 불가능

6️⃣ 그래서 업계는 무엇을 하는가?

• PQC(양자내성암호) 표준화
  • NIST는 2024년 ML‑KEM, ML‑DSA, SLH‑DSA를 확정
• 하이브리드 전환
  • 기존 ECC + PQC 서명 병행
• 암호 민첩성(Cryptographic Agility) 확보

7️⃣ 오해 정리 (한 눈에)

아직 양자컴퓨터 없는데 걱정 과하다	데이터 수명이 더 김
대칭키도 전부 깨진다	❌ (키 길이로 대응 가능)
ECC는 RSA보다 안전하다	❌ (쇼어에는 동일 취약)
키 길이 늘리면 된다	❌ (공개키에는 통하지 않음)

양자컴퓨터란? 큐비트부터 오류정정까지 한 번에 이해하기

 

QAOA란? 양자최적화를 Max-Cut 문제로 이해하기

 

큐비트(Qubit) 쉽게 이해하기: 0/1이 아닌 ‘상태’의 의미 ✅