Shamir秘密分享(Python)：秘密长度>10时无法还原原始值

问题描述 #

实现Shamir秘密分享方案时，当原始秘密长度超过10时，还原结果出现错误变体（如"Hello World►/"、"Hello Worlc"）。尝试修改reconstruct_secret算法或增大FIELD_SIZE后，结果要么为空要么是乱码。

问题根源 #

1. 精度丢失：原代码使用Decimal进行拉格朗日插值，对于长字符串转换的超大整数，除法和取整过程中会出现精度偏差，导致还原的整数与原始值不一致。
2. 域大小不足：原FIELD_SIZE=10**5远小于长字符串对应的整数值，Shamir方案要求所有运算（秘密、系数、份额）必须在有限域内，秘密超出域大小会被自动取模，破坏原始数据。

修复方案 #

关键修改 #

• 改用有限域内的整数运算实现拉格朗日插值，彻底避免精度问题。
• 选用足够大的质数作为FIELD_SIZE，确保其大于原始秘密的数值大小。
• 所有多项式计算和插值操作均在模FIELD_SIZE下执行。

修复后代码 #

import random
from math import gcd

# 选用大质数作为有限域大小，需确保大于长字符串转成的整数
FIELD_SIZE = 10**18 + 3

def egcd(a, b):
    """扩展欧几里得算法，用于计算模逆"""
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    """计算a在模m下的逆元（a与m互质时有效）"""
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('模逆不存在')
    else:
        return x % m

def reconstruct_secret(shares):
    """有限域内的拉格朗日插值还原秘密"""
    secret = 0
    n = len(shares)
    for j in range(n):
        xj, yj = shares[j]
        numerator = 1
        denominator = 1
        for i in range(n):
            if i != j:
                xi, _ = shares[i]
                numerator = (numerator * (-xi)) % FIELD_SIZE
                denominator = (denominator * (xj - xi)) % FIELD_SIZE
        inv_denominator = modinv(denominator, FIELD_SIZE)
        term = (yj * numerator) % FIELD_SIZE
        term = (term * inv_denominator) % FIELD_SIZE
        secret = (secret + term) % FIELD_SIZE
    return secret

def polynom(x, coefficients, field_size):
    """有限域内计算多项式值"""
    result = 0
    for coeff in reversed(coefficients):
        result = (result * x + coeff) % field_size
    return result

def coeff(t, secret, field_size):
    """生成多项式系数，最高次项为原始秘密"""
    coeffs = [random.randrange(0, field_size) for _ in range(t-1)]
    coeffs.append(secret)
    return coeffs

def generate_shares(n, t, secret, field_size):
    """生成n个唯一x值的份额"""
    coefficients = coeff(t, secret, field_size)
    shares = []
    used_x = set()
    while len(shares) < n:
        x = random.randrange(1, field_size)
        if x not in used_x:
            used_x.add(x)
            y = polynom(x, coefficients, field_size)
            shares.append((x, y))
    return shares

if __name__ == '__main__':
    t, n = 3, 5
    tt = "Hello World!!!"
    secret = int.from_bytes(tt.encode(), byteorder='big')
    
    # 检查秘密是否在有限域范围内
    if secret >= FIELD_SIZE:
        raise ValueError("FIELD_SIZE过小，请更换更大的质数")
    
    shares = generate_shares(n, t, secret, FIELD_SIZE)
    pool = random.sample(shares, t)
    r_secret_int = reconstruct_secret(pool)
    
    r_secret_string = r_secret_int.to_bytes(
        (r_secret_int.bit_length() + 7) // 8, byteorder='big').decode('utf-8')
    print("原始秘密:", tt)
    print("还原秘密:", r_secret_string)

说明 #

• 有限域运算：所有计算均在模FIELD_SIZE下进行，保证插值结果完全精确。
• 模逆替代除法：使用扩展欧几里得算法计算分母的模逆，符合有限域的运算规则。
• 大质数域：选用的FIELD_SIZE是足够大的质数，确保原始秘密不会被截断。
• 唯一x值：生成份额时避免重复x，防止插值时出现分母为0的异常。

内容的提问来源于stack exchange，提问作者Shro