양자내성암호(PQC) 정리: 흔한 오해, 지금 바꿔야 하는 이유, 적용 현황

한눈에 보기

• PQC(Post-Quantum Cryptography, 양자내성암호)는 양자컴퓨터로도 풀기 어려운 수학 문제를 쓰는 새 공개키 암호다. 지금의 RSA(Rivest–Shamir–Adleman)·ECC(Elliptic Curve Cryptography, 타원곡선 암호)를 대체한다.
• 양자컴퓨터 기술은 아직 멀었더라도 지금 바꿔야 한다. 오늘 오가는 암호문을 저장해 두었다가 나중에 푸는 공격(HNDL, Harvest Now Decrypt Later)이 있기 때문이다.
• 주요 브라우저는 TLS(Transport Layer Security) 연결에서 하이브리드 PQC 키교환을 기본으로 제안하고, 서버가 지원하면 그 방식으로 연결된다. 하지만 인증서, VPN(Virtual Private Network, 가상 사설망), 저장 데이터 키 관리, 임베디드 장비는 아직 남아 있다.
• “PQC 인증” 제품이라고 PQC가 검증된 건 아니다. 국내에서 PQC 알고리즘 자체를 국가가 검증하는 일은 2028년에야 시작한다.

PQC란 무엇인가

인터넷 보안은 크게 두 종류의 암호에 기반한다. 데이터를 실제로 암호화하는 대칭키 암호(예: AES, Advanced Encryption Standard)와, 처음 만난 두 컴퓨터가 그 대칭키를 안전하게 나눠 갖고 서로를 확인하게 해 주는 공개키 암호(RSA, ECC 등)다.

공개키 암호가 하는 일은 두 가지로 보면 된다.

• 키교환: 세션키를 안전하게 나눠 갖는 일. HTTPS(HTTP Secure) 연결을 맺을 때마다 일어난다.
• 전자서명: 상대가 진짜인지 확인하는 일. 인증서, 코드서명, 전자문서에 쓰인다.

위험한 건 공개키 암호다

양자컴퓨터가 깨는 건 이 공개키 쪽이다. 암호 종류마다 양자컴퓨터에 깨지는 방식이 다르다.

• 공개키 암호는 무너진다. RSA는 소인수분해, ECC는 이산로그 문제가 어렵다는 데 기반한다. Shor 알고리즘은 이 두 문제를 양자컴퓨터에서 효율적으로 푼다. 지금은 수십억 년 걸리는 계산이 현실적인 시간으로 줄어들고, 키를 늘려도 계산량이 함께 조금 늘 뿐이라 막을 수 없다. 그래서 바탕이 되는 수학 문제 자체를 바꿔야 한다.
• 대칭키 암호는 약해질 뿐이다. AES에는 Shor 같은 지름길이 없다. 양자컴퓨터가 쓸 수 있는 건 Grover 알고리즘으로 키 전수조사를 빠르게 하는 것뿐인데, 이 효과는 키 길이를 절반으로 줄이는 정도다. AES-128은 64비트 수준으로 떨어지지만 AES-256은 128비트 수준이 남아 여전히 안전하다. Grover는 병렬로 나눠 돌리기도 어려워서 실제 이득은 이보다 작다.
• 해시(SHA-2, SHA-3)도 같은 이유로 약간 약해질 뿐이다. 출력 길이를 넉넉히 쓰면 된다.

그래서 PQC는 공개키 암호를 양자컴퓨터에도 버티는 수학 문제로 바꾸는 작업이고, 대칭키 암호는 키 길이만 넉넉히(AES-256) 잡으면 그대로 쓴다.

다만 대칭키가 안전하다고 데이터가 안전한 건 아니다. AES 키는 공개키 암호(키교환)로 나눠 갖기 때문에, 키교환이 깨지면 그 AES 키가 그대로 드러난다. 데이터를 AES-256으로 암호화해도 키교환이 RSA·ECC면 결국 같이 풀린다는 뜻이다.

표준 알고리즘

세계 기준은 미국 NIST(National Institute of Standards and Technology, 국립표준기술연구소)가 2024년 8월에 확정한 3종이다. 한국은 여기에 2025년 1월 확정한 국산 KpqC(Korean Post-Quantum Cryptography) 4종을 더해 7종을 국가 암호모듈 검증(KCMVP, Korea Cryptographic Module Validation Program) 대상으로 정했다.

FIPS(Federal Information Processing Standards)는 미국 연방 정보처리 표준이다. 알고리즘 이름의 KEM은 Key Encapsulation Mechanism(키 캡슐화 메커니즘), DSA는 Digital Signature Algorithm(전자서명 알고리즘)의 약자다.

실무에서는 ML-KEM과 ML-DSA가 기본이다. FN-DSA는 구현이 까다롭고 아직 확정 전이라 운영 계획에 넣기는 이르다.

도식에서 보듯 대부분이 격자(lattice) 계열이다. 국산 키교환 2종도 ML-KEM과 같은 격자 계열이라, “국산 알고리즘을 더해 수학적 위험을 분산한다”는 효과는 키교환 쪽에서는 크지 않다.

흔한 오해 여섯 가지

“양자컴퓨터로 돌리는 암호다”

아니다. PQC는 지금 쓰는 컴퓨터와 스마트폰에서 도는 소프트웨어다. 이름 때문에 양자 장비가 필요하다고 생각하기 쉽지만, 양자컴퓨터에 “견디는” 암호라는 뜻이다.

양자 물리를 직접 쓰는 기술은 따로 있다. QKD(Quantum Key Distribution, 양자키분배)는 광자에 정보를 실어 보내고, 누가 엿들으면 양자 상태가 흐트러져 도청이 드러나는 원리로 키를 나눠 갖는다.

QKD는 상대 인증을 스스로 못 하고, 먼 거리는 키가 평문으로 존재하는 신뢰 노드를 거쳐야 하며, 실제 장비의 검출기를 속이는 구현 공격 사례도 많다. 그래서 미국 NSA(National Security Agency, 국가안보국)와 영국 NCSC(National Cyber Security Centre, 국가사이버보안센터)는 정부·군 용도로 QKD를 권하지 않고, 프랑스·독일·네덜란드·스웨덴 보안기관도 공동 입장문에서 “일부 특수 용도에만 맞다”고 밝혔다.

“양자컴퓨터가 나오면 모든 암호가 끝난다”

깨지는 건 공개키 암호다. 대칭키와 해시는 약해질 뿐 버틴다.

Shor 알고리즘은 공개키의 수학 문제 자체를 풀지만, Grover 알고리즘은 대칭키 전수조사를 빠르게 할 뿐이라 키 길이를 늘리면(AES-256) 충분하다.

“곧(2027년쯤) 다 깨진다”

근거가 약하다. 양자컴퓨터가 실제로 암호를 깨는 날, 이른바 Q-Day는 아직 아무도 모른다.

필요한 자원 추정이 빠르게 줄고 있는 것은 사실이다. 다만 추정이 줄었다는 것과 그런 기계가 존재한다는 것은 다른 이야기다.

“아직 멀었으니 나중에 바꾸면 된다”

이것도 틀렸다. Q-Day가 언제든, 오늘 보낸 데이터는 오늘 녹화될 수 있다. 나중에 풀면 되기 때문이다. 이게 PQC 전환을 지금 서두르는 진짜 이유다.

“브라우저와 서버만 PQC를 쓰면 끝난다”

절반만 맞다. 브라우저와 서버가 하이브리드 TLS를 쓰면 기밀성(키교환)은 지켜지지만, 인증(서명)은 여전히 RSA·ECDSA(Elliptic Curve Digital Signature Algorithm)다. 웹 바깥의 VPN, 사내 통신, 저장 데이터 키, 임베디드 장비는 각 기관이 직접 바꿔야 한다.

“‘PQC 인증’ 받은 제품이면 PQC가 검증된 것이다”

국내 기준으로는 아니다. KCMVP는 아직 PQC 알고리즘을 검증하지 않는다. 2025년 12월 검증 기준 개정으로 PQC를 ‘비보안 구성요소’, 즉 검증 범위 밖의 부품으로 모듈에 넣는 것만 허용됐다. 그래서 이 기준으로 인증받은 하이브리드 모듈도, 국가가 검증한 건 함께 들어간 기존 암호(RSA·ECDSA 등)다. PQC 알고리즘의 국가 검증은 키교환이 2028년 1월에 시작하고, 전자서명은 그 뒤다.

왜 지금 필요한가

양자컴퓨터는 공개키를 노린다

지금 인터넷의 키교환과 서명은 대부분 RSA와 ECC다. 충분히 큰 양자컴퓨터가 Shor 알고리즘을 돌리면 이것들이 한꺼번에 무너진다.

얼마나 큰 양자컴퓨터가 필요한지에 대한 추정은 계속 내려가고 있다. 구글 연구진은 2025년, RSA-2048을 노이즈 큐비트 100만 개 미만으로 일주일 안에 풀 수 있다고 추정했다. 2019년 추정치(2,000만 개)의 20분의 1이다.

녹화했다가 나중에 푼다: HNDL

HNDL(Harvest Now, Decrypt Later)은 “지금 녹화하고 나중에 푼다”는 공격이다. 공격자는 오늘 오가는 암호문을 통째로 저장해 두고, 양자컴퓨터가 생기면 그때 키교환을 깨서 과거 통신을 읽는다.

오늘 안전한 통신이라도 나중에 과거로 소급해서 깨질 수 있다. 그래서 위협이 현실화되기 전, 녹화되는 시점에 이미 PQC가 적용돼 있어야 한다.

2026년 9월에는 AI가 오래된 암호문을 풀었다는 보도가 잇따랐다. GPT-6 아스트라가 108년 동안 풀리지 않던 1918년 독일군 ADFGVX 무선 전문을 해독했고(글로벌이코노믹), 앤트로픽의 페이블 5.1은 1653년 토머스 어쿼트가 남긴 암호 이중시(Cyphral Distich)를 44분 만에 풀었다고 알려졌다(AI타임스). 수십 년 미해독이던 에니그마 메시지 2건도 AI로 풀려 암호학 전문가의 검증을 거쳤다(디지털포커스).

모두 현대 암호가 아닌 고전 암호이고 RSA나 AES를 깬 것도 아니지만, HNDL의 핵심은 그대로 보여 준다. 암호문은 수십, 수백 년 동안 남을 수 있고, 새로운 해독 도구가 나오면 그때 풀린다.

이미 늦었는지 판단하는 식

간단한 판단식이 있다. 데이터를 지켜야 하는 기간 + 전환에 걸리는 기간이 Q-Day까지 남은 기간보다 길면 이미 늦은 것이다.

예를 들어 전환에 6년, 데이터 보존 기간이 10년인데 Q-Day가 12년 뒤에 온다면, 마지막 4년 치 기밀은 지켜지지 않는다. 의료·금융·국방·국가기반시설처럼 10년 넘게 비밀이어야 하는 데이터가 먼저 바꿔야 하는 이유다.

지금 어디까지 왔나

표준: 하이브리드가 기본

지금의 표준 방식은 하이브리드다. 기존 암호(X25519, Curve25519 기반 타원곡선 키교환)와 PQC(ML-KEM)를 함께 써서, 둘 중 하나만 버텨도 안전하게 만든다. PQC는 아직 새 기술이라 혹시 모를 결함에 대비하는 것이다.

웹(TLS)에서는 X25519MLKEM768이 사실상 표준이고, IETF(Internet Engineering Task Force, 인터넷 표준화 기구)가 2026년 8월 표준 문서(RFC, Request for Comments)인 RFC 10024로 정식 표준화했다. 인증서(서명) 쪽 표준은 키교환보다 한 단계 늦다. 인증서 크기와 검증 비용 문제가 남아 있어서다.

웹, 메신저, SSH

이미 바뀐 곳부터 보면 이렇다.

• 브라우저 TLS: 주요 브라우저는 하이브리드 키교환을 기본으로 제안한다. 서버가 지원하면 하이브리드로, 지원하지 않으면 에러 없이 기존 X25519로 연결된다. 서버 쪽을 이미 바꾼 Cloudflare는 2026년 4월 기준 사람이 만든 트래픽의 65% 이상이 PQC로 암호화된다고 밝혔다.
• 메신저: Signal과 iMessage는 이미 PQC로 전환했다.
• SSH(Secure Shell): OpenSSH 최신 버전은 하이브리드가 기본이다. 버전만 올리면 된다.

다만 브라우저 쪽도 빈틈이 있다.

• CDN 뒤 구간: 브라우저와 CDN(Content Delivery Network, 콘텐츠 전송 네트워크) 사이는 PQC여도, CDN과 원 서버 사이는 옛 방식일 수 있다.
• TLS 검사 장비: 회사 방화벽이나 SSL(Secure Sockets Layer, TLS의 옛 이름) 복호화 장비가 하이브리드를 지원하지 않으면 거기서 옛 방식으로 내려간다. 패킷이 커져서 연결이 끊기기도 한다.
• TLS 1.2: 하이브리드는 TLS 1.3에서만 된다.
• 주변 프로토콜: DNSSEC(DNS Security Extensions), OCSP(Online Certificate Status Protocol, 인증서 폐기 확인), 인증서 투명성(CT, Certificate Transparency) 로그 같은 서명 기반 인프라는 그대로다.

인증서가 뒤로 밀린 데는 이유가 있다. 인증서 위조는 양자컴퓨터가 생긴 그 순간에 실시간으로 해야 하는 공격이라, 녹화처럼 과거로 소급되지 않는다. 그래서 세계적으로 “키교환 먼저, 서명은 나중” 순서로 간다.

아직 남은 곳

브라우저 TLS는 구글·애플·Cloudflare 같은 큰 회사가 대신 해 준 가장 쉬운 부분이다. 나머지는 각 기관이 직접 찾아서 바꿔야 한다.

구현할 때 공통으로 부딪히는 문제도 있다.

• 크기: PQC는 키와 서명이 크다. 패킷이 커져서 일부 네트워크 장비와 충돌할 수 있다.
• 사이드채널: 전력·시간 분석에 민감하다. 스마트카드·HSM·IoT 같은 하드웨어 구현은 평가할 항목이 크게 늘어난다.
• 암호 민첩성(crypto agility): 나중에 알고리즘을 쉽게 바꿀 수 있게 설계해야 한다.
• 암호 인벤토리: 우리 시스템 어디에 공개키가 쓰이는지 먼저 찾아야 전환을 시작할 수 있다.

앞으로: 어디부터, 어디가 급한가

가장 급한 곳

급한 정도는 데이터가 얼마나 오래 비밀이어야 하는가와 지금 녹화될 수 있는가로 정해진다. 국정원도 기밀성, 보존기간, 침해 파급력을 기준으로 우선순위를 정했다.

• 오래 비밀이어야 하는 데이터가 오가는 통신: 의료, 금융, 국방, 국가기반시설. 10년 이상 가치가 남는다.
• VPN과 전용회선: 기관 간 트래픽이 모이는 곳이라 녹화 공격의 1순위 표적이다. 장비 교체가 필요해 시간도 오래 걸린다.
• 저장 데이터의 키 관리: 데이터는 AES-256이어도, 그 키를 감싸는 KMS·HSM·백업 키가 RSA·ECC면 결국 같이 풀린다.

바꾸는 순서

순서의 첫 단계는 알고리즘 교체가 아니라 암호 인벤토리, 즉 우리 시스템 어디에 공개키가 쓰이는지 전부 찾는 일이다. 정부 계획이 ‘암호자산 인벤토리’를 첫 과제로 둔 이유다. 그다음이 녹화 공격에 직접 노출되는 통신 구간의 키교환이고, 인증서와 임베디드는 시한과 교체 주기에 맞춰 뒤따른다.

수요기관 입장에서는 2026~2027년에 인벤토리, 전환 계획, 하이브리드 TLS·VPN 우선 적용에 집중하고, 대규모 장비 교체는 2028년 이후 PQC 검증 제품이 나오는 시기에 맞추는 게 현실적이다.

정리

양자컴퓨터가 언제 나올지는 아무도 모르지만, 녹화는 지금도 일어날 수 있다. 바꿔야 하는 건 공개키 암호이고, 대칭키는 AES-256이면 된다.

브라우저 TLS는 큰 회사들이 이미 상당 부분 바꿔 놓았다. 남은 건 각 조직의 VPN, 키 관리, 인증서, 임베디드 장비다. 그 시작은 우리 시스템 어디에 공개키가 쓰이는지 찾는 일이다.