이 글은 제가 2020년 12월 14일 작성해서 제출했던 과제 제안서 중 학술적인 부분만 추린 글입니다.
1. 과제의 필요성
1.1.1. 양자 컴퓨팅 연구의 주요 이정표
1994년, AT&T Bell 연구소의 컴퓨터과학자인 피터 쇼어는 양자 컴퓨터를 이용하여 다항 시간에 소인수 분해와 이산 로그 문제를 해결하는 알고리즘을 발표[1-2, 3]하였다. 이는 전통적인 컴퓨터에서 기하급수적인 시간 복잡도를 가지는 것과 비교하여 더 효율적인 계산 방식이다. 또한, 1995년, 오류 없는 양자 컴퓨터를 개발하기가 어려운 현실을 다소 보완할 수 있는 양자 오류 정정 알고리즘[1-4]을 발표하였다. 현재 비대칭키 표준 암호 알고리즘인 RSA가 소인수 분해 문제의 어려움을 기반하므로, 쇼어 알고리즘은 일반적으로 양자 컴퓨터의 첫 번째 킬러 어플리케이션으로 알려져 있다.
1996년, AT&T Bell 연구소의 컴퓨터과학자인 로브 그로버는 양자 컴퓨터를 이용하여 정렬되지 않은 데이터베이스의 검색 속도를 루트 시간에 수행할 수 있는 알고리즘을 발표하였다. 이는 전통적인 컴퓨터에서 다항 시간 복잡도를 가지는 것과 비교하여 더 효율적인 계산 방식이며, 양자 컴퓨터의 두 번째 킬러 어플리케이션으로 알려져 있다.
2001년, IBM 알마덴 연구소의 리븐 벤더시펜은 7-큐비트의 핵자기공명 기반 양자 컴퓨터로 쇼어 알고리즘을 최초로 실현[1-6]하였다.
2016년, IBM은 양자 컴퓨터 클라우딩 서비스인 Quantum Experience를 출시하였다. 초기에는 5-큐비트 연산을 지원하였으나, 2017년에는 16-큐비트, 2020년 12월 현재는 53-큐비트까지 활용할 수 있다.
2018년, 미국의 물리학자 존 프레스킬은 50-큐비트 이상 규모의 양자 컴퓨터를 개발할 수 있다면, 오류 정정 알고리즘을 활용하여 양자 계산을 상용화할 수 있는 새로운 시대(NISQ era, Noisy Intermediate-Scale Quantum era)가 열릴 것으로 예상[1-7]하였다.
2019년, Google의 프랭크 알럿은 53-큐비트의 초전도체 기반 양자 컴퓨터를 이용하여 전통적인 슈 퍼컴퓨터에서 약 1만 년이 소요되는 연산을 200초에 수행했다고 발표하며, NISQ 시대의 시작과 양자 우월성(Quantum Supremacy)의 달성을 주장[1-8]하였다.
같은 해, IBM의 에드윈 페드널트는 Google에서 실험한 연산이 전통적인 슈퍼컴퓨터에서 2.5일이면 수행될 수 있으며, 2012년 프레스킬이 정의한 양자 우월성은 “양자 컴퓨터는 할 수 있으나, 전통적인 컴퓨터는 할 수 없는 일”이므로, Google의 양자 우월성의 달성을 부정[1-9]하였다.
1.1.2. 쇼어 알고리즘 관련 연구 현황
2001년, IBM에서 쇼어 알고리즘을 최초로 실현한 후, 이 알고리즘의 실현과 응용에 관한 다양한 연구가 진행되었다. 2005년, 에드워드 게르주이 등은 쇼어 알고리즘이 현재 인터넷에서 사용되는 보안 알고리즘에 영향을 주기 위해서는 키 길이의 두 배 크기의 큐비트 연산이 필요하다고 주장[1-10]하였다. 이는 쇼어 알고리즘의 위협을 축소하는 것으로 간주할 수 있다. 그러나, 2016년, 토마스 몬즈 등 은 이온 트랩 기반 13-큐비트 양자 컴퓨터에서 7개의 제어 큐비트와 4개의 캐시 큐비트를 활용하는 기법으로 쇼어 알고리즘을 실현[1-11]하며, 쇼어 알고리즘의 양적 확장성을 주장하였다. 다시 쇼어 알고리즘이 현대 암호에 위협이 될 수 있다는 의미로 해석할 수 있다. 반대로, 2019년, Google의 크레 이그 기드니 등은 양자 게이트의 오류율을 10-3 , 코드 순환 시간을 1마이크로초, 그리고 반응 시간을 10마이크로초로 가정하고, 잡음 등의 다른 요소들을 배제하였을 때 현재 권장되는 RSA 암호의 키 길 이인 2048bit 암호를 8시간 안에 깨는 데는 2천만 개의 큐비트가 필요하다고 주장[1-12]하였다. 이는 현대 사이버 보안에서 쇼어 알고리즘이 미치는 영향을 부정하는 것으로 이해할 수 있다. 이처럼, 쇼어 알고리즘이 현대 사이버 보안에 미치는 영향을 바라보는 관점은 낙관론과 부정론의 이견이 공존한다.
1.2. 연구 개발의 중요성
2016년, 미국 NIST는 대규모 양자 컴퓨터가 존재하면 쇼어 알고리즘으로 인해 RSA는 더는 안전하지 않다는 내부 보고서[1-13]를 공개하였다. 이 보고서에서 NIST는, 양자 컴퓨터의 두 번째 킬러 애플 리케이션인 그로버 알고리즘의 이차원 시간 성능 향상(quadratic speedup)은 단순히 AES와 같은 대 칭 키 암호 알고리즘의 키 길이를 두 배로 늘리고, SHA-2와 같은 해시 함수는 출력 길이를 두 배로 늘려서 대응할 수 있다고 말한다. 하지만, 쇼어 알고리즘의 급수적 성능 향상(exponential speedup)으 로 현재 비대칭키 표준인 RSA는 안전하지 않으며, 양자 컴퓨팅에 대한 더 많은 연구가 긴급하게 필요 하고, 향후 비대칭키 암호 알고리즘의 표준 전환을 대비하여 암호화 민첩성(crypto agility)를 강조하였다.
2020년 7월, NIST는 69종류의 차기 양자 후 비대칭키 암호 알고리즘 표준 후보 중 3차 심사를 통과한 4개의 알고리즘을 발표하였다. 하지만, 상기 NIST의 보고서[1-13]에서도 언급된 바와 같이, 지난 30여 년간 발전하여 오늘날 널리 사용되고 있는 TLS, PKI, IKE 등 다양한 통신 보안 체계가 RSA에 의존하고 있으며, 양자 후 비대칭키 암호 표준으로 손쉽게 교체(drop-in replacement)되는 것은 불가능 하다. 따라서 NIST에서 강조한 암호화 민첩성에는 상당한 저항이 예상된다.
과거에는 양자 컴퓨팅에 대한 접근이 어려웠으나, 최근에는 빠르게 상용화되고 있다. 상기 기술한 IBM에 이어, Microsoft는 2020년 1월, 양자 컴퓨터 클라우딩 서비스인 애저 퀀텀(Azure Quantum)을 발표[1-14]했다. 이어서, 2020년 8월, Amazon도 초전도체 기반 양자 컴퓨터 회사인 Rigetti, 이온 트랩 방식의 양자 컴퓨터 회사인 IONQ, 양자 어닐링 기반 양자 컴퓨터 회사인 DWave 사의 기술을 제공하는 클라우딩 서비스인 아마존 브라켓(Braket)을 발표하였다.
쇼어 알고리즘의 위협성 평가는 이견이 공존하고, 양자 컴퓨터는 빠르게 발전하고 있으며, 클라우딩 서비스를 통해 점점 보편화하고 있다. 하지만, NIST는 추가 연구와 암호화 민첩성을 강조할 뿐 명확한 위협 수준과 현대 사이버 보안 체계가 양자 후 암호(Post Quantum Cryptography) 체계로 전환하는 타임라인을 제시하지 못한다. 이 연구는 현대 양자 컴퓨팅을 기반으로 쇼어 알고리즘이 현대 사이버 보안에 미치는 실질적인 영향을 분석하고, NIST에서 요구하는 암호화 민첩성에 관한 판단의 기준을 제시할 것이다.
* 참고
[1-1] Richard P. Feynman, “Simulating physics with computers”, Int. J. Theor. Phys, 1982
[1-2] Peter W. Shor, “Algorithms for Quantum Computation : Discrete Logarithms and Factoring”, IEEE, 1994
[1-3] Peter W. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”, SIAM, 1997
[1-4] Peter W. Shor, “Scheme for reducing decoherence in quantum computer memory”, SIAM, 1997
[1-5] Lov K. Grover, “A fast quantum mechanical algorithm for database search”, IEEE, 1994
[1-6] Lieven M. K. Vandersypen et al, “Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance”, Nature, 2001
[1-7] John Preskill, “Quantum Computing in the NISQ era and beyond”, Quantum J., 2018
[1-8] Frank Arute et al, “Quantum supremacy using a programmable superconducting processor”, 2019
[1-9] Edwin Pednault et al, “Quantum Computing On Quantum Supremacy”, IBM Research Blog, 2019, https://www.ibm.com/blogs/research/2019/10/on-quantum-supremacy/
[1-10] Edward Gerjuoy , “Shor’s factoring algorithm and modern cryptography. An illustration of the capabilities inherent in quantum computers”, American J. of Phy., 2005
[1-11] Thomas Monz et al, "Realization of a scalable Shor algorithm", Science, 2016
[1-12] Craig Gidney, “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits”, 2019
[1-13] NIST, “Report on Post-Quantum Cryptography”, NISTIR 8105, 2016
[1-14] ZDNet Korea, https://zdnet.co.kr/view/?no=20200130140036
2. 과제의 목표 및 내용
2.1. 최종 목표
양자 컴퓨터 클라우딩 서비스를 이용한 쇼어 알고리즘의 RSA 알고리즘 공격 실증 및 최적화 가능성 연구
2.2. 연구 범위
최종 목표 달성을 위해 아래와 같은 연구 주제를 목표로 한다.
- 양자 컴퓨터 클라우딩 서비스의 활용 방법 분석 및 쇼어 알고리즘의 구현
- 양자 컴퓨팅과 전통적인 컴퓨팅에서 쇼어 알고리즘 동작 비교 분석
- 양자 컴퓨팅의 쇼어 알고리즘을 통한 RSA 알고리즘 공격 실증 및 최적화 가능성 연구
2.3. 연구 내용
2.3.1. 양자 컴퓨터 클라우딩 서비스의 활용 방법 분석 및 쇼어 알고리즘의 구현
양자 컴포저는 드래그 엔 드롭 방식의 GUI를 제공하는 양자 컴퓨팅 인터페이스이다. 상단에는 연산에서 사용할 수 있는 게이트들이 나열되어 있다. 아래 그림2는 두 개의 큐비트를 초기화하고, 하다마드 게이트와 CNOT 게이트를 적용한 후, 고전 레지스터에 각 큐비트의 측정값을 기록하는 예제이다.
Qiskit은 IBM QX를 활용할 수 있는 Python 라이브러리이다. Python 이 설치된 환경에서 pip 툴을 이용하여 Qiskit을 설치하고, 버전을 확인할 수 있다. 아래 표2는 Windows 10의 콘솔에서 수행하였다.
Qiskit 라이브러리를 사용하기 위해서는 IBM QX 계정에서 API 토큰을 받아 활성화해야 한다. IBM QX 사이트에 회원 가입 후 account 페이지에서 Copy token을 누르면 API 토큰이 클립보드에 복사된다.
2.3.2. 양자 컴퓨팅과 전통적인 컴퓨팅에서 쇼어 알고리즘 동작 비교 분석
RSA 암호 알고리즘은 소인수 분해 문제의 어려움을 기반으로 한다. 소수 17과 23을 곱하는 데 필요한 시간은 몇 초에 불과하지만, 두 수의 곱인 391을 소인수 분해하기 위해서는 훨씬 더 많은 시간이 필요하다. 가능한 수를 모두 시도해보는 시행착오 방법을 이용했을 때, 자릿수를 4개에서 8개로 늘리면 계산 과정의 수는 대략 70번에서 5,000번으로 늘어나며, 5,000번의 계산을 4시간으로 가정할 때 16자리 수로 늘어나는 경우, 계산 시간은 약 2년이 된다. 최근 전통적인 컴퓨터는 1초 동안 1조 번의 계산을 수행하는 테라플롭스(Teraflops)의 성능을 가지고 있지만, 130자리 수를 갖는 소인수 분해는 약 42일이 소요되며, 자릿수가 2배가 되면 대략 100만 년 정도의 시간이 걸리고, 자릿수가 몇 개 더 늘어나면 계산 시간은 우주의 나이보다 길어질 수 있다[2-1].
소인수 분해 문제는 시행착오 방법이 아닌 푸리에 변환(Fourier transform)문제로 변형하여 접근할 수 있다. 푸리에 변환은 함수가 가진 주기성을 이용한다. 예를 들어, 다음과 같은 수열이 있는 경우,
1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, ...
숫자 4 다음에는 1이 될 것을 알 수 있는 데, 이는 수열의 주기가 4이기 때문이다. 소수 7의 지수로부터 유도되는 수열은 다음과 같다.
71 = 7, 72 = 49, 73 = 343, 74 = 2401, 75 = 16807, ...
위 수열에 각각 modulo 15를 적용하면 7, 4, 13, 1가 반복되며, 주기가 4 임을 알 수 있다. 즉, 수 a의 n 제곱 형태의 n에 따라 커지는 수열을 어떤 수 N으로 modulo 연산을 하면 수열 an mod N은 주기 r을 가지며, r이 짝수인 경우, 수 N의 소인수는 ar/2 + 1 과 N의 최대공약수와, ar/2 - 1 과 N의 최대공약수이다. 위 식에 대입하면, 수 15의 소인수는 74/2 + 1 = 50 과 N의 최대공약수, 74/2 – 1 = 48과 N의 최대공약수이고, N에 15를 대입하여 GCD(50, 15)와 GCD(48, 15)를 계산하면, 15의 소수는 5와 3임을 알 수 있다.
두 소수 p와 q의 곱으로 생성된 N을 소인수 분해하는 쇼어 알고리즘은 다음의 단계들로 요약할 수 있다[2-2].
Step1) 1보다 크고, N보다 작은 임의의 정수 a를 선택한다. 만일, GCD(N, a) ≠ 1 이면, p = GCD(N, a)이고, q = N / q 이다.
Step2) 함수 f(x)로 ax mod N 의 주기 r을 구한다. 주기가 짝수가 아니면 Step1 부터 다시 시작한다.
Step3) 주기 r로 두 개의 최대공약수 GCD(N, ar/2 + 1) 과 GCD(N, ar/2 – 1)을 구한다.
Step4) 두 최대공약수가 1과 N이라면, Step1부터 다시 시작한다.
표4. 전통적인 컴퓨터에서 쇼어 알고리즘의 구현
쇼어 알고리즘을 표4와 같이 Python으로 전통적인 컴퓨터에서도 구현[2-3]할 수 있다. 표4의 코드를 실행하면 라인 25의 결과는 출력되지만, 라인 28의 결과는 다소 시간이 소요된다. 12번 라인에서 선택된 난수와 컴퓨팅 환경에 따라 상당히 긴 시간이 걸릴 수 있다. 코드에서 가장 많은 계산 시간을 차지하는 부분은 라인 6의 주기를 찾는 부분으로, 양자 컴퓨터에서 양자 푸리에 변환(QFT, Quantum Fourier Transform)을 이용하여 최적화할 수 있다. 일반적으로, 전통적인 컴퓨터에서 고속 푸리에 변환(FFT, Fast Fourier Transform)은 O(n log n)의 시간 복잡도[2-4]를 가지지만, 양자 푸리에 변환은 O(log n)의 시간 복잡도[2-5]를 가진다.
2.3.3. 양자 컴퓨팅에서 쇼어 알고리즘을 이용한 RSA 알고리즘 공격 실증 및 최적화 가능성 연구
쇼어 알고리즘은 QFT를 이용한 소인수 분해의 최적화 기법이지만, 이는 시간 복잡도(Time complexity)에 집중되어 있어서, 실질적인 RSA 알고리즘의 위협이 되기 위해서는 최소 세 가지 추가적인 관점이 고려되어야 한다. 첫 번째는 공간 복잡도이다. 양자 컴퓨터가 빠르게 발전하고, 클라우딩 서비스를 통해 진입장벽이 낮아지고 점차 보편화하여 가고 있지만, 양자 계산에 사용할 수 있는 큐비트의 수는 제한되어 있다. 두 번째 필수적인 고려 사항은 결잃음 시간(Decoherence time)이다. 양자 컴퓨팅과 전통적인 컴퓨팅의 대표적인 차이는 큐비트들의 중첩(Superposition)을 통한 병렬 연산이지만, 양자 컴퓨터의 큐비트들이 중첩을 유지하는 시간은 제한되어 있다. 마지막으로, 양자 컴퓨팅의 오류 보정이 고려되어야 한다. 큐비트는 일반적인 비트의 비트 플립에 추가하여 위상 플립(phase flip)의 오류도 영향을 받으며, 이는 양자 계산의 신뢰도를 위협할 수 있다. 일반적으로, 전통적인 컴퓨팅 수준의 신뢰할 수 있는 큐비트와 양자 연산을 가리켜 충실도(fidelity)라는 표현[2-6]을 사용한다.
결잃음 시간과 오류 보정이 필요하지 않다고 가정했을 때, RSA 알고리즘을 공격하기 위해 몇 개의 큐비트가 필요한지에 대한 정보는 이견이 공존한다. 유명 개발자 커뮤니티 중 하나인 StackOverflow 에서는 4N + 2개의 큐비트가 필요하다는 답변[2-7]이 있다. 반면에, StackExchange 에서는 2N + 2개의 큐비트가 필요하다는 답변[2-8]을 찾을 수 있다.
양자 컴퓨팅 환경에서 쇼어 알고리즘을 기반으로 RSA 알고리즘을 효과적으로 공격하는 다수의 연구가 최근까지 발표[2-9, 10, 11, 12]되고 있다. 따라서 이 연구는 현재 발표된 쇼어 알고리즘 최적화 연구들의 이론적 분석 및 양자 클라우딩 서비스를 이용한 실증과 추가적인 최적화 기법의 발견 가능성 연구를 목표로 한다.
* 참고
댓글 없음:
댓글 쓰기