양자내성암호
양자내성암호(PQC; post-quantum cryptography)란
목차
개요
양자와 관련된 암호기술은 크게 두갈래로 나뉜다. 전자는 양자를 이용해 키를 공유하는 암호기술인 양자키분배이고, 후자는 양자컴퓨팅 환경에서 안전한 암호알고리즘인 양자내성암호이다. 그 중에서도 양자내성암호는 양자컴퓨터의 공격으로부터 안전하다고 알려진 공개키 암호로, 양자컴퓨팅의 출현 전부터 적용되어야 하며, 현 컴퓨팅환경에도 적용이 가능하다. 양자내성암호는 다섯 가지 분야로 구분할 수 있는데, 다변수기반 암호, 코드기반 암호, 격자기반 암호, 아이소제니기반 암호, 해시기반 전자서명으로 구분된다. 최근 양자 컴퓨팅 기술이 발전하면서 양자내성암호가 주목을 받고 많은 연구가 이루어지고 있다. 미국 국립표준기술연구소에서는 2017년 11월 30일, 양자내성암호에 대한 연방 표준화 사업을 진행했다.
종류
다변수기반 암호
다변수기반 암호는 안전성과 연산 효율성을 위하여 주로 이차함수를 사용한다. 암호화 및 복호화가 다항식의 계산이기 때문에 전력 분석의 부채널 공격에 강하여 안전하다는 장점이 있다. 하지만 키 사이즈가 크기 때문에 주로 서명 기법에 사용되는 편이며, 이러한 다변수기반 암호 알고리즘의 예로는 HFE, ZHFE, UOV 등이 있다. ZHFE를 적용하면 역함수를 쉽게 계산할 수 있어서 효율적인 복호화 과정을 밟을 수 있지만, 개인키를 생성하는 시간이 길다는 단점이 있다. 반면에 UOV는 키를 생성하는 속도가 빠르고, 필요한 저장 메모리의 양이 매우 적다. 그러나 큰 공개키 사이즈에는 부적합하기 때문에 유의해야 하며, 주로 서명 알고리즘에 적용되어 스마트 카드에서 구현하기에 적합하다. 레인보우(Rainbow)는 UOV에 비해 키 사이즈가 작고 안전성이 높다.
코드기반 암호
코드기반 암호는 양자내성암호 중에서 가장 오래된 분야에 해당한다. 코드기반 암호화는 행렬 연산이기 떄문에 연산 속도가 빠르다는 장점이 있으나, 복호화가 암호화에 비해 연산 속도가 느리고 키의 크기가 크다는 단점이 있다. 코드기반 암호 설계의 주요 아이디어는 메시지에 의도적으로 오류를 주입해서 오류를 알고 있는 사용자만 메시지를 복원할 수 있도록 만드는 것이다. 코드기반 암호 알고리즘에는 매켈리스(McEliece), 모던 매켈리스, Niederreiter, MCPC-매켈리스, 와일드 매켈리스, McBits 등이 있다. 매켈리스는 효율적인 디코딩 알고리즘을 이용하여 복호화할 수 있으나, 큰 키 사이즈를 갖고 있다는 단점이 있다. 모던 매켈리스는 개인 키 사이즈를 크게 죽이고 암호화 연산 과정에서 저장 공간을 줄여서 효율성을 크게 높인다. Niederreiter는 오류 벡터를 이용해서 메시지를 인코딩하는 알고리즘으로, 복호화 연산량은 감소하지만 키의 크기에 큰 영향이 없다. MCPC-매켈리스는 대수적인 구조를 이용한 공격 대응을 하는데, 키의 사이즈가 짧고 안전한 알고리즘이다. 와일드 매켈리스는 동일한 안전성에 대해 더 짧은 키 사이즈를 가진다는 특징을 갖고 있다. McBits는 복호화의 속도를 올린다.
격자기반
격자기반 암호는 LWE(Learning with errors) 등의 문제를 푸는 어려움을 기반으로 설계되었다. 이 암호는 암호화 및 복호화, 전자서명 외에도 동형암호, 함수암호, IBE 등 다양한 응용 분야에서 연구가 진행되고 있다. 격자기반 알고리즘에는 NTRU, SS-NTRU, BLISS, 뉴 홉, NTRU-프라임, LWE-Prodo 등이 있다. NTRU은 연산 속도가 빠르고 키 사이즈가 작다는 장점이 있지만, 안전성 증명 결과가 부재하다는 단점이 있다. 최초의 다항식 ring을 이용하여 설계했고, IEEE 스탠다드 1363.1 표준에 등록했다. SS-NTRU은 NTRU를 변형한 알고리즘으로, 기반문제를 CVP에서 R-LWE로 바꿔서 안전성을 증명했다. 연산속도가 빠른 것이 특징이다. BLISS는 샘플링의 변형을 통해 샘플링 거부 비율을 줄이고, 메모리 효율을 높인 전자서명 알고리즘이다. 뉴 홉은 키 교환 프로토콜 중 하나로, 128비트 양자내성 보안을 만족한다.
아이소제니기반
아이소제니기반 암호는 주어진 두 타원 곡선들 사이의 아이소제니 관계를 구하는 문제를 이용한 암호 알고리즘을 말한다. 아이소제니기반 암호 알고리즘에는 디피-헬만같은 프로토콜, SIDH 등이 있다. 디피-헬만같은 프로토콜은 큰 소수를 이용하기 때문에 연산 속도가 느려서 효울성이 떨어지고, 커널이 같은 아이소제니는 동치임을 이용한다.
해시기반
해시기반 전자 서명은 암호학적 해시함수를 이용하여 전자서명 스킴을 구성하고, 사용되는 해시함수의 충돌 저항성에 의해 안전성을 보장한다. 양자컴퓨팅 환경에서도 해시함수는 출력의 길이를 늘려서 안전성을 보장할 수 있다. 해시기반 암호 알고리즘은 W-OTS, W-OTS+, HORS, SPHINCS 등이 있다. W-OTS는 서명하려는 메시지에 따라서 입력값에 반복적으로 함수를 적용하는 특징이 있다. W-OTS+는 W-OTS보다는 서명 값의 크기를 줄여서 보안 레벨을 높인 알고리즘이다. HORS는 공개키 사이즈가 크다는 단점이 있다. SPHINCS는 서명 값의 크기가 크다는 단점을 가지고 있지만, 공개키와 개인키의 사이즈가 작다는 장점이 있다.
양자내성암호의 유형과 장단점 유형 알고리즘 장점 단점 다변수기반(Multivariate-based) 레인보우, Gui 작은 서명 크기, 빠른 계산 큰 키 사이즈 코드 기반(Code-based) QC-MDPC, Wild McEliece 빠른 암호화 및 복호화 속도 큰 키 사이즈 격자기반(Lattice-based) SS-NTRU, NTRU Prime, LWE-Frodo 다양한 응용환경 지원, 빠른 속도의 구현 변수 설정 어려움 아이소제니기반(Isogeny-based) SIDH 구현의 편리성, 작은 키 사이즈 연산속도가 느림 해시기반(Hash-based) XMSS, SPHINCS 안전성 증명 가능 큰 서명 사이즈
특징
고성능 양자 컴퓨터를 이용한 보안 위협을 대비하기 위해 양자내성암호가 필요하다. 기존의 양자 알고리즘 중 대표적인 예시의 특징과 안전성은 다음과 같다.[1]
양자 알고리즘 특징 기존 암호 안전성 쇼어 알고리즘 인수분해 문제 해결 속도 감소 공개키 더 이상 안전하지 않다. 그로버 알고리즘 정렬되지 않은 데이터베이스의 원소를 검색하는 속도 향상 대칭키 키 사이즈 증가가 필요하다. 해시 암호 알고리즘의 출력 길이가 늘어날 필요가 있다.
활용
동향
사례
- 구글 : 기업에서 차후에 개발될 양자컴퓨터들에 대비하기 위해 양자내성암호 기술을 적용하여 안전성을 높인 대표적인 사례로는 구글의 카나리아(Canary)를 예로 들 수 있다. 구글은 격자기반 암호인 뉴 홉의 키 교환 프로토콜을 자사의 웹브라우저인 카나리아에 적용했다. 구글의 최신 브라우저인 카나리아는 뉴 홉과 타원곡선 디피헬만 키교환(ECDHE)를 결합한 CECPQ1이라는 키 교환 프로토콜을 적용했다.
- 인피니온 테크놀로지스 : 독일의 인피니온 테크놀로지스는 뉴 홉 알고리즘이 구현된 보안 칩을 출시했다. 뉴 홉 알고리즘의 키 교환 방식을 적용함으로써 두 당사자 간의 암호화된 채널을 설정할 수 있게 되었다. 칩의 크기를 키워서 추가 메모리 없이 오직 칩 내부의 공간만을 통해 고전 컴퓨팅 분야에서 RSA와 ECC가 제공하는 수준의 안전성을 제공하면서 양자 계산 능력을 견딜 수 있도록 설계했다.
각주
- ↑ 도리, 〈양자 암호 기술과 양자내성암호(PQC) 알고리즘〉, 《개인블로그》, 2019-07-16
참고자료
- 박태환, 김호원, 〈양자내성암호 표준화, 연구 동향 및 전망〉, 《국가과학기술정보센터》, 2018-10
- 도리, 〈양자 암호 기술과 양자내성암호(PQC) 알고리즘〉, 《개인블로그》, 2019-07-16
같이 보기
