Shor·양자내성암호·양자 난수¶
이전: 클라우드·산업·양자 우위 · 심화 과정 홈 · FAQ
Shor 알고리즘과 공개키 암호¶
Shor 알고리즘은 충분히 큰 오류내성 양자컴퓨터에서 정수 소인수분해와 이산로그를 다항시간에 푼다. 따라서 다음 공개키 체계에 근본적인 영향을 준다.
- RSA: 소인수분해
- Diffie–Hellman: 유한체 이산로그
- 타원곡선 암호(ECC): 타원곡선 이산로그
Shor가 “가능한 인수를 모두 동시에 시험”하는 것으로만 설명되면 핵심을 놓친다. 모듈러 지수 함수의 주기를 양자 푸리에 변환과 고전 후처리로 찾는 것이 중심이다. 실제 자원의 상당 부분은 모듈러 산술을 가역 회로로 구현하고 오류 정정하는 데 든다.
현재 공개 장비의 규모는 RSA-2048 공격에 필요한 수준에 미치지 못한다. 암호 체계의 교체에는 오랜 시간이 걸리고, 오늘 수집한 암호문을 미래에 복호할 수 있는 harvest now, decrypt later 위험이 있으므로 준비는 장비 완성 전에 시작해야 한다.
대칭키와 해시¶
Grover 탐색은 이상적인 비정형 키 탐색을 N회에서 약 √N회로 줄인다.
| 대상 | 알려진 일반적 양자 영향 | 실무적 해석 |
|---|---|---|
| RSA·DH·ECC | Shor의 큰 가속 | PQC로 교체 필요 |
| AES | Grover의 제곱근 질의 감소 | AES-256으로 충분한 안전 여유 확보 |
| 해시 역상 | Grover형 제곱근 감소 | 출력 길이와 실제 회로 비용 고려 |
| 해시 충돌 | 양자 충돌 알고리즘 | 적절한 출력 길이와 표준 지침 사용 |
Grover 반복 한 번에는 암호 회로 전체의 결맞은 실행이 필요하다. 실제 공격 시간은 병렬화, 오류 정정과 회로 깊이를 포함해 계산한다.
PQC는 무엇인가¶
양자내성암호(post-quantum cryptography, PQC)는 고전 컴퓨터에서 실행되는 새로운 공개키 알고리즘이다. 양자와 고전 공격 모두에 강할 것으로 평가된 수학 문제를 사용한다.
NIST는 2024년 다음 세 표준을 확정했다.
| 표준 | 알고리즘 | 역할 |
|---|---|---|
| FIPS 203 | ML-KEM | 키 설정을 위한 KEM |
| FIPS 204 | ML-DSA | 격자 기반 전자서명 |
| FIPS 205 | SLH-DSA | 해시 기반 전자서명 |
NIST는 조직에 전환 시작을 권고한다. NIST PQC 프로젝트, 표준 확정 발표
PQC 표준은 오랜 공개 분석과 보안 감소, 구현 검토를 거친 현재의 최선이다. 장기 안전성은 알고리즘 다양성, 구현 보안과 암호 민첩성(crypto-agility) 으로 보완한다.
실무 순서:
- RSA·DH·ECC가 사용되는 위치와 장기 보관 데이터를 목록화한다.
- 프로토콜·인증서·HSM·펌웨어의 교체 가능성을 평가한다.
- 표준 PQC와 필요한 하이브리드 구성을 시험한다.
- 키·서명 크기, 성능, 상호운용성과 구현 취약점을 검증한다.
- 알고리즘을 다시 교체할 수 있는 운영 체계를 만든다.
양자 난수¶
양자 난수 생성기(QRNG)는 양자 측정의 예측 불가능성을 이용해 고전 비트를 만든다. 생성 후 출력은 일반적인 고전 데이터이므로, 키가 QRNG에서 왔는지 다른 안전한 난수원에서 왔는지가 Shor나 Grover 공격 방식을 바꾸지는 않는다.
QRNG의 잠재 가치:
- 약한 시드와 예측 가능한 PRNG 상태 위험 감소
- 물리적 엔트로피원의 다양화
- 장치 독립 또는 검증 가능한 난수 연구
주의점:
- 실제 장치에는 편향, 고전 잡음과 공격자 측 정보가 있을 수 있다.
- 엔트로피 추정, randomness extractor, 건강 상태 검사와 인증이 필요하다.
- 안전한 난수도 키 저장·전달·사용이 취약하면 전체 암호를 지키지 못한다.
키를 자주 바꾸면 안전한가¶
키 회전은 유출된 키 하나의 피해 범위를 줄일 수 있지만, 그 자체가 전방 비밀성(forward secrecy)을 보장하지 않는다.
전방 비밀성을 얻으려면 과거 세션 키를 복원할 수 없는 독립적인 임시 키 교환, 안전한 키 삭제 또는 래칫 구조가 필요하다. 하나의 장기 시드에서 모든 키를 만들고 그 시드가 유출되면 단순 회전은 과거와 미래 키를 함께 노출할 수 있다.
또한 이미 저장된 암호문은 해당 세션 키가 미래에 깨지면 복호될 수 있다. 키 회전은 캡처된 트래픽을 자동으로 지우지 않는다.
일회용 패드와 키 배송¶
메시지와 같은 길이의 참난수를 한 번만 사용하고 비밀로 공유하는 일회용 패드는 기밀성 면에서 정보이론적으로 안전하다. 그러나 데이터만큼 긴 키를 안전하게 전달하고 절대 재사용하지 않아야 하며, 무결성과 인증은 별도로 제공해야 한다.
이 예는 암호의 어려움이 암호화 연산, 키 분배와 운영에 걸쳐 있음을 보여준다.
QKD와 PQC의 차이¶
양자 키 분배(QKD)는 양자 상태를 전송해 도청 흔적을 탐지하며 키 재료를 합의하는 기술이다. 안전한 사용에는 인증된 고전 채널과 구현 보안이 필요하다. 광자 수 분할이나 검출기 공격 같은 구현 취약점도 고려해야 한다.
| PQC | QKD |
|---|---|
| 고전 네트워크와 컴퓨터에서 실행 | 양자 광학 링크와 장비 필요 |
| 계산 난이도에 기반 | 이상화된 안전성은 양자 물리에 기반 |
| 인터넷 전반의 소프트웨어 전환 대상 | 거리·장비·토폴로지 제약이 있는 특수 인프라 |
대부분의 조직에서 당장의 우선순위는 QRNG나 QKD 도입보다 암호 자산 목록화와 표준 PQC 전환 준비다.
Shor 알고리즘의 계산 흐름¶
정수 N을 인수분해할 때 Shor 알고리즘은 N과 서로소인 값 a를 고르고 함수 f(x)=aˣ mod N의 주기 r을 찾는다.
- 고전 컴퓨터가
a를 선택하고 최대공약수를 확인한다. - 양자 회로가 여러
x에 대한 모듈러 지수함수를 결맞게 계산한다. - 위상 추정 또는 양자 푸리에 변환으로 주기 정보를 추출한다.
- 고전 연분수 알고리즘이 측정값에서 후보 주기
r을 복원한다. gcd(a^(r/2)±1,N)으로 인수 후보를 계산하고 검증한다.
양자 부분의 큰 비용은 모듈러 산술 회로다. 긴 논리 깊이와 많은 비-Clifford 연산이 필요하므로 물리 큐비트 수, 논리 오류율과 magic state 처리량이 전체 공격 시간을 결정한다. 보안 평가는 공개 장비의 물리 큐비트 수보다 오류내성 논리 자원 추정을 사용한다.
harvest now, decrypt later¶
장기 기밀성이 필요한 암호문은 현재 수집된 뒤 미래 장비에서 복호될 수 있다. 위험 기간은 다음 세 시간을 연결해 본다.
예를 들어 15년간 보호해야 할 데이터와 전환에 5년이 걸리는 시스템은 공격 장비 등장보다 훨씬 앞서 대응을 시작해야 한다. 서명 체계의 위험은 기밀성 외에도 장기 서명, 코드 서명, 펌웨어 업데이트와 신뢰 루트의 수명에 나타난다.
암호 자산 목록에 들어갈 내용¶
조직의 PQC 전환은 알고리즘 이름 교체보다 넓다. 자산 목록에는 다음을 기록한다.
| 항목 | 예시 |
|---|---|
| 사용 위치 | TLS, VPN, PKI, 코드 서명, 데이터베이스 암호화 |
| 알고리즘·키 | RSA, ECDH, ECDSA, 키 크기와 인증서 체인 |
| 구현 | 라이브러리, HSM, 펌웨어, 공급자 서비스 |
| 데이터 수명 | 기밀 유지 기간, 서명 검증 기간 |
| 교체 조건 | 성능, 패킷 크기, 저장공간, 상호운용성 |
| 소유자 | 시스템·보안·조달 담당 조직 |
자산 발견 자동화, SBOM과 암호 BOM(CBOM), 중앙 정책과 테스트 환경이 전환의 기반이 된다. 오래된 장비와 제3자 제품은 알고리즘 교체 기능이 제한될 수 있으므로 조달과 수명주기 계획에 포함한다.
하이브리드 전환¶
전환기에는 기존 알고리즘과 PQC 알고리즘을 결합한 하이브리드 키 설정이나 서명을 사용할 수 있다. 목표는 한 구성요소가 깨져도 다른 구성요소의 안전성이 남도록 결합하는 것이다. 결합 방식, 키 파생, 실패 처리와 프로토콜 협상이 안전성에 영향을 준다.
하이브리드는 패킷·인증서 크기와 계산량을 늘리고 운영 복잡성을 더한다. 배포 전에는 네트워크 장비, 프록시, HSM, 인증기관과 관측 도구의 호환성을 시험한다. 표준의 최종 상태와 규제 요구를 확인하며 단계별로 운영한다.
PQC 전환 단계¶
- 암호 자산과 장기 보호 데이터를 식별한다.
- 시스템을 중요도·수명·교체 난이도로 분류한다.
- 표준 구현의 성능과 상호운용성을 시험한다.
- crypto-agility 인터페이스와 키 관리 절차를 정비한다.
- 제한된 서비스에서 시범 배포하고 관측 지표를 수집한다.
- 공급망·인증서·프로토콜을 포함해 단계적으로 확대한다.
- 기존 알고리즘 제거 조건과 사고 대응 절차를 관리한다.
NIST는 FIPS 203의 ML-KEM, FIPS 204의 ML-DSA와 FIPS 205의 SLH-DSA를 2024년에 확정했다. 조직은 적용되는 국가 표준, 산업 규제와 제품 인증 절차를 함께 확인한다. NIST PQC 표준 발표