Offcanvas

보안 / 서버 / 신기술|미래

양자 컴퓨팅은 어떻게 암호화를 위협하는가

2022.05.25 Matthew Tyson  |  InfoWorld
양자 컴퓨팅은 여전히 이론적 추정과 실제 응용 사이의 모호한 영역에 머물고 있지만 실제 구현 쪽으로 조금씩 다가가고 있다. 양자 컴퓨터에서 많은 관심을 끄는 사용 사례 중 하나는 현대 인터넷 암호화다.
 
ⓒ Getty Images Bank
 

양자 컴퓨팅과 큐비트

양자 컴퓨팅이라는 이름은 이 기술이 거시 세계에 익숙한 보통 사람에겐 생소한 법칙으로 움직이는 아원자 입자의 속성에 의존한다는 데서 비롯됐다. 특히 양자 컴퓨터는 전통적인 컴퓨터 시스템의 2진 숫자(비트)가 아닌 큐비트(quantum bit의 줄임말)를 사용한다.

결정적 속성을 갖는 비트와 달리 큐비트는 확률적이다. 비트는 최종적으로는 물리적 스위치가 된다(나노미터 단위로 측정되는 매우 작은 스위치이긴 하지만). 비트는 2진이다. 즉, 온 또는 오프, 참 또는 거짓, 0 또는 1이다. 큐비트는 그렇지 않다. 큐비트의 물리적 기반은 전자의 회전, 광자의 편광과 같은 수많은 현상이 될 수 있다. 이것은 대단히 흥미로운 주제로, 상상과 현실 사이를 잇는 선형 방정식의 영역이다. 양자 역학은 기반 현실에 대한 설명이 아닌 해석으로 간주하며 그 계산 복잡도는 극한에 이른다.

큐비트의 상태는 가능한 두 상태의 선형적 중첩으로 설명된다. 이 상태가 관찰되면 참 또는 거짓으로 해석된다. 그런데 같은 입력이 항상 같은 출력으로 해석되지는 않으며, 관찰되지 않은 시점의 상태는 확률적 관점에서만 설명할 수 있다. 전통적인 물리학 관점에서 더 놀라운 점은 양자 컴퓨터의 큐비트는 동시에 여러 상태를 지닐 수 있다는 것이다. 컴퓨터가 큐비트의 상태의 표본을 뽑으면 상태는 하나의 either/or(이것 아니면 저것)로 해석된다(파동 함수 붕괴라고도 함).
 

암호에서의 양자 컴퓨팅

과학과 철학적 관점에서는 매우 재미있는 이야기다. 예를 들어 양자 컴퓨터가 기능한다는 것은 입자에 대한 관찰의 효과를 입증하며 신이 우주로 주사위 놀이(확률 게임)를 하고 있을지도 모른다는 생각이 들게 한다. 그러나 우리의 관심사는 일상의 실질적인 측면에서 양자 컴퓨팅의 발전이 우리에게 미치는 영향이다. 그리고 미래에 양자 컴퓨터의 파급력이 가장 클 분야는 암호가 될 가능성이 크다.

양자 컴퓨팅과 암호의 관계에서 가장 잘 알려진 이야기는 1994년의 중대한 이론적 업적인 쇼어 알고리즘이다. 이론적으로 이 알고리즘은 기존 컴퓨터로는 풀기가 어려웠던 문제, 즉 큰 정수의 인수분해를 양자 튜링 기계가 효율적으로 풀 수 있다는 것을 보여줬다. 디피-헬만(Diffie-Hellman), RSA와 같은 비대칭 암호 시스템 알고리즘에 익숙한 사람이라면 잘 알겠지만 이러한 알고리즘은 큰 수의 인수분해가 어렵다는 점에 기반을 둔다. 그런데 양자 컴퓨팅이 이 어려운 문제를 해결한다면 어떻게 될까?
 

양자 역학을 사용한 큰 정수 크랙

쇼어 알고리즘과 그 외의 여러 알고리즘은 비대칭 암호화의 중심에 있는 일방함수를 크랙하기 위해 양자 역학을 사용한다. 단열 양자 계산도 예전부터 인수분해를 공격하는 데 사용되고 있다.

쇼어와 기타 알고리즘은 큐비트를 통해 여러 상태를 지닐 수 있는 양자 컴퓨터의 능력에 의존한다. 이와 같은 큐비트를 높은 확률이 가능한 방식으로 샘플링한다(샘플링하면 상태가 축소됨). 사실상 “어떤 수의 인수는 무엇인가?”라는 질문을 입자 속성이 여러 상태로 존재할 수 있는, 누구도 본 적이 없는 미지의 세계로 떠넘기는 것이다. 그런 다음 이러한 속성을 쿼리해 가장 가능성 높은 답을 얻는다(믿기 어렵지만 이 방식이 실제로 동작한다).

현재까지 쇼어 알고리즘에 의해 인수분해된 가장 큰 수는 21이다. 단열 양자 계산은 143을 성공적으로 인수분해했다. 이와 같은 알고리즘은 정교하고 인상적이지만, 지금까지 보여준 수치는 보잘것없다. 현재 RSA의 표준은 2,048비트인데 자릿수로는 617이다! 다만 143을 공략하는 동안 연구원은 적어도 이론적으로는 더 큰 수의 인수분해도 가능한 접근 방법을 자신들도 모르게 찾아냈다. 예를 들어 56,153이 그 수다. 그런데 이 수도 실제 사용되는 암호화 시스템을 붕괴시키는 데 필요한 수에 비하면 작다. 또한 여기에 필요한 축소 기법이 모든 수에 다 적용되는 것도 아니다.
 

웹 보안 인프라에 대한 위협

지금 우리가 아는 것은 비대칭 알고리즘에 대한 양자 공격의 기반이 점점 모양을 갖춰 나가는 중이라는 것이다. 훨씬 더 큰 수에 접근할 수 있는 지점까지 기술이 발전하는 데는 얼마나 걸릴까? 흥미로운 점은 우리가 매일 사용하는 AES와 같은 대칭 알고리즘이 양자 알고리즘에 대해 그렇게 취약하지는 않다는 사실이다. 그로버(Grover) 알고리즘이 여기에 해당한다. 256비트 키가 사용된다는 전제로 이러한 알고리즘을 공격하는 데 필요한 시간을 전통적인 알고리즘보다 더 줄이는 것은 이론적으로도 불가능하다.

그런데 대칭적으로 보호되는 통신의 대부분은 비대칭적 교환을 통해 키를 설정한다. 따라서 오늘날 대부분의 웹 트래픽은 첨단 양자 컴퓨팅 공격에 취약하다. 상호작용이 시작되는 시점에 설정된 키를 공격자가 발견할 수 있다면, 대칭 암호화를 아무리 많이 해봐야 소용이 없다.

따라서 웹 보안 인프라에 대한 위협은 현실이다. 여기에 작용하는 역학에 대해 잠깐 생각해 보자. 가장 먼저 고려할 것은 순수한 경제성과 접근성이다. 지금으로서는 돈이 넘쳐나는 기업만 이러한 기술에 접근할 수 있다. IBM, 구글, 그리고 중국의 연구자는 실용적인 시스템 생산에서 앞서가기 위해 경쟁 중이며 대학의 연구도 다양하게 진행되고 있다. 물론 드러나지는 않지만 미국 국가 안전국(NSA)과 같은 정부 기관도 가만히 있지는 않을 것이다. 실제로 NSA는 공개 암호화와 양자 컴퓨팅을 독자적으로 연구하고 있다.
 

양자 컴퓨팅에 대한 보안의 발전

적은 인원의 그룹이 현대의 비대칭 키를 공격하는 데 충분할 만큼의 양자 컴퓨팅 역량을 확보하는 시점은 대기업이 이룬 한참 이후가 될 가능성이 높다. 이 말은 보안 인프라가 긴 시간에 걸쳐 양자 컴퓨팅의 역학에 대응해 발전하게 될 것이란 의미다. 정말 암호화를 무력화하는 양자 기계가 언제 등장할지는 아무도 모르지만, 어쨌든 등장할 가능성은 높아 보인다. 이 질문에 대한 답을 가늠하기 위한 두 가지 지표는 시스템의 큐비트 수와 수명이다.

큐비트는 결어긋남(decoherence)이라는 현상에 취약하다. 엔트로피는 항상 전자와 광자의 섬세한 조화를 흩트린다. 문제는 큐비트의 수와 수명 모두 수량화하기 어렵다는 점이다. RSA 2048 키에 대한 현실적이고 재현 가능한 공격에 필요한 큐비트의 수는 몇 개일까? 몇십 개라는 사람도 있고 몇백만 개라는 사람도 있다. 얼마 동안의 결맞음(coherence)이 필요할까? 몇백 나노초라는 사람도 있고 몇 분이라는 사람도 있다. 게다가 이런 모든 이야기는 앞서 언급한 전처리 알고리즘의 교묘한 사용을 통해 뒤집어질 수 있다. 어느 영리한 대학생이 지금 당장 새로운 접근 방법을 생각해 내지 말란 법이 없다. 양자 기계에서 143을 인수분해한 사람들은 자신들이 사실은 56,153도 크랙했다는 사실을 2년이 지나도록 몰랐다.
 

포스트 양자 시대의 암호화

모든 길은 포스트 양자 세계를 향하고 있으며 많은 사람이 이미 그 분야에서 열심히 연구하는 중이다. 미국 국립 기술 표준원은 양자 저항 알고리즘 개발 대회를 주최했고, 일부는 이미 성과를 거두고 있다. 현실 세계에서의 성과가 점차 늘고 있는 것을 보면 양자가 가진 암호에 대한 위협은 실재한다고 말할 수 있다. 그러나 지금으로서는 대항력에 의해 충분히 상쇄가 가능하다. 궁극적으로는 오랫동안 애용된 몇몇 알고리즘에 작별을 고해야 하겠지만 새로운 알고리즘이 나와 그 자리를 채우게 된다. 앞으로 10년 동안 이런 과정을 지켜보는 일은 흥미로울 것이다.
editor@itworld.co.kr
CIO Korea 뉴스레터 및 IT 트랜드 보고서 무료 구독하기
추천 테크라이브러리

회사명:한국IDG 제호: CIO Korea 주소 : 서울시 중구 세종대로 23, 4층 우)04512
등록번호 : 서울 아01641 등록발행일자 : 2011년 05월 27일

발행인 : 박형미 편집인 : 천신응 청소년보호책임자 : 한정규
사업자 등록번호 : 214-87-22467 Tel : 02-558-6950

Copyright © 2024 International Data Group. All rights reserved.