쇼어 알고리즘과 양자 내성 암호
인터넷이 보편화되면서 로그인과 결제는 우리의 일상이 되었습니다. 이러한 인터넷 사용을 안전하게 하기 위해 암호가 쓰이는데요, 그런데 양자 컴퓨터가 상용화되면 이 암호 체계가 깨질 수 있다고 합니다. 그래서 양자 컴퓨터가 기존의 컴퓨터와 어떤 차이가 있어 암호 체계를 쉽게 깰 수 있는지 알아보고자 합니다. 또한 양자 컴퓨터를 이용해 우리가 사용하는 암호 체계를 깨는 알고리즘을 살펴보고, 양자 컴퓨터에도 안전한 암호 체계도 살펴보고자 합니다.
현재 우리가 인터넷에서 사용하는 암호화 방식에는 여러 가지가 있는데, 그 중 대표적인 것으로는 RSA 암호 체계가 있습니다. RSA 암호 체계는 큰 수의 소인수분해가 어렵다는 점을 이용한 암호 체계입니다. 즉, 큰 수를 빠르게 소인수분해 하는 방법을 찾으면 RSA 암호 체계를 깰 수 있습니다.
양자 컴퓨터는 쇼어 알고리즘을 통해 큰 수를 소인수분해 할 수 있습니다. 쇼어 알고리즘에 대해 알아보기 위해 편의상 두 개의 소수의 곱으로 이루어진 수를 소인수분해 하는 상황을 가정하겠습니다. 쇼어 알고리즘은 랜덤한 수를 고르고 그 수를 소인수가 될 것 같은 수로 바꾼 뒤 진짜 소인수가 맞는지 확인하는 과정을 반복하는 것입니다.
소인수분해 하고 싶은 수를 N이라고 하겠습니다. 예를 들어 N=35라고 하겠습니다. 우선 1부터 N 사이에 있는 수 중 아무 숫자를 하나 랜덤으로 선택하고 그 숫자를 g라고 합시다. 예시로 g=3이라고 하겠습니다. 그리고 N을 g로 나누고 만약 우연히 g가 N의 약수가 된다면 소인수분해가 끝납니다.
하지만 대부분은 g가 N의 약수가 아니고, 그때는 g를 계속 거듭제곱해 g2, g3, …을 구합니다. 우리의 예시에서는 3, 9, 27, 81, …을 계산합니다. 그 숫자들을 N으로 나눠 나머지를 구하면 나머지가 처음으로 1이 되는 순간이 생기는데, 그때 g를 거듭제곱한 횟수를 h라고 하겠습니다. 3을 12제곱했을 때 35로 나눈 나머지가 처음으로 1이 되므로 우리의 예시에서는 h=12가 됩니다. 정리하면, g - 1, g2 - 1, …, gh-1 - 1은 N으로 나누어떨어지지 않지만, gh - 1은 N으로 나누어떨어집니다.
여기서 h가 홀수라면 맨 처음으로 돌아가서 다시 1부터 N 사이에 있는 숫자를 랜덤하게 고르고 앞의 과정을 반복합니다. 만약 h가 짝수라면 합차 공식을 이용해 gh – 1을 (gh/2 – 1) (gh/2 + 1)로 쓸 수 있고, 이 수가 N으로 나누어떨어지게 됩니다. 우리의 예시에서는 312 - 1 = (36 + 1)(36 - 1)로 쓰게 됩니다.
만약 gh/2 – 1과 gh/2 + 1 중 하나가 N으로 나누어떨어진다면 다시 맨 처음으로 돌아가 g를 랜덤하게 고르는 것부터 시작합니다. 만약 gh/2 – 1과 gh/2 + 1 모두 N으로 나누어떨어지지 않는다면 gh/2 – 1과 gh/2 + 1 모두 N의 소인수를 약수로 갖게 되므로 gh/2 – 1과 N의 최대공약수, 또는 gh/2 + 1과 N의 최대공약수를 찾으면 N의 소인수가 되고 소인수분해가 끝납니다. 우리의 예시에서는 36 + 1과 36 - 1 모두 35로 나누어떨어지지 않으므로 36 + 1과 35의 최대공약수인 5와 36 - 1과 35의 최대공약수인 7이 N=35의 소인수가 됩니다. 최대공약수는 유클리드 알고리즘을 통해 빠르게 찾을 수 있다고 이미 알려져 있습니다. 또한, 앞에서 h가 짝수이고 gh/2 – 1과 gh/2 + 1 모두 N으로 나누어떨어지지 않는 상황을 생각했는데, 임의로 g를 고르면 1/2의 확률로 이런 일이 발생하게 되므로 2번 정도만 반복하면 소인수분해를 마칠 수 있습니다.[1]
이 알고리즘 자체는 양자 컴퓨터가 아닌 일반적인 컴퓨터로도 가능합니다. 하지만 랜덤하게 g를 골랐을 때 h를 찾기 위해서 일반적인 컴퓨터는 g를 계속 곱해야 하므로 매우 오랜 시간이 걸립니다. 양자 컴퓨터는 이 과정을 효율적으로 계산할 수 있습니다.
그 방법을 알아보기 전에 우선 g를 거듭제곱하는 과정의 주기성에 대해 살펴보겠습니다. f(x)를 gx을 N으로 나눈 나머지로 정의하겠습니다. 그러면 f(h) = 1이 되고, f(x+h)=f(x)f(h)=f(x)이므로 f는 주기함수임을 알 수 있습니다. 이제 우리는 양자 컴퓨터가 어떻게 함수 f의 주기를 빠르게 찾을 수 있는지를 생각해 보겠습니다.
그림1. 거듭제곱 함수의 주기성[2]
양자 컴퓨터에서는 큐비트라는 단위를 사용하는데 큐비트 하나당 0과 1 두 가지 값이 중첩되어 있습니다. 즉, 큐비트의 값을 실제로 확인하면 0 또는 1의 값이 나오는데, 확인하기 전까지는 특정한 하나의 값으로 정해져 있는 것이 아니라 0과 1 두 상태가 중첩되어 있고 관측할 때 하나의 값으로 정해지게 됩니다. 만약 큐비트가 n개 있다면 2n개의 상태가 중첩되어 있고, 이 상태를 0, 1, 2, …, 2n-1의 값들이 중첩되어 있다고 볼 수 있습니다. 양자 컴퓨터는 이 중첩된 값들을 동시에 계산하여 (0, f(0)=1), (1, f(1)=g), (2, f(2)=g2), …, (2n-1, f(2n-1)=g2^(n-1))으로 바꿀 수 있습니다. 이 상태에서 결과를 확인하면 2n-1개의 중첩된 상태 중 하나가 랜덤으로 나오기 때문에 아직은 주기를 알 수 없습니다. 하지만 그렇게 결과를 읽고 난 뒤에는 2n-1의 중첩된 상태 중 함숫값이 앞에서 읽은 결괏값과 같은 상태만 남게 됩니다. f는 주기가 h인 주기함수이므로 남아있는 상태들은 (a, f(k)), (a+h, f(k)), (a+2h, f(k)), …의 꼴이 됩니다. 여기서 주기를 알아내기 위하여 양자 푸리에 변환이라는 방법을 사용합니다. 각각의 상태 (a, f(k)), (a+h, f(k)), (a+2h, f(k)), …에 양자 푸리에 변환을 적용하면 각 상태가 2n개의 새로운 상태로 바뀌고 각각의 상태들에 의해 만들어진 새로운 상태들이 서로 간섭을 일으키면서 우리가 원하는 f의 주기를 빠르게 구할 수 있습니다. 이러한 방법으로 f의 주기를 구하게 되면 h를 얻게 되고, 앞에서 살펴본 쇼어 알고리즘을 통해 큰 수를 소인수분해 하게 되어 RSA 암호를 빠르게 깰 수 있습니다.
모든 암호체계가 양자 컴퓨터에 의해 쉽게 깨지는 것은 아닙니다. 일반적으로 사용되는 또 다른 암호화 체계인 AES는 양자 컴퓨터를 이용해 더 빨리 풀 수는 있지만 효율적으로 풀 수는 없기 때문에 키의 비트 수를 늘리는 방법을 통해 양자 컴퓨터에 대응할 수 있습니다. 예를 들어 128비트의 키를 사용할 경우 일반적인 컴퓨터에서의 안전성은 128인데 양자 컴퓨터에서의 안전성은 64로 줄어듭니다. 여기서 안전성이 128, 64라는 것은 암호를 깨기 위해 2128번, 264번 공격을 시도해야 한다는 뜻입니다.[3] 따라서 키의 길이를 2배로 늘리면 똑같은 128의 안전성을 확보할 수 있어 양자컴퓨터가 나오더라도 계속 사용할 수 있습니다.
그림2. 각 암호 체계의 안전성[4]
하지만 RSA의 경우 2048비트의 키를 사용하면 일반적인 컴퓨터에서의 안전성은 112인데, 양자 컴퓨터에서의 안전성은 25로 크게 줄어듭니다. 즉, 일반적인 컴퓨터로는 해독하는 데에 수십억 년이 걸리는 암호도 양자 컴퓨터로는 몇 분 안에 해독할 수 있습니다. 키의 길이를 8배 정도로 늘리더라도 양자 컴퓨터는 소인수분해를 효율적으로 하므로 안전성은 31로 큰 차이가 없습니다. 따라서 키의 길이를 늘이더라도 양자 컴퓨터에 의해 암호가 쉽게 깨지게 됩니다.
아직 양자 컴퓨터가 발전하지 않아 RSA 암호가 깨지지는 않았지만, 미래에 양자컴퓨터가 발전하여 암호가 깨질 것에 대비해 양자 컴퓨터로부터도 안전한 양자 내성 암호(Post Quantum Cryptography)가 연구되고 있습니다. 여기에는 여러 수학적 난제들을 이용하여 만든 후보들이 있는데 그 중 격자 이론을 이용한 암호가 대표적입니다.
그림3. 2차원 격자[5]
위 그림처럼 점들이 배열된 격자에서 가장 짧은 길이를 찾는 문제를 생각해 볼 수 있습니다. 격자들이 직사각형에 가깝게 배열되어 있으면 쉽게 풀 수 있겠지만 직사각형에서 멀어질수록 풀기 어려워집니다. 2차원의 경우에는 풀기 어려운 배열이라도 빠르게 풀 수 있지만 100차원 정도의 격자에서 가장 짧은 길이를 찾는다고 생각하면 양자 컴퓨터에게도 어려운 문제가 됩니다. 이러한 수학적 난제를 기반으로 하여 양자 컴퓨터로도 깰 수 없는 암호들이 연구되고 있습니다.
이렇게 양자 컴퓨터가 어떻게 현재의 암호 체계를 깰 수 있고 거기에 어떻게 대비하고 있는지를 살펴봤습니다. 우리가 매일 사용하는 인터넷의 안전성을 위해 끊임없이 연구하고 있는 암호학자들 덕분에 양자 컴퓨터가 상용화되더라도 우리는 안전하게 인터넷을 사용할 수 있을 것입니다.
References
[1] Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. Peter W. Shor.
[2] https://qiskit.org/textbook/ch-algorithms/shor.html
[3] Key Lengths: Contribution to The Handbook of Information Security. Arjen K. Lenstra.
[4] https://techbeacon.com/security/waiting-quantum-computing-why-encryption-has-nothing-worry-about
[5] https://en.wikipedia.org/wiki/Lattice_problem
Written by GLEAP 11기 서현우
Edited by GLEAP 학술팀·홍보팀
Comments