비밀키를 보여주지 않고, 이 코인이 네 것이라는 걸 어떻게 증명할까?

무엇이 참이어야 하는가

세 가지가 동시에 참이어야 한다. (a) 주어진 메시지에 대한 유효 서명은 오직 너만 만들 수 있다, (b) 누구나 그 서명을 확인할 수 있다, (c) 확인하는 과정에서 그 서명을 만들어낸 비밀이 드러나지 않는다. 어떤 비밀번호 방식도 이 셋을 다 만족시키지 못한다 — 비밀번호는 보여줘야만 확인되니까. 필요한 건 일방통행 함수다. 만드는 쪽으로는 쉽고, 거꾸로 되돌리는 쪽으로는 불가능하며, 그 둘을 깔끔하게 묶어주는 대수 항등식이 따라붙는.

일방통행 함수 — 곡선 위의 스칼라 곱셈

유한체 위의 타원곡선 $y² = x³ + 7$을 잡자. 이 곡선의 점들은 하나의 군을 이룬다. 임의의 두 점에 합이 정의되고, 그 합은 베주 정리를 떠받치던 바로 그 현·접선 작도로 구한다. 생성점 $G$를 하나 잡고 덧셈을 반복하면 스칼라 곱셈 이 된다: $kG = G + G + ⋯ + G$ (k번).

$(k, G)$에서 $kG$를 구하는 데는 약 $\log₂ k$번의 덧셈이면 충분하다 (배수-덧셈). 반대로 $(G, kG)$에서 $k$를 되찾는 건 이산 로그 문제다 — secp256k1 같은 암호용 곡선에서는 $\sqrt{n}$ ($n ≈ 2²⁵⁶$) 정도보다 빠른 알고리즘이 아직 없다. 모든 체계가 이 비대칭 위에 서 있다.

# Toy curve E: y² = x³ + 7 over F_17.
# Same shape (a=0, b=7) as secp256k1, microscopic prime.
P, A, B = 17, 0, 7
INF = None  # the point at infinity is the group identity

def add(P_, Q_):
    if P_ is INF: return Q_
    if Q_ is INF: return P_
    x1, y1 = P_; x2, y2 = Q_
    if x1 == x2 and (y1 + y2) % P == 0:
        return INF
    if P_ == Q_:
        lam = (3 * x1 * x1 + A) * pow(2 * y1, -1, P) % P
    else:
        lam = (y2 - y1) * pow(x2 - x1, -1, P) % P
    x3 = (lam * lam - x1 - x2) % P
    y3 = (lam * (x1 - x3) - y1) % P
    return (x3, y3)

def scalar_mul(k, P_):
    R = INF
    while k > 0:
        if k & 1: R = add(R, P_)
        P_ = add(P_, P_)
        k >>= 1
    return R

G = (1, 5)             # generator
N = 9                  # order of G — 9G = INF
scalar_mul(2, G)       # → (2, 10)
scalar_mul(3, G)       # → (5, 9)
scalar_mul(9, G)       # → None (= O)

키 — 누구나 만들 수 있지만 아무도 되돌릴 수 없는 한 걸음

임의 정수 $d ∈ {1, …, n−1}$을 하나 골라 비밀로 간직한다 — 이것이 개인키 다. $Q = dG$를 구해 공개한다 — 이것이 공개키 다. $d$에서 $Q$를 구하는 건 누구든 밀리초 안에 끝내지만, $Q$에서 $d$를 되찾는 건 이 우주의 누구도 해낼 수 없다.

위젯의 개인키 d 슬라이더를 움직이면 G는 그대로 있는데 Q가 곡선 위를 뛰어다닌다. ${1, …, 8}$의 $d$는 저마다 부분군의 다른 점에 가서 박힌다. 퍼즐 하나: 그래프 위 Q의 위치만 보고, 여덟 개를 다 대입하지 않은 채 $d$를 맞힐 수 있을까? 장난감 곡선에서는 가능하지만, secp256k1에서는 불가능하다.

서명 — 메시지에 묶고, 키는 숨긴다

메시지 해시 $h$에 대한 서명 은 두 수 $(r, s)$다. 매번 새로운 임의 nonce $k$를 뽑아 $R = kG$를 구하고, $r = R.x \mod n$, $s = (h + r·d) · k⁻¹ \mod n$으로 둔다. $k⁻¹$가 $d$를 가려준다 — $k$가 임의이고 비밀이면 $s$도 임의처럼 보인다. nonce가 없다면 같은 키로 만든 두 서명은 $d$에 대한 일차 연립방정식이 되어 누구나 풀어버린다.

위젯의 서명자 패널은 식을 실시간으로 보여준다. d, h, k를 움직이면 서명이 그 자리에서 다시 계산된다. 검증자 · h, (r, s), Q 만 본다 라고 표시된 줄이 곧 경계다 — 서명 장치 밖으로 나가는 것과 안에 남는 것을 가르는 선.

# Sign a message hash with private key d, nonce k.
def sign(d, h, k):
    R = scalar_mul(k, G)
    r = R[0] % N
    s = (h + r * d) * pow(k, -1, N) % N
    if r == 0 or s == 0:
        raise ValueError("retry with another k")
    return r, s

# Toy: d = 5 (private), h = 3 (message hash), k = 7 (nonce)
sign(5, 3, 7)  # → (2, 7)

검증 — 키를 알았을 때만 성립하는 항등식

검증자는 $h$, $(r, s)$, $Q$만 건네받는다. 다른 건 없다. $u₁ = h · s⁻¹ \mod n$, $u₂ = r · s⁻¹ \mod n$, $V = u₁G + u₂Q$를 차례로 구하고, $V.x ≡ r (\mod n)$이면 서명을 받아들인다. 대수를 한 줄씩 따라가 보자:

V = u₁·G + u₂·Q
= (h/s)·G + (r/s)·dG
= ((h + r·d)/s)·G                       ← group up by G
= ((h + r·d) · k / (h + r·d))·G        ← s = (h + r·d)/k
= k·G
= R                                      ← so V.x = R.x = r ✓

$s = (h + r·d)/k$이라는 한 줄이 $(r, s, h, Q)$만 보는 사람으로부터 $d$를 가린다. 그러면서 같은 줄을 $V = u₁G + u₂Q$에 대입하면 $V$가 정확히 $R$로 떨어진다. 검증자는 $d$를 되찾지 않고도 서명자가 닿았던 바로 그 점에 닿는다. $d$를 알아야만 만들 수 있고, $d$를 모르고도 확인할 수 있는 이 일치가 — 이 체계의 핵심이다.

# Verify uses only public information: h, (r, s), Q.
def verify(h, r, s, Q):
    s_inv = pow(s, -1, N)
    u1 = h * s_inv % N
    u2 = r * s_inv % N
    V = add(scalar_mul(u1, G), scalar_mul(u2, Q))
    return V is not INF and V[0] % N == r

Q = scalar_mul(5, G)            # public key matching d = 5
verify(3, 2, 7, Q)              # → True

# The algebra: V = u1·G + u2·Q
#                = (h/s)G + (r/s)·dG
#                = ((h + r·d)/s)·G
#                = ((h + r·d) · k / (h + r·d))·G   # because s = (h+r·d)/k
#                = k·G = R.   So V.x mod N = r.
# Verifier never sees d. The identity holds iff signer knew d.

secp256k1 — 같은 알고리즘, 더 큰 수

비트코인은 secp256k1 — 소수 $p = 2²⁵⁶ − 2³² − 977$ 위의 $y² = x³ + 7$ — 위에서 똑같은 군 법칙과 똑같은 ECDSA 식을 돌린다. 위의 위젯은 그 축소판이다. $2²⁵⁶$ 대신 17, $~2²⁵⁶$ 대신 부분군 차수 9. 알고리즘은 그대로다. 규모만 달라지는 게 하나 있으니, 곱셈 (여전히 $O(\log k)$) 과 되돌리기 (이제 $~2¹²⁸$) 사이의 격차다. 지갑이 안전한 유일한 이유가 바로 이 격차다.