Shamir 门限秘密共享算法：原理、Python 实现与破解流程

一、实验目的

掌握车联网中的数据共享方案原理，并利用 Python 编程实现 Shamir 门限秘密共享算法。

二、实验环境

Python 3.9 及以上版本。

三、实验内容

Shamir (t, w) 门限密钥共享方案，该方案由 Shamir 在 1979 年提出。该方案通过构造一个 t-1 次多项式，将需要共享的主密钥 S 作为常数项，并将碎片密钥分成 w 部分，分别分发给 w 个参与者。当碎片密钥数量大于或等于 t 时，就可以求解出主密钥 S。

子密钥生成：

构造多项式：

F(x) = s + a1 * x + a2 * x^2 + ... + a(t-1) * x^(t-1)

其中 s 为密钥，p 为素数 (s 取 w 个不相等的 x 带入 F(x) 中，得到 w 组子密钥，分发给 w 个人保管)，并将 p 公开。销毁子密钥生成多项式，每个人保管自己的子密钥。

恢复密钥：

构造多项式：

F(x) = s + a1 * x + a2 * x^2 + ... + a(t-1) * x^(t-1)

取 x = 0，代入 t 组密钥可以求解出 F(0)，也就是主密钥 s。

1) 熟悉并简要说明车联网中的 Shamir 数据共享方案原理。

Shamir 门限秘密共享方案是一种将秘密信息分割成多个碎片，并分发给多个参与者的方案。只有收集到至少 t 个碎片才能恢复原始秘密。在车联网中，可以利用该方案来保护关键数据，例如车辆身份信息、行驶记录等。例如，可以将车辆身份信息分成多个碎片，并分别存储在不同的车载设备上。只有收集到至少 t 个碎片才能恢复车辆身份信息，从而防止恶意攻击者获取车辆身份信息。

2) 利用 Python 3.9 编程实现 Shamir 门限秘密共享算法。

import Crypto.Util.number as numb
import random


# 求逆的函数，之前的版本用python2写的，这次用的python3，只把整除符号改了一下
def oj(a, n):
    a = a % n
    s = [0, 1]
    while a != 1:
        if a == 0:
            return 0
        q = n // a
        t = n % a
        n = a
        a = t
        s += [s[-2] - q * s[-1]]
    return s[-1]


# max_length 为p的长度，同时也是秘密的最大长度
# secret_is_text =0 默认输入时文本， 非0时认为是数字
# p 默认为0， 会根据max_length 自动生成，不为0时直接使用，需要保证p为素数， 函数内没有素性检验
def create(max_length=513, secret_is_text=0, p=0):
    if not p:
        p = numb.getPrime(max_length)

    w = int(input("请输入秘密保存人数："))
    t = int(input("请输入秘密恢复所需人数："))
    while not (t > 0 and t <= w):
        t = int(input("请重新输入："))
    s = input("请输入你的秘密:")

    if secret_is_text:
        s = numb.bytes_to_long(s.encode("utf-8"))
    else:
        try:
            s = int(s)
        except Exception as e:
            s = numb.bytes_to_long(s.encode("utf-8"))

    x_list = list()
    a_list = list()
    i = w
    while i > 0:
        x = random.randint(p // 2, p)  # 该范围没有特定限制，如果想让xi,yi取小一点儿的话可把范围写小点儿，但是要大于w
        if x not in x_list:
            x_list.append(x)
            i -= 1

    for a in range(t):
        a_list.append(random.randint(p // 2, p))  # 同上

    result = list()
    for x in x_list:
        y = s
        for a_n in range(t):
            a = a_list[i]
            y += a * pow(x, i + 1, p)
        result.append((x, y))
    return t, p, result


# get_text=1 默认恢复为字符串，若想得到数字填0
def restore(p, information, get_text=1):
    x_list = list()
    y_list = list()
    for x, y in information:
        x_list.append(x)
        y_list.append(y)

    s = 0
    for x_i in range(len(x_list)):
        tmp_num = y_list[x_i]
        x_i_j = 1
        for x_j in range(len(x_list)):
            if x_i != x_j:
                tmp_num = tmp_num * (0 - x_list[x_j]) % p
                x_i_j *= x_list[x_i] - x_list[x_j]
        tmp_num = tmp_num * oj(x_i_j, p) % p
        s += tmp_num

    s = s % p
    print(s)
    if get_text:
        try:
            s = numb.long_to_bytes(s)
            s = s.decode("utf-8")
        except Exception as e:
            print(e)

    return s


t, p, result = create()  # result为秘密碎片的列表

print(result)
print("还原出最初的秘密S:")
print(restore(p, result[:t], 0))

四、破解流程

由于 Shamir 门限秘密共享算法需要至少 t 个碎片才能恢复秘密，因此破解流程需要获取至少 t 个碎片。

收集至少 t 个碎片。 可以通过拦截车联网传输、入侵车载设备等方式获取碎片。
根据已知的 p 和收集到的 t 个碎片，使用恢复函数 restore() 恢复出秘密 S。
如果碎片数量不足 t，则无法破解秘密 S。

注意： 由于该算法的安全性依赖于 p 的素性，因此破解者需要知道 p 的值才能进行破解。如果 p 的值保密，则该算法的安全性将大大提高。

五、总结

Shamir 门限秘密共享算法是一种常用的数据共享方案，可以有效地保护重要信息。但是，该算法也存在一定的破解风险，需要采取相应的安全措施，例如使用更大的素数 p、使用更安全的传输协议等，才能保证数据的安全。