한양과기고 에듀테크 수업도구 대시보드

샤미르 비밀 분할 (Shamir's Secret Sharing)

은행 금고 마스터 키, 암호화폐 지갑의 시드처럼 절대 잃어버려도 안 되고 한 사람이 독차지해서도 안 되는 비밀이 있다. 1979년 Adi Shamir(RSA의 S)가 낸 답은 우아하다. 비밀을 다항식의 y절편에 숨기고, 그 곡선 위의 점들을 조각(share)으로 나눠 준다. k개의 점이 모이면 곡선이 딱 하나로 정해져 비밀이 드러나지만, k−1개로는 무한히 많은 곡선이 가능해 아무것도 알 수 없다.

1. 비밀을 다항식에 숨기기

비밀 S (y절편) = 42

임계값 k (필요한 조각 수) = 3

조각 총 개수 n = 5

차수 k−1짜리 다항식 f(x) = S + a₁x + a₂x² + … 을 만든다. 상수항이 곧 비밀 S = f(0) 이고, 나머지 계수 a₁ … a₍ₖ₋₁₎ 는 무작위다.

2. 곡선 위의 점을 조각으로 배포

각 참가자에게 x = 1, 2, 3 … 에서의 좌표 (x, f(x)) 를 하나씩 준다. 조각을 눌러 복원에 사용할 점을 골라 보자. 아래에서 곡선이 어떻게 재구성되는지 볼 수 있다.

3. 라그랑주 보간으로 비밀 복원

k개의 점이 있으면 차수 k−1 곡선은 유일하다(라그랑주 보간). 그 곡선을 x = 0 에서 평가하면 비밀이 나온다. 점이 k−1개뿐이면 임의의 y절편마다 서로 다른 곡선이 존재한다 — 점선으로 그린 가짜 후보들을 보라. 모두 주어진 점을 지나지만 y절편이 제각각이다.

4. 왜 안전할까 · 어디에 쓰일까

정보 이론적 안전성

k−1개의 조각을 가진 공격자에게 비밀 S의 모든 값은 똑같이 그럴듯하다. 조각을 아무리 모아도 k개 미만이면 0비트의 정보도 새지 않는다. (실제 구현은 실수 대신 소수 p로 나눈 유한체에서 계산해 크기 정보까지 감춘다.)

임계 구조 (k, n)

(2, 3): 3명 중 아무 2명. (3, 5): 이사 5명 중 3명 합의로 금고 개방. 조각을 잃어도 n−k개까지는 여유. 새 조각 발급도 곡선을 알면 얼마든지 가능하다.

실제 사용처

HashiCorp Vault의 언실(unseal) 키, 하드웨어 보안 모듈(HSM) 마스터 키, 암호화폐 지갑 백업(SLIP-0039), 인증서 기관(CA) 루트 키 관리.

한계

조각을 나눠 주는 딜러는 한때 비밀 전체를 안다(신뢰 필요). 조각이 위조됐는지 검증은 기본 방식엔 없다 → 검증 가능한 비밀 분할(VSS)로 확장.

5. 파이썬으로 20줄

import random
P = 2**127 - 1              # 유한체 소수 (메르센 소수)

def split(secret, k, n):
    coeff = [secret] + [random.randrange(P) for _ in range(k - 1)]
    def f(x):
        return sum(c * pow(x, i, P) for i, c in enumerate(coeff)) % P
    return [(x, f(x)) for x in range(1, n + 1)]   # n개의 조각

def recover(shares):                        # x=0 에서 라그랑주 보간
    secret = 0
    for j, (xj, yj) in enumerate(shares):
        num, den = 1, 1
        for m, (xm, _) in enumerate(shares):
            if m != j:
                num = num * (-xm) % P
                den = den * (xj - xm) % P
        secret = (secret + yj * num * pow(den, -1, P)) % P   # 모듈러 역원
    return secret

s = split(1234567, k=3, n=5)
print(recover(random.sample(s, 3)))    # -> 1234567  (아무 3개면 OK)