샤미르의 비밀 공유

**샤미르의 비밀 공유**(, **SSS**)는 1979년 아디 샤미르가 처음 개발한, 그룹 내에서 개인 정보(즉 "비밀")를 분배하는 효율적인 비밀 공유 알고리즘이다. 그룹 구성원 중 최소 인원이 함께 지식을 모아야만 비밀이 드러날 수 있다. 이를 달성하기 위해 비밀은 수학적으로 여러 부분("공유물")으로 나뉘며, 충분한 수의 공유물이 결합될 때만 비밀을 재구성할 수 있다. SSS는 정보 이론적 보안의 속성을 가지는데, 이는 공격자가 일부 공유물을 훔치더라도 충분한 수의 공유물을 훔치지 않았다면 비밀을 재구성하는 것이 불가능하다는 것을 의미한다.

샤미르의 비밀 공유는 일부 응용 프로그램에서 마스터 비밀에 대한 접근 키를 공유하는 데 사용된다.

## 개요
SSS는 비밀을 분산된 형태로 보호하는 데 사용되며, 주로 암호화 키를 보호하는 데 사용된다. 비밀은 여러 공유물로 분할되며, 각 공유물만으로는 비밀에 대한 어떤 정보도 제공하지 않는다.

SSS로 보호된 비밀을 재구성하려면 임계값이라고 불리는 일정 수의 공유물이 필요하다. 임계값 미만의 공유물 수로는 비밀에 대한 어떤 정보도 얻을 수 없다(완전한 보안이라는 속성). 이러한 의미에서 SSS는 원 타임 패드(두 개의 공유물 임계값과 총 두 개의 공유물로 볼 수 있는 SSS)의 일반화이다.

### 응용 예시
어떤 회사가 금고를 보호해야 한다. 만약 한 사람만이 금고의 코드를 알고 있다면, 금고를 열어야 할 때 코드가 분실되거나 사용 불가능할 수 있다. 만약 여러 사람이 코드를 알고 있다면, 그들이 항상 정직하게 행동할 것이라고 서로 신뢰하지 못할 수도 있다.
이러한 상황에서 SSS를 사용하여 금고 코드의 공유물들을 생성하고, 이를 회사 내 권한 있는 개인들에게 분배할 수 있다. 최소 임계값과 각 개인에게 주어지는 공유물의 수는 금고가 오직 권한 있는 개인(또는 그룹)에 의해서만 접근 가능하도록 선택될 수 있다. 만약 임계값보다 적은 수의 공유물이 제시되면, 금고는 열리지 않는다.
사고로, 강압에 의해, 또는 반대 행위로 인해 일부 개인들은 공유물에 대해 부정확한 정보를 제시할 수 있다. 만약 정확한 공유물의 총합이 최소 임계값을 충족하지 못하면 금고는 계속 잠긴 상태로 유지된다.

### 사용 사례
샤미르의 비밀 공유는 다음 용도로 사용될 수 있다.
* 비밀번호 관리자의 루트 키를 해독하는 데 필요한 키 공유,
* 암호화된 이메일 접근을 위한 사용자 키 복구, 그리고
* 마스터 비밀을 재구성하는 데 사용되는 비밀구절 공유. 이 마스터 비밀은 다시 암호화폐 지갑에 접근하는 데 사용된다.

## 속성과 약점
SSS는 유용한 속성을 가지고 있지만 일부 사용에는 부적합하게 만드는 약점도 있다.

유용한 속성은 다음과 같다.
# **보안성**: 이 방식은 정보 이론적 보안을 갖는다.
# **최소성**: 각 조각의 크기는 원본 데이터의 크기를 초과하지 않는다.
# **확장성**: 주어진 임계값에 대해 기존 공유에 영향을 주지 않고 공유를 동적으로 추가하거나 삭제할 수 있다.
# **동적성**: 비밀을 변경하지 않고, 때때로 다항식(상수항 유지)을 변경하고 각 참여자를 위한 새로운 공유를 구성하여 보안을 강화할 수 있다.
# **유연성**: 계층이 중요한 조직에서는 각 참여자에게 조직 내 중요성에 따라 다른 수의 공유를 발행할 수 있다. 예를 들어, 임계값이 3일 때, 사장은 세 개의 공유를 받으면 혼자서 금고를 열 수 있는 반면, 각 비서는 한 개의 공유를 가지고 있어 세 명이 공유를 합쳐야 금고를 열 수 있다.

약점은 다음과 같다.
# **[[검증 가능한 비밀 공유]] 없음**: 공유 재조립 과정에서 SSS는 사용되는 각 공유의 정확성을 검증하는 방법을 제공하지 않는다. 검증 가능한 비밀 공유는 주주들이 정직하고 가짜 공유를 제출하지 않는지 확인하는 것을 목표로 한다.
# **[[단일 장애점]]**: 비밀은 공유로 분할될 때 한 곳에 존재해야 하며, 재조립될 때도 한 곳에 존재해야 한다. 이들은 공격 지점이며, 다중서명을 포함한 다른 방식은 이러한 단일 장애점 중 적어도 하나를 제거한다.

## 역사
이스라엘 과학자 아디 샤미르는 1979년에 이 방식을 처음 공식화했다.

## 수학적 원리
이 방법은 라그랑주 보간 정리를 활용하는데, 특히 k개의 다항식 위의 점들이 k-1차 이하의 다항식을 고유하게 결정한다는 점이다. 예를 들어, 2개의 점은 직선을 정의하기에 충분하고, 3개의 점은 포물선을 정의하기에 충분하며, 4개의 점은 삼차 곡선을 정의하기에 충분하다.

## 수학적 공식화
샤미르의 비밀 공유는 유한체 상의 다항식 보간법에 기반한 이상적이고 완벽한 \left(k,n\right)-임계값 스킴이다. 이러한 스킴에서 목표는 비밀 S(예: 금고의 조합)를 n개의 데이터 조각 S_1,\ldots,S_n(공유물이라고 함)으로 나누는 방식이며, 다음 조건을 만족한다.
# k개 이상의 공유물 S_i를 알면 S를 계산할 수 있다. 즉, 전체 비밀 S는 k개의 공유물의 어떤 조합으로부터도 재구성될 수 있다.
# k-1개 이하의 공유물 S_i를 알면 S는 완전히 결정되지 않는다. 즉, k-1개까지의 공유물을 알 때 가능한 S의 값은 0개의 공유물을 알 때와 마찬가지로 동일하게 가능성이 있다. 비밀 S는 k개 미만의 공유물로는 재구성될 수 없다.

만약 n=k라면, 비밀 S를 재구성하기 위해 모든 공유물이 필요하다.섬네일|right|두 개의 점을 통과하는 2차 다항식을 무한히 그릴 수 있다. 2차 다항식을 고유하게 결정하려면 3개의 점이 필요하다. 이 이미지는 설명 목적으로만 사용되며, 샤미르의 방식은 유한체 상의 다항식을 사용하므로 2차원 평면에서 쉽게 표현되지 않는다.

비밀 S가 유한체 \mathrm{GF}(q)의 원소 a_0로 표현될 수 있다고 가정하자 (여기서 q는 생성되는 공유물의 수 n보다 크다). \mathrm{GF}(q)에서 k-1개의 원소, a_1,\cdots,a_{k-1}을 무작위로 선택하고 다항식 f\left(x\right)=a_0+a_1x+a_2x^2+a_3x^3+\cdots+a_{k-1}x^{k-1}을 구성한다. 곡선 상의 n개의 점을 계산하는데, 예를 들어 i=1,\ldots,n을 설정하여 점 \left(i,f\left(i\right)\right)를 찾는다. 각 참여자는 하나의 점(다항식에 대한 0이 아닌 입력과 해당 출력)을 받는다. 이들 쌍 중 임의의 k개 부분집합이 주어지면, 보간법을 사용하여 a_0를 얻을 수 있으며, 가능한 공식 중 하나는 a_0 = f(0) = \sum_{j=0}^{k-1} y_j \prod_{\begin{smallmatrix} m\,=\,0 \\ m\,\ne\,j \end{smallmatrix}}^{k-1} \frac{x_m}{x_m - x_j} 이다. 여기서 다항식 상의 점 목록은 k개의 (x_i, y_i) 형태의 쌍으로 주어진다. f(0)는 다항식 f(x)의 첫 번째 계수와 동일하다는 점에 유의한다.

## 계산 예시
다음 예시는 기본적인 아이디어를 설명한다. 그러나 예시의 계산은 아이디어를 이해하기 쉽게 하기 위해 유한체 산술 대신 정수 산술을 사용한다. 따라서 아래 예시는 완벽한 비밀성을 제공하지 않으며 샤미르 방식의 적절한 예시가 아니다. 다음 예시에서 이 문제를 설명할 것이다.

### 준비
공유할 비밀이 1234라고 가정하자 (S=1234).

이 예시에서는 비밀을 6개의 공유물로 나눌 것이며 (n=6), 어떤 3개의 공유물 조합이라도 (k=3) 비밀을 재구성하기에 충분하다. k-1=2개의 숫자를 무작위로 선택한다. 166과 94라고 하자.
: 이는 계수 (a_0=1234;a_1=166;a_2=94),를 생성하며, 여기서 a_0가 비밀이다.

비밀 공유물(점)을 생성하는 다항식은 다음과 같다.
: f(x)=1234+166x+94x^2

다항식에서 6개의 점 D_{x-1}=(x, f(x))은 다음과 같이 구성된다.
: D_0=(1, 1494);D_1=(2, 1942);D_2=(3, 2578);D_3=(4, 3402); D_4= (5, 4414);D_5=(6, 5614)

이 방식의 각 참여자는 다른 점( x와 f(x)의 쌍)을 받는다. D_x 대신 D_{x-1}이 사용되므로 점은 (0, f(0))가 아닌 (1, f(1))부터 시작한다. 이는 f(0)가 비밀이기 때문에 필요하다.

### 재구성
비밀을 재구성하려면 어떤 3개의 점이라도 충분하다.

세 점 \left(x_0,y_0\right)=\left(2,1942\right);\left(x_1,y_1\right)=\left(4,3402\right);\left(x_2,y_2\right)=\left(5,4414\right)를 사용한다고 가정하자.

라그랑주 기저 다항식을 계산한다.

: \ell_0(x)=\frac{x-x_1}{x_0-x_1}\cdot\frac{x-x_2}{x_0-x_2}=\frac{x-4}{2-4}\cdot\frac{x-5}{2-5}=\frac{1}{6}x^2-\frac{3}{2}x+\frac{10}{3}

: \ell_1(x)=\frac{x-x_0}{x_1-x_0}\cdot\frac{x-x_2}{x_1-x_2}=\frac{x-2}{4-2}\cdot\frac{x-5}{4-5}=-\frac{1}{2}x^2+\frac{7}{2}x-5

: \ell_2(x)=\frac{x-x_0}{x_2-x_0}\cdot\frac{x-x_1}{x_2-x_1}=\frac{x-2}{5-2}\cdot\frac{x-4}{5-4}=\frac{1}{3}x^2-2x+\frac{8}{3}

다항식 보간법 공식을 사용하면 f(x)는 다음과 같다.

: 
\begin{align}
f(x) & =\sum_{j=0}^2 y_j\cdot\ell_j(x) \\[6pt]
& =y_0\ell_0(x)+y_1\ell_1(x)+y_2\ell_2(x) \\[6pt]
& =1942\left(\frac{1}{6}x^2-\frac{3}{2}x+\frac{10}{3}\right) + 3402\left(-\frac{1}{2}x^2+\frac{7}{2}x-5\right) + 4414\left(\frac{1}{3}x^2-2x+\frac{8}{3}\right) \\[6pt]
& =1234+166x+94x^2
\end{align}


비밀은 상수항이며 S=1234이므로 비밀이 복원되었다.

### 계산적으로 효율적인 접근법
라그랑주 다항식을 사용하여 소스 다항식의 계수 S=f(0)를 찾는 다항식 보간법은 사용되지 않는 상수들이 계산되기 때문에 효율적이지 않다.

이를 고려하여, 라그랑주 다항식을 사용하여 f(0)를 찾는 최적화된 공식은 다음과 같이 정의된다.

: f(0) = \sum_{j=0}^{k-1} y_j \prod_{\begin{smallmatrix} m\,=\,0 \\ m\,\ne\,j \end{smallmatrix}}^{k-1} \frac{x_m}{x_m - x_j} 

### 정수 산술 사용의 문제점
위에서 설명한, 유한체 산술 대신 정수 산술을 사용하는 간소화된 버전의 방법은 작동하지만, 보안 문제가 있다: 이브는 자신이 찾는 모든 D_i로부터 S에 대한 정보를 얻는다.

그녀가 점 D=(2,1942)를 찾았다고 가정해보자. 그녀는 아직 k=3개의 점을 가지고 있지 않으므로 이론적으로는 S에 대한 어떤 추가 정보도 얻지 못해야 한다. 하지만 그녀는 그 점의 정보와 공개된 정보: n=6, k=3, f(x)=a_0+a_1x+\cdots+a_{k-1}x^{k-1}, a_0=S, a_i\in\mathbb{Z}를 결합할 수 있다. 그렇게 함으로써 이브는 다음 대수학을 수행할 수 있다.

# f(x) 공식에 S와 k의 값을 채워넣는다: f(x)=S+a_1x+\cdots+a_{k-1}x^{k-1}\Rightarrow{}f(x)=S+a_1x+a_2x^2
# (1)에 D의 x와 f(x) 값을 채워넣는다: 1942=S+a_{1}2+a_{2}2^2\Rightarrow{}S=1942-2a_1-4a_2
이는 그녀에게 S가 짝수라는 정보를 제공한다.

### 유한체 산술을 사용한 해결책
섬네일|이것은 유한체 상의 다항식 곡선이다 – 다항식의 차수는 그래프의 모양과 거의 관련이 없는 것처럼 보인다.

위의 공격은 다항식이 어떻게 구성되었는지에 따라 다항식이 취할 수 있는 값에 대한 제약을 악용한다. 즉, 다항식은 정수 계수를 가져야 하며, 방식에 사용된 각 좌표에서 평가될 때 정수 값을 취해야 한다. 이것은 k개 미만의 공유물이 주어졌을 때, 결과적인 비밀을 포함하여 알려지지 않은 점들에서의 가능한 값을 줄인다.

이 문제는 유한체 산술을 사용하여 해결할 수 있다. 유한체는 항상 q = p^r 크기를 가지며, 여기서 p는 소수이고 r는 양의 정수이다. 필드의 크기 q는 q>n을 만족해야 하며, q는 비밀의 가능한 값의 수보다 커야 한다. 후자의 조건은 비밀을 더 작은 비밀 값으로 분할하고, 각각에 대해 이 방식을 적용함으로써 우회할 수 있다. 아래 예시에서는 소수 필드(즉, r = 1)를 사용한다. 그림은 유한체 상의 다항식 곡선을 보여준다.

실제로는 작은 변화일 뿐이다. 필드의 차수 q(즉, 필드가 가지는 값의 수)는 참여자 수와 비밀 a_0=S가 가질 수 있는 값의 수보다 크게 선택되어야 한다. 다항식을 포함하는 모든 계산은 정수 대신 필드 위에서(예시에서는 p = q를 소수로 취급하여 mod p로) 계산되어야 한다. 필드 선택과 비밀을 이 필드의 값으로 매핑하는 것은 모두 공개적으로 알려진 것으로 간주된다.

이 예시에서는 p=1613을 선택하면 다항식은 f(x)=1234+166x+94x^2\bmod{1613}이 되며, 다음 점들을 얻는다. (1,1494);(2,329);(3,965);(4,176);(5,1188);(6,775)

이 경우 이브는 D_x를 찾았을 때( k개의 점을 가질 때까지) 어떤 정보도 얻지 못한다.

다시 이브가 D_0=\left(1,1494\right)와 D_1=\left(2,329\right)를 찾았고, 공개 정보가 n=6, k=3, p=1613, f(x)=a_0+a_1x+\dots+a_{k-1}x^{k-1}\mod{p}, a_0=S, a_i\in\mathbb{N}라고 가정해보자. 이전 공격을 시도하면 이브는 다음을 수행할 수 있다.
# f(x) 공식에 S와 k 및 p 값을 채워넣는다: f(x)=S+a_1x+\dots+a_{3-1}x^{3-1}\mod1613
# (1)에 D_0의 x와 f(x) 값을 채워넣는다: 1494\equiv S+a_1 1+a_2 1^2 \pmod{1613}\Rightarrow {} 1494\equiv S+a_1+a_2 \pmod{1613}
# (1)에 D_1의 x와 f(x) 값을 채워넣는다: 1942\equiv S+a_{1}2+a_{2}2^2 \pmod{1613}\Rightarrow{}1942\equiv S+2a_1+4a_2 \pmod{1613}
# (3)-(2)를 뺀다: (1942-1494)\equiv (S-S)+(2a_1-a_1)+(4a_2-a_2) \pmod{1613}\Rightarrow{}448 \equiv a_1+3a_2 \pmod{1613} 이를 a_1\equiv 448-3a_2 \pmod{1613}으로 다시 쓴다.
a_1에 대해 p개의 가능한 값이 있다. 그녀는 [448,445,442,\ldots]가 항상 3씩 감소한다는 것을 알기 때문에, 만약 p가 3으로 나누어떨어진다면 a_1\in[1, 4, 7, \ldots]이라고 결론 내릴 수 있다. 하지만 p는 소수이므로 이렇게 결론 내릴 수 없다. 따라서 유한체를 사용하면 이 가능한 공격을 피할 수 있다.

또한, 이브가 S\equiv 1046+2a_2 \pmod{1613}이라고 결론 내릴 수 있다 하더라도, 모듈러 산술의 "둘러싸는" 동작으로 인해 위에서 정수 산술 예시와 달리 "S가 짝수이다"와 같은 정보 유출을 방지하므로 추가적인 정보를 제공하지 않는다.

## 파이썬 코드
코드를 명확하게 유지하기 위해 여기에서는 소수 필드를 사용한다. 실제로는 편의를 위해 더 작은 이진 필드를 사용하여 구성된 방식을 비밀의 작은 비트 문자열에 별도로 적용할 수 있다(예: 바이트 단위 적용을 위한 GF(256)). 이 경우 보안 손실은 없다. 필드의 크기가 공유 개수보다 커야 한다는 엄격한 조건은 여전히 준수되어야 한다(예: 공유 개수가 255를 초과할 수 있다면 GF(256)은 GF(65536) 등으로 대체될 수 있다).



```python
"""
The following Python implementation of Shamir's secret sharing is
released into the Public Domain under the terms of CC0 and OWFa:
https://creativecommons.org/publicdomain/zero/1.0/
http://www.openwebfoundation.org/legal/the-owf-1-0-agreements/owfa-1-0

See the bottom few lines for usage. Tested on Python 2 and 3.
"""

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():
    """Main function"""
    secret = 1234
    shares = make_random_shares(secret, minimum=3, shares=6)

    print('Secret:                                                     ',
          secret)
    print('Shares:')
    if shares:
        for share in shares:
            print('  ', share)

    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()
```



## 같이 보기
* 비밀 공유
* 다자간 보안 컴퓨팅
* 라그랑주 다항식
* 동형 비밀 공유 – 간단한 분산 투표 프로토콜
* 이인감시태세
* 부분 비밀번호

## 각주


## 더 읽어보기
* .
* .

## 외부 링크
* Shamir's Secret Sharing in the Crypto++ library
* Shamir's Secret Sharing Scheme (ssss) – a GNU GPL implementation
* sharedsecret – implementation in Go
* s4 - online shamir's secret sharing tool utilizing HashiCorp's shamir secret sharing algorithm
* Shamir39 - webversion on iancoleman.io
* kn Secrets - webversion on a dedicated website, aiming to make Shamir's secret sharing as accessible as possible
* xecrets-cli - cross-platform command line tool (Linux, macOS, Windows)

분류:키 관리