金风玉露一相逢，便胜却人间无数。

始于2024-03-15，新增2024-08-09

前言

先来看一个故事，1月8日，贵州省锦屏县平秋镇圭叶村开始了第七届村主任换届选举。这个藏身大山深处的偏僻小山村，最近刚刚因一枚奇特的公章而成为了人们关注的焦点。为了在村里进行民主理财管理，一年多前，村民想出了一个点子，把村财务公章分成五瓣交由5位选出的村民代表掌管，专门审核村干部的开销。近日消息一传出后，顿时引起了外界的广泛热议。这枚“五瓣章”更是被网友称为史上最牛公章。

那么在密码学当中，有没有这种方案，必须满足一定人数才能解出来整个秘密消息，而少于预设的人数阈值则解不出来这个秘密消息呢？

Shamir秘密共享方案

Shamir秘密共享方案，叫做Shamir Secret Sharing, SSS。

其有两个参数 n、t（$t\le n$），由此也称作 (t,n)-门限方案 。

秘密 s 被分成 n 份信息，每一份信息被称为一个子密钥，只有至少t份子密钥时才能会出秘密 s，t称为方案的门限值

子密钥生成算法

秘密为 s
大素数 p
确定 n，作为子密钥的持有者的数量
确定 t
n个持有者记作 $P_1,P_2,\dots,P_n$ ，$P_i$ 分到的子密钥为 $f(i)$
销毁多项式

恢复秘密过程

当 x = 0 时，$f(0)=s$ ，即可恢复出 s ，s即我们所求

恢复秘密至少需要 t 个子密钥

用到拉格朗日插值公式：

计算过程如下：

References:

Shamir 门限方案｜秘密共享｜拉格朗日插值｜密码学_shamir门限方案-CSDN博客

Shamir 门限秘密共享方案 - SAGIRI’S BLOG

例题

[NKCTF2023] Raven

题目

#!/usr/bin/env sage
# Problem by rec, with a bad raven.
import os, hashlib
from Crypto.Util.number import *
from Crypto.Cipher import AES

def Raven(n: int, secret: bytes):
    H = lambda x: hashlib.md5(os.urandom(8) + x).digest()

    p = getPrime(728)
    R.<z> = PolynomialRing(GF(p))

    seed = H(secret)
    f = R(
        [bytes_to_long(secret)] + [bytes_to_long(H(seed)) for _ in range(n - 1)]
    )
    x = [getRandomRange(2, p - 1) for _ in range(n)]
    y = [ZZ(f(xi)^2 + getPrime(256)) for xi in x]

    pairs = list(zip(x, y))
    return p, pairs

flag = b'#####'
key = os.urandom(16)
cipher = AES.new(key=key, IV=bytes(range(16)), mode=AES.MODE_CBC)
ct = cipher.encrypt(flag + os.urandom(16 - len(flag) % 16))
p, pairs = Raven(4, key)

print(f"{p = }\n{pairs = }\n{ct = }")
'''
p = 1018551160851728231474335384388576586031917743463656622083024684199383855595168341728561337234276243780407755294430553694832049089534855113774546001494743212076463713621965520780122783825100696968959866614846174188401153
pairs = [(615358616404864757405587650175842125441380884418119777842292095751090237848084440177153221092040264723889917863863854377665802549748720692225139890884830475485512763149974948701807492663962748292710803434009673589337265, 84982753624462868217739962129526665082932464631118597651920986288766037499319751354013335054886685186857222944776560264528363811382359242656883760986496856164448940929282013856762706210675691655747370624405968909408102), (528363810186974800127873139379943131424126521611531830591311656948009967709310974894584084912262479395720199930206495204352231804549705720854271566421006481173043064265399467682307971910488405265826107365679757755866812, 496810092723839642457928776423789418365006215801711874210443222720529161066621876103037104247173440072986344011599384793861949574577559989016501090247331146721371126871470611440468688947950954988175225633457347666551944), (68711183101845981499596464753252121346970486988311398916877579778110690480447199642602267233989256728822535174215153145632158860662954277116345331672194812126361911061449082917955000137698138358926301360506687271134873, 995428771589393162202488762223106955302099250561593105620410424291405842350539887383005328242236156038373244928147473800972534658018117705291472213770335998508454938607290279268848513727721410314612261163489156360908800), (61574167546312883246262193556029081771904529137922128124933785599227801608271357738142074310192454183183340219301304405636497744152219785042075198056952749425345561162612590170550454476602892138914473795478531165181812, 618169326093802548516842299173393893046765466917311052414967158839652012130855552015876657514610755108820971877570295328618373296493668146691687291894702228119875561585283226588768969944781923428807766632578060221034862)]
ct = b"|2\xf0v7\x05Y\x89\r]\xe93s\rr)#3\xe9\x90%Z\x9a\xd9\x9ck\xba\xec]q\xb8\xf2'\xc8e~fL\xcf\x93\x00\xd6^s-\xc9\xd6M"
'''

题解：

记 getPrime(256) 为 t ，

f = R(
        [bytes_to_long(secret)] + [bytes_to_long(H(seed)) for _ in range(n - 1)]
    )
print(f)
# 267335269824855211160668069721049574997*z^3 + 213474783285830430446771422061600488619*z^2 + 206893878840893771912598891815113528931*z + 269303276331389960303404727575127360280

可以得到函数$f(x)=ax^3+bx^2+cx+d\bmod p$

而 $y=f(x)^2+t$

根据最高项幂可以看出这里的门阀值为 4，恰好四组数据，可解得 s，即此处的d，也即 key

两式联立得

$y_i=a^2x_i^6+2abx_i^5+(b^2+2ac)x_i^4+(2ad+2bc)x_i^3+(2bd+c^2)+2cdx_i+d^2+t_i$

也即：

$a^2x_i^6+2abx_i^5+(b^2+2ac)x_i^4+(2ad+2bc)x_i^3+(2bd+c^2)+2cdx_i+d^2-y_i=-t_i$

构造示例

$c = mb+r \mod n $ ,

根据 la 佬的格构造示例，构造如下格：

$d^2~~~ 2cd~~~c^2+2bd~~~2ad+2bc~~~2ac+b^2~~~2ab~~~a^2~~~1~~~k_1\cdots k_4 \begin{bmatrix} 1 & & & & & & & x_1^0 &\cdots & &x_4^0 \\ & & \ddots & & & & & \vdots & \vdots & &\vdots \\ & & & & & 1 & & x_1^6 &\cdots & &x_4^6 \\ & & & & & & 2^{256} & -y_1 &\cdots & &-y_4 \\ & & & & & & & p & & & \\ & & & & & & & & \ddots & & \\ & & & & & & & & & &p \end{bmatrix}=d^2~~~ 2cd~~~c^2+2bd~~~2ad+2bc~~~2ac+b^2~~~2ab~~~a^2~~~2^{256}~~~-t_1\cdots -t_4$

这里直接求的d似乎不准确，不能直接用做key求来AES求flag，所幸求出 a、b、c再求出的d是可以的

LLL算法功能暂且一张截图，后面或许会总结，到时候再写上去，如果不总结，那就。。。。

exp:

import libnum, gmpy2
from Crypto.Cipher import AES

p = 1018551160851728231474335384388576586031917743463656622083024684199383855595168341728561337234276243780407755294430553694832049089534855113774546001494743212076463713621965520780122783825100696968959866614846174188401153
pairs = [(615358616404864757405587650175842125441380884418119777842292095751090237848084440177153221092040264723889917863863854377665802549748720692225139890884830475485512763149974948701807492663962748292710803434009673589337265, 84982753624462868217739962129526665082932464631118597651920986288766037499319751354013335054886685186857222944776560264528363811382359242656883760986496856164448940929282013856762706210675691655747370624405968909408102), (528363810186974800127873139379943131424126521611531830591311656948009967709310974894584084912262479395720199930206495204352231804549705720854271566421006481173043064265399467682307971910488405265826107365679757755866812, 496810092723839642457928776423789418365006215801711874210443222720529161066621876103037104247173440072986344011599384793861949574577559989016501090247331146721371126871470611440468688947950954988175225633457347666551944), (68711183101845981499596464753252121346970486988311398916877579778110690480447199642602267233989256728822535174215153145632158860662954277116345331672194812126361911061449082917955000137698138358926301360506687271134873, 995428771589393162202488762223106955302099250561593105620410424291405842350539887383005328242236156038373244928147473800972534658018117705291472213770335998508454938607290279268848513727721410314612261163489156360908800), (61574167546312883246262193556029081771904529137922128124933785599227801608271357738142074310192454183183340219301304405636497744152219785042075198056952749425345561162612590170550454476602892138914473795478531165181812, 618169326093802548516842299173393893046765466917311052414967158839652012130855552015876657514610755108820971877570295328618373296493668146691687291894702228119875561585283226588768969944781923428807766632578060221034862)]
ct = b"|2\xf0v7\x05Y\x89\r]\xe93s\rr)#3\xe9\x90%Z\x9a\xd9\x9ck\xba\xec]q\xb8\xf2'\xc8e~fL\xcf\x93\x00\xd6^s-\xc9\xd6M"

L = Matrix(ZZ,12,12)

for i in range(7):
    L[i,i]=1

L[7,7] = 2^256

for i in range(4):
    for j in range(7):
        L[j,8+i]=pairs[i][0]^j
        
for i in range(4):
    L[7,8+i] = -pairs[i][1]
for i in range(8,12):
        L[i,i] = p

L = L.LLL()[1]
print(list(L))

a = int(gmpy2.iroot(abs(L[6]), 2)[0])
b = abs(L[5])//(2*a)
c = (abs(L[4])-b^2)//(2*a)
d = abs(L[1])//(2*c)
key = libnum.n2s(int(d))
cipher = AES.new(key=key, IV=bytes(range(16)), mode=AES.MODE_CBC)
print(cipher.decrypt(ct))

# nkctf{..escape..}

NKCTF2023·Crypto WP | Harry’s Blog (harry0597.com)

EZshamir

Shamir + LWE

task.sage

import os
from random import getrandbits
from hashlib import sha256, md5
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from secret import flag

class Shamir:
    def __init__(self, pbits, noise_bit, n, m):
        self.pbits = pbits
        self.noise_bit = noise_bit
        self.n = n
        self.m = m
        self.p = getPrime(pbits)
        P.<x> = PolynomialRing(Zmod(self.p))
        self.poly = P([bytes_to_long(sha256(os.urandom(32)).digest()) for i in range(self.n)])

    def sample(self):
        t = getrandbits(self.pbits)
        y = int(self.poly(t))
        noise = getrandbits(noise_bit)
        return (t, y | noise)

    def get_msg(self):
        res = []
        for i in range(self.m):
            res.append(self.sample())
        return res

pbits = 400
noise_bit = 32
n = 100
m = 75

shamir = Shamir(pbits, noise_bit, n, m)
coefficient = shamir.poly()
key = "".join([str(i) for i in list(coefficient)[1:]])
key = md5(key.encode()).digest()
aes = AES.new(key = key, mode = AES.MODE_ECB)
ct = aes.encrypt(pad(flag, 16))

with open("data.txt", "w") as f:
    f.write(str(shamir.p)+'\n')
    f.write(str(shamir.get_msg())+'\n')
    f.write(str(bytes_to_long(ct))+'\n')

如果我们知道 LWE，就容易看出这题除了是Shamir，还涉及 LWE，低位加噪

何为 LWE？看完这篇想必就有大概的认识

初探全同态加密之二：格密码学与LWE问题 - 知乎 (zhihu.com)

有点抽象，所以结合 LWE | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz) 一起食用

给定矩阵A以及带有误差的乘积$Ax+e$，还原出未知的向量x。

$\vec{b} =A\vec{x}+\vec{e}$

其中e是我们在一个固定数值范围内随机采集的一个随机噪音向量 ，在模p下要显得数量级较小

带上了噪音之后，这个问题就变成了已知一个矩阵A，和它与一个向量x相乘得到的乘积再加上一定的误差（error）e，即Ax+e，如何有效的还原（learn）未知的向量，我们把这一类的问题统称为误差还原（Learning With Error， LWE）问题

结合 LWE，我们可以得到如下多项式：

$a_0+a_1x_i+a_2x_i^2+\dots+a_{n-1}x_i^{n-1} +e_i=b_i \pmod p$

这里 xi = t，bi = y | noise

转换一下：

$x_{75\times 100}A_{100\times 1}+e_{75\times 1}=b_{75\times 1}$

构造矩阵如下：

$(a_0~~~a_1~~~\dots ~~~a_{99}~~~1~~~l_0~~~l_1~~~\dots~~~l_{99})\begin{bmatrix} 1 & & & & & & & x_1^0 &\cdots & &x_{75}^0 \\ & & \ddots & & & & & \vdots & \vdots & &\vdots \\ & & & & & 1 & & x_{1}^{99} &\cdots & &x_{75}^{99} \\ & & & & & & K & -b_1 &\cdots & &-b_{75} \\ & & & & & & & p & & & \\ & & & & & & & & \ddots & & \\ & & & & & & & & & &p \end{bmatrix}=(a_0~~~a_1~~~\dots ~~~a_{99}~~~K~~~e_0~~~e_1~~~\dots~~~e_{74})$

为了写的方便点：

$(a_0~~~a_1~~~\dots ~~~a_{99}~~~1~~~l_0~~~l_1~~~\dots~~~l_{99})\begin{bmatrix} x_1^0 &\cdots &x_{75}^0 & 1 & & & \\ \vdots & \vdots &\vdots & & \ddots & & \\ x_{1}^{99} &\cdots &x_{75}^{99} & & & 1 & \\ -b_1 &\cdots &-b_{75} & & & & K \\ p & & & & & & \\ & \ddots & & & & & \\ & & p & & & & \end{bmatrix}=(e_1~~~e_2~~~\dots~~~e_{75}~~~a_0~~~a_1~~~\dots ~~~a_{99}~~~K)$

exp:

from hashlib import sha256, md5
from Crypto.Util.number import *
from Crypto.Cipher import AES


def flatter(M):
    from subprocess import check_output
    from re import findall
    # compile https://github.com/keeganryan/flatter and put it in $PATH
    z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
    ret = check_output(["flatter"], input=z.encode())
    return matrix(M.nrows(), M.ncols(), map(int, findall(b"-?\\d+", ret)))

with open('data.txt','r') as f:
    f = (f.read().encode().split(b'\n')[:-1])

p = eval(f[0])
msg = eval(f[1])
ct = eval(f[2])
ct = long_to_bytes(ct)

pbits = 400
noise_bit = 32
n = 100
m = 75

X = []
B = []
for i in msg:
    X.append(i[0])
    B.append(i[1])

L = matrix(ZZ,m+1+n,m+1+n)

K = 2**256
Kn = 2**(256-noise_bit)

for i in range(m):
    for j in range(n):
        L[j,i] = pow(X[i],j,p)
    L[n,i] = B[i]
    L[i+n+1,i] = p

L = Kn*L 

for i in range(n):
    L[i,i+m] = 1
L[n,-1] = K


LL = flatter(L)

for i in LL:
    if abs(i[-1]) == K:
        res = [abs(j) for j in i[-n:-1]]
        key = ''.join([str(i) for i in res])
        key = md5(key.encode()).digest()
        aes = AES.new(key=key, mode=AES.MODE_ECB)
        print(aes.decrypt(ct))

# DASCTF{3617af36-7869-6939-3a09-bb8038aea171}

井然有条 糖醋小鸡块师傅：

from hashlib import sha256, md5
from Crypto.Util.number import *
from Crypto.Cipher import AES
from subprocess import check_output

def flatter(M):
    # compile https://github.com/keeganryan/flatter and put it in $PATH 
    z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]" 
    ret = check_output(["flatter"], input=z.encode()) 
    from re import findall 
    return matrix(M.nrows(), M.ncols(), map(int, findall(b"-?\\d+", ret))) 

pbits = 400
noise_bit = 32
n = 100
m = 75
p = 
msgs = 
ct = 

########################################################### part1 construct
A= []
b = []
for i in range(m):
    temp = [msgs[i][0]^j % p for j in range(n)]
    A.append(temp)
    b.append(msgs[i][1])
A = Matrix(ZZ,A)
b = vector(ZZ,b)

########################################################### part2 LLL
#primal_attack1
def primal_attack1(A,b,m,n,p,esz):
    L = block_matrix(
        [
            [matrix.identity(m)*p,matrix.zero(m, n+1)],
            [(matrix(A).T).stack(-vector(b)).change_ring(ZZ),matrix.identity(n+1)],
        ]
    )
    print(L.dimensions())
    Q = diagonal_matrix([2^256//esz]*m + [1]*n + [2^256])
    L *= Q
    L = flatter(L)
    L /= Q
    for res in L:
        if(res[-1] == 1):
            s = vector(GF(p), res[-n-1:-1])
            return s
        elif(res[-1] == -1):
            s = -vector(GF(p), res[-n-1:-1])
            return s
        
res = primal_attack1(A,b,m,n,p,2^32)
print(res)

key = "".join([str(i) for i in list(res)[1:]])
key = md5(key.encode()).digest()
aes = AES.new(key = key, mode = AES.MODE_ECB)
flag = aes.decrypt(long_to_bytes(ct))
print(flag)

W'Blog

Shamir门限方案

前言

Shamir秘密共享方案

子密钥生成算法

恢复秘密过程

References:

例题

[NKCTF2023] Raven

题解：

构造示例

EZshamir

exp: