양자 보안 (Quantum Security)

아직 RSA-2048을 실제로 깨뜨릴 만큼 큰 양자컴퓨터는 없다. 그런데 왜 지금 대비하는가? 이유는 두 가지다.

1. Shor 알고리즘이 이미 존재한다(1994). 하드웨어만 커지면 RSA·ECC 공개키 암호가 원리적으로 붕괴한다. "언젠가"의 문제이지 "가능한가"의 문제가 아니다.
2. 수확 후 해독(Harvest Now, Decrypt Later, HNDL) — 공격자는 오늘 암호문을 통째로 긁어 저장해두고, 미래에 양자컴퓨터가 완성되면 그때 복호화한다. 즉, 지금 오가는 통신 중 수십 년간 비밀이어야 하는 것(의료·국가기밀·금융·유전정보)은 이미 위험에 노출돼 있다.

현대 암호의 안전성은 대부분 "어떤 계산은 정답이 있어도 실행하는 데 천문학적 시간이 걸린다"는 계산적 난이도(computational hardness)에 기댄다. 정답이 존재하지 않는 게 아니라, 제 시간에 못 찾는 것이다.

1.1 공개키: 되돌리기 어려운 일방향 문제

RSA와 ECC는 한 방향은 쉽고 반대 방향은 어려운 수학 문제(일방향 함수, trapdoor)를 쓴다.

• RSA — 두 큰 소수 \(p, q\)를 곱해 \(N = pq\)를 만드는 건 쉽다. 반대로 \(N\)만 보고 \(p, q\)를 알아내는 소인수분해는 고전적으로 지수급에 가깝다. 대략 \(\exp\!\big(c\,(\ln N)^{1/3}(\ln\ln N)^{2/3}\big)\) (수체 체, GNFS).
• ECC (타원곡선) — 점 \(G\)를 \(k\)번 더해 \(Q = kG\)를 구하는 건 쉽지만, \(Q, G\)로부터 \(k\)를 찾는 이산로그(discrete log)는 어렵다. 같은 보안강도를 RSA보다 훨씬 짧은 키로 얻는다(예: ECC 256비트 ≈ RSA 3072비트).

1.2 대칭키·해시: 무차별 대입에 기댄다

AES(대칭키 암호)와 SHA-2/3(해시)는 소인수분해 같은 구조적 약점이 없다. 이들의 안전성은 "키 \(2^n\)개를 전부 시도(brute force)하는 것 말고는 방법이 없다"에 기댄다. AES-128이면 \(2^{128}\), AES-256이면 \(2^{256}\)가지를 다 해봐야 한다 — 고전 컴퓨터로는 불가능한 규모.

정리하면, 기존 암호는 모두 "계산이 어렵다"는 한 가지 가정 위에 서 있다. 이 가정을 양자컴퓨터가 흔든다.

양자컴퓨터는 "모든 계산을 빨리" 하지 못한다. 하지만 하필 공개키 암호가 기대는 그 문제들(소인수분해·이산로그)에서 지수적 가속을 낸다. 이게 문제의 핵심이다.

2.1 Shor — 공개키의 종말 (지수 → 다항)

Shor 알고리즘은 소인수분해를 주기 찾기(period finding) 문제로 바꾼다. 함수 \(f(x)=a^x \bmod N\)은 어떤 주기 \(r\)마다 값이 반복된다(\(f(x+r)=f(x)\)). 이 \(r\)만 알면 초등적 계산으로 \(N\)의 소인수가 튀어나온다.

고전 컴퓨터는 \(r\)을 찾으려면 값을 하나씩 뒤져야 한다. 양자컴퓨터는 양자 푸리에 변환(QFT)으로 중첩된 상태 전체의 숨은 주기를 한 번에 드러낸다. 복잡도가 사실상 지수급에서 다항급 \(O((\log N)^2\,\log\log N\,\log\log\log N)\)(간단히는 \(O((\log N)^3)\))으로 떨어진다.

결과: RSA·ECC·DH가 전부 다항시간에 깨진다. 키를 키운다고 해결되지 않는다 — 지수가 다항으로 바뀌었으므로, 키 길이를 늘리는 방어는 곧 따라잡힌다.

2.2 Grover — 대칭키를 절반으로 (√N 가속)

Grover 알고리즘은 구조 없는 탐색을 가속한다. \(N=2^n\)개 후보 중 정답 하나를 고전적으로는 평균 \(N/2\)번 시도해야 하지만, Grover는 \(O(\sqrt{N})\)번이면 된다. 진폭을 정답 쪽으로 조금씩 회전시켜 증폭하는 방식이다.

암호에 대입하면: \(2^n\) 키 탐색이 \(2^{n/2}\)로 준다. 즉 유효 키 길이가 절반이 된다.

* 충돌 탐색 \(2^{85}\)은 Grover가 아니라 BHT(Brassard–Høyer–Tapp) 알고리즘 수치이며, 대규모 양자메모리(QRAM)를 가정한 이상적 값이다. 현실적 비용 모델에선 고전 병렬 공격(\(2^{128}\))이 더 나을 수 있어 실전 이득은 논쟁적이다. 순수 Grover는 역상(preimage)만 \(2^{128}\)로 줄인다.

"양자 보안"이라는 말은 자주 뒤섞여 쓰이지만, 사실 철학이 정반대인 두 접근을 함께 가리킨다.

QKD의 목표는 단 하나: 앨리스와 밥이 도청 없이 같은 비밀 난수 열쇠를 나눠 갖는 것. 그 열쇠를 얻고 나면, 그걸로 일회용 패드나 AES를 돌려 실제 메시지를 암호화한다. 여기서 마법은 도청을 원리적으로 탐지할 수 있다는 점이다.

4.1 바탕 원리 — 측정은 상태를 바꾼다

큐비트 하나는 \( |\psi\rangle = \alpha|0\rangle + \beta|1\rangle,\ |\alpha|^2+|\beta|^2=1 \). 측정은 사영(projection)이라, 관측하는 순간 상태가 \(|0\rangle\) 또는 \(|1\rangle\)로 붕괴하고 원래의 \(\alpha,\beta\)는 사라진다. 물리 전공자 감각으로는 "측정이 파동함수를 특정 기저의 고유상태로 사영시킨다"는 그 얘기다.

더 중요한 건 어떤 기저로 재느냐다. 같은 큐비트라도 다른 기저로 측정하면 결과가 달라진다. 도청자 이브가 어떤 기저로 재야 할지 모른 채 측정하면, 절반은 틀린 기저로 재고 그 과정에서 상태를 교란한다 — 이 교란이 흔적으로 남는다.

4.2 복제 불가 정리 (No-Cloning)

이게 왜 보안인가? 이브는 큐비트를 가로채도 완벽한 복사본을 떠서 하나는 밥에게 보내고 하나는 자기가 나중에 분석하는 수법을 쓸 수 없다. 정보를 얻으려면 반드시 측정해야 하고, 측정하면 반드시 교란이 남는다.

4.3 BB84 프로토콜 (Bennett & Brassard, 1984)

앨리스는 각 비트를 두 기저 중 무작위로 하나를 골라 큐비트(예: 광자 편광)로 인코딩한다.

• 직교 기저(+, rectilinear): \(|0\rangle\)=수평, \(|1\rangle\)=수직 편광
• 대각 기저(×, diagonal): \(|+\rangle=\tfrac{1}{\sqrt2}(|0\rangle+|1\rangle)\)=45°, \(|-\rangle=\tfrac{1}{\sqrt2}(|0\rangle-|1\rangle)\)=135°

이 두 기저는 켤레(conjugate) 관계라, 한 기저의 상태를 다른 기저로 재면 결과가 50:50 무작위가 된다. 밥도 각 광자를 무작위 기저로 측정한다.

절차를 말로 풀면:

1. 전송 — 앨리스가 (비트, 기저)를 무작위로 골라 광자로 보낸다.
2. 측정 — 밥이 무작위 기저로 측정. 기저가 우연히 같으면 값이 일치, 다르면 무작위.
3. 기저 대조(sifting) — 공개 채널로 기저만 공개(측정값은 비밀). 기저가 일치한 비트만 남긴다(평균 절반). 이게 원시 키.
4. 도청 점검 — 원시 키 일부를 서로 공개해 오류율(QBER, Quantum Bit Error Rate)을 계산. 이브가 없었다면 오류가 거의 없어야 한다.

4.4 E91 프로토콜 (Ekert, 1991) — 얽힘과 벨 부등식

BB84가 "복제 불가·측정 교란"에 기댄다면, E91은 얽힘(entanglement)을 직접 쓴다. 얽힌 광자쌍 \( |\Phi^+\rangle=\tfrac{1}{\sqrt2}(|00\rangle+|11\rangle) \)을 만들어 하나는 앨리스, 하나는 밥에게 보낸다. 둘은 여러 각도의 측정을 무작위로 골라 수행한다.

핵심은 벨/CHSH 부등식이다. 만약 이브가 중간에서 측정하거나(=국소적 숨은 변수로 대체하거나) 상태를 복제하려 하면, 얽힘이 깨져 상관관계가 약해진다. 그 결과 측정 데이터가 벨 부등식을 위반하지 못하게 된다.

이 페이지 전체의 뼈대. 보안의 "근거"가 세 가지로 갈린다.

5.1 계산적 안전 vs 정보이론적 안전 — 이게 핵심 차이

※ QKD의 "무조건 안전"에는 별표가 하나 붙는다 — 고전 채널이 인증(authentication)되어 있어야 성립한다. 인증이 없으면 중간자(MITM)가 양쪽과 각각 열쇠를 나눠 무력화한다(→ 7.1). 실무의 인증은 흔히 계산적(PQC 서명)이라, 엄밀한 정보이론적 안전은 인증까지 정보이론적일 때만 완결된다.

여기서 QKD가 유일하게 특별한 이유가 드러난다. RSA도, PQC도 결국 "충분히 어려운 계산"에 기대는 계산적 안전이다 — 언젠가 더 똑똑한 공격이 나올 가능성이 원리적으로 남아 있다. 반면 QKD로 나눈 열쇠를 일회용 패드에 쓰면, 그 통신은 물리 법칙이 바뀌지 않는 한 절대 못 깬다. 계산 문제가 아니라 정보의 부재이기 때문이다.

그럼 왜 다들 QKD로 안 가고 PQC를 주류로 미는가? 정보이론적 안전이 이론상 더 강한데도 말이다. 답은 7절의 "현실 제약"에 있다. QKD는 물리 인프라가 무겁고, 인증이 없으면 중간자 공격에 뚫리며, 열쇠 분배밖에 못한다. 반면 PQC는 소프트웨어 업데이트만으로 전 세계에 뿌릴 수 있다.

PQC는 여전히 고전 컴퓨터에서 돌아가는 알고리즘이다. 다만 안전성의 뿌리를 Shor·Grover가 이득을 못 보는 문제로 갈아 끼웠다. 소인수분해·이산로그가 아닌, 격자(lattice)·해시(hash)·부호·다변수 다항식 기반이다.

6.1 격자 기반 (Lattice) — 주류

격자는 \(n\)차원 공간에 규칙적으로 찍힌 점들의 무한 배열이다. 핵심 난제는 "주어진 임의의 점에서 가장 가까운 격자점을 찾아라"(최근접 벡터 문제, CVP/SVP) — 차원이 높아지면 고전이든 양자든 지수적으로 어렵다.

Shor가 소인수분해에서 통했던 이유는 그 문제에 깔끔한 주기 구조가 있었기 때문이다. 격자 문제엔 그런 주기 구조가 없어 QFT를 걸 곳이 없다 — 그래서 양자컴퓨터도 뾰족한 수가 없다(현재까지).

6.2 해시 기반 (Hash) — 가장 보수적

해시 기반 서명은 오직 해시 함수의 안전성 하나에만 기댄다(예: SHA-256의 역상 저항성). 새로운 수학 가정을 도입하지 않으므로 가장 신뢰가 높은 백업이다. 대신 서명이 크고 상태 관리가 까다로울 수 있다. Grover의 √N 가속은 해시 출력을 넉넉히(예: 256비트) 잡으면 흡수된다.

6.3 NIST 표준 — 2024년 8월 확정

NIST는 8년(2016–2024) 공모·검증 끝에 2024년 8월 최종 표준(FIPS)을 발표했다. 이름이 알고리즘 원안(괄호)에서 표준명으로 바뀐 점에 유의.

QKD는 이론상 가장 강한 안전(정보이론적)을 준다. 그런데도 실무 주류는 PQC다. 이유를 솔직하게 정리한다.

7.1 QKD의 실전 한계

• 거리 감쇠 — 광섬유에서 광자가 흡수되어 신호가 지수적으로 줄어든다. 복제 불가 정리 때문에 고전 통신처럼 증폭(리피터)을 할 수 없다. 실용 구간은 수십~수백 km. 그 이상은 신뢰 중계 노드(보안 취약)나 아직 미성숙한 양자 중계기가 필요하다. 위성 QKD(예: 中 Micius)로 장거리를 시연하긴 했다.
• 전용 하드웨어 — 단일광자원·초고감도 검출기·전용 광섬유/자유공간 링크가 필요. 인터넷 위에 소프트웨어로 얹을 수 없다. 비싸고 무겁다.
• 인증 없으면 중간자 공격(MITM) — QKD는 도청 탐지는 하지만, 앨리스와 밥이 서로 진짜인지는 보장 못 한다. 이브가 양쪽과 각각 QKD를 맺어 중계하면 뚫린다. 그래서 QKD도 결국 별도의 인증(대개 고전/PQC 서명)이 필요하다 — 완전 자립이 아니다.
• 열쇠 분배만 한다 — QKD는 전자서명·부인방지·인증서 같은 걸 못 한다. 공개키 인프라(PKI) 전체를 대체하지 못하고, 딱 "비밀 난수 나누기"만 담당한다.
• 구현 부채널 — 이론은 완전해도, 실제 검출기의 결함을 노린 공격(예: detector blinding)이 보고돼 왔다. "물리 법칙이 안전"이라도 장치가 이상적이지 않으면 틈이 생긴다.

7.2 그래서 지형은 PQC로 이동 중