Shamir (k, n)门限秘密分发

秘密分发我分为了两个模块，一个是分发，一个是恢复。

秘密分发

环境：Windows 10，Python 3.7.1

因为k，n都是整数，因此输入的时候进行一下强制类型转换，对于需要分发的秘密，示例是整数，但有可能是字符串，因此利用 libnum.s2n 将字符串转换成整数，再进行运算。

D = input("Input your secret: ")
n = int(input("How many parts do you want to devide: "))
k = int(input("Subset: "))

对于素数 p 的获取，我使用了 Crypto.Util.number 模块中 getPrime 函数，它的参数取决于 D 和 n 的字节长度，在p不会太过大的情况同时，保证 D、n<p，并在后面判断若p<D或n，重新取值，然后用随机数生成对多项式的系数进行赋值，放进一个列表里，然后公开 p 和 k。

def printnum(num): # 打印多项式，便于自己查看
	print(str(num[0]), end='')
	for i in range(1, len(num)):
		if(i == 1):
			print('+' + str(num[i]) + "x", end='')
		else:
			print('+' + str(num[i]) + "x^" + str(i), end='')
	print()


D = libnum.s2n(D)
bit_D = math.log(D, 2)
bit_n = math.log(n, 2)
bit = max(bit_D, bit_n)
p = getPrime(int(bit) + 2)
while p < D or p < n:
		p = getPrime(int(bit) + 2)

num = [D]
for i in range(k-1):
	num.append(random.randint(1, p))

printnum(num)
print("Your Prime:", p)
print("Subset:", k)

然后求出所有的 Di，将它的 i 和 Di 以 (x, y) 的形式打包存储进一个列表中。

def f(num, x, p): # 计算每个i多项式方程的值
	result = 0
	for i in range(len(num)):
		result += num[i]*(x**i)
	return (x, result % p)


_D = []
for i in range(1, n+1):
	tmp = f(num, i, p)
	_D.append(tmp)
	print("D" + str(i) + ':' + str(tmp))

将每一个 Di 输出，由秘密输入者进行分发 n 个部分。

运行效果：

(k, n) = (3, 6)

秘密恢复

首先输入 k，然后输入素数 p，接着将 Di 的值输入进去，以 (x, y) 的形式打包存储进一个列表中。

recoverD = []
print("Now to recover your secret")
k = int(input("Subset: "))
p = int(input("Prime: "))
print("Now to input your point like x,y")
for i in range(k):
	x, y = map(int, input("Input point " + str(i+1) + ": ").split(','))
	recoverD.append((x, y))

数据获取完毕后，利用拉格朗日插值法进行计算，将 i 值和 Di 的值分开各位一个列表，然后每一次计算每一个小块的 q(x)。对于多项式的计算，形如 (x-1)(x-2) ，这里为了偷懒我利用了 numpy 里的 array，并利用它的性质计算多项式。

def l(D): # 拉格朗日插值法
	x_s, y_s = zip(*D)
	lst = []
	for i in range(len(x_s)):
		others = list(x_s)
		cur = others.pop(i)
		dxs = cal(cur, others)
		fm = fm_cal(cur, others)

		lst.append((dxs, fm))

	return lst


def cal(x, others): # 计算多项式，即分子
	re = np.array([1])
	for i in others:
		p = np.array([1, -i])
		re = np.convolve(re, p)

	return re


def fm_cal(x, others): # 计算分母
	re = 1
	for i in others:
		re *= (x-i)

	return re

待计算好返回每一个 Di 的分子和分母后，即可以计算 i 模 p 的逆元，利用 gmpy2.invert 来计算，求出后将各项相加，即是多项式方程，其中常数项位秘密，可利用 libnum.n2s() 恢复成字符串。

def recover_secret(k, p, D):
	re = l(D)
	cnt = 0
	fz, fm = zip(*re)
	for i in range(k):
		inv = gmpy2.invert(fm[i], p)
		cnt += D[i][-1] * inv * fz[i][-1]
	cnt %= p

	return libnum.n2s(cnt)

利用上面的秘密分发的数据进行恢复：

如：
Prime: 167569419418447
Subset: 3
D2:(2, 59529348878006)
D4:(4, 21970926061031)
D5:(5, 35309714193955)

效果图如下：