4'00" 읽기
- 이메일, 온라인 쇼핑, 기타 디지털 통신 등 오늘날 대부분 데이터는 암호화되어 전송
- 일반적인 방법은 소수를 곱하여 생성된 큰 숫자가 키 역할을 하는 RSA 암호화
- 알고리즘은 Regev의 2048비트보다 최소 13배 적은 큐비트를 사용
- 양자 인수분해의 두 가지 장애물 극복

큐비트가 RSA 암호화를 해독할까?
새로운 양자 알고리즘은 일반적인 암호화 방법을 더 빠르고 경제적으로 해독한다.

암호화 기술이 보이나요?
지금까지 데이터 암호화는 양자 컴퓨터의 컴퓨팅 성능을 견뎌왔지만, 곧 바뀔 수도 있다. 미국 연구자들이 이제 일반 RSA 암호화의 양자 지원 크래킹을 더 빠르고 효율적으로 만드는 방법을 개발했다. Shor 알고리즘에서 요구하는 수백만 개의 큐비트와 오류 없는 양자 연산 대신 훨씬 작고 덜 완벽한 양자 컴퓨터로도 충분하다. RSA 암호화가 곧 종료될까? 

▲ 양자 컴퓨터는 이론적으로 RSA 암호화의 종말을 의미할 수 있다. 해당 양자 알고리즘은 얼마나 발전되어 있을까? © Bartholomiej Wroblewski/Getty 이미지

이메일, 온라인 쇼핑, 기타 디지털 통신 등 오늘날 대부분 데이터는 암호화되어 전송된다. 일반적인 방법은 소수를 곱하여 생성된 큰 숫자가 키 역할을 하는 RSA 암호화다. 선택의 폭이 넓기 때문에 이 숫자를 생성한 요소는 엄청난 계산 노력을 통해서만 결정될 수 있다. 이는 기존 컴퓨터에서는 거의 불가능하다.

Shor 알고리즘과 그 약점

그러나 양자 컴퓨터의 경우는 그렇지 않다. 큐비트는 양자 물리적 중첩 덕분에 수많은 잠재적 솔루션을 동시에 확인할 수 있기 때문에 적어도 이론상으로는 RSA 암호화가 더 해독 불가능하지 않다. 미국 수학자 피터 쇼어(Peter Shor)는 1994년에 이를 달성할 수 있는 알고리즘을 발표했다. “그게 전환점이 됐어요. 그러나 1994년에는 필요한 크기의 양자 컴퓨터를 만드는 방법을 아는 사람이 아무도 없었다”고 MIT(매사추세츠 공과대학)의 Vinod Vaikuntanathan이 설명했다.

문제:
Shor의 알고리즘은 비효율적이다. 현재 일반적인 2048비트 RSA 암호화를 해독하려면 약 2천만 개의 오류 없는 큐비트가 필요하다. 이는 큐비트의 오류 취약성 때문에 거의 불가능하다. Vaikuntanathan은 "어떤 사람들은 충분히 큰 양자 컴퓨터를 개발하는 것이 결코 불가능할 것이라고 생각하기도 한다"고 말했다. 실제로 대부분의 최신 양자 컴퓨터에는 수십 큐비트만 포함돼 있다. 현재까지 가장 큰 양자 컴퓨터에는 1,100큐비트가 있다.

새로운 방법은 더 빠르고 경제적이다.

또 다른 옵션이 있다. Vaikuntanathan과 그의 동료 Seyoon Ragavan은 이제 이를 사용했다. 그들은 Shor 알고리즘을 훨씬 더 빠르고 경제적으로 개선하는 방법을 개발했다. 이것의 출발점은 뉴욕대학교의 Oded Regev가 약 1년 전에 개발한 알고리즘이다. 이는 Shor의 알고리즘에 비해 암호화 코드 크래킹을 가속화할 수 있지만, 메모리보다 훨씬 더 많은 양자 비트가 필요하다.

이것이 바로 두 명의 MIT 연구원이 등장하는 곳이다. 그들은 이제 Regev의 접근 방식만큼 빠르지만 더 적은 큐비트가 필요한 솔루션을 개발했다. 그들의 양자 알고리즘에는 오류율을 줄이고 간섭에 대해 양자 계산을 더욱 강력하게 만드는 방법도 포함되어 있다. Vaikuntanathan은 “우리의 작업을 통해 실제 구현에 한 걸음 더 가까워질 수 있다”고 말했다.

▲ 일반적인 RSA 암호화의 기본은 두 개의 소수를 곱하여 생성되는 키다. 일반적인 2048비트 RSA 암호화를 사용하면 결과 숫자는 617자리가 된다. © HG: sakkmesterke/Getty 이미지

메모리 레지스터의 탁구

특히 새로운 방법에는 두 가지 접근 방식이 포함된다. 한편으로 두 명의 MIT 연구원은 제곱 작업의 필요성을 피했다. 2의 거듭제곱 계산은 직접적으로 되돌릴 수 없으므로 복잡하고 메모리 집약적이다. “우리는 피보나치 지수를 통해 이를 방지한다. 이 방법은 모듈러 제곱이 필요하지 않고 대신 모듈러 곱셈만 사용한다”고 Vaikuntanathan과 Ragavan은 설명했다. 이러한 유형의 수학적 행렬 지수화를 사용하면 지수화 계산을 보다 빠르고 효율적으로 수행할 수 있다.

양자 컴퓨터를 사용한 코드 크래킹의 경우 이는 다음을 의미한다. 암호화 코드를 인수분해할 때 계산해야 하는 각 지수에 대해 새 알고리즘에는 두 개의 양자 저장 장치만 필요하다. Vaikuntanathan은 "이것은 일종의 탁구 게임과 같다. 숫자로 시작한 다음 곱할 때 두 개의 양자 저장 레지스터 사이를 앞뒤로 이동한다"며 "결과적으로 우리 알고리즘은 Regev의 2048비트보다 최소 13배 적은 큐비트를 사용한다"고 설명했다.

오류가 차단된다.

두 번째 개선 사항은 오류 수정에 관한 것이다. Shor와 Regev의 양자 알고리즘의 경우 모든 양자 작업은 사실상 오류가 없어야 한다. 이는 가까운 미래에 실제로 구현할 수 없는 요구 사항이다. 물리학자들은 이미 양자 컴퓨터의 오류율을 줄이기 위한 몇 가지 방법을 개발했다. 기록적인 모델을 사용하더라도 신뢰성은 현재 약 35%에 불과하다.

두 명의 MIT 연구원은 특정 특성을 기반으로 큐비트 회로에서 잠재적으로 결함이 있는 출력을 식별하여 이 문제를 해결했다. Vaikuntanathan과 Ragavan은 "이를 바탕으로 손상된 장치를 감지하고 필터링하는 필터 절차를 개발했다"고 설명했다. "이것은 Regev의 알고리즘을 사용해 전통적인 후처리에 공급할 수 있는 온전한 단위 모음을 제공한다.“

양자 인수분해의 두 가지 장애물 극복

팀은 함께 양자 컴퓨터를 사용해 암호화를 해독하는 데 있어 두 가지 주요 장애물을 해결했다. Ragavan은 "그러나 가장 큰 문제는 이것이 RSA 암호화를 해독하는 데 더 가까워지는지 여부다. 우리의 개선 사항은 2048비트보다 큰 숫자에만 적용되기 때문에 지금까지는 이것이 완전히 명확하지 않다"고 말했다. 알고리즘이 일반적인 2048비트 숫자 키를 해독하기 위해 추가로 최적화될 수 있는지는 아직 밝혀지지 않았다.

그럼에도 불구하고 Regev는 RSA 암호화의 종말이 조금 더 가까워지고 있다고 믿는다. “두 연구원은 양자 인수분해에 대한 이전 알고리즘의 가장 중요한 두 가지 병목 현상을 극복했다”며 "그들의 작업이 아직 즉시 실용적이지는 않더라도 양자 분해를 현실에 더 가깝게 만든다"고 그는 말했다.
(2024 International Cryptology Conference; Preprint, doi: 10.48550/arXiv.2310.00899)
출처: MIT

[더사이언스플러스=문광주 기자]

[저작권자ⓒ the SCIENCE plus. 무단전재-재배포 금지]