Shor 알고리즘과 Grover 알고리즘 해설

양자 컴퓨터는 고전 알고리즘을 단순히 더 빠르게 실행하는 데 그치지 않고, 양자 중첩과 간섭을 활용하여 특정 문제를 지수적으로 더 빠르게 해결합니다. 현재 배포된 암호 체계를 위협하는 두 알고리즘은 쇼어 알고리즘(RSA/ECC를 해독)과 그로버 알고리즘(대칭키 암호와 해시를 약화)입니다.

쇼어 알고리즘(1994년)은 양자 컴퓨터에서 정수 인수분해와 이산 로그 문제를 다항 시간에 해결합니다. 이는 인수분해에 기반한 RSA, 소수 p를 법으로 하는 이산 로그에 기반한 디피-헬먼(DH), 타원 곡선 이산 로그에 기반한 ECDH/ECDSA를 직접적으로 해독합니다.

쇼어 알고리즘의 핵심 요소는 양자 푸리에 변환(QFT)입니다. 이는 DFT를 양자 방식으로 구현한 지수적으로 더 빠른 변환입니다. 주기 찾기에서 QFT는 f(x) = a^x mod N의 주기를 식별하며, 이 주기로부터 GCD를 사용해 N의 인수를 구합니다.

N을 인수분해하려면 다음과 같이 합니다. (1) N보다 작은 무작위 a를 선택하고 gcd(a,N)=1인지 확인합니다. (2) QFT를 사용하여 f(x)=a^x mod N의 주기 r을 찾습니다. (3) 높은 확률로 gcd(a^{r/2}±1, N)을 계산하면 자명하지 않은 인수를 얻을 수 있습니다. 고전 단계의 복잡도는 O(log N)이고, 양자 주기 찾기의 복잡도는 O((log N)^3)으로 다항 시간입니다.

고전적 인수분해에서 가장 우수한 방법은 GNFS이며, 복잡도는 준지수 시간인 O(exp((64/9 log N)^{1/3} log log N)^{2/3}))입니다. 결함 허용 양자 컴퓨터에서 쇼어 알고리즘의 복잡도는 다항 시간인 O((log N)^3)입니다. RSA-2048을 해독하려면 약 4000개의 논리 큐비트와 약 10^9회의 게이트 연산이 필요합니다. 현재의 NISQ 컴퓨터는 약 1000개의 잡음이 있는 큐비트만 보유하고 있으므로 아직 위협이 되지 않습니다.

그로버 알고리즘(1996년)은 비구조적 검색에서 이차적인 속도 향상을 제공합니다. N개의 항목으로 이루어진 검색 공간에서 고전 알고리즘은 O(N)회의 질의가 필요하지만, 그로버 알고리즘은 O(√N)회가 필요합니다. 암호학에 적용하면 n비트 대칭키를 O(2^n) 대신 O(2^{n/2})에 해독할 수 있습니다.

AES-128의 고전적 보안 수준은 2^128이지만 그로버 알고리즘에 의해 2^64로 낮아져 대규모 양자 컴퓨터에 안전하지 않습니다. AES-256은 2^256에서 2^128로 낮아지지만 여전히 안전합니다. 해결 방법은 대칭키 크기를 두 배로 늘리는 것입니다. SHA-256의 충돌 저항성은 2^128에서 2^85로 낮아집니다(생일 공격+그로버 알고리즘). SHA-256의 원상 공격 저항성은 2^256에서 2^128로 낮아지며, 이는 OK입니다.

현재의 NISQ 양자 컴퓨터(IBM Heron: 133큐비트, Google Sycamore: 70큐비트)는 암호학적으로 의미 있는 계산을 수행하기에는 너무 작고 잡음이 많습니다. RSA-2048 해독 시점은 결함 허용 양자 컴퓨터가 등장한다는 가정 아래 2035~2050년으로 추정됩니다. 지금 수집하고 나중에 복호화하는 공격은 현재 진행 중인 위협입니다.

공격자는 오늘 암호화된 트래픽을 수집하여 저장합니다. 양자 컴퓨터를 사용할 수 있게 되면 이를 과거로 거슬러 올라가 복호화합니다. 따라서 수명이 긴 비밀 정보(정부 기밀 데이터, 의료 기록)는 오늘부터 취약합니다. 이러한 데이터를 보호하려면 지금 PQC 전환을 시작해야 합니다.

격자 문제(LWE, SIS), 코드 기반 문제(McEliece), 해시 기반 서명(SPHINCS+), 다변량 문제에는 알려진 다항 시간 양자 알고리즘이 없습니다. 이러한 문제들이 NIST 포스트양자 표준의 기반입니다.

NIST PQC 표준(ML-KEM, ML-DSA, SLH-DSA)은 2024년에 최종 확정되었습니다. 조직은 현재 암호 사용 현황을 목록화하고, 수명이 긴 데이터를 식별하며, 키 교환에 PQC를 우선적으로 배포해야 합니다. 지금 수집하고 나중에 복호화하는 공격 때문에 키 교환이 가장 시급합니다. 서명 전환에는 더 많은 시간이 있습니다.

그로버 알고리즘이 AES-128에 미치는 영향은 무엇인가요?

쇼어 알고리즘(다항 시간)은 RSA, DH, ECC를 해독합니다. 그로버 알고리즘(이차적 속도 향상)은 대칭키 강도를 절반으로 낮춥니다. 해결 방법은 NIST PQC 표준(격자 기반)으로 전환하는 것입니다. 다음으로 CRYSTALS-카이버 KEM을 살펴봅니다.