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