Skip to main content

Shamir's Secret Sharing (SSS)

비밀 보관의 딜레마​

ECDSA를 통해 개인키로 트랜잭션에 서명하고, 공개키로 검증하는 방법을 살펴보았다. 하지만 아무리 서명 알고리즘이 안전해도, 개인키 자체가 유출되거나 분실되면 의미가 없을 것이다.

블록체인 생태계에서 개인키(Private Key)나 시드 구문(Seed Phrase)을 안전하게 보관하는 것은 가장 중요한 문제 중 하나이다. 개인키를 분실하면 자산에 대한 접근이 영원히 불가능해지고, 반대로 유출되면 자산을 모두 탈취당할 수 있기 때문이다.

가장 단순한 보관 방식은 시드 구문을 종이에 적어 금고에 보관하거나, 암호화된 파일로 저장하는 것이다. 하지만 이 방식에는 명확한 한계가 있다.

  • 단일 실패 지점(Single Point of Failure): 보관 장소가 하나뿐이라면, 그 장소가 훼손되거나 접근 불가능해지면 비밀 전체를 잃게 된다.
  • 복제의 딜레마: 안전을 위해 여러 곳에 복사본을 두면, 유출 위험이 그만큼 증가한다.
  • 신뢰 문제: 타인에게 백업을 맡기면 그 사람이 전체 비밀에 접근할 수 있게 된다.

이러한 문제를 해결하기 위해 1979년 이스라엘의 암호학자 Adi Shamir가 제안한 기법이 바로 Shamir's Secret Sharing(SSS)이다.

Shamir's Secret Sharing 개념​

Shamir's Secret Sharing은 비밀을 여러 조각(share)으로 분산하여, 일정 개수 이상의 조각이 모여야만 원본 비밀을 복원할 수 있는 (k, n) 임계값 구조를 제공한다.

  • n: 생성되는 총 조각(share)의 개수
  • k: 비밀을 복원하기 위해 필요한 최소 조각 개수 (임계값, threshold)

예를 들어 (3, 5) 구조는 5개의 조각을 생성하고, 그 중 최소 3개가 모여야 비밀을 복원할 수 있음을 의미한다. 2개 이하의 조각만으로는 비밀에 대한 어떠한 정보도 얻을 수 없다.

정보 이론적 보안 (Information-Theoretic Security)​

SSS의 가장 강력한 특성 중 하나는 정보 이론적 보안을 제공한다는 점이다. 이는 k-1개 이하의 조각을 가진 공격자가 무한한 컴퓨팅 파워를 갖고 있더라도 비밀에 대한 정보를 전혀 추론할 수 없음을 의미한다. 이러한 보안 수준은 현대 암호학에서 가장 높은 수준의 보안으로 간주된다.

수학적 원리​

SSS의 핵심 아이디어는 기하학에서 잘 알려진 사실에 기반한다.

다항식과 점의 관계​

두 점을 지나는 직선은 단 하나뿐이다. 점이 하나만 주어지면 그 점을 지나는 직선은 무수히 많지만, 점이 두 개가 되는 순간 그 두 점을 모두 지나는 직선은 유일하게 결정된다.

이 원리는 더 복잡한 곡선에도 동일하게 적용된다.

  • 직선(1차 다항식): 2개의 점이 있어야 유일하게 결정
  • 포물선(2차 다항식): 3개의 점이 있어야 유일하게 결정
  • k-1차 다항식: k개의 점이 있어야 유일하게 결정

SSS는 이 성질을 교묘하게 활용한다. 비밀을 다항식의 한 지점(y절편, 즉 f(0)의 값)에 숨겨놓고, 다항식 위의 여러 점을 share로 배포한다. k개의 점이 모여야만 원래 다항식을 복원할 수 있고, 그래야만 y절편에 숨겨둔 비밀을 찾을 수 있다.

Share 생성 과정​

(k, n) 임계값 구조에서 비밀 S를 분산하는 과정은 다음과 같다.

  1. 다항식 생성: 비밀 S를 상수항(f(0))으로 하는 k-1차 다항식을 생성한다.

    f(x) = S + a₁x + a₂x² + ... + aₖ₋₁xᵏ⁻¹

    여기서 a₁, a₂, ..., aₖ₋₁은 랜덤하게 선택된 계수이다.

  2. Share 계산: 서로 다른 n개의 x 값(보통 1, 2, 3, ..., n)에 대해 f(x)를 계산하여 n개의 점 (xᵢ, f(xᵢ))을 생성한다. 각 점이 하나의 share가 된다.

비밀 복원: 라그랑주 보간법​

k개 이상의 share가 모이면 원래의 다항식을 복원하여 f(0), 즉 비밀 S를 계산할 수 있다. 이때 사용하는 기법이 라그랑주 보간법(Lagrange Interpolation)이다.

라그랑주 보간법의 핵심은 점마다 “가중치”를 곱해 더하면, 그 점들을 정확히 지나는 곡선이 복원된다는 것이다. 각 점에 대해 Lᵢ(x)라는 “보조 다항식”을 만든다. 이 다항식은 자기 점에서는 1, 다른 점에서는 0이 되도록 설계된다. 그래서 모든 점을 동시에 만족하는 식이 만들어진다.

이렇게 복원된 곡선에서 x=0일 때의 값이 바로 비밀 S다.

S = f(0) = Σᵢ yᵢ · Lᵢ(0)

여기서 Lᵢ(0)은 “i번째 점의 영향력(가중치)”이라고 보면 된다. 각 점의 y값에 이 가중치를 곱해서 모두 더하면 f(0), 즉 비밀이 나온다.

간단한 예시: (2, 3) 구조​

비밀 S = 42를 (2, 3) 구조로 분산하는 예시를 살펴보자. (2, 3) 구조는 3개의 share를 생성하고, 그 중 최소 2개가 모여야 비밀을 복원할 수 있다는 의미다. 따라서 1차 다항식(직선)을 사용한다.

1단계: 다항식 생성

비밀 42를 y절편(상수항)으로 하고, 랜덤한 계수 7을 선택하여 1차 다항식을 만든다:

f(x) = 42 + 7x

그래프로 그리면 y절편이 42이고 기울기가 7인 직선이다.

2단계: Share 생성

x = 1, 2, 3을 대입하여 직선 위의 세 점을 계산한다:

  • Share 1: (1, f(1)) = (1, 49)
  • Share 2: (2, f(2)) = (2, 56)
  • Share 3: (3, f(3)) = (3, 63)

각 share는 좌표평면 위의 한 점이다. 이 점들은 모두 같은 직선 위에 있다.

3단계: 복원

Share 1과 Share 2만 사용하여 비밀을 복원해보자. 두 점 (1, 49)와 (2, 56)을 지나는 직선을 찾으면, 그 직선의 y절편이 바로 비밀이다.

라그랑주 보간법을 적용하면:

S = 49 × 2 + 56 × (-1)
  = 98 - 56
  = 42

만약 Share 1만 가지고 있다면 어떨까? 점 (1, 49)를 지나는 직선은 무수히 많다. 기울기가 0이면 y절편은 49, 기울기가 1이면 y절편은 48, 기울기가 7이면 y절편은 42, 따라서 어떤 값이 진짜 비밀인지 알 수 없다.

위의 예시는 이해를 위해 일반 정수로 설명했지만, 실제 구현에서는 유한체(Finite Field) 연산을 사용한다. 보통 큰 소수 p를 선택해 GF(p) 위에서 모든 계산을 수행한다.

TypeScript 구현​

간단한 SSS 구현을 통해 위에서 설명한 개념을 코드로 확인해보자.

예제 코드

전체 테스트 코드는 crypto-examples/cryptography-examples/04-shamir-secret-sharing에서 확인할 수 있다.

// Simple SSS implementation
const PRIME = BigInt("170141183460469231731687303715884105727"); // 2^127 - 1

// Modular arithmetic: normalize to 0 ~ PRIME-1 range
function mod(n: bigint): bigint {
  return ((n % PRIME) + PRIME) % PRIME;
}

// Modular inverse: a * a^{-1} ≡ 1 (mod PRIME)
function modInverse(a: bigint, m: bigint): bigint {
  let [oldR, r] = [a, m];
  let [oldS, s] = [BigInt(1), BigInt(0)];

  while (r !== BigInt(0)) {
    const quotient = oldR / r;
    [oldR, r] = [r, oldR - quotient * r];
    [oldS, s] = [s, oldS - quotient * s];
  }

  return mod(oldS);
}

// Random BigInt (0 ~ max-1)
function randomBigInt(max: bigint): bigint {
  const bytes = 16;
  const array = new Uint8Array(bytes);
  crypto.getRandomValues(array);
  let result = BigInt(0);
  for (const byte of array) {
    result = (result << BigInt(8)) + BigInt(byte);
  }
  return result % max;
}

interface Share {
  x: bigint;
  y: bigint;
}

// Polynomial evaluation: f(x) = c0 + c1*x + c2*x^2 + ...
function evaluatePolynomial(coefficients: bigint[], x: bigint): bigint {
  let result = BigInt(0);
  let xPower = BigInt(1);

  for (const coef of coefficients) {
    result = mod(result + mod(coef * xPower));
    xPower = mod(xPower * x);
  }

  return result;
}

// Create shares
function createShares(
  secret: bigint,
  threshold: number,
  totalShares: number,
  coefficients?: bigint[]
): Share[] {
  if (threshold > totalShares) {
    throw new Error("Threshold cannot be greater than total shares");
  }
  if (threshold < 2) {
    throw new Error("Threshold must be at least 2");
  }

  // Coefficients: f(x) = secret + a1*x + a2*x^2 + ...
  const coeffs: bigint[] = coefficients
    ? [...coefficients]
    : [
        secret,
        ...Array.from({ length: threshold - 1 }, () => randomBigInt(PRIME)),
      ];

  if (coeffs.length !== threshold) {
    throw new Error("Coefficients length must match threshold");
  }
  if (coeffs[0] !== secret) {
    throw new Error("coefficients[0] must be the secret (f(0))");
  }

  // Generate n shares
  const shares: Share[] = [];
  for (let i = 1; i <= totalShares; i++) {
    const x = BigInt(i);
    shares.push({
      x,
      y: evaluatePolynomial(coeffs, x),
    });
  }

  return shares;
}

// Reconstruct secret using Lagrange interpolation
function reconstructSecret(shares: Share[]): bigint {
  if (shares.length === 0) {
    throw new Error("At least one share is required");
  }

  let secret = BigInt(0);

  for (let i = 0; i < shares.length; i++) {
    let numerator = BigInt(1);
    let denominator = BigInt(1);

    for (let j = 0; j < shares.length; j++) {
      if (i !== j) {
        // L_i(0) = Π(j≠i) (0 - x_j) / (x_i - x_j)
        numerator = mod(numerator * mod(-shares[j].x));
        denominator = mod(denominator * mod(shares[i].x - shares[j].x));
      }
    }

    // y_i * L_i(0)
    const lagrangeTerm = mod(
      shares[i].y * mod(numerator * modInverse(denominator, PRIME))
    );
    secret = mod(secret + lagrangeTerm);
  }

  return secret;
}

export { createShares, reconstructSecret, Share, PRIME };

위 테스트 코드를 실행하면 다음과 같은 결과를 확인할 수 있다.

=== Shamir's Secret Sharing Test ===

Original Secret: 123456789
Threshold: 3, Total Shares: 5

Generated Shares:
  Share 1: (x=1, y=123457368)
  Share 2: (x=2, y=123458859)
  Share 3: (x=3, y=123461262)
  Share 4: (x=4, y=123464577)
  Share 5: (x=5, y=123468804)

--- Test: Reconstruct with exactly 3 shares ---
Recovered Secret: 123456789
Success: true

--- Test: Reconstruct with 4 shares ---
Recovered Secret: 123456789
Success: true

--- Test: Reconstruct with all 5 shares ---
Recovered Secret: 123456789
Success: true

--- Test: Attempt with only 2 shares (below threshold) ---
Attempted Recovery: 123455877
Matches Original: false

테스트 결과에서 볼 수 있듯이, 임계값(3) 이상의 share를 사용하면 정확하게 원본 비밀이 복원되지만, 임계값 미만(2개)의 share로는 전혀 다른 값이 계산된다. 이는 SSS의 핵심 특성인 임계값 보안이 정상적으로 동작함을 보여준다.

정리​

Shamir's Secret Sharing은 비밀을 안전하게 분산 저장하기 위한 암호학적 기법이다.

장점​

  • 정보 이론적 보안: 임계값 미만의 share로는 비밀에 대한 어떤 정보도 얻을 수 없다.
  • 유연한 임계값 설정: 필요에 따라 (k, n) 값을 자유롭게 설정할 수 있다.
  • 결함 허용(Fault Tolerance): 일부 share가 손실되어도 임계값 이상이 남아있으면 복구 가능하다.
  • 구현의 단순성: 수학적 원리가 명확하고 구현이 비교적 간단하다.

한계​

  • 생성/복원 시 단일 실패 지점: 비밀이 한 곳에 모이는 순간이 존재한다.
  • 정적 구조: share 추가/제거 시 전체 재생성이 필요하다.

참고 자료​