쇼어 알고리즘은 ‘어렵다고 믿어온 수학 문제’를
양자컴퓨터에서 ‘다항시간’에 풀 수 있음을 증명했다.
그 결과 RSA·Diffie‑Hellman·ECC 기반 공개키 암호는
충분히 큰 양자컴퓨터 앞에서 근본적으로 붕괴한다.
1️⃣ 현대 공개키 암호는 무엇을 믿고 있을까?
오늘날 인터넷 보안의 핵심(HTTPS, 인증서, 전자서명)은 아래 가정을 전제로 합니다.
| RSA | 큰 수의 소인수분해 |
| Diffie‑Hellman | 이산 로그 문제 |
| ECC(ECDSA/Ed25519) | 타원곡선 이산 로그 문제 |
- 곱하기는 쉽고, 되돌리기는 어렵다는 비대칭성
- 고전 컴퓨터로는 수명이 우주보다 김
2️⃣ 쇼어 알고리즘은 무엇이 다른가?
1994년 피터 쇼어는 다음을 보였습니다.
✅ 정수 소인수분해·이산 로그 문제를
양자컴퓨터에서 다항시간(polynomial time)에 해결 가능
핵심은 문제 환원입니다.
- 소인수분해/이산로그 → 주기 찾기(period finding)
- 주기 찾기 → **양자 푸리에 변환(QFT)**로 효율적 추출
이는 “조금 빠름”이 아니라 차원이 다른 가속입니다.
(고전: 아득한 시간 → 양자: 현실적 시간)
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보다 안전하다 | ❌ (쇼어에는 동일 취약) |
| 키 길이 늘리면 된다 | ❌ (공개키에는 통하지 않음) |
최종 요지
쇼어 알고리즘은 “해킹 기술”이 아니라
“암호 안전성 가정이 틀렸음”을 증명한 알고리즘이다.문제는 가능성이 아니라 시간과 준비다.