[전문가 칼럼] 양자컴퓨터에 위협받는 전통 암호체계, 양자내성암호에 주목해야
2023-02-20 00:10
서화정 한국정보보호학회 이사 기고
지난 2022년 11월 9일, IBM에선 세계 최초로 433큐비트(Qbit, 양자컴퓨터 정보 단위) 양자컴퓨터 오스프리(Osprey)를 발표했다. IBM은 양자컴퓨터 개발에 있어서 세계 선두 그룹으로, 오는 2025년까지 4158큐비트를 달성하는 것이 목표다.
만약 연산 오류가 없고, 안정적인 1만 큐비트 이상의 양자컴퓨터가 개발된다면 현재 대표적인 암호화 알고리즘 RSA가 쉽게 복호화될 수 있다. RSA는 아주 긴 숫자를 소인수분해하는 데는 오랜 시간이 걸린다는 수학적 원리를 이용해 데이터를 암호화하는 방식이다. 현재 컴퓨터는 193자리 수만 돼도 소인수분해에 수개월에서 수년이 걸린다.
하지만 응용수학자 피터 쇼어가 1994년 제안한 알고리즘(Shor's Algorithm)을 양자컴퓨터로 구현하면 다항 시간(문제 해결에 걸리는 시간이 문제의 다항식 함수보다 크지 않은 것)에 소인수분해가 가능하다.
양자컴퓨터는 기존 컴퓨터에서 사용하는 데이터 단위 '비트'와 달리, 큐비트를 활용해 복잡한 연산을 가속화할 수 있다. 기존 비트가 0과 1 중 하나의 정보만을 표현할 수 있다면, 큐비트는 0과 1을 확률적으로 한 번에 표현하는 것이 가능하다. 이를 양자중첩이라고 하며, 병렬 연산에 효율적인 구조다.
병렬적으로 연산된 큐비트는 실제 활용 가능한 형식으로 전환하기 위해 측정과정을 거친다. 측정된 큐비트는 특정 비트로 정보로 결정돼 우리가 인식할 수 있는 형태가 된다. 더불어 양자얽힘이라는 특성을 통해 큐비트 사이에 한 번이라도 양자 연산이 수행된 경우, 중첩된 다른 큐비트의 상태도 결정된다.
이 같은 양자컴퓨터의 특성은 현대 암호 해독을 비롯해 현대 슈퍼컴퓨터로는 불가능한 난제를 실시간으로 해결할 전망이다. 양자컴퓨터 기술 개발은 세계적인 IBM, 구글, 아마존, 마이크로소프트 등의 경쟁으로 인해 점차 가속화되는 추세다.
◆양자컴퓨터 시대를 위한 보안체계, 양자내성암호
고성능 양자컴퓨터 개발에 대비하기 위해 미국 국립표준기술연구소(NIST)는 2017년부터 양자내성암호 공모전을 진행하고 있다. 해당 공모전은 양자컴퓨터에 내성을 가지는 수학적 기반 문제를 통해 안전성을 확보하는 알고리즘을 제안하는 것을 목표로 한다. 양자컴퓨터 환경에서 취약해진 RSA 공개키 암호화 시스템을 안전하게 대체할 수 있는 방안을 전 세계 암호학자가 함께 고민하는 것이다.
지난 2022년에는 최종 표준안으로 4개의 암호화 알고리즘이 선정됐다. 키 교환 알고리즘에는 크리스탈-카이버(CRYSTALS-Kyber) 알고리즘이 선정됐으며, 서명 알고리즘에는 크리스탈-딜리슘(CRYSTALS-Dilithium), 팔콘(Falcon), 스핑크스 플러스(SPHINCS+)가 선정됐다.
이 중 스핑크스 플러스는 해시 기반 암호화 방식이다. 해시 기반 암호는 매우 오랜 기간 연구된 암호학적 해시함수의 안전성을 기반으로 한다. 양자컴퓨터 상에서의 보안성이 다른 알고리즘에 비해 확실하다는 것도 장점이다.
나머지 3개는 격자 기반 암호화 방식이다. 격자 기반 암호화는 격자 연산에 오류를 포함시켜, 실제 비밀 키 값을 해커가 확인할 수 없도록 하는 기법이다. 특히 연산 효율성이 매우 높고, 암호화 키 길이도 다른 방식과 비교해 짧은 것이 특징이다.
현재 해시와 격자 이외에도 아이소지니 기반 암호, 코드 기반 암호 등도 표준안으로 선정하기 위한 추가 공모전이 진행되고 있다. 다만 아이소지니의 경우 보안 취약성이 최근에 밝혀져서 선정될 확률이 낮아진 상태다.
반면 코드 기반 암호는 해시 기반 암호와 같이 매우 오랜 기간 동안 연구된 오류 수정 코드에 기반하고 있다. 이에 대한 해킹도 현재까지 이뤄지지 않았기 때문에, 격자 기반 암호와 함께 큰 관심을 받고 있다. 현재 후보군으로 올라와 있는 코드기반 암호는 클래식 매켈리스(Classic McEliece), HQC, 바이크(BIKE) 등이다. 이 중에서도 가장 보수적인 보안성을 갖춘 클래식 매켈리스에 대한 관심이 높다.
◆다수의 암호 알고리즘 등장 전망... 운용 방법론도 필요
국내에서도 양자내성암호 공모전을 추진하고 있다. 오는 2024년까지 국내 양자내성암호 표준안을 결정하는 것을 목표로, 지난 2022년부터 진행 중이다. 1차 선정 결과는 올해 중 발표될 예정이다. 양자내성암호 선정 시 고려 사항으로는 해당 암호의 안전성과 구현 효율성 등이다.
암호는 전통컴퓨터나 양자컴퓨터 등 어떠한 연산에도 내성을 가져야 한다. 동시에 현재 상용화된 컴퓨터에서도 효율적으로 구현될 수 있어야 한다. 공모전 결과는 국내 암호모듈검증(KCMVP) 암호 알고리즘에 추가된다. 추후 국내 정보시스템 서비스에 탑재돼 양자컴퓨터로부터 안전성을 확보할 전망이다.
앞서 이야기한 것처럼 양자내성암호에 대한 연구는 최근 10년간 폭발적으로 이뤄졌다. 하지만 암호 기술이 가지는 보안성은 암호학자들이 발명하는 새로운 암호분석 기술에 의해 언제든지 훼손될 수 있다. 즉 표준안이 되는 양자내성암호라고 할지라도 언젠가는 해킹될 수 있다. 이러한 이유 때문에 현재 양자내성암호 공모전에서 선정하는 알고리즘은 하나의 기반 문제가 아닌 서로 상이한 여러 문제를 함께 선정하고 있다.
물론 이에 따라 경우의 수가 늘어나고, 운영 상에 있어서 복잡도는 높아질 전망이다. 따라서 추후 여러 암호화 알고리즘이 양자내성암호 표준으로 선정된다면, 이를 잘 운용하기 위한 방법론에 대해서도 함께 연구가 진행돼야 한다.
이에 대한 예로 기존의 타원곡선암호(ECC) 알고리즘과 양자내성암호를 결합해 사용하는 하이브리드 기법도 제안되고 있다. 이는 양자내성암호의 보안성을 현재 시점에선 확신할 수 없기 때문에, 현대 공개키 암호인 ECC의 보안성을 함께 활용하는 것이다.
살펴본 바와 같이 양자컴퓨터는 매우 활발히 연구·개발되고 있으며, 이에 대비하기 위해 다양한 양자내성암호 기술도 연구되고 있다. 따라서 실용적인 양자컴퓨터가 등장하는 시점에는 현재 정보시스템이 양자내성암호로의 전환을 원활히 이룰 것으로 예상된다. 해킹으로 인해 암호화 체계가 무너지는 등 큰 혼란은 당분간 발생하지 않을 전망이다.
만약 연산 오류가 없고, 안정적인 1만 큐비트 이상의 양자컴퓨터가 개발된다면 현재 대표적인 암호화 알고리즘 RSA가 쉽게 복호화될 수 있다. RSA는 아주 긴 숫자를 소인수분해하는 데는 오랜 시간이 걸린다는 수학적 원리를 이용해 데이터를 암호화하는 방식이다. 현재 컴퓨터는 193자리 수만 돼도 소인수분해에 수개월에서 수년이 걸린다.
하지만 응용수학자 피터 쇼어가 1994년 제안한 알고리즘(Shor's Algorithm)을 양자컴퓨터로 구현하면 다항 시간(문제 해결에 걸리는 시간이 문제의 다항식 함수보다 크지 않은 것)에 소인수분해가 가능하다.
양자컴퓨터는 기존 컴퓨터에서 사용하는 데이터 단위 '비트'와 달리, 큐비트를 활용해 복잡한 연산을 가속화할 수 있다. 기존 비트가 0과 1 중 하나의 정보만을 표현할 수 있다면, 큐비트는 0과 1을 확률적으로 한 번에 표현하는 것이 가능하다. 이를 양자중첩이라고 하며, 병렬 연산에 효율적인 구조다.
병렬적으로 연산된 큐비트는 실제 활용 가능한 형식으로 전환하기 위해 측정과정을 거친다. 측정된 큐비트는 특정 비트로 정보로 결정돼 우리가 인식할 수 있는 형태가 된다. 더불어 양자얽힘이라는 특성을 통해 큐비트 사이에 한 번이라도 양자 연산이 수행된 경우, 중첩된 다른 큐비트의 상태도 결정된다.
이 같은 양자컴퓨터의 특성은 현대 암호 해독을 비롯해 현대 슈퍼컴퓨터로는 불가능한 난제를 실시간으로 해결할 전망이다. 양자컴퓨터 기술 개발은 세계적인 IBM, 구글, 아마존, 마이크로소프트 등의 경쟁으로 인해 점차 가속화되는 추세다.
◆양자컴퓨터 시대를 위한 보안체계, 양자내성암호
고성능 양자컴퓨터 개발에 대비하기 위해 미국 국립표준기술연구소(NIST)는 2017년부터 양자내성암호 공모전을 진행하고 있다. 해당 공모전은 양자컴퓨터에 내성을 가지는 수학적 기반 문제를 통해 안전성을 확보하는 알고리즘을 제안하는 것을 목표로 한다. 양자컴퓨터 환경에서 취약해진 RSA 공개키 암호화 시스템을 안전하게 대체할 수 있는 방안을 전 세계 암호학자가 함께 고민하는 것이다.
지난 2022년에는 최종 표준안으로 4개의 암호화 알고리즘이 선정됐다. 키 교환 알고리즘에는 크리스탈-카이버(CRYSTALS-Kyber) 알고리즘이 선정됐으며, 서명 알고리즘에는 크리스탈-딜리슘(CRYSTALS-Dilithium), 팔콘(Falcon), 스핑크스 플러스(SPHINCS+)가 선정됐다.
이 중 스핑크스 플러스는 해시 기반 암호화 방식이다. 해시 기반 암호는 매우 오랜 기간 연구된 암호학적 해시함수의 안전성을 기반으로 한다. 양자컴퓨터 상에서의 보안성이 다른 알고리즘에 비해 확실하다는 것도 장점이다.
나머지 3개는 격자 기반 암호화 방식이다. 격자 기반 암호화는 격자 연산에 오류를 포함시켜, 실제 비밀 키 값을 해커가 확인할 수 없도록 하는 기법이다. 특히 연산 효율성이 매우 높고, 암호화 키 길이도 다른 방식과 비교해 짧은 것이 특징이다.
현재 해시와 격자 이외에도 아이소지니 기반 암호, 코드 기반 암호 등도 표준안으로 선정하기 위한 추가 공모전이 진행되고 있다. 다만 아이소지니의 경우 보안 취약성이 최근에 밝혀져서 선정될 확률이 낮아진 상태다.
반면 코드 기반 암호는 해시 기반 암호와 같이 매우 오랜 기간 동안 연구된 오류 수정 코드에 기반하고 있다. 이에 대한 해킹도 현재까지 이뤄지지 않았기 때문에, 격자 기반 암호와 함께 큰 관심을 받고 있다. 현재 후보군으로 올라와 있는 코드기반 암호는 클래식 매켈리스(Classic McEliece), HQC, 바이크(BIKE) 등이다. 이 중에서도 가장 보수적인 보안성을 갖춘 클래식 매켈리스에 대한 관심이 높다.
◆다수의 암호 알고리즘 등장 전망... 운용 방법론도 필요
국내에서도 양자내성암호 공모전을 추진하고 있다. 오는 2024년까지 국내 양자내성암호 표준안을 결정하는 것을 목표로, 지난 2022년부터 진행 중이다. 1차 선정 결과는 올해 중 발표될 예정이다. 양자내성암호 선정 시 고려 사항으로는 해당 암호의 안전성과 구현 효율성 등이다.
암호는 전통컴퓨터나 양자컴퓨터 등 어떠한 연산에도 내성을 가져야 한다. 동시에 현재 상용화된 컴퓨터에서도 효율적으로 구현될 수 있어야 한다. 공모전 결과는 국내 암호모듈검증(KCMVP) 암호 알고리즘에 추가된다. 추후 국내 정보시스템 서비스에 탑재돼 양자컴퓨터로부터 안전성을 확보할 전망이다.
앞서 이야기한 것처럼 양자내성암호에 대한 연구는 최근 10년간 폭발적으로 이뤄졌다. 하지만 암호 기술이 가지는 보안성은 암호학자들이 발명하는 새로운 암호분석 기술에 의해 언제든지 훼손될 수 있다. 즉 표준안이 되는 양자내성암호라고 할지라도 언젠가는 해킹될 수 있다. 이러한 이유 때문에 현재 양자내성암호 공모전에서 선정하는 알고리즘은 하나의 기반 문제가 아닌 서로 상이한 여러 문제를 함께 선정하고 있다.
물론 이에 따라 경우의 수가 늘어나고, 운영 상에 있어서 복잡도는 높아질 전망이다. 따라서 추후 여러 암호화 알고리즘이 양자내성암호 표준으로 선정된다면, 이를 잘 운용하기 위한 방법론에 대해서도 함께 연구가 진행돼야 한다.
이에 대한 예로 기존의 타원곡선암호(ECC) 알고리즘과 양자내성암호를 결합해 사용하는 하이브리드 기법도 제안되고 있다. 이는 양자내성암호의 보안성을 현재 시점에선 확신할 수 없기 때문에, 현대 공개키 암호인 ECC의 보안성을 함께 활용하는 것이다.
살펴본 바와 같이 양자컴퓨터는 매우 활발히 연구·개발되고 있으며, 이에 대비하기 위해 다양한 양자내성암호 기술도 연구되고 있다. 따라서 실용적인 양자컴퓨터가 등장하는 시점에는 현재 정보시스템이 양자내성암호로의 전환을 원활히 이룰 것으로 예상된다. 해킹으로 인해 암호화 체계가 무너지는 등 큰 혼란은 당분간 발생하지 않을 전망이다.
서화정 한성대학교 IT융합공학부 교수. [사진=한국정보보호학회]