Post Quantum Cryptography(PQC), PQC란

복잡한 설명은 파란색으로 함께 진행하겠습니다. 파란색은 이런 게 있구나라고 보시고 넘어가셔도 좋습니다.

먼저 용어부터 소개하도록 하겠습니다. Post Quantum Cryptography(PQC)는 양자내성 암호라고 합니다.

이름을 들었을 땐 어딘가 생소합니다. 양자암호도 아니고 양자내성 암호라니요.

양자 암호와 양자내성 암호는 서로 다른 분야입니다. PQC가 무엇인지 자세히 알아봅시다.

다시 PQC를 검색해 봅니다.

양자내성암호(Post Quantum Cryptography; PQC)는 양자컴퓨터로도 풀어내는 데 수십억 년이 걸리는 복잡한 수학 알고리즘을 사용하는 암호화 방식이다[1].

PQC란 양자컴퓨터로 풀어내는 데 수십억 년이 걸리는 수학 알고리즘을 사용하는 암호화 방식입니다[2].

'양자컴퓨터' 시대에는 기존 암호체계가 취약할 수 있어 새로운 보안기술을 확보하는 게 필수다[3].

위에 적힌 내용과 같이 비슷한 단어가 많이 나오는 것을 확인 할 수 있습니다. 키워드는 다음과 같습니다.

양자컴퓨터
수학 알고리즘
보안

보안이란 정보의 기밀성(Confidentiality), 무결성(Integrity), 가용성(Availability)을 특징으로 가집니다. 이러한 특징들은 수학 알고리즘을 사용하는 암호화 알고리즘에 의해 얻을 수 있습니다. 암호화 알고리즘은 대칭키 암호와 공개키 암호로 분류됩니다.

현재까지를 잠시 정리하고 넘어가겠습니다.

요약

보안성은 암호화 알고리즘을 통해 제공된다.
암호화 알고리즘은 크게 공개키와 대칭키 알고리즘으로 분류된다.

공개키 암호을 위주로 살펴보겠습니다.

공개키 암호는 인수분해문제 기반 암호와 이산대수문제 기반 암호로 분류할 수 있습니다. 내용에 대한 자세한 설명보다는 예시를 보고 넘어가겠습니다.

인수분해문제 기반 암호로 세계 최초의 공개키 암호이자 공동인증서 등에 쓰이는 RSA 암호가 있습니다.
이산대수문제 기반 암호로 비트코인 지갑의 주소와 개인키로 사용되는 타원곡선 암호가 있습니다.

RSA 암호는 큰 수를 소인수분해 하는것의 어려움을 기반으로 합니다. 임의의 큰 양의 정수를 빠르게 소인수분해 하는 방법이 알려져 있지 않습니다. 이에 대해 General Number Field Seive(GNFS) 알고리즘을 이용하여 소인수분해 연구가 진행되고 있습니다. RSA 챌린지에서 2020년 2월 28일에는 829 비트(250 자리 십진수)크기의 정수를 소인수분해하는데 성공했습니다[4]. 더 큰 자리수에 대해서는 아직 미지의 영역으로 남아있습니다. 가능하더라도 현재 컴퓨터로는 굉장히 오랜 시간을 필요로합니다.

소인수 분해 예시.

\( 25707189880159888913 = 4338573307 * 5925263459 \)

1994년 피터 쇼어(Peter Shor)가 양자의 성질을 이용하여 인수분해 문제와 이산대수 문제를 다항식 시간 내에 해결할 수 있음을 보였습니다.

부가적인 설명으로 양자컴퓨터에서 다항시간의 실행시간을 가지는 알고리즘의 집합을 BQP(bounded error quantum polynomial time) 라고 말합니다. 쇼어가 인수분해와 이산대수문제가 BQP 내에 포함되는 것을 증명한 것입니다.

현재 상황을 다시 정리해 봅시다.

요약

암호화 알고리즘은 공개키와 대칭키 알고리즘으로 분류
공개키 알고리즘은 인수분해 문제와 이산대수 문제를 기반으로 함
양자 컴퓨터 등장 시 인수분해 문제와 이산대수 문제를 빠른 시간 내에 해결할 수 있음
공개키 암호화 알고리즘을 사용할 수 없음
양자컴퓨터 시대를 대비하기 위한 새로운 공개키 암호 필요

키워드 중 하나였던 양자컴퓨터의 동향에 대해서 알아봅시다. 쇼어 알고리즘의 발표 이후 양자컴퓨터에 대한 관심이 높아졌습니다. 현재도 양자컴퓨터 연구가 활발히 진행되고 있습니다.

구글 - 2019년 53 큐빗 양자컴퓨터로 양자우위 달성, 10년내 상용화 목표 [5, 6]
IBM - 2023년 1,121큐빗 목표 [7]
D Wave - 2020년 2월 5000 큐빗 [8]

아직 양자컴퓨터의 상용화는 예상할 수 없지만 PQC는 미리 준비해야 합니다.

Mosca의 부등식으로 설명을 진행합니다.

X - 데이터 보호를 원하는 기간

Y - 현재 보안 시스템에서 post quantum 보안 시스템으로 변경되는 기간

Z - 양자컴퓨터가 상용화되어 기존 암호화를 위협할 때

X + Y > Z 일 경우 남은 기간에 대해서는 데이터를 보호할 수 없습니다.

개발 후 적용에 걸리는 시간을 고려합니다. 현재 사용중인 소프트웨어와 하드웨어를 모두 수정하는 것은 오랜 시간을 필요로합니다.

따라서 양자 컴퓨터 이후에도 안전하게 사용할 수 있는 암호라는 의미의 포스트 양자 암호(Post Quantum Cryptography: PQC)라 말합니다.

마지막으로 김승주 교수님의 제언을 인용합니다.

그러나 아무리 양자 보안이 중요하고 보다 많은 저변 확대와 투자를 위해 관심을 고취시킬 필요가 있다 하더라도 그 의욕이 지나치게 과해 QKD(양자암호키분배)나 QRNG(양자난수발생기) 또는 PQC(양자내성암호)가 절대로 해킹이 불가능하다는 잘못된 환상을 갖게 한다거나, 단위 요소기술일 뿐인 난수발생기 및 키분배 기술을 마치 양자 보안의 전부인양 과도하게 부풀려서 홍보하는 식의 태도는 곤란할 것이다. 이러한 과도한 홍보는 결국 거품 논란을 일으키게 돼 있고, 종국에는 사람들로부터 빠르게 외면을 받게 되는 주요 원인으로 작용할 수 있기 때문이다.

자료 출처

[1] https://www.e4ds.com/sub_view.asp?ch=23&t=0&idx=12476

[2] https://m.mk.co.kr/stockview/?sCode=21&t_uid=31&c_uid=154608

[3] http://www.worldyan.com/pages/page_24.php?sn=32592

[4] https://en.wikipedia.org/wiki/RSA_Factoring_Challenge

[5] https://www.nature.com/articles/s41586-019-1666-5

[6] https://zdnet.co.kr/view/?no=20210520135253

[7] https://www.ibm.com/blogs/research/2021/02/quantum-development-roadmap/

[8] https://www.dwavesys.com/

[9] https://csrc.nist.gov/csrc/media/events/workshop-on-cybersecurity-in-a-post-quantum-world/documents/presentations/session8-mosca-michele.pdf

참고 자료

차세대 표준암호 기술동향.pdf