양자컴퓨터 실사용 - 정보보안

범위

이 문서는 양자 알고리즘이 기존 암호 체계에 주는 계산복잡도 관점의 영향을 설명합니다. Kyber 같은 post-quantum cryptography는 여기서 다루지 않습니다. 목표는 “왜 Shor와 Grover가 보안 파라미터를 바꾸는가”를 이해하는 것입니다.

Shor로 비대칭 암호를 부수는 이유

RSA는 큰 합성수 N=pq를 소인수분해하기 어렵다는 가정 위에 있습니다. 공개키에는 N이 들어가지만, 개인키를 만들려면 p,q를 알아야 합니다.

Shor 알고리즘은 소인수분해를 order finding으로 바꾸고, 양자 위상추정으로 order 후보를 찾습니다. 후보가 성공하면 고전적인 gcd 계산으로 인수를 얻습니다.

$$
\gcd(a^{r/2}-1,N),\qquad \gcd(a^{r/2}+1,N)
$$

이 말은 충분히 큰 fault-tolerant quantum computer가 있다면 RSA의 핵심 난제가 더 이상 현재 보안 가정처럼 작동하지 않는다는 뜻입니다. 양자컴퓨터가 암호문을 “마법처럼 읽는” 것이 아니라, 공개키 안의 수학 문제를 빠르게 풀어 개인키에 해당하는 정보를 복원하는 것입니다.

이산로그 기반 암호도 같은 계열이다

Diffie-Hellman, DSA, ECDSA, elliptic-curve Diffie-Hellman 계열은 이산로그 문제가 어렵다는 가정 위에 있습니다. Shor는 소인수분해뿐 아니라 이산로그 문제에도 다항시간 알고리즘을 제공합니다.

즉 RSA만 문제가 되는 것이 아닙니다. 현재 널리 쓰이는 많은 공개키 암호와 전자서명 방식이 Shor의 직접 영향권에 들어갑니다. 특히 elliptic curve cryptography는 고전적으로 짧은 키로 높은 보안을 제공하지만, 충분한 양자컴퓨터 앞에서는 이산로그 구조 자체가 약점이 됩니다.

Grover로 대칭 암호 복호화를 더 쉽게 하기

대칭키 암호는 보통 키 공간을 전수조사하는 비용으로 보안 강도를 말합니다. 키 길이가 n비트이면 가능한 키 수는 2^n개입니다.

$$
\text{classical brute force}\sim O(2^n)
$$

Grover 알고리즘은 정답 키를 찾는 oracle이 있을 때 탐색 비용을 제곱근으로 줄입니다.

$$
\text{Grover search}\sim O(2^{n/2})
$$

예를 들어 128비트 대칭키는 양자 회로에서 64비트 보안 강도를 가집니다. 그로버 알고리즘은 안정적으로 손실 없이 게이트를 굴릴 수 있을 때 기준으로 시간복잡도 O(루트n)이라는 지점을 확실히 잡고 넘어가야 함. 그래서 대칭 암호는 “완전히 붕괴”라기보다 키 길이를 늘려 대응하는 방향으로 이해하는 것이 맞습니다. 256비트 키는 양자컴퓨터서 128비트 수준의 전수조사 비용을 기대할 수 있습니다.

Grover에서 oracle 비용을 빼먹으면 안 된다

Grover가 키 탐색을 빠르게 한다고 할 때, oracle은 “이 키가 맞는지 검사하는 회로”입니다. 실제로는 암호 알고리즘 자체를 reversible quantum circuit으로 구현해야 합니다.

$$
O_f|k\rangle=(-1)^{f(k)}|k\rangle
$$

여기서 f(k)=1은 키 k로 복호화했을 때 알려진 평문/태그/검증 조건을 만족한다는 뜻입니다. oracle 구현이 비싸면 Grover 반복 한 번도 비싸집니다. 따라서 실제 공격 비용은 단순히 2^{n/2}만 보고 끝내면 안 되고, 암호 회로의 gate count, depth, 오류정정 비용까지 함께 봐야 합니다.

비대칭과 대칭의 차이

핵심 정리

• Shor는 공개키 암호의 수학적 가정을 직접 공격합니다.
• Grover는 대칭키와 hash 전수조사를 제곱근만큼 빠르게 합니다.
• Shor의 영향은 질적으로 크고, Grover의 영향은 보안 파라미터를 키우는 방식으로 해석하기 쉽습니다.
• 두 경우 모두 실제 공격에는 fault-tolerant quantum computer와 큰 리소스가 필요합니다.