홍라이프 계산기비밀 분산 임계값 계획 쉽게 이해하기 — 개념과 원리
샤미르 비밀 분산은 마스터 키나 지갑 시드 같은 비밀을 n개의 조각으로 나누어, 그중 k개만 모이면 복원되고 k − 1개로는 아무것도 알 수 없게 만드는 방법입니다. k와 n을 정하는 것은 균형의 문제로, 임계값이 높으면 도난에 강하고 낮으면 분실에 강합니다. 이 계산기는 각 조각이 서로 독립적으로 분실될 수 있을 때 비밀을 복원할 확률과, 공격자가 훔쳐야 하는 조각 수를 구합니다.
계산 방법
조각 하나를 잃을 확률을 p, 남을 확률을 1 − p라 하면 살아남는 조각 수는 이항분포를 따릅니다. k개 이상 남으면 복원할 수 있습니다.
P(복원) = Σ(i = k부터 n까지) C(n, i) × (1 − p)ⁱ × pⁿ⁻ⁱ
C(n, i)는 n개 중 i개를 고르는 경우의 수입니다. k개 미만으로는 정보를 전혀 얻을 수 없으므로 공격자는 k개를 확보해야 합니다.
원리
샤미르 방식은 비밀을 유한체 위의 k − 1차 무작위 다항식의 상수항으로 숨기고, 각 조각을 그 곡선 위의 한 점으로 나누어 줍니다. 두 점이 직선을, 세 점이 포물선을 정하듯 k개의 점은 k − 1차 다항식을 하나로 정하므로, 라그랑주 보간법으로 비밀을 복원합니다. k − 1개의 점만 있으면 가능한 모든 비밀이 똑같이 들어맞아 정보 이론적으로 안전합니다. 이항분포 합은 임계값 이상이 살아남는 모든 경우를 더한 것입니다.
예제 풀이
- 입력값은 조각 n = 5, 임계값 k = 3, 분실 확률 p = 0.05입니다.
- 5개 모두 남을 확률은 0.95⁵ = 0.77378입니다.
- 정확히 4개 남을 확률은 5 × 0.95⁴ × 0.05 = 0.20363입니다.
- 정확히 3개 남을 확률은 10 × 0.95³ × 0.05² = 0.02143입니다.
- 합은 0.99884이므로 복원 확률은 99.88%입니다.
- 공격자는 3개를 훔쳐야 합니다.
| 각 조각의 분실 확률 | 비밀을 복구할 수 있는 확률 |
|---|---|
| 0.0125 | 100% |
| 0.025 | 99.98% |
| 0.0375 | 99.95% |
| 0.05 | 99.88% |
| 0.0625 | 99.78% |
| 0.075 | 99.62% |
| 0.1 | 99.14% |
결과 해석
사본 하나만 있을 때의 보존 확률 95%와 비교해 보십시오. k를 그대로 두고 n을 늘리면 복원 확률이 오르고, k를 높이면 도난에는 강해지지만 복원 확률은 떨어집니다. 2-of-3이나 3-of-5처럼 한두 조각을 잃어도 되고 한 사람이 혼자 비밀을 쓸 수 없는 구성을 많이 고릅니다.
흔한 실수
- 여러 조각을 한곳에 보관해 화재나 도난 한 번에 독립성 가정이 무너집니다.
- k = n으로 정해 조각 하나만 잃어도 비밀을 영영 잃습니다.
- 비밀을 단순히 몇 토막으로 잘라 나눕니다. 이 경우 토막마다 비밀의 일부가 드러납니다.
자주 묻는 질문
2-of-3과 3-of-5 중 어느 쪽이 낫습니까?
3-of-5는 두 조각까지 잃어도 되고 세 개를 훔쳐야 하며, 2-of-3은 단순하지만 한 조각만 잃을 수 있고 두 개면 도난이 성립합니다.
샤미르 방식과 멀티시그는 같습니까?
다릅니다. 샤미르는 비밀 하나를 한곳에서 복원하고, 멀티시그는 키를 모으지 않고 여러 서명을 각각 요구합니다.
출처: A. Shamir, "How to Share a Secret", Communications of the ACM 22(11), 1979 · W. Feller, An Introduction to Probability Theory and Its Applications, Vol. 1, Wiley