뉴스Q

[칼럼] 김승주의 암호학&블록체인

양자컴퓨터로 비트코인을 깰 수 있다?

2021. 07. 13 by 김승주 고려대 교수
출처=pixabay
출처=pixabay

양자컴퓨터가 비트코인 등 암호화폐나 블록체인 보안에 위협이 될까? 내가 강연 중 가장 많이 받는 질문이다.

1982년에 처음 소개된 양자컴퓨터는 양자역학 기술을 활용해 동작하는 컴퓨터다. 기존 컴퓨터는 01만 구분할 수 있는 이진법을 사용한다. 하지만 퀀텀비트(큐빗)라는 정보 단위를 사용하는 양자컴퓨터는 01을 동시에 공존시킬 수 있다. 이런 속성을 '중첩(superposition)'이라고 한다.

이로 인해 양자컴퓨터의 연산 능력은 기존 컴퓨터와 비교 불가능한 수준이며, 상용화되면 암호화폐 기술의 기반인 블록체인 보안까지도 위협할 수 있다는 주장이 나온다.

 

기존 컴퓨터 연산을 뛰어넘는 양자컴퓨터

보안 분야에서 양자컴퓨터에 대한 관심이 본격적으로 높아지게 된 계기는 1994년 미국 벨연구소의 피터 쇼어(Peter Shor)'양자 연산 알고리즘(컴퓨Algorithms for Quantum Computation: Discrete Logarithms and Factoring)'란 논문을 통해, 큰 수를 소인수 분해(임의의 숫자가 주어졌을 때 이를 소수들의 곱으로 쪼개는 방식)할 때 양자컴퓨터가 일반 컴퓨터보다 훨씬 더 효율적이란 사실을 발표하면서부터이다.

지금까지 연구된 바에 따르면, 300자리 정도의 수가 주어졌을 때 기존 컴퓨터로 소인수 분해하는 데는 현재까지 알려진 가장 빠른 방법을 이용한다고 하더라도 우주의 나이보다 긴 시간이 필요하다고 한다.

즉 5와 3의 곱셈을 계산하는 것은 쉬운 반면 반대로 곱해서 15가 될 수 있는 두 소수 5와 3을 구하는 것은 어려운데, 숫자가 클수록 계산하는데 걸리는 시간이 기하급수적으로 증가한다. 이를 'NP(Non-deterministic Polynomial Problem) 문제'라고 한다.

 

IBM이 개발한 양자컴퓨터. 출처=IBM
IBM이 개발한 양자컴퓨터. 출처=IBM

그런데 문제는 세계 최초의 공개키 암호이자 현재 인터넷 보안기술로 널리 활용되고 있는 'RSA 암호'가 바로 이 소인수 분해 문제와 깊은 관련이 있다.

1978년 로널드 리베스트(Ronald Rivest), 아디 샤미르(Adi Shamir), 레너드 애들먼(Leonard Adleman) 3명의 과학자는 RSA 암호를 발명한다. RSA 암호의 안전성은 큰 숫자를 소인수 분해 하는 것이 매우 어렵다는 전제에 기반을 두고 있는데, 임의의 정수를 이른 시간 안에 소인수 분해할 수 있는 양자컴퓨터는 RSA 암호를 무용지물로 만들 수 있다.

더욱더 우려스러운 것은 쇼어의 알고리즘은 양자컴퓨터로 이산 대수 문제(Discrete Logarithm Problem)를 단시간에 풀어냄으로써 ECDSA(Elliptic Curve Digital Signature Algorithm)와 같은 타원 곡선 암호를 깨는 데도 사용될 수 있다는 점이다.

 

양자컴퓨터를 막을 수 있는 '양자내성암호'

다행스럽게도 20168월부터 미국을 중심으로 전세계 암호학자들은 양자내성암호(PQC: Post-Quantum Cryptography)의 개발 및 표준화에 착수했다.

양자내성암호는 양자컴퓨터로도 풀기가 어렵다고 알려진 수학 문제에 기반해 만들어지기 때문에 RSAECDSA보다 안전하다.

 

양자내성암호 구조. 출처=퀀텀엑스체인지
양자내성암호 구조. 출처=퀀텀엑스체인지

한국에서는 고려대 정보보호대학원의 이동훈 교수 연구팀이 제안한 EMBLEMR.EMBLEM, 국가수리과학연구소의 심경아 박사팀이 제안한 HiMQ-3, 서강대의 김종락 교수팀이 제안한 McNie, 서울대의 노종선 교수 연구팀이 제안한 pqsigRM, 서울대 천정희 교수 연구팀이 제안한 Lizard 등이 있다.

쇼어 알고리즘과 더불어 암호학계에 큰 충격을 준 것은 '데이터베이스 검색을 위한 양자 역학 알고리즘(A Fast Quantum Mechanical Algorithm for Database Search)'란 논문을 통해 공개된 '그로버 알고리즘(Grover algorithm)'이다.

1996년 인도계 미국 컴퓨터 공학자인 로브 그로버(Lov Grover)는 양자컴퓨터 기반의 검색 알고리즘을 발명한다.

정렬되지 않은 데이터베이스(unstructured database)에 있는 N개의 항목 중 특정 조건을 만족하는 데이터를 찾는 경우를 상상해 보자. 기존 컴퓨터를 이용해 이 문제를 해결하려면 전수 조사(brute force search)가 유일한 해결책이며, 최악의 경우 대략 N(O(N))의 시도(검색)가 필요하다. 반면 양자컴퓨터로 그로버의 알고리즘을 적용하면 'N(O(N))'의 시도면 충분하다.

그로버 알고리즘은 AES(Advanced Encryption Standard)와 같은 대칭키 암호나 SHA-2(Secure Hash Algorithm 2), SHA-3(Secure Hash Algorithm 3)와 같은 해시 함수에 적용될 수 있다.

예를 들어 128비트 길이의 키(key)를 이용해 생성된 AES 암호문을 전수 조사만을 이용해 해독하려고 하는 경우, 일반 컴퓨터로는 최대 2128번의 시도를 해야 하지만 그로버 알고리즘을 사용할 경우 264번 만에 해독이 가능하다. 128비트 AES의 암호 강도가 지금은 폐기된 DES(Data Encryption Standard) 수준으로 떨어지는 셈이다.

다행히 AESSHA-2/SHA-3 등은 키 길이를 증가시킨다거나 또는 해시 함수의 출력 길이를 늘이면 쉽게 대처가 가능하다. 대칭키 암호의 경우 AES-256, 해시 함수의 경우 SHA-256 또는 SHA-384를 사용한다. 비트코인은 SHA-256을 사용한다.

양자컴퓨터 기술의 발전만큼이나 암호학계 또한 패러다임의 변화에 발 빠르게 대응해오고 있다. 영원히 안전한 보안이란 없다. 암호화폐와 블록체인도 마찬가지이며, 개인과 사회 그리고 기업과 정부가 꾸준히 연구하고 관심을 두며 미리 대비하는 자세가 필요하다.

김승주 교수는 2011년부터 고려대학교 정보보호대학원 교수로 재직했으며, 올해부터는 새롭게 사이버국방학과의 학과장을 맡고 있다. 교수 재직 전에는 한국인터넷진흥원(KISA)에서 암호기술팀장과 IT보안평가팀장으로 근무한 암호 보안 전문가다.

댓글삭제
삭제한 댓글은 다시 복구할 수 없습니다.
그래도 삭제하시겠습니까?

기사 댓글

댓글쓰기
계정을 선택하시면 로그인·계정인증을 통해
댓글을 남기실 수 있습니다.