드림시큐리티

양자컴퓨팅이 '창'이라면, 이에 대응하는 양자내성암호(Post-Quantum Cryptography, PQC)는 '방패'에 비유할 수 있다. 양자컴퓨터가 현재의 암호 알고리즘(특히 RSA 또는 ECC)을 쉽게 해독할 수 있는 잠재력을 가진 반면, PQC는 양자컴퓨터의 공격에 대항할 수 있도록 설계된 암호 알고리즘이다.

양자내성암호는 특정 수학적 문제를 기반으로 하며, 대표적인 예로 격자 기반 암호(Lattice-based cryptography), 코드 기반 암호(Code-based cryptography), 다변수 다항식 기반 암호(Multivariate polynomial cryptography), 해시 기반 암호(Hash-based cryptography) 등이 있다. 이들은 현재 양자컴퓨터의 알고리즘으로는 풀기 어렵다고 평가된다. 양자컴퓨터의 알고리즘은 양자컴퓨터의 프로그램이라고 생각하면 이해하기 쉽다.

또한 양자암호통신(양자키분배, Quantum Key Distribution, QKD)도 양자컴퓨팅에 대비하기 위한 하나의 방패로 여겨질 수 있다. QKD는 양자 역학의 원리를 이용해 전송되는 데이터의 도청을 무력화하는 기술로, 해커가 양자암호통신으로 전송되는 키를 도청하려 시도하면 그 즉시 이를 탐지해 해킹을 무력화하고 보안성을 강화한다.

따라서 종합해보면 양자컴퓨팅의 위협에 대응하기 위한 방패는 아래 두 가지 기술이라고 할 수 있다.

• 양자내성암호(PQC)
• 양자키분배(QKD)

본 칼럼에서는 이 중 ‘양자내성암호’의 최신 기술 동향을 살펴보고자 한다.

1. 양자컴퓨터의 발전과 보안 위협

양자컴퓨터는 양자역학의 원리를 통해 기존 컴퓨터와는 비교할 수 없는 강력한 연산 능력을 갖추고 있다. 양자 중첩(Superposition)과 양자 얽힘(Entanglement)을 활용하여 양자컴퓨터는 여러 계산을 동시에 수행할 수 있다. 이 기술은 기존 공개키 암호화 방식의 근본적인 취약점을 유발하여, 새로운 보안 기술의 필요성이 대두되고 있다. 양자컴퓨팅에서 활용되는 대표적인 알고리즘을 알아보자.

1.1 Grover 알고리즘과 대칭키 암호화에 미치는 영향

Grover 알고리즘은 양자컴퓨터가 데이터베이스 내에서 특정 항목을 찾는 데 필요한 시간 복잡도를 제곱근 수준으로 낮출 수 있는 양자 검색 알고리즘이다. 이를 활용하면 기존 컴퓨터를 사용한 검색 속도가 양자 컴퓨터에서는 절반 이하로 줄어들게 된다. 이 알고리즘은 기존의 대칭키 암호화 방식, 예를 들어 ARIA, AES와 같은 대칭키 알고리즘과 SHA2, SHA3와 같은 해시 알고리즘에 영향을 미친다.

• 대칭키 크기 및 해시 출력의 변화: Grover 알고리즘은 양자컴퓨터가 특정 암호화 키를 찾아내는 속도를 높이며, 대칭키 암호화의 보안성을 절반으로 감소하게 할 수 있다. 예를 들어, 기존에는 128비트 키가 충분히 안전하다고 여겨졌지만, Grover 알고리즘을 통해 양자컴퓨터를 이용한 공격이 가능해지면서 키 용량을 256비트로 확장할 필요가 생겼다. 해시 알고리즘의 출력 길이 또한 기존 256비트에서 512비트로 확장되고 있다.
• 실제 보안에 미치는 영향: Grover 알고리즘이 적용된 양자컴퓨터에 대한 대응은 비교적 쉽게 접근할 수 있다. 양자컴퓨터의 공격 속도가 빨라짐에 따라 충분한 안전성을 확보하기 위해 키 크기 또는 출력 길이를 늘리는 보완적인 대책이 필요하다.

1.2 Shor 알고리즘과 공개키 암호화에 미치는 영향

Shor 알고리즘은 양자컴퓨터가 RSA와 ECC 등 공개키 암호화 알고리즘을 해독할 수 있도록 한다. 이 알고리즘은 양자컴퓨터가 소인수분해와 이산대수 문제를 빠르게 해결할 수 있게 함으로써 공개키 기반 암호화의 근본적 위협 요소로 작용한다.

• RSA와 ECC의 취약성: Shor 알고리즘으로 인해 공개키 암호화 기술은 근본적인 보안 위협을 맞게 된다. 이에 따라 더 안전한 대체 암호화 방식인 양자내성암호의 도입이 필수적이다.
• 실제 보안에 미치는 영향: 양자컴퓨터의 연구가 빠르게 진전됨에 따라 Shor 알고리즘이 적용된 고성능 양자컴퓨터가 등장할 가능성이 매우 높아지고 있다. 이 경우 기존 공개키 암호화 방식에 즉각적인 위협이 된다. 

Peter Shor 교수 (사진 출처: Peter Shor 교수 웹페이지)

피터 쇼어(Peter Shor)는 양자 계산과 관련한 연구로 유명한 미국의 컴퓨터 이론 과학자로, 특히 쇼어 알고리즘을 고안한 것으로 잘 알려져 있다. 쇼어 알고리즘은 고전적 컴퓨터에서 실행되는 가장 잘 알려진 알고리즘보다 지수적으로 빠르게 이산대수와 인수분해 문제를 해결하는 양자 알고리즘이다. 쇼어 교수는 2003년부터 매사추세츠 공과대학 (MIT)에서 응용 수학 교수로 재직하고 있다.

2. 양자내성암호 기술 개발 현황

현재 국제 표준화 기관과 보안 솔루션 기업들은 PQC 개발에 집중하고 있다. NIST(미국 국립표준기술연구소)는 2017년부터 양자내성암호 표준 후보군을 선정하는 작업을 진행하여 2024년 8월 3개의 알고리즘에 대한 표준 작성을 완료하였다. 한국의 KpqC 연구단도 이 흐름에 따라 한국형 PQC 알고리즘을 선정하고 있으며, 표준화 작업을 추진할 예정이다.

2.1 양자내성암호의 개념과 기술 원리

양자내성암호의 가장 중요한 특징은 양자컴퓨터의 공격에도 안전성을 유지한다는 점이다. 이를 위해 PQC는 양자컴퓨터가 풀기 어려운 격자 문제, 코드 기반 문제, 다변수 다항식 문제, 해시 기반 문제 등을 활용한다. 현재 연구가 진행중인 PQC 알고리즘에는 다음과 같은 주요 기법이 포함된다:

• 격자 기반 암호화(Lattice-based Cryptography): 복잡한 격자 구조를 활용하여 수많은 계산을 동시에 풀지 않으면 접근이 불가능하도록 설계된 암호화 방식이다. 특히 SVP(Shortest Vector Problem) 및 LWE(Learning With Errors)와 같은 문제가 격자 기반 암호의 기초가 되며, 양자컴퓨터가 풀기 매우 어려운 편이다.
• 코드 기반 암호화(Code-based Cryptography): 오류 정정 코드를 기반으로 하는 암호화 기법으로 오랫동안 연구되어 온 알고리즘이다. 해당 알고리즘 또한 오류 정정 코드로 인하여 양자컴퓨터가 해독하기 어려운 것으로 알려져 있다.
• 다변수 다항식 기반 암호화(Multivariate Polynomial Cryptography): 여러 개의 변수를 가진 복잡한 다항식을 이용하여 양자컴퓨터가 문제를 풀기 어렵게 만드는 방식이다.
• 해시 기반 암호화(Hash-based Cryptography): 데이터를 해싱하여 생성된 값을 암호화에 사용하며, 양자컴퓨터가 예측 불가능한 해시 값을 단시간 내에 풀어내지 못하도록 설계되어 있다. 해시 기반 암호화 방식은 코드 서명 등에 가장 먼저 사용되었다.

2.2 격자 기반 암호화의 원리

격자(Lattice)란, 정수들의 집합이 특정 규칙에 따라 배열된 구조를 의미한다. 격자 기반 암호화에서는 이 격자 위에서 계산해야 하는 어려운 특성을 이용하여 암호화를 수행한다. 격자는 보통 고차원 벡터 공간에서 정의되며, 격자 기반 문제는 근사화 문제 또는 회전 변환 문제 등 컴퓨터로 계산하기 어려운 문제를 포함한다. 이 난제들은 기존 컴퓨터와 양자 컴퓨터 모두에서 풀기 어렵기 때문에, 격자 기반 암호는 매우 안전하다고 평가된다.

2차원 좌표 공간의 격자(Lattice) (사진 출처: 위키피디아 “Lattice(group)”)

2.2.1 격자 기반 암호화의 주요 알고리즘

격자 기반 암호 알고리즘은 오래된 역사를 가진 공개키 알고리즘 중 하나다. 이와 관련된 주요 알고리즘의 종류를 알아보자.

• NTRU: 근사 LWE 문제를 기반으로 하며, 양자 공격에 대비하기 위한 강한 내성을 제공한다.
• FrodoKEM: LWE 문제를 기반으로 하는 양자 내성 키 교환 방법 중 하나다. 이 알고리즘은 무작위화된 LWE 문제를 기반으로 양자 공격에 대비할 수 있도록 설계되었다. 또 FrodoKEM은 유럽에서 표준 알고리즘으로 선호되고 있다.
• Kyber: NIST의 양자내성암호 표준으로 선정된 KEM 알고리즘으로, LWE 문제를 기반으로 하는 키 교환 암호화 방식이다. Kyber는 양자 공격에 매우 강력한 내성을 제공하는 암호 알고리즘으로, 다른 격자 기반 암호 시스템에 비해 효율성과 보안성이 뛰어나다.
• Dilithium: 마찬가지로 NIST의 양자내성암호 표준으로 선정된 전자서명 알고리즘으로, LWE 문제를 기반으로 하는 전자서명 방식이다. Dilithium은 Kyber와 마찬가지로 양자 공격에 매우 강력한 내성을 가지는 암호 알고리즘이다. 다른 격자 기반 전자서명 시스템에 비해 효율성과 보안성이 뛰어나다.

2.2.2 격자 기반 암호화의 장점

• 키 길이와 효율성: 격자 기반 암호화 기술은 대체로 효율적인 연산을 가능하게 하며, 암호화 및 복호화 작업을 빠른 속도로 수행할 수 있다. 또한 키 길이도 상대적으로 작게 유지할 수 있어 실용적인 측면에서 유리하다.

2.2.3 격자 기반 암호화의 단점

• 알고리즘 복잡성: 격자 기반 암호화의 알고리즘은 수학적으로 매우 복잡하여 이를 이해하고 구현하기 위한 난도가 높다. 또한 안전한 파라미터의 선택과 정의가 필요하며, 구현 시 최적화가 중요한 이슈다.

2.3 코드 기반 암호화의 원리

코드 기반 암호화는 메시지에 임의의 오류를 추가하여, 수신자가 추가된 오류를 제거해야만 원래 메시지를 복원할 수 있도록 하는 방식이다. 이를 위해 에러 정정 코드(error-correcting codes)가 사용된다. 이 과정에서 메시지는 코드워드(codeword)로 변환되고, 암호문을 해독하려면 코드워드에 추가된 오류를 찾아내는 방식을 통해 원본을 복원해야 한다. 양자컴퓨터가 이를 풀기 위해서는 매우 많은 계산 자원이 필요하므로 안전성을 확보할 수 있다.

2.3.1 코드 기반 암호화의 주요 알고리즘

• McEliece: 코드 기반 암호화의 대표적인 알고리즘으로, 1978년 로버트 매켈리스(Robert McEliece) 교수가 개발하였다. 이 알고리즘은 Goppa 코드라는 특수한 오류 정정 코드를 사용하여 메시지를 암호화한다. McEliece 암호는 기존의 공통키 기반 암호보다 훨씬 큰 키를 사용하지만, 양자 알고리즘으로 풀기 어려워 양자 안전성이 높다는 장점이 있다.
• PALOMA: KpqC 공모전에 제출되었으며, 이진 분리가 가능한 Goppa 코드 기반의 KEM 알고리즘이다. PALOMA의 기반 문제로 사용된 ‘신드룸 복호화 문제(SDP)’는 McEliece 암호에도 사용되었으며, 오랫동안 안전성이 연구되어 왔다. 

PALOMA Algorithm Symbol (사진 출처: 국민대학교 미래암호 설계 연구실 웹페이지)

2.3.2 코드 기반 암호의 장점

• 작은 암호문: 코드 기반 암호화는 작은 암호문 크기를 가진다.
• 복호화 속도: 복호화 과정이 상대적으로 빠르며, 특히 특정 환경에서는 매우 빠른 복호화 속도를 제공한다. McEliece 알고리즘의 경우 RSA 알고리즘 보다 빠르게 동작한다고 알려져 있다.

2.3.3 코드 기반 암호의 단점

• 키 길이: 일반적으로 코드 기반 암호화 알고리즘은 격자 기반 암호화 알고리즘보다 큰 키를 필요로 한다. 이는 키를 저장하거나 전송하는 시점에 부담이 될 수 있다.

2.4 다변수 기반 암호화의 원리

다변수 기반 암호화는 다변수 이차식 시스템을 기반으로 하며, 다수의 변수로 구성된 다항식의 집합을 암호화에 이용한다. 이러한 시스템은 다변수 다항식 문제(MVP) 또는 다변수 문제(Multiplicative Multivariate Problem)의 해를 구하기 어려운 점을 활용해 보안을 구현한다.

2.4.1 다변수 기반 암호화의 주요 알고리즘

다변수 기반 암호화는 공개키 암호화 시스템, 디지털 서명, 서브키 생성 등에 사용될 수 있다. 대표적인 다변수 기반 암호화 알고리즘은 다음과 같다.

• Rainbow: Rainbow는 다변수 기반 디지털 서명 알고리즘으로, 다변수 다항식 문제를 해결하는 과정의 어려움에 기초한 서명 생성 및 검증 과정을 제시한다. Rainbow 서명 알고리즘은 양자 컴퓨터가 풀기 매우 어려운 문제에 기반하므로, 양자내성암호의 대표적인 예로 주목받고 있다.
• Unbalanced Oil and Vinegar (UOV): UOV는 비균형적인 오일과 식초 문제를 기반으로 하는 암호 시스템이다. 이 시스템은 다변수 다항식의 난이도를 이용하여 보안을 구현하며, 특히 서명 및 인증 분야에서 강력한 보안을 제공한다.
• MQ-Sign (Multivariate Quadratic Sign): MQ-Sign은 이차 다항식 기반의 다변수 암호화 알고리즘으로, 빠른 서명 생성을 수행하는 국산 PQC 알고리즘이다.

2.4.2 다변수 기반 암호화의 장점

• 빠른 연산: 다변수 기반 암호화는 상대적으로 빠른 암호화 및 복호화 속도를 제공할 수 있으며, 특히 디지털 서명과 같은 응용 분야에서 뛰어난 성능을 발휘한다.
• 간결한 개인키 크기: 격자 기반 암호화에 비해 다변수 기반 암호화 기술은 상대적으로 작은 개인 키 크기를 유지할 수 있어 실용적인 보안 솔루션으로 평가된다.

2.4.3 다변수 기반 암호화의 단점

• 알고리즘 복잡성: 다변수 기반 암호화 알고리즘은 수학적으로 매우 복잡하다. 따라서 다변수 다항식 시스템을 이해하기 위해서는 상당한 수학적 배경이 필요하다. 이로 인해 구현이 어려울 수 있으며, 구현 시 효율성 또한 중요한 고려사항이 된다.
• 키 길이: 일부 다변수 기반 암호화 알고리즘은 다른 PQC 알고리즘과 비교하여 매우 큰 키가 필요하다. 이는 실제 시스템에서 적용하는 과정에서 많은 부담을 줄 수 있다.

2.5 해시 기반 암호화의 원리

해시 함수는 입력값을 해시하여 얻은 출력값으로부터 원래의 입력값을 복원하는 것이 매우 어려운 알고리즘이다. 해시 기반 암호화 시스템은 다음과 같은 특성을 지닌, 암호학적으로 안전한 해시 함수와 이진트리를 기반으로 한다:

• 단방향성(Pre-image resistance): 주어진 해시값에서 원본 데이터를 복원하는 것이 불가능하거나 매우 어려운 성질이다.
• 선형 충돌 저항(Collision resistance): 두 개의 서로 다른 입력값이 동일한 해시값을 생성할 확률이 매우 낮은 특성이다.

2.5.1 해시 기반 암호화의 주요 알고리즘

• XMSS (eXtended Merkle Signature Scheme): XMSS는 해시 기반의 양자내성암호에 속한다. 이 시스템은 서명 생성 및 검증 과정에서 해시 함수를 사용하며, 양자컴퓨터에 대한 내성이 뛰어난 디지털 서명 방식으로 평가받고 있다. XMSS는 해시 트리 구조를 사용하여 서명 과정을 안전하고 효율적으로 처리할 수 있다.
• SPHINCS+: NIST의 양자내성암호 표준으로 선정된 서명 알고리즘으로, 다층 해시 트리를 사용하여 디지털 서명 등 작업을 처리한다. 이 알고리즘은 해시 함수의 강력한 특성을 기반으로 서명 생성 및 검증을 수행하며, 양자 내성을 가지도록 설계되었다. 

SPINCS+ 이진 해시 트리 구조 (사진 출처: SPHINCS: practical stateless hash-based signatures)

2.5.2 해시 기반 암호화의 장점

• 효율성: 해시 기반 암호화 알고리즘은 암호화 및 복호화 연산이 상대적으로 간단하고 빠르기 때문에 실시간으로 대량의 데이터를 처리해야 하는 시스템에 적합하다. 특히, SPHINCS+는 비교적 짧은 서명 크기를 제공하며, 효율성을 고려한 설계를 통해 뛰어난 성능을 발휘한다.
• 구현의 용이성: 해시 기반 암호화는 대부분 이미 잘 알려진 해시 함수(예: SHA-256, SHA-3 등)를 활용하므로, 기존의 알고리즘을 변형하여 사용하는 것이 상대적으로 용이하다. 또한, 기존 해시 함수를 그대로 활용할 수 있어 암호화 알고리즘을 구현하기 위한 기술적 장벽이 낮다.

2.5.3 해시 기반 암호화의 단점

• 키 길이: 해시 기반 서명 시스템은 상대적으로 큰 키 길이를 필요로 할 수 있다. 예를 들어 XMSS와 SPHINCS+는 서명 생성 시 매우 큰 키가 사용된다. 이로 인해 저장 공간과 전송 비용이 늘어날 수 있다.
• 메모리 요구 사항: 해시 기반 서명 알고리즘은 다층 해시 트리와 같은 복잡한 구조를 사용하므로 메모리 요구 사항이 상대적으로 높을 수 있다. 특히 대용량 데이터를 처리하는 시스템에서는 메모리 효율성 문제가 발생할 수 있다.

3. 드림시큐리티의 양자보안 기술

양자내성암호 기술의 발전에 따라, NIST 표준 양자내성암호와 KpqC에서 추진하는 후보군 중 몇 가지 알고리즘을 살펴보았다. 앞서 소개한 PQC 알고리즘은 드림시큐리티의 솔루션과 서비스에도 적용되고 있다.

예를 들어 암호모듈과 PKI 라이브러리, CA 시스템, SSO 및 EAM 시스템, DB 암호화 시스템, 키관리 KMS 시스템, 전자문서, 인증서비스와 양자암호통신을 위한 양자키관리 등에서 PQC 알고리즘이 사용된다. 드림시큐리티의 양자보안 기술을 사용하면 해커보다 한발 앞서 양자컴퓨터에 대비하고, 강력한 보안 환경을 구축할 수 있다.