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