본 카테고리의 글은 양자내성암호의 필요성부터 개념, 표준 알고리즘의 규격, 소스코드까지 분석할 계획입니다. 양자내성암호에 관심있는 분들에게 도움이 되는 글들이었으면 좋겠습니다.
양자내성암호 시리즈
- INTRODUCTION - 양자내성암호의 필요성과 개념
- 양자내성암호 표준화 동향
- 격자 기반 문제
- ML-KEM의 규격
- ML-KEM의 구현
- ML-DSA의 규격
- ML-DSA의 구현
INTRO
양자내성암호는 암호를 사용하는 분야에서 일하시는 분이라면 한번쯤은 들어보셨을 단어입니다.
POST-QUANTUM CRYPTOGRAPHY
양자내성암호란, 양자 컴퓨팅 환경에서도 내성을 가지는 암호를 의미합니다.
양자내성암호의 등장 배경을 알려면, 현재의 공개키 암호 체계부터 조금 공부해야 합니다. 차근차근 설명해보겠습니다.
현재의 공개키 암호
다음은 KCMVP 검증 대상 암호 알고리즘 목록입니다.
공개키 암호로 RSAES, 전자서명으로 RSAPSS, KCDSA, EC-KCDSA, ECDSA가 존재합니다. 또한 키 설정 알고리즘으로 DH, ECDH도 존재합니다.
이 암호들의 공통점이 있습니다. 바로 인수분해와 이산대수 기반의 공개키 암호라는 것입니다.
RSAES와 RSAPSS의 프리미티브가 되는 RSA의 안전성은 인수분해 문제에 기반하며, 이는 두 소수 p, q의 곱 N만이 주어졌을 때 p와 q를 찾는 것이 어렵다는 것에 기반합니다.
Shor의 알고리즘
SHOR'S ALGORITHM
Shor의 알고리즘은 양자 알고리즘으로, 정수의 소인수분해 문제를 효율적으로 해결할 수 있습니다.
다시 말해, RSA의 기반이 되는 인수분해 문제를 충분한 규모의 양자 컴퓨터가 존재한다면 Shor의 알고리즘을 이용하여 해결할 수 있다는 의미입니다.
두번째 문단 첫 줄을 보면, 인수분해 문제를 푸는 것과 이산대수 문제를 푸는 것, period-finding 문제를 푸는 것이 유사한 알고리즘으로 해결될 수 있다는 이야기도 있습니다.
현대의 공개키 암호 체계는 인수분해와 이산대수 문제를 기반으로 상당 부분 설계되어 있습니다. 따라서 충분한 규모의 양자 컴퓨터가 등장한다면 Shor의 알고리즘으로 기존 공개키 암호 체계가 큰 영향을 받을 수 있습니다.
이러한 상황 때문에 양자 컴퓨터 환경에서도 안전할 것으로 기대되는 암호, 즉 양자내성암호(Post-Quantum Cryptography)가 연구되고 있습니다.
양자내성암호 기반 문제
양자내성암호는 인수분해와 이산대수 문제와는 다른 수학적 난제를 기반으로 설계됩니다. 대표적인 기반 문제들은 다음과 같습니다.
- 격자 기반 (Lattice-based)
- 부호 기반 (Code-based)
- 다변수 기반 (Multivariate-based)
- 해시 기반 (Hash-based)
- 아이소제니 기반 (Isogeny-based)
- 대칭키 기반 (Symmetric-key-based)
이러한 기반 문제들은 어떻게 양자내성암호의 재료로 선정된 것일까요?
알아두어야 할 점
이러한 기반 문제들이 양자 컴퓨터에 영원히 안전하다고 단정할 수 있는 것은 아닙니다.
현재 알려진 고전 및 양자 알고리즘으로 효율적인 해결 방법이 알려져 있지 않기 때문에, 양자 컴퓨터 환경에서도 안전할 것으로 '기대'하는 기반 문제입니다.
실제로 격자 문제를 효율적으로 해결하기 위한 새로운 양자 알고리즘에 대한 연구 역시 지속되고 있습니다. 과거 격자 문제를 깨는 새로운 양자 알고리즘을 주장한 연구가 발표된 사례도 있었지만, 이후 알고리즘 과정에서 문제가 발견되어 철회되기도 했습니다.
양자내성암호뿐만 아니라 모든 암호는 영원히 안전하다고 말할 수 없습니다.
그렇다면 양자 컴퓨터는 공개키 암호에만 위협이 될까요?
그렇지는 않습니다. 대칭키 암호 역시 양자 컴퓨터의 영향을 받습니다.
대칭키 암호에 대해서는 대표적으로 Grover의 알고리즘을 고려할 수 있습니다. Grover의 알고리즘은 무차별 대입 탐색의 복잡도를 대략 제곱근 수준으로 감소시킬 수 있습니다.
따라서 고전 컴퓨터 환경에서 약 128비트의 brute-force 보안 수준을 제공하는 키 크기는, 이상적인 양자 탐색 모델에서는 대략 64비트 수준의 탐색 복잡도로 감소하는 것으로 볼 수 있습니다.
이러한 이유로 양자 공격을 고려한 대칭키 암호에서는 더 큰 키 크기를 사용하는 방식으로 충분한 보안 수준을 확보할 수 있습니다.
다시 돌아와서, 이렇듯 영원히 안전하다고 보장되는 암호는 없습니다. 우리는 현재 알려진 최선의 공격 방법과 계산 복잡도를 기준으로 충분히 안전할 것으로 판단되는 암호를 선택하여 사용합니다.
양자 컴퓨터가 지금 상용화되고 있나요? 아닙니다. 그런데도 우리는 양자내성암호를 '지금' 준비해야 할까요?
