sss

README

sss (Shamir's Secret Sharing)

A pure Go implementation of Shamir's Secret Sharing algorithm over GF(2^8).

Inspired by @hbs's Python implementation.

For documentation, check godoc.

Documentation

Overview

Package sss implements Shamir's Secret Sharing algorithm over GF(2^8).

Shamir's Secret Sharing algorithm allows you to securely share a secret with N people, allowing the recovery of that secret if K of those people combine their shares.

It begins by encoding a secret as a number (e.g., 42), and generating N random polynomial equations of degree K-1 which have an X-intercept equal to the secret. Given K=3, the following equations might be generated:

f1(x) =  78x^2 +  19x + 42
f2(x) = 128x^2 + 171x + 42
f3(x) = 121x^2 +   3x + 42
f4(x) =  91x^2 +  95x + 42
etc.

These polynomials are then evaluated for values of X > 0:

f1(1) =  139
f2(2) =  896
f3(3) = 1140
f4(4) = 1783
etc.

These (x, y) pairs are the shares given to the parties. In order to combine shares to recover the secret, these (x, y) pairs are used as the input points for Lagrange interpolation, which produces a polynomial which matches the given points. This polynomial can be evaluated for f(0), producing the secret value--the common x-intercept for all the generated polynomials.

If fewer than K shares are combined, the interpolated polynomial will be wrong, and the result of f(0) will not be the secret.

This package constructs polynomials over the field GF(2^8) for each byte of the secret, allowing for fast splitting and combining of anything which can be encoded as bytes.

This package has not been audited by cryptography or security professionals.

Example

secret := "well hello there!" // our secret
n := byte(30)                 // create 30 shares
k := byte(2)                  // require 2 of them to combine

shares, err := Split(n, k, []byte(secret)) // split into 30 shares
if err != nil {
	fmt.Println(err)
	return
}

// select a random subset of the total shares
subset := make(map[byte][]byte, k)
for x, y := range shares { // just iterate since maps are randomized
	subset[x] = y
	if len(subset) == int(k) {
		break
	}
}

// combine two shares and recover the secret
recovered := string(Combine(subset))
fmt.Println(recovered)

Output:

well hello there!

Index

• Variables
• func Combine(shares map[byte][]byte) []byte
• func Split(n, k byte, secret []byte) (map[byte][]byte, error)
• func SplitUsingReader(n, k byte, secret []byte, reader io.Reader) (map[byte][]byte, error)

Examples

• Package

Variables

var (
	// ErrInvalidCount is returned when the count parameter is invalid.
	ErrInvalidCount = errors.New("N must be >= K")
	// ErrInvalidThreshold is returned when the threshold parameter is invalid.
	ErrInvalidThreshold = errors.New("K must be > 1")
)

Functions

func Combine

func Combine(shares map[byte][]byte) []byte

Combine the given shares into the original secret.

N.B.: There is no way to know whether the returned value is, in fact, the original secret.

func Split

func Split(n, k byte, secret []byte) (map[byte][]byte, error)

Split the given secret into N shares of which K are required to recover the secret. Returns a map of share IDs (1-255) to shares.

func SplitUsingReader

func SplitUsingReader(
	n, k byte, secret []byte, reader io.Reader) (map[byte][]byte, error)

SplitUsingReader splits the given secret, as Split does, but using the specified reader to create random polynomials. Use for deterministic splitting; caller must ensure reader is cryptographically secure.