1package shamirsecretsharing
  2
  3import (
  4	"crypto/rand"
  5	"errors"
  6	"math/big"
  7)
  8
  9func randBigInt(p *big.Int) (*big.Int, error) {
 10	b := make([]byte, 32)
 11	_, err := rand.Read(b)
 12	if err != nil {
 13		return nil, err
 14	}
 15	r := new(big.Int).SetBytes(b)
 16	rp := new(big.Int).Mod(r, p)
 17	return rp, nil
 18}
 19
 20// Create calculates the secrets to share from given parameters
 21// t: number of secrets needed
 22// n: number of shares
 23// p: size of finite field
 24// k: secret to share
 25func Create(t, n, p, k *big.Int) (result [][]*big.Int, err error) {
 26	if k.Cmp(p) > 0 {
 27		return nil, errors.New("Error: need k<p. k: " + k.String() + ", p: " + p.String())
 28	}
 29	//generate the basePolynomial
 30	var basePolynomial []*big.Int
 31	basePolynomial = append(basePolynomial, k)
 32	for i := 0; i < int(t.Int64())-1; i++ {
 33		x, err := randBigInt(p)
 34		if err != nil {
 35			return result, err
 36		}
 37		basePolynomial = append(basePolynomial, x)
 38	}
 39
 40	//calculate shares, based on the basePolynomial
 41	var shares []*big.Int
 42	for i := 1; i < int(n.Int64())+1; i++ {
 43		var pResultMod *big.Int
 44		pResult := big.NewInt(int64(0))
 45		for x, polElem := range basePolynomial {
 46			if x == 0 {
 47				pResult = pResult.Add(pResult, polElem)
 48			} else {
 49				iBigInt := big.NewInt(int64(i))
 50				xBigInt := big.NewInt(int64(x))
 51				iPowed := iBigInt.Exp(iBigInt, xBigInt, nil)
 52				currElem := iPowed.Mul(iPowed, polElem)
 53				pResult = pResult.Add(pResult, currElem)
 54				pResultMod = pResult.Mod(pResult, p)
 55			}
 56		}
 57		shares = append(shares, pResultMod)
 58	}
 59	//put the share together with his p value
 60	result = packSharesAndI(shares)
 61	return result, nil
 62}
 63
 64func packSharesAndI(sharesString []*big.Int) (r [][]*big.Int) {
 65	for i, share := range sharesString {
 66		curr := []*big.Int{share, big.NewInt(int64(i + 1))}
 67		r = append(r, curr)
 68	}
 69	return r
 70}
 71func unpackSharesAndI(sharesPacked [][]*big.Int) ([]*big.Int, []*big.Int) {
 72	var shares []*big.Int
 73	var i []*big.Int
 74	for _, share := range sharesPacked {
 75		shares = append(shares, share[0])
 76		i = append(i, share[1])
 77	}
 78	return shares, i
 79}
 80
 81// LagrangeInterpolation calculates the secret from given shares
 82func LagrangeInterpolation(p *big.Int, sharesGiven [][]*big.Int) *big.Int {
 83	resultN := big.NewInt(int64(0))
 84	resultD := big.NewInt(int64(0))
 85
 86	//unpack shares
 87	sharesBigInt, sharesIBigInt := unpackSharesAndI(sharesGiven)
 88
 89	for i := 0; i < len(sharesBigInt); i++ {
 90		lagrangeNumerator := big.NewInt(int64(1))
 91		lagrangeDenominator := big.NewInt(int64(1))
 92		for j := 0; j < len(sharesBigInt); j++ {
 93			if sharesIBigInt[i] != sharesIBigInt[j] {
 94				currLagrangeNumerator := sharesIBigInt[j]
 95				currLagrangeDenominator := new(big.Int).Sub(sharesIBigInt[j], sharesIBigInt[i])
 96				lagrangeNumerator = new(big.Int).Mul(lagrangeNumerator, currLagrangeNumerator)
 97				lagrangeDenominator = new(big.Int).Mul(lagrangeDenominator, currLagrangeDenominator)
 98			}
 99		}
100		numerator := new(big.Int).Mul(sharesBigInt[i], lagrangeNumerator)
101		quo := new(big.Int).Quo(numerator, lagrangeDenominator)
102		if quo.Int64() != 0 {
103			resultN = resultN.Add(resultN, quo)
104		} else {
105			resultNMULlagrangeDenominator := new(big.Int).Mul(resultN, lagrangeDenominator)
106			resultN = new(big.Int).Add(resultNMULlagrangeDenominator, numerator)
107
108			resultD = resultD.Add(resultD, lagrangeDenominator)
109		}
110	}
111
112	var modinvMul *big.Int
113	if resultD.Int64() != 0 {
114		modinv := new(big.Int).ModInverse(resultD, p)
115		modinvMul = new(big.Int).Mul(resultN, modinv)
116	} else {
117		modinvMul = resultN
118	}
119	r := new(big.Int).Mod(modinvMul, p)
120	return r
121}