RSA가 무너지는 날을 위한 준비 — 양자내성암호(PQC) 설계와 이행 전략

RSA와 ECC 같은 지금의 공개키 암호는 정수분해·이산로그 문제가 계산적으로 어렵다는 가정 위에 서 있다. 양자컴퓨터가 Shor 알고리즘을 실용 규모로 돌릴 수 있게 되면 이 가정은 한 번에 무너진다. PQC(Post-Quantum Cryptography)는 이 위험에 대응하는 소프트웨어 기반 암호 기술군이다 — 광학 장비로 물리 법칙을 이용하는 QKD(양자암호통신)와 달리, 지금의 컴퓨터에서 그대로 돌아가는 수학적 난이도에 기반한다. 목표는 기밀성·무결성·인증 세 축의 양자 안전성을 확보하는 것이다.

난제와 "아코다격해"

보안 가정으로는 격자 최단벡터·가장가까운벡터 문제, 코드 이론 기반 복원 불가능성, 다변수 다항식의 해 분해 난해성, 해시 충돌저항성, 아이소제니 경로 문제 등이 쓰인다. 이 다섯 계열을 묶어 "아코다격해"라는 기억법으로 부른다.

아이소제니 기반은 타원곡선상 아이소제니 경로 찾기의 난이도를 이용하지만, 일부 체계가 실무에서 취약점을 드러내 일반 배포는 권장되지 않는다. 코드 기반은 오류가 주입된 코드에서 원본을 복원할 수 없다는 성질을 이용하는데, 공개키가 크고 복호 성능은 좋아 배포·키관리 비용이 늘어난다. 다변수(다항식) 기반은 다항식 조합으로 암복호를 구성하지만 서명계 일부에서 취약 사례가 있어 파라미터·구현을 엄격히 관리해야 한다. 격자 기반은 벡터 간 거리·최소정수해 같은 난제를 쓰며 KEM·서명 모두 고성능에 균형이 잡혀 있어 표준 채택의 중심축이다. 해시 기반은 충돌저항성과 2차 예측불가능성을 이용해 서명 크기는 크지만 보수적인 안전성과 단순한 구현이 장점이다.

NIST PQC 표준화는 KEM(CRYSTALS-Kyber)과 서명(CRYSTALS-Dilithium, Falcon, SPHINCS+)을 중심으로 FIPS 제정 단계에 있고, IETF는 TLS/IPsec/MLS에 하이브리드·순수 PQC 프로파일 초안을 진행하고 있다. 상호운용·검증 도구(ACVP, Wycheproof 유사)도 확대되는 중이다 — 다만 이 영역은 계속 바뀌므로 도입 시점에 최신 정보를 다시 확인해야 한다.

표준·상호운용과 이행 전략

알고리즘 포트폴리오는 격자 기반(Kyber/Dilithium), 해시 기반(SPHINCS+), 고정밀 부동소수(Falcon) 등을 조합해 사용처별 성능·크기·감사 용이성을 최적화하는 방향으로 짠다. 프로토콜 통합은 TLS 1.3 하이브리드 KEM, IPsec IKEv2 확장, X.509/COSE/CBOR 인증서 포맷 업데이트로 이뤄지며, 레거시와 PQC를 동시에 운용하는 점진적 이행이 기본이다. 검증·적합성 측면에서는 FIPS·CC 인증 경로를 준비하고 사이드채널·오류주입 대응 구현 가이드를 갖춰야 하며, 지속적인 크립토 애질리티 지원이 필요하다.

이행의 축은 하이브리드 모드다. 고전(ECDH/ECDSA)과 PQC(KEM/서명)를 동시에 써서 후방 호환성과 위험 분산을 함께 얻고, 협상 도중 일부가 실패하면 전체 협상이 중단되는 원자성을 유지한다. 키·서명 크기가 커지는 문제는 MTU·패킷 분할, 캐시·세션 재사용, 전송 재시도 정책 조정으로 대응한다. 운영 정책으로는 파라미터 버전닝, 키 수명·회전 주기 단축, 벤더·라이브러리 상호 검증 절차가 따라붙는다.

⤢✕

입력은 ClientHello(ECDH key_share, PQC 공개키)와 정책·파라미터이고, 처리는 KEM 캡슐화·복호, ECDH 교환, HKDF로 키 파생, 인증 확인이며, 출력은 세션 키 수립이거나 실패 시 원자적 중단과 감사 로그 기록이다.

계열마다 다른 크기, 다른 트레이드오프

분류	대표 예시(최신 정보 확인 필요)	성능	확장성	일관성(표준·호환)	안정성(암호해석)	운영 편의
격자기반	Kyber, Dilithium	KEM/서명 고속, 낮은 지연	서버·클라이언트 모두 양호	NIST FIPS 진행·생태계 풍부	연구 축적, 안전성 높음	키/서명 중간 크기, 배포 용이
해시기반	SPHINCS+	검증 빠름, 서명 느림	대규모 검증 워크로드 적합	표준 확정, 호환 양호	보수적·공학적 신뢰성 높음	서명 크기 큼(수 KB~수십 KB)
코드기반	Classic McEliece 등	복호 빠름, 키 생성 부담	대규모 서버 적합	일부 프로토콜 통합 진행 중	이론적 견고성	공개키 대형(수백 KB), 배포 부담
다변수기반	UOV 계열 등	구현별 편차 큼	제한적	일부 연구·초안 단계	일부 파기 사례로 보수적 접근	선택적/특수 목적 적용
아이소제니	SIKE 등(취약)	상대적으로 느림	제한적	실무 비권장	취약점 공개	사용 지양 권고

구현·버전에 따라 상이할 수 있지만(최신 정보 확인 필요) 참고할 만한 수치는 이렇다. Kyber-512 공개키는 약 0.8KB, 암호문은 약 0.75KB다. Dilithium2 공개키는 약 1.3KB, 서명은 약 2.4KB다. SPHINCS+ 서명은 약 830KB로 크고, Classic McEliece 공개키는 200KB1MB로 계열 중 가장 크다.

어디에 먼저 넣는가

인터넷 보안 통신에서는 TLS 1.3 하이브리드(KEM + ECDH)를 CDN·브라우저 쪽부터 점진적으로 호환시키고, VPN(IPsec IKEv2)이나 SSH KEX도 확장한다. 소프트웨어·펌웨어 서명에서는 부트체인·OTA 업데이트 서명 체계를 PQC로 전환해 부품·공급망 무결성을 강화한다. 데이터 장기보관·문서서명에서는 금융·의료 같은 규제 데이터의 장기 기밀성을 지키고 타임스탬프·공증 시스템에 PQC 서명을 도입한다. 메시징·이메일에서는 E2E 메시징의 KEM 기반 세션키 합의, PGP/SMIME의 PQC-혼합 서명이 대상이다.

도입 절차는 여섯 단계로 밟는다. 알고리즘·키 길이·프로토콜·수명 주기를 매핑하고 "지금 수집, 나중 복호" 위험이 있는 장기 기밀 대상을 식별하는 암호 자산 인벤토리, 해독 대상의 가치·보유 기간·접근 경로를 평가하고 브라우저·OS·하드웨어 등 외부 의존 호환성을 검토하는 위험 분석, 하이브리드 모드를 기본으로 하고 순수 PQC는 영역을 제한해 도입하며 크립토 애질리티(플래그·정책·버전닝·롤백)를 내장하는 아키텍처 설계, MTU·핸드셰이크 크기 영향과 지연·CPU를 분석하고 Decap 실패·파라미터 불일치·시간측채널 같은 장애를 주입해보는 파일럿·성능 검증, 프런트→백엔드→내부 서비스 순으로 단계 배포하고 KMS/HSM을 업데이트하는 운영 전환, 마지막으로 취약점 공지·표준 변경을 추적하고 파라미터 회전을 자동화하며 FIPS/CC 적합성을 유지하는 모니터링·거버넌스다. 장애 대응 원칙은 핸드셰이크의 원자성을 유지하고, 실패 시 즉시 중단한 뒤 레거시로 축소 폴백하며 감사 로그를 남기는 것이다.

직접 돌려보는 KEM 합의

전제조건은 Python 3.10+와 liboqs 빌드 또는 pyoqs 패키지다(환경별 설치 방법이 달라 최신 문서를 확인해야 한다).

# pip install oqs  (환경에 따라 수동 빌드 필요)
import oqs

kem_name = "Kyber512"  # 최신 명칭/가용 목록은 oqs.get_enabled_kem_mechanisms()로 확인
with oqs.KeyEncapsulation(kem_name) as server:
    public_key = server.generate_keypair()

    with oqs.KeyEncapsulation(kem_name) as client:
        ct, client_ss = client.encap_secret(public_key)

    server_ss = server.decap_secret(ct)

assert client_ss == server_ss, "공유 비밀 불일치"
print(f"KEM 합의 완료, 공유 비밀 길이: {len(client_ss)} 바이트")

실제 서비스에 쓰려면 여기에 인증(서명)을 결합하고, 난수·시간측채널 대응과 파라미터 정책 관리를 더해야 한다.

전환이 남기는 숫자

전환 자체가 만드는 부담은 생각보다 크지 않다. TLS 핸드셰이크 페이로드 증가는 수 KB 수준이고 왕복 지연 영향도 수 ms 내외에 그친다(범위값, 환경 의존, 최신 정보 확인 필요). 서명 검증 처리량은 Dilithium 계열 기준 서버급에서 수만 TPS까지 달성 가능하며, 저장·전송 오버헤드는 SPHINCS+ 같은 서명형을 쓸 때 문서당 8~30KB가 늘어나는 정도다. 그 대가로 얻는 것은 장기 기밀 데이터의 양자 위협 저감, 표준 기반 상호운용성, 레거시 의존 최소화와 암호 민첩성이다. 격자기반을 표준 채택의 중심에 두고, 해시기반을 보수적 백업으로, 코드기반을 특수 용도로 병행하는 포트폴리오가 지금 시점에서 현실적인 조합이다.