개요

샤미르 비밀 공유(줄여서 SSS)는 그룹원에게 각 정보를 분산하여 궁극적으로 데이터를 공유하는 알고리즘이다.^[1]

어떤 데이터가 있는데, 이것을 시크릿으로서 관리하고 싶다.
근데 그룹원이라고 아무나 막 볼 수 있는 것은 아니고 여러 명이 한꺼번에 이 시크릿을 보려는 행위를 해야만 비로소 해당 데이터를 볼 수 있도록 하는 알고리즘인 것이다.
각 개인이 가진 정보만으로는 시크릿을 알 수 없고 최소한의 그룹원(이 최소치를 threshold, 임계치라 한다)이 모여서 정보를 조합해야만 시크릿을 알 수 있다.
보통 조직에서 모든 권한을 가진 루트키를 시크릿으로 관리할 때 사용한다.

참고로 샤미르는 RSA 암호화 방식을 발명하신 분이라고 한다..

특징

일단 당연히 보안적으로 좋고, 각 개인이 가지는 정보의 크기는 무조건 원본 데이터보다 작다는 것이 보장된다.
여기에 동적인 설정이 가능하다는 게 매우 큰 특징 중 하나로, 임계치가 지정된 상황에서 새로운 그룹원에게 새로운 정보를 할당해주는 것이 자유롭다.

조금 주의점도 있는데, 일단 각 그룹원에게 제공된 정보 자체의 유효성 검증 로직은 들어가지 않는다.
그리고 시크릿은 한 공간에 무조건 존재해야 하며, 이 공간이 결국 SPOF로서 작용할 수 있다.

원리

개략

원리 자체는 꽤나 단순하다.^[2]
이렇게 2차 함수 y = ax**2 + bx + c가 있고, 이 2차 함수의 계수가 시크릿이라고 해보자.
이때 a,b,c를 알기 위해서는 해당 함수 위의 점을 최소한 3개는 알아야 한다.
단순하게 미지수가 3개이기 때문에 이를 해결하기 위해 3개의 식이 필요하기 때문이다.
관리자 A는 이렇게 시크릿을 만들고, 이차 함수 위의 임의의 점을 BCD에게 공유한다.
각 그룹원들은 좌표 하나만 가지고 있으니 당연히 시크릿을 알 수 없다.
이 그룹원들이 모여서 세 좌표를 서로 공유할 때 비로소 시크릿을 알 수 있게 된다!

이게 SSS의 핵심 원리이다.
n차 다항식을 사용하면 n+1을 임계치로 가지는 시크릿을 만들 수 있게 된다.
그룹원이 늘어나더라도 연속 선 상의 임의의 좌표를 주기만 하면 하나의 정보로서 줄 수 있게 되니 확장성도 보장되는 꼴이다.

실제로 시크릿으로 사용되는 것은 상수항으로, 변수에 0을 넣으면 나오는 값에 설정한다(위 그림으로는 3이 시크릿).
원리 자체는 간단하지만, 이를 쉽게 계산하는 방식은 수학 공식이 들어간다.
이 부분에 대해서 깊게 파볼 필요까지는 없을 것 같아서 따로 정리하지는 않겠다.
위 그림을 참고한 블로그에 설명이 자세히 돼있으니 참고하자.

코드

"""
The following Python implementation of Shamir's secret sharing is
released into the Public Domain under the terms of CC0 and OWFa:
"""

from __future__ import division
from __future__ import print_function

import random
import functools

# 12th Mersenne Prime
_PRIME = 2 ** 127 - 1

_RINT = functools.partial(random.SystemRandom().randint, 0)

def _eval_at(poly, x, prime):
    """Evaluates polynomial (coefficient tuple) at x, used to generate a
    shamir pool in make_random_shares below.
    """
    accum = 0
    for coeff in reversed(poly):
        accum *= x
        accum += coeff
        accum %= prime
    return accum

def make_random_shares(secret, minimum, shares, prime=_PRIME):
    """
    Generates a random shamir pool for a given secret, returns share points.
    """
    if minimum > shares:
        raise ValueError("Pool secret would be irrecoverable.")
    poly = [secret] + [_RINT(prime - 1) for i in range(minimum - 1)]
    points = [(i, _eval_at(poly, i, prime))
              for i in range(1, shares + 1)]
    return points

def _extended_gcd(a, b):
    """
    Division in integers modulus p means finding the inverse of the
    denominator modulo p and then multiplying the numerator by this
    inverse (Note: inverse of A is B such that A*B % p == 1). This can
    be computed via the extended Euclidean algorithm
    http://en.wikipedia.org/wiki/Modular_multiplicative_inverse#Computation
    """
    x = 0
    last_x = 1
    y = 1
    last_y = 0
    while b != 0:
        quot = a // b
        a, b = b, a % b
        x, last_x = last_x - quot * x, x
        y, last_y = last_y - quot * y, y
    return last_x, last_y

def _divmod(num, den, p):
    """Compute num / den modulo prime p

    To explain this, the result will be such that:
    den * _divmod(num, den, p) % p == num
    """
    inv, _ = _extended_gcd(den, p)
    return num * inv

def _lagrange_interpolate(x, x_s, y_s, p):
    """
    Find the y-value for the given x, given n (x, y) points;
    k points will define a polynomial of up to kth order.
    """
    k = len(x_s)
    assert k == len(set(x_s)), "points must be distinct"
    def PI(vals):  # upper-case PI -- product of inputs
        accum = 1
        for v in vals:
            accum *= v
        return accum
    nums = []  # avoid inexact division
    dens = []
    for i in range(k):
        others = list(x_s)
        cur = others.pop(i)
        nums.append(PI(x - o for o in others))
        dens.append(PI(cur - o for o in others))
    den = PI(dens)
    num = sum([_divmod(nums[i] * den * y_s[i] % p, dens[i], p)
               for i in range(k)])
    return (_divmod(num, den, p) + p) % p

def recover_secret(shares, prime=_PRIME):
    """
    Recover the secret from share points
    (points (x,y) on the polynomial).
    """
    if len(shares) < 3:
        raise ValueError("need at least three shares")
    x_s, y_s = zip(*shares)
    return _lagrange_interpolate(0, x_s, y_s, prime)

def main():
	# 시크릿
    secret = 1234
    # 시크릿을 위한 정보 풀
    shares = make_random_shares(secret, minimum=3, shares=6)

	# 시크릿 구하기
    print('Secret recovered from minimum subset of shares:             ',
          recover_secret(shares[:3]))
    print('Secret recovered from a different minimum subset of shares: ',
          recover_secret(shares[-3:]))

if __name__ == '__main__':
    main()

파이썬 코드로 간단하게 만든 예시.
모듈러 연산과 라그랑주 다항식을 쓴다 정도만 인지하고 넘어갔다.

관련 문서

참고