crossroads webzine

구글이 2024년 12월 초 양자컴퓨터인 윌로우칩을 공개하면서 정말 양자컴퓨터가 비트코인을 깰 수 있을 것인지 사람들의 궁금증이 커지고 있다. 기본적으로 비트코인의 암호화는 ECDSA (Elliptic Curve Digital Signature Algorithm)라는 타원곡선 기반의 암호 (Elliptic Curve Cryptography, ECC) 체계로 구성된다. 타원곡선은 실수 x와 y가 만들어내는 y² = x³ + ax + b 같은 함수다. 이 타원곡선 위에서는 일종의 '연산'이 가능하다. 타원곡선 위에 있는 임의의 두 점 P와 Q를 직선으로 이을 때, 그 직선이 타원곡선의 다른 지점에서 만나서 생기는 점의 x축 대칭점 R을 만드는 과정을 R = P*Q 같이 하나의 연산 ( * )로 생각해 보자. 이 연산은 어떤 특징이 있을까? 우선 P와 Q의 순서가 바뀌어도 그 결과는 같으므로, 연산 ( * )는 교환법칙이 성립한다. 또한 (P*Q)*T =P*(Q*T)가 성립하므로 결합법칙도 만족한다. 따라서 항등원과 역원도 정의할 수 있다.

타원곡선의 특징을 암호화에 어떻게 이용할 수 있을까? 타원곡선 상의 임의의 출발점 P (이를 ‘generator’라 한다.)과, 최종 도착점 R이 주어져 있다고 생각해 보자. 그렇다면 nP = P*P*...*P (n번 연산 반복) = R이라고 쓸 수 있다. 시작점 P가 주어져 있을 때 연산 횟수가 얼마나 크든, 유한 시간 안에 R을 찾을 수 있다. 예를 들어 227번 연산 반복을 생각해 보자. 이 연산을 훨씬 짧게 할 수 있는 트릭이 있다. P를 접점 삼아 타원곡선 위에서 연산을 n번 반복하면 2ⁿP를 얻는다. P에서 2ⁿP으로 가기 위해서는 2ⁿ번 연산을 반복하지 않고도, 단지 n번만 연산하면 된다. 예를 들어 227을 이진수로 표현하면 11100011이 되는데, 이는 2⁷P 연산 1번, 2⁶P 연산 1번, 2⁵P 연산 1번 등으로 구성될 수 있다는 것이다. 연산의 재활용까지 고려한다면 P에서 227P로 가기 위한 연산은 불과 총 9번으로 압축된다. 일반적으로 타원곡선 상에서 n번 반복 연산은 log₂n번에 수렴한다. 연산 횟수를 로그 스케일로 압축하는 장점은 연산 횟수라는 중요 정보를 알고 있는 경우에만 기대할 수 있다. 시작점 P에서 연산을 10⁸²번 반복하여 점 R을 얻었다고 가정해 보자. 그런데 만약 이 과정을 모르는 상황에서 타원곡선 파라미터 a와 b, 시작점 P, 그리고 최종점 R만 주어져 있다면 이 연산이 몇 번 반복되어서 P에서 R로 갔는지 알 수 있을까? 연산을 몇 번 반복했는지 파악하기 어려우니, 최악의 경우 1부터 시작하여 그 값이 나올 때까지 하나씩 계속 반복해서 돌려 봐야 한다. 이것만 놓고 본다면 타원곡선 위에서의 실수 좌표 반복 연산은 아주 좋은 암호 체계가 될 것 같다. 왜냐하면 시작점 P와 끝점 R, 그리고 타원곡선 파라미터 a와 b를 ‘공개키(public key)’로 설정해도, 유한 시간 안에 연산 반복 횟수 n을 발견하는 것은 사실상 불가능할 것이기 때문이다. 

그렇지만 '실수' 기반의 타원곡선 상 연산을 암호로 활용하기에는 몇 가지 문제가 있다. 가장 큰 문제는 이 연산을 컴퓨터로 반복해야 한다는 것이다. 디지털 컴퓨터는 2진수 기반으로 작동하므로 실수를 정확히 표현하는 것은 불가능하다. 0.3 같은 간단한 소수조차 2진수로는 0.0100110…같은 무한 소수로 표현되므로, 소수점 아래 적당한 자릿수에서 끊는 작업이 필요하다. 당연히 이 과정에서 오류가 발생한다. 또한 2진수 정보는 하드웨어 상의 메모리 공간이 필요한데, 여기에도 한계가 있다. 따라서 하드웨어에서도 연산이 반복되면 오차가 누적된다. 시작점 좌표를 임의의 실수로 정할 경우, 반복 연산하여 생성된 R의 좌표는 오차 누적으로 인해 당초 목표했던 값과 많이 틀어져 있을 것이다. 이래서는 믿을만한 암호 체계가 되기 어렵다. 실수 대신 자연수만 쓴다고 해서 문제가 해결되는 것은 아니다. 왜냐하면 애초에 타원곡선은 자연수 좌표로만 띄엄띄엄 이루어진 곡선이 아니기 때문이다. 

이 문제를 근본적으로 해결하기 위해서는 임의의 타원곡선에 대해 P, Q, R 등의 모든 x, y좌표가 무조건 자연수만 되게끔 만드는 방법이 필요하다. 이는 유한체(finite field)에서 정의되는 연산을 의미한다. 이를 위해 타원곡선 위에서 모듈러 p연산(mod p) 유한체를 생각할 수 있다. 예를 들어 타원곡선 y² = x³ + x에 대해, mod 23 연산을 적용해보자. x=11 이면 y² mod 23=8이다. 즉, x = 11에 대응되는 y 좌표는 y² mod 23=8을 만족하면서도 23보다 작은 자연수인 10과 13이다. 따라서 이 타원곡선 위의 mod 23 연산에 대응하는 유한체 요소에는 (11,10)과 (11,13)이 포함된다. 타원곡선 상의 모듈러 연산 유한체는 곡선 궤적으로 보이지만, p값이 커질수록, 유한체의 x좌표에 대해, y좌표 값을 예측하기 어렵기 때문에, 부드러운 곡선 궤적을 상상하는 어려워진다. 예를 들어, mod 19 연산의 경우, 시작점을 A = (3,2)으로, 두번째 점을 B = (5,18)으로 잡아보자. 이들을 이은 후, 모듈러 연산 특징을 이용하여 가로-세로 방향으로 무한히 주기적으로 반복되는 박스를 생각하여, 마침내 유한체 중 한 원소와 딱 만나는 점, R(예를 들어 이 사례에서는 (18,11) 같은 원소)을 찾을 수 있다. 타원곡선 상 유한체 연산을 반복하면 R의 좌표는 무조건 자연수가 되므로, 부동소수점 연산 오차가 방지된다.

이제 모듈러 연산 유한체 기반의 타원곡선 암호 원리를 알아보자. 출발점 P의 좌표로 이 유한체 중 한 점인 (3,6)을 잡고, 여기서 접선(2P = P*P 연산)을 그어 보자. P=Q인 경우, Q의 좌표를 계산하면 (80,10)이다. 연산을 계속하여 P*5P = 6P의 좌표는 (3,6), 즉, 원래의 자리로 되돌아온다. 즉, P->2P->…->5P->P 순환이 형성된다. 이러한 순환은 타원곡선 암호체계의 기반이 된다. 특히 순환 주기를 길게, 유한체도 크게, ‘mod의 법’도 큰 소수를 만들면 더 유리하다. 공개키로 타원곡선 파라미터 a와 b, 시작점 P, 끝점 Q를 설정하되, 타원곡선 유한체 위에서 모듈러 p 연산을 반복한 횟수를 감추면 된다. 타원곡선 모듈러 연산에서도 유한체와 소수 p가 충분히 크다면 이를 역추적하여 발견하는 것은 극도로 어렵기 때문이다. 따라서 Q를 암호화된 메시지로, 그리고 복호화 하려면 연산 반복횟수를 이용하면 된다. 예를 들어, 앨리스는 개인키(private key)로서 임의의 n을 이용, 특정 타원곡선 위의 유한체에서 모듈러 p연산을 통해 nP를 계산하고 공개한다. 밥도 개인키로서 임의의 m으로 mP를 공개한다. 앨리스는 밥에게 nP 좌표를, 밥은 앨리스에게 mP 좌표를 준다. 밥은 nP 좌표에 m 번을 연산해 (mn)P 좌표를, 앨리스도 mP 좌표에 n 번을 연산해 (nm)P 좌표를 얻는다. 둘 다 같은 좌표를 얻었으므로 이것이 비밀키가 된다. n이나 m은 매우 큰 소수이고, 유한체도 매우 커서 순환 주기가 매우 길어져, 역산 난도가 너무 높아지므로 외부의 해킹은 거의 불가능하다. 이러한 방식의 암호화는 효율성도 높다. 예를 들어 RSA기반 시스템은 80bit 크기의 암호문을 만들기 위해 1,024bit가 필요한데 반해, ECC 기반 시스템은 160bit만 있으면 된다. 256bit 크기라면 RSA는 13,560 bit나 필요하지만, ECC는 512bit만 있으면 된다. 이러한 효율성으로 인해 ECC는 블록체인 시스템, 디지털 서명 등에 활용된다.

(2부로 넘어갑니다.)