검수요청.png검수요청.png

양자내성암호

해시넷
7095sj (토론 | 기여)님의 2020년 8월 25일 (화) 16:16 판
이동: 둘러보기, 검색

양자내성암호(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에 비해 키 사이즈가 작고 안전성이 높다.

코드기반 암호

코드기반 암호는 일반적인 선형 코드를 디코딩하는 어려움에 기반하느 암호 시스템이다. 양자내성암호 중에서도 가장 오래된 분야에 해당한다. 코드기반 암호화는 행렬 연산이기 떄문에 연산 속도가 빠르다는 장점이 있으나, 복호화가 암호화에 비해 연산 속도가 느리고 키의 크기가 크다는 단점이 있다. 코드기반 암호 설계의 주요 아이디어는 메시지에 의도적으로 오류를 주입해서 오류를 알고 있는 사용자만 메시지를 복원할 수 있도록 만드는 것이다. 코드기반 암호 알고리즘에는 매켈리스, 모던 매켈리스, Niederreiter, MCPC-매켈리스, 와일드 매켈리스, McBits 등이 있다.

  • 매켈리스(McEliece) : 일반적인 코드기반 암호는 암호화는 빠르지만 복호화는 느린 단점이 있다. 매켈리스는 바로 이러한 단점을 극복하기 위하여 1978년에 맥켈리스에 의해 제안된 개념이다. 이항 고파(Goppa) 코드를 사용하여 패터슨의 복호화 알고리즘을 통해 효율적으로 복호화할 수 있도록 돕는다. 효율적인 디코딩 알고리즘을 이용하여 복호화할 수 있지만, 큰 키 사이즈를 가지고 있다는 단점이 있다.
  • 모던 매켈리스(Modern McEliece) : 매켈리스 알고리즘은 128비트 안전성에 대해 적어도 220KB의 공개키를 가지기 때문에 키 사이즈가 크다는 단점을 갖고 있다. 따라서 일반적인 제너레이터 행렬을 사용하기보다는 시맨틱 형태로 변형해서 저장 공간을 줄이는 방향이 제안된 것이 모던 매켈리스이다. 연산 중에 암호화 과정에서 시맨틱 형식을 사용하면 효율성을 높일 수 있는데, 특히 메시지가 항등 행렬과 연산되는 부분이 존재하기 때문에 행렬 곱셈을 수행하는 대신에 메시지를 그대로 복사하면 된다. 개인 키 사이즈를 크게 줄이고 암호화 연산 과정에서 저장 공간을 줄여서 효율성을 크게 높인다.
  • Niederreiter : 1986년에 처음으로 제안되었다. 메켈리스와 달리 오류 벡터를 이용하여 메시지를 인코딩하는 알고리즘이다. 이 때문에 매켈리스 암호와 달리 평문으로부터 비트 유출은 오류 덧셈이 영향을 주지 못한다. Niederreiter 알고리즘은 신드롬을 암호문으로 사용해서 복호화 연상량이 감소한다. 그러나 신드롬 연산은 제너레이터 행렬은 제너레이터 행렬 대신에 홀짝성 검사 행렬을 공개키로 하여 연산하기 때문에 키의 크기에 큰 영향이 없다. 즉, 키 사이즈가 줄어들지 않는다.
  • MCPC-매켈리스 : MCPC-매켈리스는 대수적인 구조를 이용한 공격 대응을 하는데, 키의 사이즈가 짧고 안전한 알고리즘이다. 2012년, 라파엘 미소츠키(Rafael Misoczki), 틸리히(Tillich), Sendrier, 바레토(Barreto)에 의해 제안되었다. 매켈리스 알고리즘은 키 사이즈가 크다는 단점이 있어서 이를 줄이기 위한 효율적인 해결책이 필요한데, 대표적인 방법이 준순환 코드처럼 큰 보형군을 가지는 코드를 선택하는 것이다. 기존의 알고리즘과는 달리 대수적인 특징을 가지지 않는 코드들은 대수적인 구조를 이용한 공격에 대응할 수 있다. 또, 안전하면서 키 사이즈가 작은 코드기반 알고리즘 설계가 가능하다.
  • 와일드 매켈리스 : 와일드 매켈리스는 2010년, 피터(Peters), 렌지(Lange) 등에 의해 제안되었다. 기존의 매켈리스 알고리즘의 정정 가능한 오류 수와 비교하면와일드 매켈리스가 동일한 안전성에 대해 더 짧은 키 사이즈를 가진다는 특징을 갖고 있다.
  • McBits : McBits는 복호화의 속도를 올린다. 번스타인, 슈바베 등에 의해 제안되었다. 기존의 코드기반 암호는 암호화에 비해 복호화의 속도가 느리다는 단점을 갖고 있는데, McBits는 FFT를 이용하여 빠른 근 계산을 통해서 복호화 과정의 속도를 높일 수 있다.

격자기반

격자 기반 암호는 격자 위에서 계산하는 문제의 어려움에 기반하는 암호 시스템이다. LWE 등의 문제를 푸는 어려움을 기반으로 설계되었다.[1] MP-hard라는 수학 문제에 안전성 기반을 두고 있기 때문에 안전성에 강점이 있다. 실제로 C 언어나 C++같은 프로그래밍 언어로 구현했을 때 모든 연산이 행렬끼리의 곱셉과 덧셈이기 때문에 계산 효율성이 높다. 공개키 암호, 완전 동형 암호, ID 기반 암호 등 다양한 암호를 격자 위에서 설계할 수 있는데, 격자 기반의 경량 공개키 암호를 설계해서 대칭키 암호와 비슷한 수준까지 계산 효율성을 극대화시키면 사물인터넷 기기 등에서도 사용될 가능성이 있다. 격자 기반 암호의 가장 큰 특징 중 하나는 암호를 만들 때 수학에서 어려운 문제를 하나 선택해서 이를 기반으로 암호를 설계하는 것이다. 암호를 만들 때 인수분해 등의 어려운 수학을 쓰는 것이 아니라, 행렬처럼 쉬운 문제를 수학적으로 어렵게 만드는 일을 한다. 예를 들어 연립방정식을 푸는 문제는 쉽지만 연립 방전식 문제에 약간에 오차를 두면 문제가 어려워진다. 연립방정식에서 변수가 세 개일 때 식도 세 개면 문제를 풀 수 있다. 그러나 여기서 끝자리를 조금씩 바꾸면, 제 아무리 쉬운 문제라도 식을 100개를 줘도 못 풀 수 있다. 이를 바로 잡음을 준다고 표현한다. 쉬운 문제의 답을 조금씩 다르게 하는 것을 말하며, 200차원의 격차를 사용하기 때문에 답을 찾기 어렵다. 오늘날에는 암호화 및 복호화, 전자서명 외에도 동형암호, 함수암호, IBE 등 다양한 응용 분야에서 연구가 진행되고 있으며, 대표적으로 NTRU, SS-NTRU, BLISS, 뉴 홉, NTRU-프라임, LWE-Prodo 등을 예로 들 수 있다.[2]

  • NTRU : 1996년에 실버맨, 피퍼, 호프스타인이 설계한 공개키 알고리즘이다. 처음으로 다항식 링을 사용하여 설계하여, 연산 속도가 빠르고 키 사이즈가 작다는 장점이 있고, 여러가지 공격 기법에 안전하다. 그러나 격자 문제로 인해 개발되지 않은 부분이 있어서 현재까지도 안전성을 증명할 수 없어서 안전성 증명 결과가 없다는 단점이 있다. 그럼에도 불구하고 NTRU는 2008년에 IEEE 스탠다드 1363.1의 표준으로 등록되었다.
  • SS-NTRU : NTRU를 변형한 알고리즘으로, 2011년에 슈텔레와 스타인필드가 제안했다. 기존의 NTRU는 안전성이 증명되지 않았기 때문에 안전성을 증명하기 위해 CVP 기반에서 설계된 NTRU를 R-LWE 기반의 설계로 변형시켰다. 연산속도가 빠른 것이 특징이다.
  • BLISS : 2013년에 듀카스 외 3인에 의해 제안된 격자 기반 전자서명 알고리즘이다. 샘플링의 변형을 통해 샘플링 거부 비율을 줄이고, 메모리 효율을 높였다.
  • 뉴 홉 : 키 교환 프로토콜 중 하나로, 128비트 양자내성 보안을 만족한다. 국내에서는 2017년 11월, 한국인터넷진흥원이 서울대학교, 울산과학기술대학교와 협력해서 격자기반 양자내성암호 리자드를 개발했다. 리자드는 전체 모양을 알 수 없게 암호화된 정보를 수신자가 전체 모양을 알 수 있도록 복호화한다.

아이소제니기반

순서가 같은 두 타원곡선 사이에 존재하는 아이소제니를 구하는 문제의 어려움에 기반을 두는 암호 시스템이다. 다시말해, 주어진 두 타원 곡선들 사이에서 아이소제니 관계를 구하는 문제를 이용한 암호 알고리즘을 말한다. 아이소제니기반 암호 알고리즘에는 디피-헬만같은 프로토콜, SIDH 등이 있다.

디피-헬만같은 프로토콜은 큰 소수를 이용하기 때문에 연산 속도가 느려서 효울성이 떨어지고, 커널이 같은 아이소제니는 동치임을 이용한다.

해시기반

해시 함수의 안전성을 기반으로 한 전자 서명 시스템이다. 해시기반 전자 서명은 암호학적 해시함수를 이용하여 전자서명 스킴을 구성하고, 사용되는 해시함수의 충돌 저항성에 의해 안전성을 보장한다. 양자컴퓨팅 환경에서도 해시함수는 출력의 길이를 늘려서 안전성을 보장할 수 있다. 해시기반 암호 알고리즘은 W-OTS, W-OTS+, HORS, SPHINCS 등이 있다.

  • W-OTS : 1989년에 처음 제안되었다. 이후 2013년에 W-OTS+ 등 W-OTS를 기반으로 한 해시기반 서명 스킴이 제안되었다. W-OTS는 서명하려는 메시지에 따라 비밀 입력 값에 대해 반복적으로 함수를 적용하는 방식을 사용한다.
  • W-OTS+ : 2013년에 헐싱(hulsing)에 의해 제안되었다. W-OTS에 비해 서명 값의 크기를 줄여서 안전성 레벨을 높인 스킴이다.
  • SPHINCS : 2015년에 번스타인, 호프우드, 헐싱, 니더하겐 등에 의해 제안되었다. 공개키와 개인키의 사이즈가 작다는 특징을 갖고 있지만 서명 값의 크기가 보안 파라미터 에 대해 의 크기를 갖는 단점이 있다. 서명 값의 크기가 작은 서명 스킴을 목표로 하며, 이때 변형한 W-OTS+를 하이퍼트리를 구성하는데 사용하는데 기존의 의사난수 키 생성을 추가하고 메시지 길이를 항상 n으로 고정한다. 또한 FTS인 HORS, HORST를 사용하여 동일한 안전성 레벨에서 작은 트리를 구성할 수 있도록 개발했다. 서명 값의 크기가 크다는 단점을 가지고 있지만, 공개키와 개인키의 사이즈가 작다는 장점이 있다.
  • HORS : 공개키 사이즈가 크다는 단점이 있다.[3]
양자내성암호의 유형과 장단점
유형 알고리즘 장점 단점
다변수기반(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법이 개정되면서 개인정도 활용과 관련된 데이터 산업이 주목받았다. 데이터를 활용하는 과정에서 개인의 프라이버시는 보호되어야 하고, 이러한 프라이버시 보호기술로는 동형암호, 차분 프라이버시, 다자간계산 등이 있다. 동형암호는 데이터를 복호화 없이 연산할 수 있는 기술로, 데이터 처리 속도가 느려지면 다른 제약 없이 모든 분야에서 활용할 수 있는데, 양자내성암호와 함께 주목받고 있다. 기존의 양자 알고리즘 중 대표적인 예시의 특징과 안전성은 다음과 같다.[4][5]

양자 알고리즘 특징 기존 암호 안전성
쇼어 알고리즘 인수분해 문제 해결 속도 감소 공개키 더 이상 안전하지 않다.
그로버 알고리즘 정렬되지 않은 데이터베이스의 원소를 검색하는 속도 향상 대칭키 키 사이즈 증가가 필요하다.
해시 암호 알고리즘의 출력 길이가 늘어날 필요가 있다.

동향

양자내성암호는 2006년에 PQCrypto 학회에서부터 본격적인 논의가 시작되었다. 2016년 미국 국립표준 기술연구소에서 양자내성암호 표준 공모를 시작함에 따라, 전 세계적으로 양자내성암호에 대한 연구 개발이 진행되고 있다. 미국 국립표준 기술연구소 양자내성암호 표준 알고리즘을 선정하기위해 표준 공모를 시작했다. 2017년도 12월에 1라운드에 제출된 총 69개의 알고리즘이 공개되었고, 그 중 국내에서 제안한 알고리즘은 5개이다. 1라운드의 평가 기준은 알고리즘의 안전성에 관한 부분이 비율을 많이 차지했고, 2019년 1월에 2라운드로 제출된 26개의 알고리즘이 공개되었다. 통과한 알고리즘의 대부분은 미국이나 유럽의 비중이 높았고, 아시아에서는 중국에서 제안한 하나뿐인 알고리즘만 2라운드에 남았다. 2라운드의 평가 기준은 1라운드의 안전성과 함께 성능도 본격적으로 평가될 예정이고, 2024년 이전까지 드래프트 표준이 완료될 예정이다. 국제표준화 기구 ISO/IEC에서도 양자내성암호 표준화를 준비 및 진행 중에 있다. 격자 기반, 코드 기반 등 기반을 두는 문제에 따라 표준 파트가 구분되고, 많은 검증이 이루어진 해시 기반 전자서명을 가장 우선적으로 표준화할 예정이다. 국내의 알고리즘 출품작은 미국 국립표준 기술연구소의 표준 공모의 2라운드 진출에 실패했다. 그러나 NIMS에서 개발한 MIMQ와 서울대학교에서 개발한 격자 기반 양자내성암호 링-리자드는 TTA 표준으로 등록되어 있다.[5]

연구 개발

  • ㈜엘지유플러스 : 2019년 12월, ㈜엘지유플러스는 서울대 산업수학센터와 크립토랩과 유무선 양자내성암호 분야 업무협약을 체결했다. 그리고 2020년 6월, ㈜엘지유플러스와 서울대학교 산업수학센터, 크립토랩이 서로 협력하여 양자 내성암호 기술을 개발하는데 성공했으며, 이에 그치지 않고 고객전용망장비, 즉 광통신전송장비에도 성공적으로 적용했다. ㈜엘지유플러스가 양자내성암호 기술을 개발한 것은 양자컴퓨팅 기술의 발전으로 양자컴퓨터가 상용화된다면 기존의 암호체계는 취약해질 수 있기 때문이다. 양자내성암호는 기존의 암호체계와는 달리 양자컴퓨터로도 풀어내는데 수십억 년이 걸리는 수학 알고리즘을 활용하여 암호키 교환, 데이터의 암호화 및 복호화, 무결성 인증 등 보안의 핵심요소와 관련한 보안 서비스를 제공할 수 있게 한다. 별도의 장비 없이 소프트웨어만으로도 구현이 가능해서 휴대폰에서 소형 사물인터넷 기기까지 유연하게 적용하여 유무선에 상관없이 모든 영역에 안전한 보안을 제공할 수 있다. 새로운 양자내성암호 기술은 미국 국립표준기술 연구소의 주도로 IBM, 아마존, 구글, 마이크로소프트 등 글로벌 기업들과 함께 표준화 작업을 진행하고 있다. 또한, 수많은 IT 업계와 보안연구소들이 연합한 오픈퀀텀세이프 프로젝트 같은 보안 기술 생태계를 통하여 연구 개발을 꾸준히 진행하고 있다. 세계 최초로 고객전용망 장비에 대한 양자내성암호를 적용한 사례이며, ㈜엘지유플러스는 앞으로 5G 서비스와 유무선 가입자 서비스에도 적용할 예정이다.[6]
  • 구글 : 기업에서 차후에 개발될 양자컴퓨터들에 대비하기 위해 양자내성암호 기술을 적용하여 안전성을 높인 대표적인 사례로는 구글의 카나리아(Canary)를 예로 들 수 있다. 구글은 격자기반 암호인 뉴 홉의 키 교환 프로토콜을 자사의 웹브라우저인 카나리아에 적용했다. 구글의 최신 브라우저인 카나리아는 뉴 홉과 타원곡선 디피헬만 키교환(ECDHE)를 결합한 CECPQ1이라는 키 교환 프로토콜을 적용했다.
  • 인피니온 테크놀로지스 : 독일의 인피니온 테크놀로지스는 뉴 홉 알고리즘이 구현된 보안 칩을 출시했다. 뉴 홉 알고리즘의 키 교환 방식을 적용함으로써 두 당사자 간의 암호화된 채널을 설정할 수 있게 되었다. 칩의 크기를 키워서 추가 메모리 없이 오직 칩 내부의 공간만을 통해 고전 컴퓨팅 분야에서 RSA와 ECC가 제공하는 수준의 안전성을 제공하면서 양자 계산 능력을 견딜 수 있도록 설계했다.
  • 국가수리연구소

각주

  1. 황정빈 기자, 〈KISA "양자컴퓨팅 시대, 양자내성암호로 대응해야"〉, 《메가뉴스》, 2018-11-05
  2. 이경원 기자, 〈'양자내성 암호' 기술 개발 천정희 서울대 교수〉, 《서울대학교수리과학부》, 2018-10-05
  3. 차세대암호인증팀 김도원, 〈양자컴퓨팅 환경에서의 암호기술 이용 안내서〉, 《한국인터넷진흥원》, 2018-02-21
  4. 도리, 〈양자 암호 기술과 양자내성암호(PQC) 알고리즘〉, 《개인블로그》, 2019-07-16
  5. 5.0 5.1 김도원, 〈[차세대 암호기술 '양자내성암호'와 '동형암호']〉, 《한국인터넷진흥원》, 2020-06
  6. 임춘호 기자, 〈양자컴퓨팅 시대에도 끄떡없는 '양자내성암호 기술' 세계 최초 적용〉, 《중소기업뉴스》, 2020-06-10

참고자료

같이 보기


  검수요청.png검수요청.png 이 양자내성암호 문서는 암호 알고리즘에 관한 글로서 검토가 필요합니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 문서 내용을 검토·수정해 주세요.