[Vault] shamir's secret sharing algorithm !!

 

 

 

 

1. Shamir’s Secret Sharing이란?

**Shamir’s Secret Sharing(SSS)**은 하나의 비밀 정보를 여러 조각으로 나누고, 그 중 일부 조각만으로 원래 비밀을 복원할 수 있게 해주는 알고리즘입니다. 이 방식은 1979년 암호학자 Adi Shamir에 의해 제안되었으며, 현재도 암호 키 보호, 복구 키 분산, 블록체인 개인 키 저장 등 다양한 분야에서 널리 사용되고 있습니다.

• n개의 조각 중에서 최소 k개의 조각이 모이면 비밀을 복원할 수 있으며,
• k개 미만의 조각만으로는 비밀에 대한 정보론적 보안상 어떤 정보도 유출되지 않습니다.

---

2. 알고리즘 핵심 개념

Shamir의 비밀 공유 기법은 **다항식 보간(polynomial interpolation)**에 기반합니다.

2.1. 임계값 (Threshold)

• (k, n) 구조: n명에게 비밀을 분산하고, k명 이상이 모였을 때 비밀을 복원 가능
• 예시: (k=3, n=5) → 5명 중 3명이 모이면 원래 비밀 복원 가능

2.2. 유한체(Finite Field)

• 모든 수학 연산은 유한체 GF(p)에서 이루어집니다. (p는 큰 소수)
• 모듈러 연산을 통해 안정적인 보간과 보안을 유지합니다.

2.3. 라그랑주 보간법(Lagrange Interpolation)

• k개의 포인트만 있으면 원래 다항식을 복원 가능
• 비밀 S는 다항식의 **f(0)**에 해당하며, 이 값을 복원하는 것이 목표입니다.

---

3. 동작 원리

3.1. 비밀 분할 과정

1. 보호할 비밀 S를 정합니다. (예: 1234)
2. (k-1)개의 무작위 계수를 생성합니다. (예: a₁, a₂)
3. 다항식 구성:
   f(x) = S + a₁·x + a₂·x² + ... + aₖ₋₁·xᵏ⁻¹ mod p
4. x값에 따라 f(x)를 계산하여 조각을 생성합니다.
5. 생성된 n개의 조각을 서로 다른 사용자에게 배포합니다.

3.2. 비밀 복원 과정

1. 참여자 중 임계값 k개 이상의 조각을 수집합니다.
2. 수집한 (xᵢ, yᵢ) 값들을 바탕으로 라그랑주 보간법을 이용해 f(x) 복원
3. 최종적으로 f(0)을 계산하여 원래 비밀 S 복원

---

4. 예제: (k=3, n=5)의 SSS 분할

4.1. 설정

• 비밀 S = 1234
• p = 2089 (소수)
• a₁ = 166, a₂ = 94

다항식:
f(x) = 1234 + 166x + 94x² mod 2089

4.2. 조각 생성

x	f(x)	조각
1	1494	(1, 1494)
2	1850	(2, 1850)
3	230	(3, 230)
4	824	(4, 824)
5	1524	(5, 1524)

 

4.3. 복원

예: (2, 1850), (3, 230), (5, 1524) 조각만으로도 f(0)=1234 복원 성공

---

5. 장점과 단점

5.1. 장점

• 정보론적 보안: k개 미만 조각으로는 비밀 추정 불가능
• 신뢰 분산: 관리자 간 권한을 분산하여 보안 강화
• 유연성: 다양한 구조로 설계 가능 (예: k=2, n=10 등)

5.2. 단점

• 복잡한 수학 연산: 라그랑주 보간법 등 이해 필요
• 관리 어려움: 조각 분실 시 복원 불가
• 재구성 복잡: n 또는 k를 변경할 경우 전체 시스템 재설계 필요

---

6. 2025년 활용 사례

6.1. 암호화폐 개인 키 보관

• 메타마스크, Ledger 등은 백업 시 SSS 기반 방식 적용
• 키를 5개로 나누어 가족, 은행, 금고에 분산 저장

6.2. 기업 보안 키 관리

• HSM(하드웨어 보안 모듈) 대신 SSS 활용
• 관리자 A, B, C가 각각 키 조각을 갖고 k명이 승인 시 키 사용 가능

6.3. 클라우드 보안

• AWS, Google Cloud 기반 분산 시스템에서 API Key 분산 관리
• 단일 노드 해킹 시 전체 키 유출 방지 가능

---

7. 최신 트렌드 및 비교

7.1. XOR 기반 방식과 비교

항목	Shamir’s Secret Sharing	XOR Secret Sharing
보안 수준	정보론적 완전 보안	낮음
유연성	threshold 조절 가능	제한적
계산 속도	느림	빠름
실용성	키 관리 등 고급용	단순 파일 공유 등

 

7.2. Verifiable Secret Sharing (VSS)

• SSS에 검증 기능 추가 → 조각이 위조되었는지 확인 가능
• 대표 기술: Pedersen VSS
• Ledger Recover, Threshold Signature System(TSS)과 연계됨

---

8. Python 코드 예시

import random

PRIME = 2089

def make_shares(secret, n, k):
    coeffs = [secret] + [random.randint(0, PRIME-1) for _ in range(k-1)]
    def f(x):
        return sum([coeffs[i] * pow(x, i, PRIME) for i in range(k)]) % PRIME
    return [(i, f(i)) for i in range(1, n+1)]

def recover_secret(shares):
    result = 0
    for j, (xj, yj) in enumerate(shares):
        prod = 1
        for m, (xm, _) in enumerate(shares):
            if m != j:
                prod *= (-xm * pow(xj - xm, -1, PRIME)) % PRIME
        result = (result + yj * prod) % PRIME
    return result

# 사용 예시
secret = 1234
shares = make_shares(secret, 5, 3)
print("공유된 조각:", shares)
recovered = recover_secret(shares[:3])
print("복원된 비밀:", recovered)

 

 

---

9. 결론

Shamir’s Secret Sharing 알고리즘은 민감한 정보를 분산 보관하고 안전하게 복원할 수 있도록 하는 강력한 암호 기술입니다. 2025년 기준으로도 여전히 가장 신뢰받는 분산 보안 솔루션 중 하나이며, 암호 키 관리, 클라우드 보안, 재해 복구 설계 등 다양한 분야에 폭넓게 활용되고 있습니다.