中国剩余定理的 (k, n) 门限方案

秘密分发

秘密 D 输入，k，n的输入和 p 的获取和上面一样，这里不多说，获取完后，要生成一个集合 D，其中有 n 个 di，且满足条件

1. p > D
2. d1<d2<...<dn
3. p 与任意 di 互素
4. di 之间两两互素
5. 最小的 k 个 di 的乘积 > p 与 最大的 k-1 个 di 的乘积

这里采取的方法是

1. 还是用 getPrime 函数，参数字节数为 max(D字节数，n字节数) + 2，并在后面判断若p<D或n，重新取值，保证 p > D,n
2. 用 getPrime 函数取 n 个素数，然后进行 sort() 排列，素数间一定两两互素，解决条件3，4
3. 判断 ‘最小的 k 个 di 的乘积 > p 与 最大的 k-1 个 di 的乘积’ 是否成立，若不成立，重新取值

生成 di

def make_d(bit, n): # 生成d序列
	d = []
	for i in range(n):
		tmp = getPrime(int(bit) + 3)
		if tmp not in d:
			d.append(tmp)
		else:
			i -= 1
	d.sort()

	return d

生成完之后进行检查：

def check(d, p, k, n): # 检查是否符合条件
	mm = p # p与最大的k-1个di的乘积
	m = getM(d, k)
	for i in range(n-k+1, n):
		mm *= d[i]
	if(m > mm):
		return True
	else:
		return False
    
    
def getM(d, k): # k个最小di的乘积
	m = 1
	for i in range(k):
		m *= d[i]
	return m
	
	
d = make_d(bit, n)
while (not check(d, p, k, n)):
	d = make_d(bit, n)
print(d)

在 [0,(m/p)-1] 的范围内随机取一个 r，计算 D' = D + rp，最后计算出 n 个 $Di$ 块

m = getM(d, k)
rand = random.randint(0, m//p-1)
print("r:", rand)

_D = D + rand*p
for i in range(n):
	print((_D % d[i], d[i]))

只要知道上述 Di 块中的任意 k 个，就可以应用中国剩余定理求出 D’。

公开 p 和 r，并分发每一份数据给每个秘密共享者。

效果图：

秘密恢复

输入 k，p 和每一份 Di，计算出 m = d1d2..dk ，为了应用中国剩余定理，首先求出 inv(m/di, di)，即 m/di 与 di 的逆元，然后计算出 ($\sum_{m=0}^k \frac{m}{di}yiDi$) mod m

def recover():
	k = int(input("k: "))
	rand = int(input("r: "))
	p = int(input("Prime: "))
	m1 = 1
	recoverD = []
	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))
	for i in recoverD:
		m1 *= i[1]
	result = 0
	for i in recoverD:
		y = gmpy2.invert(m1//i[1], i[1])
		result += m1//i[1]*y*i[0]

	DD = result % m1
	print("===============Result===============")
	print(libnum.n2s(DD-rand*p))

利用上面的数据进行计算：