Shamir형 2-of-3 비밀분산에서는 비밀을 지나는 임의의 1차 다항식에서 세 점을 만들고 각 점을 조각으로 나눠 줍니다. 서로 다른 두 점이면 직선과 y절편을 정할 수 있어 비밀을 복구하지만 한 점만으로는 그 점을 지나는 여러 직선이 가능하므로 비밀값이 하나로 정해지지 않습니다.
이 예시는 mod 17에서 직접 만든 숫자로 보간 원리를 보여 줍니다. 실제 구현에서는 계수의 무작위 선택, 좌표의 구별, 참여자 관리, 프로토콜 가정이 필요합니다. 비밀을 다시 복구하는 방식과 비밀키를 복원하지 않고 분산 서명·계산을 수행하는 임계 암호는 같은 절차가 아닙니다.
문턱 수와 조각 수는 다른 숫자입니다
2-of-3은 조각 세 개 가운데 임의의 두 개를 모으면 비밀을 복구할 수 있고, 하나만으로는 비밀을 정할 수 없도록 만든 구조를 뜻합니다. 단순 파일을 셋으로 잘라서 둘을 이어 붙이는 방식과는 다릅니다. 각 조각은 비밀을 지나는 다항식 위의 한 점입니다. 두 점은 직선을 결정하지만 한 점만으로는 기울기가 여러 값일 수 있습니다. NIST 문서는 임계 방식의 목표와 구현 가정이 방식마다 달라질 수 있어 종류와 보안 속성을 분리해 검토해야 한다고 설명합니다. 예를 들어 조각을 여러 장소에 보관하면 복구 가능성과 함께 보관자 인증, 분실 대응, 사본 통제도 고려해야 합니다. 수학적 문턱이 맞는다고 장치나 참여자 관리가 자동으로 검증되는 것은 아닙니다.
손계산 예제를 만들기 위해 유한체 mod 17에서 f(x)=5+3x를 사용합니다. 여기서 x와 y는 0부터 16까지의 잔여값이며 모든 덧셈과 곱셈 뒤에는 17로 나눈 나머지를 취합니다. 비밀은 f(0)=5입니다. 실제 Shamir 방식에서 일차항 계수는 예시처럼 고정해 두는 것이 아니라 허용된 체에서 무작위로 고릅니다. 이번 계산은 결과를 확인하기 위해 계수 3을 택했습니다.
| 조각 | x | 계산 f(x)=5+3x mod 17 | y |
|---|---|---|---|
| A | 1 | 5+3×1 | 8 |
| B | 2 | 5+3×2 | 11 |
| C | 3 | 5+3×3 | 14 |
두 점으로 y절편을 되찾습니다
A와 B 조각을 모으면 점 (1,8), (2,11)을 얻습니다. y가 x가 한 칸 늘 때 3만큼 늘므로 기울기는 (11−8)/(2−1)=3입니다. mod 17에서 1의 역원은 1이라 이 나눗셈은 그대로 3입니다. x=1일 때 y=8이므로 y절편은 8−3×1=5입니다. 혹은 f(0)을 바로 구하는 라그랑주 보간식을 적용해 f(0)=2×8−11=5 mod 17을 얻습니다. 결과가 원래 비밀과 같습니다.
두 점이면 직선의 기울기와 절편이 정해집니다. 다른 두 조각 B·C나 A·C를 골라도 같은 직선으로 돌아와 5를 복구해야 합니다. 이는 2-of-3에서 가능한 쌍이 세 가지이며, 선택한 쌍에 따라 비밀이 달라지는 구조가 아니라는 검산입니다. 실제 방식은 허용 범위 내 점 좌표와 계수, 조각 형식에 따라 세부 규칙이 달라질 수 있으므로 이 손계산만으로 제품 구현을 검증할 수는 없습니다. 조각은 접근 권한 그 자체가 아니라 복구에 필요한 수학 정보입니다. 실제 운영에서는 참여자 신원, 조각 변경 여부, 복구 절차와 감사 기록을 별도로 설계해야 할 수 있으며, 요구 사항은 방식의 위협 모델에 따라 달라집니다.
한 점으로는 비밀이 하나로 정해지지 않습니다
A 하나만 알면 (1,8)을 지나는 직선은 여럿입니다. 비밀을 s라고 두고 f(x)=s+(8−s)x를 만들면 x=1에서 항상 8을 지납니다. 예를 들어 s=5이면 기울기는 3이고, s=1이면 기울기는 7입니다. 두 다항식은 모두 조각 A와 맞지만 y절편인 비밀이 각각 5와 1로 다릅니다. 계수를 0부터 16까지 균등하게 고르는 조건에서는 한 점을 관찰해도 가능한 s가 한 값으로 좁혀지지 않습니다. 이는 교육용 구조의 핵심이지, 조각을 저장한 시스템이 실제로 안전하다는 결론은 아닙니다.
- 문턱 t와 전체 조각 n을 먼저 씁니다. 이번 예는 t=2, n=3입니다.
- 비밀이 다항식의 상수항인지 확인합니다.
- 점 좌표가 서로 다른지 확인하고, mod 연산을 매 줄 끝에 적용합니다.
- t개의 점으로 보간해 상수항을 구합니다.
- t보다 적은 점으로는 서로 다른 상수항이 가능한지 직접 다른 다항식을 만들어 봅니다.
- 복구형 비밀분산인지 키를 한곳에 복구하지 않는 임계 계산인지 용어를 확인합니다.
회상 연습: 한 조각에 맞는 두 직선을 찾습니다
교육용 문제입니다. 조각 A가 (1,8)이고 체가 mod 17일 때, 이 점과 맞으면서 비밀값 f(0)이 다른 직선 두 개를 적어 보세요. 이어 (1,8),(2,11)을 함께 사용했을 때 f(0)을 계산하고, 몇 조각부터 복구 문턱을 충족하는지 답하세요.
예를 들면 f(x)=5+3x와 f(x)=1+7x는 모두 x=1에서 8을 냅니다. 상수항이 달라 한 점으로 비밀을 결정하지 못합니다. 두 번째 점 (2,11)을 추가하면 두 점이 직선을 정하므로 기울기는 3, 상수항은 8−3=5 mod 17입니다. 두 조각부터 2-of-3의 복구 문턱을 충족합니다.
정답을 가리고 확인해 보세요
이 글을 위해 만든 학습 예시이며 공식 기출문제나 판매 카드의 인용이 아닙니다.
mod 17의 점 (1,8),(2,11)이 f(x)=s+ax 위에 있다. 두 점으로 비밀 s를 구하고, 한 점 (1,8)만으로 s가 결정되지 않는 이유를 서로 다른 직선 예로 답하라.
정답과 해설 확인
두 점의 기울기는 3이고 s=8−3=5 mod 17입니다. 한 점만으로는 f(x)=5+3x와 f(x)=1+7x처럼 서로 다른 절편을 갖는 직선이 모두 (1,8)을 지납니다.두 개의 서로 다른 x 좌표는 1차 다항식의 기울기와 상수항을 정합니다. 한 점은 절편과 기울기를 분리하지 못합니다. NIST 임계 방식 문서는 threshold cryptographic scheme의 목적·종류·구현 가정이 다양함을 다룹니다. 이 교재 계산은 실제 제도 인증이나 키 관리 구현 검증이 아닙니다.