Shamir门限秘密共享方案
Shamir的秘密共享（Shamir’s Secret Sharing）是一个将秘密分解为多个部分的方法，这样只有得到一定数量的部分才能重新构建该秘密。它是基于多项式插值，尤其是Lagrange插值原理。
在秘密共享的场景中，Shamir的方法允许一个秘密被分解为n个部分，其中任何k个部分可以用来重新构建原始的秘密，但k-1个部分或更少的部分没有任何信息。
以下是该方法的基本原理和流程：
选择秘密: 假设我们有一个秘密S，并且S是一个数字。在数字图像中，这一数字可认为是图片中各个像素值。
定义多项式: 选择一个k-1阶多项式：
$$
f(x)=a_0+a_1x+a_2x^2+…+a_{k-1}x^{k-1}
$$
其中，$a_0=S$(秘密），并且$a_0,a_2,…,a_{k-1}$是随机数。
生成分享：对于共享秘密的每个接收者，选择一个不同的x值，并计算多项式f(x)在这个x值上的值。这将生成一系列的(x, y)坐标，其中x是x值，y是f(x)的结果。
分发分享：将每个接收者的(x, y)坐标提供给相应的接收者。每个接收者将获得一个坐标点，这个坐标点包含了足够的信息来还原出原始的秘密。
重构秘密：为了还原原始秘密S，至少需要k个坐标点。这可以通过使用拉格朗日插值法来实现，从这些坐标点中重建多项式f(x)，并找到其常数项$a_0$，即原始秘密S。
改进部分
课上示例为灰度图片，要实现彩色图片秘密共享其实也很简单，把彩色图片分成RGB三个通道分别按灰度图片的方法处理，三通道合成为一个其中一个子秘密，共n个子秘密，选择其中任意k个（门限）即可恢复原图。
在解密实现上，使用了拉格朗日插值函数进行逐比特差值恢复。在拉格朗日函数的实现上进行了优化改进，由于原始的浮点数计算将会产生小数，在恢复为像素时由于近似运算会使恢复的秘密图片产生可察觉的视觉差异。这里将原拉格朗日函数中的除法修改为与其模逆元的乘法，避免了小数的出现，由于原本像素模数256不是质数，在计算模逆元时会带来一定麻烦，因此模数选用了大小近似但是质数的257，在此基础上可以使用费马小定理计算模逆元，提高了算法的效率，从测试结果看，这一替换方法在秘密恢复过程中不会产生可察觉的视觉影响。
效果展示
采用 3/5 门限共享 ，原图如下：
加密生成的5个子秘密如下：
对以上彩色图像的 5 个子秘密进行了组合遍历测试，即遍历了 5 个子秘密中任意选取 3 个的所有可能情况，测试可视化结果如下：
源码
from PIL import Image
import numpy as np
#--------------------------------参数设定-------------------------------
n = 5 # 秘密分割份数
r = 3 # 门限数
path = 'test4.png' # 秘密图片路径
testNum = 4 # 用于测试图片的命名
mod = 257 # 模数
#--------------------------------参数设定-------------------------------
def read_image(path):
'''
input: 图片路径
output: 图片矩阵的三个通道, 图片矩阵形状
'''
img = Image.open(path)
img_array = np.asarray(img)
red_channel = img_array[:,:,0].flatten()
green_channel = img_array[:,:,1].flatten()
blue_channel = img_array[:,:,2].flatten()
return red_channel, green_channel, blue_channel, img_array.shape
def polynomial(img, n, r):
'''
input:
img: 输入图像，它应该是一个2D numpy数组。
n: 想生成的图像的数量。
r: 多项式的阶数。
output:
一个形状为 (n, num_pixels) 的numpy数组，其中每一行代表一个生成的图像
'''
num_pixels = img.shape[0]
coef = np.random.randint(low = 0, high = mod, size = (num_pixels, r - 1))
gen_imgs = []
for i in range(1, n + 1):#子秘密
base = np.array([i ** j for j in range(1, r)])
base = np.matmul(coef, base)
img_ = img + base
img_ = img_ % mod
gen_imgs.append(img_)
return np.array(gen_imgs)
def lagrange(x, y, num_points, x_test):
l = np.zeros(shape=(num_points, ))
for k in range(num_points):
l[k] = 1
for k_ in range(num_points):
if k != k_:
num = (x_test - x[k_]) % mod
den = (x[k] - x[k_]) % mod
inverse_den = pow(int(den), mod-2, mod)
l[k] = (l[k] * num * inverse_den) % mod
L = 0
for i in range(num_points):
L = (L + y[i]*l[i]) % mod
return L
def decode(imgs, index, r, n):
assert imgs.shape[0] >= r
x = np.array(index)
dim = imgs.shape[1]
img = []
for i in range(dim):
y = imgs[:, i]
pixel = lagrange(x, y, r, 0) % mod
img.append(pixel)
return np.array(img)
if __name__ == "__main__":
#------------------------------------加 密------------------------------------
print("**************")
print("Encrypt begin.")
print("**************")
r_channel, g_channel, b_channel, shape = read_image(path)
gen_imgs_r = polynomial(r_channel, n = n, r = r)
gen_imgs_g = polynomial(g_channel, n = n, r = r)
gen_imgs_b = polynomial(b_channel, n = n, r = r)
for i in range(n):
# 将三个通道合并，得到其中一个子秘密
combined_img = np.stack((
gen_imgs_r[i].reshape(shape[0], shape[1]),
gen_imgs_g[i].reshape(shape[0], shape[1]),
gen_imgs_b[i].reshape(shape[0], shape[1])
), axis=-1)
Image.fromarray(combined_img.astype(np.uint8)).save(f"test{testNum}_{i+1}.jpeg")
print(f"test{testNum}_{i+1}.jpeg is saved.")
#------------------------------------加 密------------------------------------
#------------------------------------解 密------------------------------------
print("**************")
print("Decrypt begin.")
print("**************")
# 遍历所有图片组合以验证解密效果
for i in range(n):
for j in range(i+1, n):
for k in range(j+1, n):
# 选择子秘密和对应的x值
selected_subsecrets = [i, j,k]
selected_x_values = [i+1, j+1,k+1]
# 解密
origin_img_r = decode(gen_imgs_r[selected_subsecrets, :], selected_x_values, r=r, n=n)
origin_img_g = decode(gen_imgs_g[selected_subsecrets, :], selected_x_values, r=r, n=n)
origin_img_b = decode(gen_imgs_b[selected_subsecrets, :], selected_x_values, r=r, n=n)
# 将解密结果合并
combined_origin_img = np.stack((
origin_img_r.reshape(shape[0], shape[1]),
origin_img_g.reshape(shape[0], shape[1]),
origin_img_b.reshape(shape[0], shape[1])
), axis=-1)
# 保存图像，名称包含所选的子秘密的编号
filename = f"test{testNum}_recovered_{i+1}_{j+1}_{k+1}.jpeg"
Image.fromarray(combined_origin_img.astype(np.uint8)).save(filename)
print(f"{filename} is saved.")
# 挑选制定的子秘密进行解密，如下标第1,2,4张，对应x值为2,3,5
# selected_subsecrets = [1,2,4]
# selected_x_values = [2,3,5]
# origin_img_r = decode(gen_imgs_r[selected_subsecrets, :], selected_x_values, r=r, n=n)
# origin_img_g = decode(gen_imgs_g[selected_subsecrets, :], selected_x_values, r=r, n=n)
# origin_img_b = decode(gen_imgs_b[selected_subsecrets, :], selected_x_values, r=r, n=n)
# 将解密结果合并
# combined_origin_img = np.stack((
# origin_img_r.reshape(shape[0], shape[1]),
# origin_img_g.reshape(shape[0], shape[1]),
# origin_img_b.reshape(shape[0], shape[1])
# ), axis=-1)
# Image.fromarray(combined_origin_img.astype(np.uint8)).save(f"test{testNum}_origin.jpeg")
#------------------------------------解 密------------------------------------