[ 암호학 ] 양자내성암호 (PQC, Post-Quantum Cryptography)

최근에 자료를 찾아보다가 양자내성암호(이하 PQC)라는 개념을 알게 되었다. 양자컴퓨팅 기술이 빠르게 발전하면서, 언젠가 양자컴퓨터가 완성되면 기존의 RSA나 ECC 같은 암호체계가 무력화될 수 있다는 우려가 커지고 있다. 특히 ‘HNDL’ 공격처럼 지금 데이터를 수집해 두었다가 나중에 해독하는 방식이 등장하면서, 전 세계 보안 기업과 기관들이 양자 이후(Post-Quantum) 시대를 대비하기 위한 PQC 연구와 표준화 작업에 속도를 내고 있다.

양자컴퓨터와 기존의 암호체계

양자컴퓨터는 기존의 0과 1로 이루어진 비트 대신에 양자비트(qubit)를 사용하여, 중첩이나 얽힘 같은 양자역학적 성질을 활용한다. 이러한 특성 덕에 양자컴퓨터는 일부 문제에 있어 기존 컴퓨터보다 훨씬 빠르게 복잡한 계산 문제를 풀어낼 수 있다. 모든 문제에 그러한 것은 아니고, 양자컴퓨터의 계산 방식상 기존 컴퓨터보다 특화되어 수만 배 빠르게 해결하는 특정한 문제 종류들이 있다고 한다.

기존 암호 체계 RSA, ECC

현재 널리 쓰이는 공개키 암호(RSA, ECC 등)는 정수분해나 이산대수 문제와 같은 대수적 난제에 기반을 두고 있다.

RSA는 큰 수를 소인수분해하는 것은 매우 어렵다 라는 원리에 기반한 암호 알고리즘이다. ECC는 작은 키로 동일한 보안 수준을 보장하는 알고리즘으로 타원곡선 상의 한 점 P에 대하여 개인키, P보다 작은 소수 k를 곱한 값(공개키) Q=kP를 계산하는 것은 쉽지만, P와 Q 값을 통해 k값을 구하기 어려운 점에 기반한다. 아래는 ECC 알고리즘의 이해를 돕기 위한 그림이다.

1. 생성 포인트 시작해서 타원곡선의 접선을 그음
2. 타원곡선과 만나는 점을 찍음
3. 2번에서의 점과 대칭인 점이 목표점

-> 위의 과정은 반복하기 쉬우나, 3번 목표점 1번의 생성점을 찾긴 매우 어려움

양자컴퓨터의 쇼어 알고리즘

기존의 RSA나 ECC와 같은 암호 알고리즘은 기존의 컴퓨터로는 필요한 계산량이 기하급수적으로 증가하여 사실상 해독이 불가능하여 다양한 인증, 서명, 로그인 단계에서 보안 알고리즘으로 채택되어 왔다.

문제가 되는 부분은 양자컴퓨터의 쇼어 알고리즘을 이용해 현재 흔히 쓰이고 있는 암호 알고리즘을 모두 무력화할 수 있다는 것이다. 실제로 최근 양자컴퓨팅 기술이 발전하면서 암호화 트래픽이 급증하고 공격 또한 정교해지고 있다. 암호화 트래픽은 보안을 위해서 데이터를 암호화하여 전송하는 네트워크 통신으로 최근 전체 트래픽의 대부분을 차지하고 있는데, 이렇게 되면 지금 우리가 신뢰하고 있는 보안 구조가 양자컴퓨터 앞에서는 무용지물이 될 수도 있다는 말이다.

보안 위협의 현실화, HDNL

Harvest Now, Decrypt Later 데이터는 지금 수집, 해독은 나중에!

최근 양자컴퓨터 위협이 현실적인 이유 중 하나는 바로 HNDL 공격(수확 후 해독, Harvest Now Decrypt Later) 개념 때문이다. 이는 지금은 해독할 수 없더라도, 나중에 양자컴퓨터가 등장하면 해독할 수 있다는 전제하에 암호화된 데이터를 미리 수집(“Harvest Now”)해두었다가, 양자컴퓨터가 상용화되는 시점에 해독(“Decrypt Later”)하는 방식이다.

즉, 지금 전송 중인 민감한 데이터(금융거래, 의료정보, 군사통신 등)가 나중에 복호화될 가능성이 있다는 뜻이다. 특히 정부기관, 은행, 대기업처럼 규제에 의해서 수명주기가 길고 민감한 데이터를 다루는 곳은 이 공격에 더욱 취약하다. 예를 들어, 오늘 암호화된 통신이 양자컴퓨터 등장 이후 해독된다면, 과거의 모든 기밀 데이터가 순식간에 노출될 수도 있다.

이 때문에 보안 업계에서는 양자컴퓨팅 기술이 완성되기 전부터 PQC로 전환해야 한다는 인식이 확산되고 있다.

양자내성암호(PQC) 개념

양자내성암호(PQC)는 양자 컴퓨터의 공격에도 안전하다고 여겨지는 암호 알고리즘이다. 이론에 따르면 양자컴퓨터도 푸는 데 수십억 년이 걸린다고 한다. 어떤 알고리즘이길래 안전한 걸까?

기존 암호화 알고리즘이 소인수분해나 이산로그에 기반했다면, PQC는 양자컴퓨터로도 풀기 어려운 수학 알고리즘을 이용한다.

PQC의 유형 및 원리

1. 격자 기반 알고리즘
   • 가장 활발히 연구되는 방식으로, 격자 위에서 계산하는 문제의 어려움에 기반함
   • NP-hard라는 수학 문제에 안정성 기반을 두고 있기에 안전성에 강점이 있으며 계산 효율성이 높음
   • Kyber, Dilithium

     

   문제 이름	설명
   SVP (Shortest Vector Problem)	격자 안에서 ‘가장 짧은 벡터’를 찾는 문제. 차원이 커질수록 계산이 폭발적으로 어려워짐.
   CVP (Closest Vector Problem)	임의의 점이 주어졌을 때, 격자 내에서 그 점과 가장 가까운 격자 벡터를 찾는 문제.
   LWE (Learning With Errors)	선형 방정식에 ‘작은 오차(error)’를 섞어 만든 값에서 원래의 해를 추정하는 문제. 오류가 조금만 있어도 원래 해를 찾기가 극도로 어렵다.

2. 해시 기반 알고리즘
   • 해시함수의 안전성에 기반하는 전자 서명 시스템
   • 해시함수 = 임의의 길이를 가진 입력 데이터 -> 고정된 길이의 출력 값 hash value
   • 양자컴퓨팅 환경에서도 해시함수의 출력의 길이를 늘여서 안전성 보장 가능하지만 큰 서명 사이즈를 가진다는 단점이 있음.

   

3. 다변수 기반 알고리즘
   • 유한 field 위에서 계산하는 다변수함수 문제의 어려움에 기반하는 암호 시스템으로 주로 이차함수를 사용
   • key 사이즈가 크기 때문에 주로 서명 기법에 사용됨
   • 암호화와 복호화가 다항식의 계산이기 때문에 전력 분석의 부채널 공격에 강하여 안전하다는 장점이 있음
4. 코드 기반 알고리즘
   • 일반적인 선형 코드를 디코딩하는 어려움에 기반하는 암호 시스템
   • 행렬 연산이기 때문에 연산 속도가 빠르다는 장점이 있음
   • 복호화가 암호화보다 연산 속도가 느리고 key 크기가 크다는 단점이 있음
   • 의도적으로 오류를 메시지에 주입해서 오류를 알고 있는 사용자만 메시지를 복원할 수 있도록 만듦

   

PQC 표준화 현황

미국 NIST(국립표준기술연구소)는 2016년부터 PQC 표준화를 추진해 왔고, 2022년 7월 1차 표준 후보로 다음 알고리즘들을 발표했다.

PQC 도입 시 고려해야 할 점

1. 호환성과 성능 문제
   • 운영·보안 테스트
   • PQC 알고리즘은 RSA/ECC 알고리즘보다 key의 크기와 연산량이 크기 때문에 웹·모바일 등 환경별, 이기종별 최적화가 필요하다.
   • 한 번 시스템을 구축하면 암호 알고리즘을 쉽게 구축하기 어렵기 때문에, 향후 새로운 표준이 등장하더라도 쉽게 교체할 수 있는 구조로 순차적으로 변경하는 것이 필요하다.
2. 도입 우선순위 설정
   • 네트워크별 (외부망/폐쇄망/백오피스/채널계/코어계 등) 통신 목록 인벤토리화
   • 데이터 민감도 & 보존기간에 따라 데이터 분류
   • 코드·라이브러리 분류
   • 파일럿 프로젝트 순차 도입
   • 하이브리드 PQC 고려
3. 키 관리 시스템 업데이트
   • KMS(Key Management System): 암호키 생성·저장·배포·폐기까지 전 주기를 관리하는 소프트웨어 중심의 키 관리 플랫폼
     • 누가, 언제, 어떤 키를 사용했는지 접근 이력 로깅
     • 키 자동으로 교체·폐기
     • PQC키는 기존 RSA보다 길고 구조도 다르기 때문에, 이를 지원하도록 업데이트해야 함
   • HSM(Hardware Security Module): 하드웨어 장치로 된 키 금고
     • 암호 연산(RSA, ECC, PQC 서명 등)을 내부에서 직접 수행
     • PQC 알고리즘 연산을 지원하도록 HSM 업데이트해야 함

참고

• 나무위키 - 양자컴퓨터
• PQC, 양자컴퓨터도 풀기 어려운 암호가 있다?!