ShamirSecretShare

Shamir秘密共享算法

算法背景

Sharmir‘s Secret Share 算法是一种加密算法，在不受信任的网络中可以使用它来安全地分发私密信息。无密钥安全技术（生物识别数据、私钥等）使用 Sharmir‘s Secret Share 算法来确保个人数据的安全。Sharmir‘s Secret Share 算法是 1979 年著名密码学家阿迪·沙米尔（Adi Shamir）提出了一种新的 secret 共享方法。该算法基于Lagrange插值法及矢量计算。

SSS算法的数学原理

Shamir Secret Share算法是一种秘密分享方案，由Adi Shamir在1979年提出。该算法允许一个秘密被分割成多个部分，这些部分可以分发给多个参与者。只有当足够数量的部分被重新组合时，秘密才能被恢复。

假设我们有一个秘密S，我们想要将其分割成n个部分，并且我们希望至少有k个部分才能恢复秘密。我们可以通过以下步骤实现：

1. 选择一个k-1次的多项式f(x)，使得f(0) = S。这个多项式的系数是随机选择的，只有常数项是S。即，我们有：

$
f(x) = a_{k-1}x^{k-1} + a_{k-2}x^{k-2} + … + a_1x + S
$

其中，$a_{k-1}, a_{k-2}, …, a_1$ 是随机选择的系数。

1. 为每个参与者i生成一个点(即share)$(i, f(i))$。这个点就是他们的秘密部分。

要恢复秘密，我们需要至少k个点。我们可以使用Lagrange插值法来恢复f(x)，然后计算f(0)来得到秘密S。具体来说，我们有：

$
f(x) = \sum_{i=0}^{k-1} y_i \cdot l_i(x)
$

其中，$l_i(x)$ 是 Lagrange 基函数，定义为：

$
l_i(x) = \prod_{0 \leq m \leq k-1, m \neq i} \frac{x - x_m}{x_i - x_m}
$

这种方法的优点是，任何少于k个的点都无法提供关于秘密的任何信息。这是因为k-1次的多项式有无穷多个，而且除了f(x)外，所有的多项式在x=0处的值都与S不同。

但使用常规多项式存在安全漏洞

如果攻击者拥有一些点，但不足以满足阈值，则可以使用代数来减少可能的多项式的数量。这使得执行暴力攻击以解密secret 变得更加容易。
于是我们引入模运算，将普通多项式取模一个大素数转换为循环多项式。
$
f(x) = (a_{k-1}x^{k-1} + a_{k-2}x^{k-2} + … + a_1x + S) \mod P
$
应用模数会使函数循环，因为它只能达到模数的数量，然后它会再次回到零。
在多普通多项式应用模数的时候有一个需要注意的点：需要确保模数是一个比 Secret、多项式系数以及打算生成的份额数量更大的质数。选择的质数越大，找到 secret 的概率就越低。
当已知点数量达到阈值的时候，仍然可以通过插值找到 secret，但是现在由于应用模数丢失共享数据的部分信息从而低于共享数据数量的阈值并不能提供更多关于 secret 的信息，所以普通多项式存在的安全漏洞也就迎刃而解。

模运算

$
(a+b) \mod c = (a \mod c) + (b \mod c)
$

$
(a-b) \mod c = (a \mod c) - (b \mod c)
$

$
a^b \mod c = ((a \mod c)^b)\mod c
$

$(a \cdot b) \mod c = ((a \mod c) \cdot (b \mod c)) \mod c$

模运算不仅解决了普通多项式的安全问题，还限定了加密结果的长度（一定是小于取模的大素数大的），使数据的处理更加简单

Lagrange插值法

Lagrange插值法是一种通过已知的点集合来找到一个多项式函数，使得这个函数在这些已知点的值与实际值相等的方法。假设我们有n个点，我们可以找到一个n-1次的多项式来适应这些点。

假设我们有n个点 $(x_0, y_0), (x_1, y_1), …, (x_{n-1}, y_{n-1})$，Lagrange插值多项式可以表示为：

$
L(x) = \sum_{i=0}^{n-1} y_i \cdot l_i(x)
$

其中，$l_i(x)$ 是 Lagrange 基函数，定义为：

$
l_i(x) = \prod_{0 \leq m \leq n, m \neq i} \frac{x - x_m}{x_i - x_m}
$

每个 $l_i(x)$ 在 $x = x_i$ 时等于1，在 $x = x_j$ (j ≠ i) 时等于0。这就确保了在每个已知点 $x_i$ 上，$L(x_i) = y_i$。

简而言之，假定我们已知一个一元n次的多项式$f(x)$，我们只需要n+1个点，就可以通过Lagrange插值法快速的计算出$f(x)$的值。
而在此算法中，我们只需要计算出$f(0)$的值再取模即可计算出加密数据。

代码实现

package myShamirDemo

import (
	"math/big"
)

const prime = 257


func Encrypt(secret []byte, n, num int) [][]byte {
	if len(secret) == 0 || n <= 0 {
		panic("illegal input data")
	}
	
	if num < n {
		panic("num has to be greater than n")
	}
	result := initArray(num, len(secret))
	for j := 0; j < len(secret); j++ {
		f := getPolynomial(n, secret[j])
		for i := 0; i < num; i++ {
			if j == 0 {
				result[i][0] = byte(i + 1)
			}
			result[i][j+1] = f(uint8(i + 1))
		}
	}
	temp := Decrypt(result, n)
	for i := 0; i < len(secret); i++ {
		if temp[i] != secret[i] {
			return Encrypt(secret, n, num)
			break
		}
	}
	return result
}

func Decrypt(shares [][]byte, n int) []byte {
	if len(shares) == 0 {
		panic("illegal input data")
	}
	x := make([]int64, n)
	for i := 0; i < n; i++ {
		x[i] = int64(i + 1)
	}
	yss := initInt64Array(len(shares[0])-1, n)
	for i := 0; i < n; i++ {
		for j := 1; j < len(shares[i]); j++ {
			yss[j-1][i] = int64(shares[i][j])
		}
	}
	
	result := make([]byte, 0)
	for _, ys := range yss {
		secret := Lagrange(0, x, ys)
		temp, _ := new(big.Float).SetString(secret.FloatString(0))
		secretBigInt := new(big.Int)
		temp.Int(secretBigInt)
		secretBigInt.Mod(secretBigInt, big.NewInt(int64(prime)))
		tempSecret := int(secretBigInt.Int64())
		if tempSecret < 0 {
			tempSecret += prime
		}
		result = append(result, byte(tempSecret))
	}
	return result
}

func initArray(a, b int) [][]byte {
	result := make([][]byte, 0)
	for i := 0; i < a; i++ {
		nums := make([]byte, b+1)
		result = append(result, nums)
	}
	return result
}
func getPolynomial(n int, secretMsg byte) func(x uint8) uint8 {
	coefficients := make([]uint8, n-1) 
	for i := 0; i < n-1; i++ {
		for true {
			temp := uint8(rand.Intn(math.MaxInt8))
			if temp != 0 {
				coefficients[i] = temp
				break
			}
		}
	}
	return func(x uint8) uint8 {
		var count = new(big.Int).Set(big.NewInt(0))
		for i := 0; i < len(coefficients); i++ {
			bigCoefficient := new(big.Int).Set(big.NewInt(int64(coefficients[i])))
			exponent := new(big.Int).Set(big.NewInt(int64(n - 1 - i)))
			bigX := new(big.Int).Set(big.NewInt(int64(x)))
			bigPrime := new(big.Int).Set(big.NewInt(int64(prime)))
			bigX.Exp(bigX, exponent, bigPrime)
			bigX.Mul(bigX, bigCoefficient)
			bigX.Mod(bigX, bigPrime)
			count.Add(count, bigX)
			count.Mod(count, bigPrime)
		}
		count.Add(count, big.NewInt(int64(secretMsg)))
		count.Mod(count, big.NewInt(int64(prime)))
		return uint8(count.Int64())
	}
}

func getRandIndex(num int) []int {
	numArr := make([]int, 0)
	for i := 0; i < 256; i++ {
		numArr = append(numArr, i+1)
	}
	r := rand.New(rand.NewSource(time.Now().UnixNano()))
	r.Shuffle(len(numArr), func(i, j int) {
		numArr[i], numArr[j] = numArr[j], numArr[i]
	})
	return numArr[:num]

}

func Lagrange(x int64, xs, ys []int64) *big.Rat {
	l := big.NewRat(0, 1)
	for i := 0; i < len(xs); i++ {
		term := big.NewRat(ys[i], 1)
		for j := 0; j < len(xs); j++ {
			if i != j {
				num := big.NewRat(x-xs[j], 1)
				den := big.NewRat(xs[i]-xs[j], 1)
				frac := new(big.Rat).Quo(num, den)
				term.Mul(term, frac)
			}
		}
		l.Add(l, term)
	}
	return l
}

func initInt64Array(a, b int) [][]int64 {
	result := make([][]int64, 0)
	for i := 0; i < a; i++ {
		nums := make([]int64, b)
		result = append(result, nums)
	}
	return result
}