샤미르 비밀 공유 알고리즘(Shamir's Secret Sharing Algorithm)

샤미르 비밀 공유 알고리즘(Shamir's Secret Sharing Algorithm)은 비밀을 여러 조각으로 나누어 각각의 조각을 다른 사람들에게 나누어주는 알고리즘입니다. 이러한 방식으로 하나의 비밀을 보호하고 여러 사람이 협력하여 원래의 비밀을 복원할 수 있습니다.

샤미르 비밀 공유 알고리즘은 다음과 같은 방식으로 동작합니다:

비밀을 나누기 위해 소유자는 먼저 비밀을 생성합니다.
비밀을 나눌 조각의 개수와 필요한 조각 수를 정합니다. 예를 들어, 10개의 조각으로 나누고 5개의 조각이 필요한 경우를 생각해보겠습니다.
비밀을 나누기 위해 소유자는 다항식을 생성합니다. 이 다항식의 차수는 필요한 조각 수와 같아야 합니다. 예를 들어, 5차 다항식을 생성하여 10개의 조각으로 나눌 수 있습니다.
소유자는 이 다항식을 이용하여 비밀을 나누어 줍니다. 각각의 조각에는 이 다항식에서 뽑은 임의의 x 값과 해당 x 값에서의 다항식 값이 들어가게 됩니다.
이제 각각의 조각을 다른 사람들에게 나누어 주면 됩니다. 이를 받은 사람들은 나누어진 조각들을 결합하여 원래의 다항식을 복원하고 이를 이용하여 원래의 비밀을 복원할 수 있습니다.

샤미르 비밀 공유 알고리즘은 보안성이 높고, 여러 사람들이 협력하여 비밀을 복원할 수 있기 때문에 많은 분야에서 사용됩니다. 예를 들어, 암호화된 파일을 여러 사람에게 나누어 줌으로써 모든 사람이 함께 협력하여 파일을 복원할 수 있게 할 수 있습니다.

샘플 구현

특정 키 값을 샤미르 비밀 공유 알고리즘을 통해 나누는 예시 코드
5개의 조각으로 나누고 3개의 조각이 필요한 경우를 가정
키를 5조각으로 나누는 과정의 코드

package main

import (
    "fmt"
    "math/big"
    "math/rand"
    "time"
)

func generateRandomNumber() int64 {
    rand.Seed(time.Now().UnixNano())
    return rand.Int63()
}

func generatePolynomial(secret *big.Int, degree int) []*big.Int {
    coefficients := make([]*big.Int, degree+1)
    coefficients[0] = secret
    for i := 1; i <= degree; i++ {
        coefficients[i] = big.NewInt(generateRandomNumber())
    }
    return coefficients
}

func calculateShares(polynomial []*big.Int, sharesNeeded int, shareCount int) []*big.Int {
    shares := make([]*big.Int, shareCount)
    for i := 1; i <= shareCount; i++ {
        x := big.NewInt(int64(i))
        y := big.NewInt(0)
        for j := range polynomial {
            xPower := big.NewInt(0).Exp(x, big.NewInt(int64(j)), nil)
            term := big.NewInt(0).Mul(polynomial[j], xPower)
            y = big.NewInt(0).Add(y, term)
        }
        shares[i-1] = y
    }
    return shares
}

func main() {
    secret := big.NewInt(12345)
    degree := 4
    sharesNeeded := 3
    shareCount := 5
    
    polynomial := generatePolynomial(secret, degree)
    shares := calculateShares(polynomial, sharesNeeded, shareCount)
    
    fmt.Println("Generated Shares:")
    for _, share := range shares {
        fmt.Println(share)
    }
}

generateRandomNumber() 함수: 이 함수는 무작위로 생성된 64비트 정수를 반환. 이 함수는 나중에 사용될 랜덤한 계수를 생성하기 위해 사용.
generatePolynomial(secret *big.Int, degree int) []*big.Int 함수: 이 함수는 비밀값과 차수를 인자로 받아, 다항식의 계수를 무작위로 생성하여 해당 계수들을 포함하는 다항식을 반환. 이 함수에서는 math/big 라이브러리의 big.Int 타입을 사용하여 계산.