elliptic.w

@s Int int
@s Reader int
@s WaitGroup int

\input kotexgweb
\input pic

\def\title{나의 타원곡선 답사기}

@* 여행 배낭을 꾸리며.
이 문서는 타원 곡선을 스스로 익히려고 쓴 답사기다. 목적지는 두 곳이다.
하나는 곡선 위의 점을 세는 {\it Schoof 알고리즘}---순수 수학이 어떻게 다항
시간 마술을 부리는지 보여 주는 봉우리이고, 다른 하나는 그 곡선을 무기로
쓰는 {\it 타원 곡선 암호}---이산 로그의 어려움 위에 세운 서명 ECDSA다.
가는 길에 유한체, 다항식과 그 빠른 곱셈(NTT), 나눗셈 다항식, 이산 로그
공격 삼종을 차례로 지난다.

답사에는 사연이 있다. 전에 같은 것을 |math/big|만으로 짰더니 Schoof가
너무 느려, 60비트 소수 하나 세는 데 밤을 새웠다. 그래서 이번 판은 점 세기
엔진을 통째로 |uint64| 산술 위에 다시 세우고 다항식 곱셈에 수론적
변환(NTT)을 얹었다---학습용 장난감치고는 제법 이빨이 있다. 하지만 이 글의
진짜 목적은 속도가 아니라 이해다. 그래서 함수 하나하나에 ``무엇을''과 함께
``왜''를 적으려 했고, 곡선의 역사와 뒷이야기도 곳곳에 끼워 넣었다.

@ 프로그램은 한 \GO/ 패키지 |elliptic|으로 나온다. \.{gtangle}하면 주
출력 \.{elliptic.go}와 시험 파일 \.{elliptic\_test.go}가 함께 떨어진다.
층은 아래에서 위로 쌓인다.

$$\vbox{\halign{\indent#\hfil&\quad#\hfil\cr
{\bf 유한체}&    |uint64| 위의 $F_p$ 산술\cr
{\bf 다항식}&    $F_p[x]$와 NTT 빠른 곱셈\cr
{\bf 타원 곡선}& |big.Int| 위의 군 법칙 (그림과 함께)\cr
{\bf 나눗셈 다항식}& 등분점을 붙드는 $\psi_n$\cr
{\bf Schoof}&    프로베니우스로 점 세기\cr
{\bf 이산 로그}& Shanks, Pollard $\rho$, Pohlig--Hellman\cr
{\bf ECDSA}&     secp256k1 위의 서명\cr}}$$

낮은 두 층(유한체·다항식)은 속도가 생명이라 힙을 꺼리는 |uint64|로 짜고,
높은 층(곡선·암호)은 256비트 수를 다뤄야 하니 |big.Int|로 짠다. Schoof는
이 두 세계에 다리를 놓아, 큰 곡선의 문제를 작은 체의 빠른 산술로 푼다.
@c
package elliptic

import (
	"errors"
	"io"
	"math/big"
	"math/bits"
	"sort"
	"sync"

	"crypto/rand"
)

@<유한체@>@;
@<다항식@>@;
@<타원 곡선@>@;
@<나눗셈 다항식@>@;
@<Schoof 알고리즘@>@;
@<이산 로그 문제@>@;
@<ECDSA@>@;

@ 시험 파일은 패키지 안에서 돌며 내부 함수까지 들여다본다. 각 장이 제
시험을 \.{elliptic\_test.go}에 조금씩 보태므로, 여기서는 임포트만 모아
둔다. 무작위성은 재현 가능하도록 씨앗을 고정한 |math/rand/v2|의 PCG를 쓰되,
암호 연산(키 생성·서명)만은 진짜 |crypto/rand|를 쓴다.
@(elliptic_test.go@>=
package elliptic

import (
	"crypto/rand"
	"crypto/sha256"
	"math/big"
	mrand "math/rand/v2"
	"testing"
)

@i fp.w
@i poly.w
@i curve.w
@i divpoly.w
@i schoof.w
@i dlp.w
@i ecdsa.w

@* 짐을 풀며.
짐을 풀 때가 되었다. 시계 산술에서 출발해 비트코인의 곡선에서 서명을
받아 들었으니, 여정치고는 제법 멀리 왔다.

돌아보면 같은 얼굴을 여러 고개에서 만났다. 현-접선 공식은 곡선 장에서
수를 받아 점을 더하더니, Schoof 장에서는 다항식을 받아 사상을 더했다 —
옷만 갈아입은 같은 기하다. 중국인의 나머지 정리는 세 번 나왔다: NTT의
계수를 꿰맬 때, $t\bmod\ell$ 조각들을 이을 때, Pohlig--Hellman이 훔친
조각들을 맞출 때. 큰 문제를 작은 조각으로 쪼개 각개격파하고 도로 꿰매는
이 한 수가 이 답사기의 숨은 주인공인 셈이다. 페르마의 작은 정리는
역원이 필요한 곳마다 궂은일을 도맡았고, Pollard의 $\rho$는 이산 로그와
인수분해 양쪽에서 같은 곡조를 불렀다. 그리고 배운 것 하나---수학이 방패와
창을 가리지 않는다는 것. 점을 세던 프로베니우스와 위수를 쪼개던
Pohlig--Hellman은 적이 아니라, 좋은 곡선을 고르는 한 저울의 두 접시였다.

속도에 관한 교훈은 몸으로 얻었다. |math/big|으로 며칠 밤을 새우던 점
세기가 |uint64|와 NTT 위에서는 차 한 잔 식기 전에 끝난다. 알고리즘의
점근 기호가 같아도 상수는 이렇게 다르다---힙에 눕는 수와 레지스터를
달리는 수의 차이를, 표가 아니라 새벽으로 배웠다.

물론 지도에는 가 보지 못한 길이 더 많다. $\psi_\ell$을 작은 인수로 갈아
끼우는 Elkies와 Atkin의 지름길(SEA), 나눗셈을 아끼는 사영 좌표, 덧셈
공식에 예외가 없는 Edwards 곡선과 Curve25519, 두 곡선을 겹치는 페어링.
그리고 지평선 너머에는 Shor의 알고리즘이 있다---양자 컴퓨터가 서면 이산
로그는 다항 시간에 풀리고, 이 답사기의 암호 절반은 유적지가 된다.
그날이 와도 곡선 자체는 유적이 되지 않는다. 다음 세대 암호의 유력 후보
하나(아이소제니)가 다름 아닌 타원 곡선 사이의 길이니, 이 곡선과의 인연은
꽤 길게 갈 모양이다.

채트윈은 «송라인»에서 노래로 대륙의 길을 외는 사람들 이야기를 썼다.
조상들이 노래한 길을 따라 걸으면 사막에서도 길을 잃지 않는다던가.
문학적 프로그램도 결국 그런 것이라고 믿는다---코드만 남기면 사막이지만,
사연과 함께 남기면 길이 된다. 이 답사기가 누군가에게 그런 노랫길이기를.
$$y^2=x^3+Ax+B$$
끝으로, 여행 안내인 없이 이 길을 처음 낸 이들---Hasse, Schoof, Shanks,
Pollard, Koblitz, Miller---에게 답사객의 예를 표한다.

@* 찾아보기.