쇼어알고리즘(Shor's Algorithm) - 양자컴퓨터는 이것으로 현대의 암호 방식을 무력화한다고?

양자컴퓨터가 세간의 관심을 끌어모은 가장 큰 이유는 아마도 현재 컴퓨터 암호화 기술이나 이를 이용한 암호화 통신기술에 거의 대부분 사용되는 RSA알고리즘을 기반으로 한 공개키암호화 방식을 단시간 내에 쉽게 풀수 있는 파괴적인 능력을 가지고 있다고 알려졌기 때문일 것이다.

 

RSA알고리즘의 기반이 되는 수학적 사실은 두 소수(prime number) p와 q를 곱하여 N이라는 정수를 만들었을 때, N이 충분히 큰 수라면 역으로 N을 소인수 분해하여 p와 q를 찾아내는 것은 매우 어렵다라는 것에 있다. 이 p와 q를 각각 공개키, 개인키로 사용하여 공개키는 말 그대로 공개되어 누구나 볼 수 있지만 이 공개키를 이용하여 어떤 문서를 암호화하면 이 암호화된 문서는 본인만 알고 있는 개인키를 이용해서만 풀 수 있다라는 논리이다.

 

예를 들어 두 소수 3,5를 곱하면 15라는 수를 구할수 있고 15를 소인수분해하면 3,5의 답을 쉽게 구할 수 있다.

하지만 두 소수가 각각

 

p = 5210644015679228794060694325390955853335898483908056458352183851018372555735221,

q = 531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728127

 

이런 수라면?

 

딱 봐도 불가능해 보이지 않는가? 위에 예를 든 q는 183자리 소수이다. 그런데 RSA 2048알고리즘은 약 617자리 숫자까지 표현할 수 있으므로 617자리 수를 소인수분해 하려면 왜 수퍼컴퓨터로도 몇천년이 걸린다고 하는지 짐작이 될 수 있을 것이다.

 

Peter Shor (news.mit.edu)

 

 

하지만 양자컴퓨터가 등장하기도 전인 1994년 미국 MIT공대의 수학과 교수 피터쇼어(Peter Shor)는 쇼어알고리즘을 공개하여 양자컴퓨터를 이용한다면 아무리 큰 수라도 쉽게 인수분해 할 수 있음을 증명하였다.

 

이 쇼어알고리즘이라는 것은 알고리즘 자체로는 그렇게 어려워 보이지는 않기 때문에 한 번 소개해 본다.(물론 그 내면에 숨어있는 수학적 원리는 매우 어려울 것이다.) 

 

쇼어 알고리즘은 두 소수로 곱해진 정수 N을 소인수 분해하는 과정이며 다음과 같은 절차를 거친다.  아래에서 등장하는 gcd(a,b)는 두 수의 최대공약수(Greatest Comon Divisor), a(mod b)는 a를 b로 나누었을때 나머지를 구하는 함수를 의미한다.

 

 

1. 1보다 크고 N보다는 작은 정수 a를 임의로 선택한다. (1 < a < N)

 

2. N과 a의 최대공약수 gcd(N,a)를 구해서 그 값이 이 1이 아니면 gcd(N,a)가 N의 소인수중 하나가 되어 소인수분해는 종료되고, 1이라면 함수 f(x) = a^x(mod N)의 주기 r을 찾는다.

 

예를 들어 a = 3이라면 gcd(15,3) = 3이므로 3은 15의 소인수가 맞고 소인수분해는 풀린 것이다. 나머지 하나의 소인수는 15를 3으로 나눈 5가 된다. 하지만 N이 충분히 큰 수일때 저렇게 한방에 바로 소인수분해가 완성될 정확한 숫자를 골라낼 확률은 로또에 당첨될 확률보다 작다. 

반면에 a = 4라면 gcd(15,4) = 1이다.

그렇다면, 함수 f(x) = a^x(mod N)의 주기 r을 찾는다.

mod란 나머지를 구하는 함수로 예를 들어 5(mod 2)은 5를 2로 나누었을 때, 몫은 2이고 나머지는 1이므로 함수 값은 나머지인 1이다.

 

 f(x) = a^x(mod N)의 주기 r을 찾는 과정을 보다 이해하기 쉽게 설명하자면 N=35, a=4일 경우를 가정하여 다음과 같이 전개해보면 된다.

 

4¹ ≡ 4(mod 35) -> 4의 1승은 4이고, 4를 35로 나누면 몫은 0이고 나머지는 4이다. ≡ 기호는 합동을 의미한다. (정수론에서 정수 a, b를 양의 정수 m으로 나눈 나머지가 같을 때, a와 b가 m을 법으로 하여 합동이라고 한다)

4² ≡ 16(mod 35)

4³ ≡  64 ≡ 29(mod 35)

4⁴ ≡ 256  ≡ 11(mod 35)

4⁵ ≡ 1024 ≡ 9(mod 35)

4⁶ ≡ 4096 ≡ 1(mod 35)

4⁷ ≡ 16384 ≡ 4(mod 35)

...

 

이런식으로 x에 1,2,3,4,5,... 를 계속 대입해서 풀어보면 4의 x승을 35로 나눈 나머지 값은 4,16,29,11,9,1,4,16,29,11,9,1,...과 같이 4,16,29,11,9,1 (붉은색으로 표현된 숫자들) 이 반복되며 나타나는 주기성을 갖게 되는데 하나의 주기에 포함되는 숫자가 총 6개이고 이 숫자가 r이 되는 것이다.

 

 

3. r이 홀수이면 1번부터 다시 시작하고 r이 짝수라면 gcd₁과 gcd₂를 구한다.

 

gcd₁ = gcd(N,a^r/2 + 1), gcd₂ = (N, a^r/2 -1) 이고

gcd₁과 gcd₂가 1과  N이 아니라면 gcd₁과 gcd₂가 N의 소인수이다.

 

위 2번의 예에서 r=6이고 6은 짝수이므로

gcd₁ = gcd(N,4^6/2 + 1) = gcd(35,65) = 5,

gcd₂ = gcd(N, 4^6/2 -1) = gcd(35,63) = 7

이렇게 35의 소인수인 5와 7이 구해지게 된다.

 

 

이런식으로 소인수분해가 가능하다니 참 신기하다.

그런데 이건 일반컴퓨터로도 가능한 연산 아닌가? 어떤 부분을 가지고 양자알고리즘이라고 하는 걸까?라는 질문을 할 수 있다.

 

"양자컴퓨터가 일반컴퓨터보다 월등한 부분을 갖는 부분은 바로 2번 f(x) = a^x(mod N)의 주기 r을 구하는 과정이다."

 

r을 구하려면 임의로 정한 수 a의 거듭제곱을 계속해서 수행해 나가야 하는데 일반컴퓨터로는 이를 수행하는데 걸리는 시간이 기하급수적으로 증가하기 때문에 그 한계를 극복하지 못하게 되는 것이다.

그렇다면 양자컴퓨터로는 어떻게 위 식의 값을 구하는가라는 부분 또한 궁금할텐데 사실 그 부분은 양자푸리에변환(QFT - Quantum Fourier Transform), 연분수 확장(Continued Fraction), Hadamard Gate, Toffoli Gate, CNOT Gate, Swap Gate의 양자게이트 등에 대한 고차원적인 수학적, 과학적 이해와 지식이 없이는 설명이 힘든 부분이다. 예를 들어 아래의 그림과 같은 양자회로도를 보고 이해할 수 있어야 한다. (사실은 본인도 잘 이해하지 못한다^^)

 

 

쇼어알고리즘을 구현한 양자회로도. (https://media.springernature.com/)

 

 

시간이 된다면 하나하나 파헤쳐보고 싶은 생각도 있지만 일단 저 부분을 양자컴퓨터가 일반컴퓨터보다 월등하게 빠른 시간내에 풀어낸다라는 사실만 알면 충분할 듯 하다.

 

다행(?)스러운 사실은 아직 현재의 양자컴퓨터 수준으로는 현존 최강의 수퍼컴퓨터보다 소인수분해를 빠르고 안정적으로 수행할 수 없다라는 것이다. 그만큼 양자컴퓨터를 구현하는 것이 극강의 난이도를 자랑하는 기술이라 할 수 있고 전문가들도 지금부터 대략 10년 정도 후에나 쓸만한 양자컴퓨터 구현이 가능할 것이라고 이야기하고 있다. 그리고 그 기간동안이라면 양자내성을 가진 암호화 알고리즘도 등장하게 될 것이다. 우리는 두려움보다는 편한 마음으로 세상의 첨단 기술이 발전해가는 과정을 지켜보면 되지 않을까 한다.