양자컴퓨터와 보안 위협 (쇼어 알고리즘)

양자컴퓨터

기존 컴퓨터는 트랜지스터로 이루어져 있고 

전기가 흐르냐 안흐르냐에 따라 0과 1로 데이터를 다룬다.

그런데 기술의 발전으로 트랜지스터가 점점 작아지고 나노미터단위가 되면서 

양자 영역으로 진입하게 되었고, (원자 한개가 0.1 나노미터) 

트랜지스터의 채널과 절연막의 두께가 전자의 파동이 미치는 범위만큼 얇아지면서

전자가 벽을 뚫고 지나가는 현상이 발생하기 시작했다. 

(양자역학으로 인해 전자가 존재할 확률이 절연체 너머에서도 나타남)

따라서 스위치를 꺼도 전류가 흐르는 '누설 전류'가 발생하면서

스위치로서의 기능을 상실하기 시작하는데...

공상과학 소설에 등장하는 이야기 같지만, 양자 컴퓨터란 이렇게 

미시세계에서의 양자역학적 현상을 이용한 컴퓨터를 설계 및 계산하는 것이고, 

따라서 양자역학적 현상이 있는 원자, 빛, 스핀, 초전도체(전하량/위상) 등 

다양한 것을 활용해서 만들 수 있다

보통 양자컴퓨터는 미로를 예시로 든다. 

기존에는 손오공 한명이 길을 다 가보고 결과를 알았다면

양자컴퓨터는 손오공 한명이 분신술을 써서 동시에 계속 길을 찾고

막다른 길로 간 분신들은 서로 상쇄되어 사라지고, 

출구로 간 분신들만 서로 합쳐져서 정답일 확률이 극대화된다.

이걸 다시 정리하면 아래와 같다.

1. 큐비트(Qubit)에 자기장이나 레이저를 정밀하게 쏘아 상태를 변화 시키고, 기존 컴퓨터의 NOT, CNOT 같은 양자 논리 게이트를 구현

2. 양자 상태를 중첩시키고 간섭을 일으켜서 찾는 정답이 나올 확률을 증폭시킴

3. 양자를 관측하면, 중첩되어 있던 상태가 하나로 붕괴되면서 최종 결과가 나옴

수학적으로는 양자 푸리에 변환으로 풀게 된다.

이 수식에서 가장 중요한 부분은 자연상수 e가 허수 i를 지수로 가지고 있어서 

회전을 나타낸다는 점이다.

(e는 변화율이 자기 자신의 크기에 비례하는 자연계의 현상에서 비롯한 자연상수로, 

미분하면 자기 자신이 나와서 내 크기가 곧 내가 변하는 속도라는 의미를 가진다)

 

데이터를 일정한 각도로 계속 회전 시키다 보면 원래 위치로 돌아오는 '주기'가 생기고,

이 회전의 빈도를 측정하여 숫자의 소인수 분해나 복잡한 패턴을 쉽게 찾아낼 수 있다.

고전적인 이산 푸리에 변환은 

$$O(N^2)$$ 의 계산량이 필요하지만, (고속 푸리에 변환도 $$O((\N log N))$$ 

양자 회로에서는 이 '회전 게이트(Rotation Gate)'들을 중첩된 상태에 동시에 적용함으로써 

$$O((\log N)^2)$$ 

이라는 엄청난 속도 향상을 보인다.

즉, 슈뢰딩거의 고양이가 살아있을 확률을 최대한 높여 놓은 다음 상자를 여는 것과 비슷하다

결과를 모르는 상태에서 파동을 잘 간섭 시키고, 

알고리즘을 통해 관측하면 정답이 나올 확률을 수학적으로 최대한 높여 놓고 관측해서 

정답이 결정 되도록 하는 것이다.

만약 주기를 찾는다면, 주기와 일치하는 부분은 보강 간섭이 일어나게 하고 

나머지 오답은 상쇄되어 사라지도록 해서 데이터를 겹치도록 알고리즘을 구성한다면 

관측 순간 가장 크게 솟아오른 주기 값이 정답이 된다.

보안 위협 (쇼어 알고리즘)

양자컴퓨터는 중첩 상태에 있는 큐비트를 제어해서

 

답이 나올 확률을 높이는 방식을 사용한다. 

즉, 간단한 사칙연산을 예로 들면, 

10+20을 계산하면 30이 나올 확률이 95%, 29가 나올 확률이 5% 

이렇게 계산 결과가 확률로 나온다.

그럼 양자컴퓨터를 왜 쓸까? 이제 왜 쓰는지 그 특별한 이유를 알아보자.

비대칭키 암호화 중 RSA는 큰 수의 소인수 분해가 어렵다는 수학적 난제를 이용하는데,

두 소수의 곱으로 이루어진 큰 수 N만 아는 상태라면,

N을 만들 때 곱셈에 사용된 두 소수의 값을 알 수 없다는 점을 이용한다.

 

하지만 쇼어 알고리즘은 양자컴퓨터가 잘 풀 수 있는 형태로 이 문제를 변환한다.

1. 1보다 크고 N보다 작은 작은 정수 a를 임의로 선택

2. gcd (N,A)가 1이 아니면 gcd (N, a)가 N의 소인수이다

1이라면, 함수 

$$f(x) = a^x (mod N)$$

의 주기 r을 찾는다.

3. r이 홀수이면 1번부터 다시 시작하고, r이 짝수이면 다음과 같은 gcd1, gcd2 를 구한다.

$$ gcd_1 = gcd(N, a^{r/2} +1) $$ 
$$ gcd_2 = gcd(N, a^{r/2} -1) $$

4. gcd1, gcd2 이 1과 N이라면 처음부터 다시 시작하고, 아니라면 gcd1, gcd2 가 N의 소인수이다.

어려워 보이지만, 예를 들어 35를 소인수 분해 해보면, 

1. a를 4로 무작위로 잡는다.

2. gcd(35,4) = 1 이므로, 주기 r을 찾는다.

 

$$ 4^1 \equiv 4 (mod35) $$ $$ 4^2 \equiv 16 (mod35) $$

$$ 4^3 \equiv 64 \equiv 29 (mod35) $$

$$ 4^4 \equiv 29*4 = 116 \equiv 11 (mod35) $$

$$ 4^5 \equiv 44 \equiv 9 (mod35) $$

$$ 4^6 \equiv 36 \equiv 1 (mod35) $$

$$ 4^7 \equiv 4 (mod35) $$

3. 6번 만에 주기를 찾았으므로, r=6. 그리고 r이 짝수이므로, 

$$ gcd_1 = gcd(35, 4^{6/2} +1) = 5 $$

$$ gcd_2 = gcd(35, 4^{6/2} -1) = 7 $$

4. 35의 소인수는 5, 7이다.

그래서 원래 소인수 분해 문제는 소수를 하나씩 다 대입해보는 문제이고, 

이 주기를 찾는것도 원래는 하나씩 다 해봐야 한다.

즉, N이 35라면 34는 100010이므로,

일반 컴퓨터라면 6개의 비트를 사용해서 대략 2의 6승에 해당하는 

계산을 수행 해야 한다. (GNFS 같은 최적 알고리즘도 있으나 그래도 훨씬 느림)

하지만 양자 컴퓨터로는 6개의 큐비트를 중첩해서 (000000 ~ 111111)

$$a^x \equiv 1 (mod35) $$ 가 되도록 하는 x를 타겟해서 쉽게 찾을 수 있는 것이다.

즉, 문제가 주기를 찾는 깔끔한 문제로 떨어지기 때문에,

양자 컴퓨터는 이 문제를 매우 쉽게 해결 하는 것이 가능하다.

그런데 알다시피 거의 모든 암호학에서 RSA, DH, 타원곡선류 문제를 사용하고 있는데, 

소인수분해 문제 뿐만 아니라 이산대수나 타원곡선 문제도 쇼어알고리즘으로

주기를 찾는 문제로 변환할 수 있어서 

현재 금융을 포함한 모든 보안이 양자 컴퓨터에 위험한 상태이다.

다음 시간에는 이 위험한 보안 문제를 어떻게 격자 암호를 통해 해결 할 수 있을지 확인 해 보자.