网鼎杯玄武 crypto 0：解析变形的 Shamir 密钥分享机制

题目概述

本题围绕一个基于 Shamir 密钥分享的加密方案展开，涉及自定义的ShamirSS类和ShamirProtocol类。通过特定的input_share方法将flag分割成大量份额并保存为.sobj文件，其中n_players与flag长度相关，threshold设置为len(flag) * 2，模数p为 257，份额计算方式与常规 Shamir 密钥分享有明显区别

题目

# SageMath version 10.0, Release Date: 2023-05-20

from sage.all import *
from Crypto.Util.number import *

from secret import flag

flag = flag.lstrip(b"NSSCTF{").rstrip(b"}")


class ShamirSS:
    def __init__(self, coefs, value):
        self.coefs = coefs
        self.value = value


class ShamirProtocol:
    def __init__(self, n_players, threshold, modulus):
        self.n_players = n_players
        self.threshold = threshold

        assert isPrime(modulus), "Modulus must be a prime number"
        self.modulus = modulus

    def input_share(self, values):
        coefs = [
            [getRandomRange(1, self.modulus) for _ in range(self.threshold)]
            for _ in range(self.n_players)
        ]

        randoms = values + [getRandomRange(1, self.modulus) for _ in range(self.threshold - len(values))]

        values = [
            sum([r * c for r, c in zip(randoms, coef)]) % self.modulus
            for coef in coefs
        ]

        shares = [ShamirSS(coef, value) for coef, value in zip(coefs, values)]
        return shares


protocol = ShamirProtocol(len(flag), len(flag)45 * 2, 257)
values = list(flag)

import os

os.mkdir("shares")

for i in range(10000):
    shares = protocol.input_share(values)
    save(shares, f"shares/share_{i}.sobj")

Shamir 密钥分享原理回顾

Shamir 密钥分享算法（Shamir's Secret Sharing）是一种秘密共享方案，用于将一个秘密（如加密密钥）分割成多个份额，使得只有当足够数量的份额组合在一起时才能恢复出原始秘密。用于实现门限秘密共享。

基本数学属性：

k-1次多项式需要k个点唯一确定

Y=aX^2+bX+S a,b为随机数，S为秘密

比如 Y=94X^2+166X+1234 ，其实我们只需要三个点就可以恢复秘密S，即通过三个点恢复多项式，当X取0时，Y=S

安全性：

如果没有定义有限域，可以通过爆破恢复S

基本原理：

将多项式定义在有限域上，通过应用模数取余数)将普通多项式转换为循环多项式，使得这些点从有规律，可穷举的上图转换为无规律，难穷举的下图。
Y =aX2+bX+S mod p

该算法基于多项式插值原理

矩阵

多元同余方程组

根据克拉姆法则

从题目分析Shamir密钥分享

ShamirSS 类

包含两个属性：coefs（系数列表）和value（该份额对应的值）。

ShamirProtocol 类

在初始化时，它接收三个参数：

n_players：参与分享的玩家数量（在本题中与要分享的秘密的长度相关，即len(flag)）。
threshold：能够重构出秘密所需的最少份额数量（本题中设置为len(flag) * 2）。
modulus：一个素数，用于在计算份额值等操作中的模运算，确保计算结果在一定范围内，这里通过断言确保传入的是素数（本题模数为257）。

input_share方法：

首先，生成一个二维列表coefs，其中每个子列表包含threshold个在1到modulus之间的随机数。这个coefs列表的长度是n_players，即每个参与者都有一组对应的系数。
然后，创建一个randoms列表，它由传入的values（在本题中是flag的字节列表形式）和额外生成的threshold - len(values)个在1到modulus之间的随机数组成。
接着，通过循环计算每个参与者份额对应的values。计算方式是对于每个参与者的系数列表coef，将randoms中的每个元素与coef中的对应元素相乘后求和，再对modulus取模。
最后，根据计算得到的系数列表和份额值创建ShamirSS对象列表，并返回这些份额对象列表。

与常规的区别

1.n_player和threshold

n_players=len(flag)，threshold=2*len(flag)

这里n_players<threshold。常规的Shamir密钥分享，参与者player要大于threshold，然后用基多项式和每个参与者的份额yi ,插值出多项式，恢复秘密值。

2.份额计算方式

计算份额的方式是通过values = [sum([r * c for r, c in zip(randoms, coef)]) % self.modulus for coef in coefs]。这里是将randoms（包含秘密字节和额外随机数）中的元素与系数列表coef中的元素对应相乘并求和，然后取模得到份额值。与常规方式相比，不是基于多项式对参与者编号的求值，而是一种更复杂的线性组合计算。

3.多项式系数生成

在input_share方法中，对于每个参与者，系数列表coefs是通过[getRandomRange(1, self.modulus) for _ in range(self.threshold)]生成的。这里没有像常规方式那样先确定一个以秘密为常数项的多项式，而是生成了多个随机系数列表（每个参与者一组），并且没有将秘密作为系数的一部分。

解法

根据c 的长度，我们可知flag的长度 72//2=36

import os

from Crypto.Util.number import *
from tqdm import *
from sage.all import *

class ShamirSS:
    def __init__(self, coefs, value):
        self.coefs = coefs
        self.value = value


from tqdm import trange
shares=[]
shares_folder = "shares"
sum=0
p=257
n=72//2
for i in trange(10000):
    file_path=os.path.join(shares_folder, "share_" + str(i) + ".sobj")
    share=load(file_path)
    shares.append(share)
    # for s in share:
    #     print(s.coefs)
    #     print(len(s.coefs))
    #     break
    # break
    C1 = matrix(GF(p), [s.coefs[:n] for s in share])
    C2 = matrix(GF(p), [s.coefs[n:] for s in share])
    V = vector(GF(p), [s.value for s in share])
    if (C2.rank()< n):
        sum+=1
print(sum)

100%|██████████| 10000/10000 [00:51<00:00, 194.63it/s]
38

发现10000条数据里有 38 份数据满足c_2不满秩,38>36可以恢复flag

for i in trange(10000):
    file_path=os.path.join(shares_folder, "share_" + str(i) + ".sobj")
    share=load(file_path)
    shares.append(share)
    # for s in share:
    #     print(s.coefs)
    #     print(len(s.coefs))
    #     break
    # break
    C1 = matrix(GF(p), [s.coefs[:n] for s in share])
    C2 = matrix(GF(p), [s.coefs[n:] for s in share])
    V = vector(GF(p), [s.value for s in share])
    if (C2.rank()< n):
        T= C2.left_kernel().basis()[0]
        VT=T*V
        TC1=T*C1
        R.append(VT)
        L=L.stack(TC1)
print(f'{R=}')
print(f'{L=}')
R = vector(Zmod(p), R)
flag = L.solve_right(R)
print(flag)
print(''.join(chr(_) for _ in flag))