위키원
양자내성암호
양자내성암호(PQC; post-quantum cryptography)란
목차
개요
양자와 관련된 암호기술은 크게 두갈래로 나뉜다. 전자는 양자를 이용해 키를 공유하는 암호기술인 양자키분배이고, 후자는 양자컴퓨팅 환경에서 안전한 암호알고리즘인 양자내성암호이다. 그 중에서도 암호의 원천 기술 중 하나인 공개키암호는 인터넷 뱅킹, 전자 주식 거래, 인터넷 쇼핑 등 전자 거래 보안의 핵심으로서 전 세계인이 사용하고 있다. RSA, 디피-헬먼 교환, 타원 곡선 암호 등의 공개키암호 기술을 활발하게 이용하고 있고, 이들은 인수분해나 이산대수 같은 수학적인 원리를 이용하여 개발됐다. 그러나 1994년, 쇼어는 양자 알고리즘을 이용해서 인수분해나 이산대수 문제를 모두 짧은 시간 안에 해결할 수 있다고 증명했고, 이를 통해 기존에 있던 대부분의 공개키 암호들이 해독될 수 있다는 사실이 밝혀졌다. 이전까지는 기술적인 어려움으로 양자컴퓨터를 실용화하지 못해서 크게 눈길을 끄는 문제가 아니었지만, 최근에 양자 컴퓨팅 기술의 발달로 양자 컴퓨터 실현 가능성이 증가함에 따라 해결책인 양자내성암호이 중요해졌다. 양자내성암호는 기존의 공개키암호가 가지고 있던 문제를 해결하고 대체할 수 있는 암호로, 기존의 인수분해나 이산대수 문제가 아닌 전혀 새로운 문제에 안전성을 기반한다. 기반하는 분야에 따라 총 다섯 가지로 나눌 수 있는데, 다변수기반(Multi-variate) 암호, 코드기반(Code-based) 암호, 격자기반(Lattice-based) 암호, 아이소제니기반(Isogeny-based) 암호, 해시기반 전자서명(Hash-based)으로 구분된다. 또한, 알고리즘의 기능에 따라 암호화 및 키교환 알고리즘과 전자서명 알고리즘으로 구분할 수 있다.
양자 컴퓨팅 기술의 발전으로 양자내성암호와 관련한 연구도 크게 증가했다. 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비트 양자내성 보안을 만족한다. 국내에서는 2017년 11월, 한국인터넷진흥원이 서울대학교, 울산과학기술대학교와 협력해서 격자기반 양자내성암호 리자드를 개발했다. 리자드는 전체 모양을 알 수 없게 암호화된 정보를 수신자가 전체 모양을 알 수 있도록 복호화한다.[1]
아이소제니기반
순서가 같은 두 타원곡선 사이에 존재하는 아이소제니를 구하는 문제의 어려움에 기반을 두는 암호 시스템이다. 다시말해, 주어진 두 타원 곡선들 사이에서 아이소제니 관계를 구하는 문제를 이용한 암호 알고리즘을 말한다. 아이소제니기반 암호 알고리즘에는 디피-헬만같은 프로토콜, 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 안전성 증명 가능 큰 서명 사이즈
특징
오늘날의 IT 사회는 AES나 RSA와 같은 형대 암호들로 필요한 기능들이 충분히 제공되고 있지만, 점점 4차 산업혁명 시대가 다가오면서 사회적으로 문제를 일으킬 수 있는 새로운 보안 문제들도 함께 등장하고 있다. 사회의 변화에 발맞추어 고성능 양자 컴퓨터가 개발된다면 외부로부터의 보안 위협을 대비하기 위해서 양자내성암호가 필요하다. 양자 컴퓨터가 개발된다면 양자 기반 알고리즘인 쇼어 알고리즘에 의해서 기존의 공개키 암호 알고리즘을 더 이상 사용할 수 없다. 또한, 그로버 알고리즘으로 인해서 대칭키 암호의 키 사이즈를 두배, 해시 함수의 출력 길이를 세배 정도 증가시켜야 기존의 안전성을 가질 수 있다. 2020년 초, 데이터 3법이 개정되면서 개인정도 활용과 관련된 데이터 산업이 주목받았다. 데이터를 활용하는 과정에서 개인의 프라이버시는 보호되어야 하고, 이러한 프라이버시 보호기술로는 동형암호, 차분 프라이버시, 다자간계산 등이 있다. 동형암호는 데이터를 복호화 없이 연산할 수 있는 기술로, 데이터 처리 속도가 느려지면 다른 제약 없이 모든 분야에서 활용할 수 있는데, 양자내성암호와 함께 주목받고 있다. 기존의 양자 알고리즘 중 대표적인 예시의 특징과 안전성은 다음과 같다.[2][3]
양자 알고리즘 특징 기존 암호 안전성 쇼어 알고리즘 인수분해 문제 해결 속도 감소 공개키 더 이상 안전하지 않다. 그로버 알고리즘 정렬되지 않은 데이터베이스의 원소를 검색하는 속도 향상 대칭키 키 사이즈 증가가 필요하다. 해시 암호 알고리즘의 출력 길이가 늘어날 필요가 있다.
동향
양자내성암호는 2006년에 PQCrypto 학회에서부터 본격적인 논의가 시작되었다. 2016년 미국 국립표준 기술연구소에서 양자내성암호 표준 공모를 시작함에 따라, 전 세계적으로 양자내성암호에 대한 연구 개발이 진행되고 있다. 미국 국립표준 기술연구소 양자내성암호 표준 알고리즘을 선정하기위해 표준 공모를 시작했다. 2017년도 12월에 1라운드에 제출된 총 69개의 알고리즘이 공개되었고, 그 중 국내에서 제안한 알고리즘은 5개이다. 1라운드의 평가 기준은 알고리즘의 안전성에 관한 부분이 비율을 많이 차지했고, 2019년 1월에 2라운드로 제출된 26개의 알고리즘이 공개되었다. 통과한 알고리즘의 대부분은 미국이나 유럽의 비중이 높았고, 아시아에서는 중국에서 제안한 하나뿐인 알고리즘만 2라운드에 남았다. 2라운드의 평가 기준은 1라운드의 안전성과 함께 성능도 본격적으로 평가될 예정이고, 2024년 이전까지 드래프트 표준이 완료될 예정이다. 국제표준화 기구 ISO/IEC에서도 양자내성암호 표준화를 준비 및 진행 중에 있다. 격자 기반, 코드 기반 등 기반을 두는 문제에 따라 표준 파트가 구분되고, 많은 검증이 이루어진 해시 기반 전자서명을 가장 우선적으로 표준화할 예정이다. 국내의 알고리즘 출품작은 미국 국립표준 기술연구소의 표준 공모의 2라운드 진출에 실패했다. 그러나 NIMS에서 개발한 MIMQ와 서울대학교에서 개발한 격자 기반 양자내성암호 링-리자드는 TTA 표준으로 등록되어 있다.[3]
연구 개발
- 구글 : 기업에서 차후에 개발될 양자컴퓨터들에 대비하기 위해 양자내성암호 기술을 적용하여 안전성을 높인 대표적인 사례로는 구글의 카나리아(Canary)를 예로 들 수 있다. 구글은 격자기반 암호인 뉴 홉의 키 교환 프로토콜을 자사의 웹브라우저인 카나리아에 적용했다. 구글의 최신 브라우저인 카나리아는 뉴 홉과 타원곡선 디피헬만 키교환(ECDHE)를 결합한 CECPQ1이라는 키 교환 프로토콜을 적용했다.
- 인피니온 테크놀로지스 : 독일의 인피니온 테크놀로지스는 뉴 홉 알고리즘이 구현된 보안 칩을 출시했다. 뉴 홉 알고리즘의 키 교환 방식을 적용함으로써 두 당사자 간의 암호화된 채널을 설정할 수 있게 되었다. 칩의 크기를 키워서 추가 메모리 없이 오직 칩 내부의 공간만을 통해 고전 컴퓨팅 분야에서 RSA와 ECC가 제공하는 수준의 안전성을 제공하면서 양자 계산 능력을 견딜 수 있도록 설계했다.
- 국가수리연구소
각주
- ↑ 황정빈 기자, 〈KISA "양자컴퓨팅 시대, 양자내성암호로 대응해야"〉, 《메가뉴스》, 2018-11-05
- ↑ 도리, 〈양자 암호 기술과 양자내성암호(PQC) 알고리즘〉, 《개인블로그》, 2019-07-16
- ↑ 3.0 3.1 김도원, 〈[차세대 암호기술 '양자내성암호'와 '동형암호']〉, 《한국인터넷진흥원》, 2020-06
참고자료
- 박태환, 김호원, 〈양자내성암호 표준화, 연구 동향 및 전망〉, 《국가과학기술정보센터》, 2018-10
- 황정빈 기자, 〈KISA "양자컴퓨팅 시대, 양자내성암호로 대응해야"〉, 《메가뉴스》, 2018-11-05
- 도리, 〈양자 암호 기술과 양자내성암호(PQC) 알고리즘〉, 《개인블로그》, 2019-07-16
같이 보기
