NSS工坊格

发表于 2025-11-29 更新于 2026-01-20 分类于 Lattice 阅读次数：

NSSCTF工坊格密码

1.

from Crypto.Util.number import *

p = getPrime(1024)

f = getPrime(400)
g = getPrime(512)
r = getPrime(400)

h = inverse(f, p) * g % p

m = b'******'
m = bytes_to_long(m)

c = (r*h + m) % p

print(f'p = {p}')
print(f'h = {h}')
print(f'c = {c}')

'''
p = 170990541130074930801165526479429022133700799973347532191727614846803741888876816210632483231997413973919037199883422312436314365293577997262903161076615619596783971730864586404602951191341733308807254112018161897113881363794353050758324742415299277578203838160939521046655099610387485947145087271531951477031
h = 19027613518333504891337723135627869008620752060390603647368919831595397216728378486716291001290575802095059192000315493444659485043387076261350378464749849058547797538347059869865169867814094180939070464336693973680444770599657132264558273692580535803622882040948521678860110391309880528478220088107038861065
c = 75639016590286995205676932417759002029770539425113355588948888258962338419567264292295302442895077764630601149285564849867773180066274580635377957966186472159256462169691456995594496690536094824570820527164224000505303071962872595619159691416247971024761571538057932032549611221598273371855762399417419551483
'''

经典的ntru

进行一个简单的推导：

造格：

$\left(\begin{matrix}1&h\\0&p\end{matrix}\right)$

得到f，g,然后得出 $，根据数量大小，能够得出再即可轻松求解$

这边想给出一些其他的解法和我的一些困惑：

首先对于

能够直接构造三维格进行处理：

$\left(\begin{matrix}2^{400}&0&c\\0&1&p\\0&0&-h\end{matrix}\right)$

但是对于四维格的情况却无法得到想要的结果：

$\left(\begin{matrix}1&0&0&2^{1000}h\\0&1&0&2^{1000}\\0&0&1&2^{1000}p\\0&0&0&-2^{1000}c\end{matrix}\right)$

对于这个格将其左乘(r,m,-k,1)能够得到(r,m,-k,0)（理想情况下）但发现无法得到想要的m（即使对最后一列进行系数调整,使其满足hermite定理也无法得到）

通过咨询DexterJie师傅学习到了一个重要的结论：造格的时候模数最好放在对角线上！

于是对格进行调整：

$\left(\begin{matrix}1&0&0&2^{1000}h\\0&1&0&2^{1000}\\0&0&1&-2^{1000}c\\0&0&0&2^{1000}p\end{matrix}\right)$

这个时候对应的式子就是(r,m,1,-k)A=(r,m,1,0)由于系数不平衡，进行配平：

$\left(\begin{matrix}1&0&0&2^{1000}h\\0&1&0&2^{1000}\\0&0&2^{400}&-2^{1000}c\\0&0&0&2^{1000}p\end{matrix}\right)$

于是就能够得到flag了

这边做出来之后分析了一下，好像顿悟了一点，本来的格出来的小基向量中含有k，这是未知位数的，很可能会对规约结果造成影响；而调整格的构造后基向量中k就消失了，可以对明确的位数进行平衡，于是就能很好地解决了

总结：

造格的时候最好把模数放在对角线上

当基向量中存在未知位数的k且求不出结果时，不妨试一试调整一下格的构造

2.

from Crypto.Util.number import *
import random
from gmpy2 import *

flag = bytes_to_long(b'******')
flag = bin(flag)[2:]
n = len(flag)

a = [random.randint(1, 4**n)]
s = a[0]
for i in range(1, n):
    a.append(random.randint(s+1, 4**(n+i)))
    s += a[i]

m = random.randint(a[-1] + 1, 2*a[-1])
w = random.randint(1, m)

assert gcd(w, m) == 1
b = [w*i % m for i in a]

c = 0
for i in range(len(b)):
    c = (c + b[i]*int(flag[i]))
with open('output', 'w+') as f:
    print(f'b = {b}', file=f)
    print(f'c = {c}', file=f)

这道题刚开始被引导到奇怪的方向了，实际上不需要管b具体的生成过程，主要关注这一段代码：

1 2	for i in range(len(b)): c = (c + b[i]*int(flag[i]))

这边将flag转为长整数后将其转换为二进制字符串，然后与b列表对应索引的值进行相乘并累加，实际上就是一个背包密码的考察

构造以下格：

$\left( \begin{matrix} 1 & 0 & …&0&b_0\\ 0 & 1 & …&0&b_1 \\ \vdots & \vdots & \ddots&\vdots&\vdots&\\0&0&… &1&b_n\\0&0&…&0&-c\end{matrix}\right)$

用乘这个矩阵即能得到小基

from Crypto.Util.number import *

b = 
c = 
n = len(b)
L = Matrix(ZZ,n+1,n+1)
for i in range(n):
    L[i,i] = 1
    L[i,-1] = b[i]
L[-1,-1] = -c
res = L.LLL()
for j in range(n+1):
    M = res.row(j).list()
    flag = True
    for m in M:
        if m!=0 and m!=1:
            flag = False
            break
    if flag:
        print(j)
        print(M)
        flag = ''.join(str(bit) for bit in M[:-1])
        print(long_to_bytes(int(flag, 2)))

需要注意的是，恢复flag的时候需要将得到的小基向量的最后一列值去掉

3.

from Crypto.Util.number import *
import random

flag = b'******'
m = bytes_to_long(flag)

a = getPrime(1024)
b = getPrime(1536)

p = getPrime(512)
q = getPrime(512)
r = random.randint(2**14, 2**15)
assert ((p-r) * a + q) % b < 50

c = pow(m, 65537, p*q)

print(f'c = {c}')
print(f'a = {a}')
print(f'b = {b}')

4.

from Crypto.Util.number import *
from gmpy2 import *

flag = b'******'
flag = bytes_to_long(flag)

p = getPrime(1024)
r = getPrime(175)
a = inverse(r, p)
a = (a*flag) % p

print(f'a = {a}')
print(f'p = {p}')

这道题比较简单，进行简单推导：

于是构造格：

$\left( \begin{matrix} 1 & a\\0&p\end{matrix}\right)$

预期的小基向量是(r,m)，此处大小设置合理，满足hermite定理

from Crypto.Util.number import *

a = 79047880584807269054505204752966875903807058486141783766561521134845058071995038638934174701175782152417081883728635655442964823110171015637136681101856684888576194849310180873104729087883030291173114003115983405311162152717385429179852150760696213217464522070759438318396222163013306629318041233934326478247
p = 90596199661954314748094754376367411728681431234103196427120607507149461190520498120433570647077910673128371876546100672985278698226714483847201363857703757534255187784953078548908192496602029047268538065300238964884068500561488409356401505220814317044301436585177722826939067622852763442884505234084274439591

ge=Matrix(ZZ,[[1,a],[0,p]])
tg=ge.LLL()[0].list()
tg=[abs(i) for i in tg]
print(long_to_bytes(tg[1]))

5.

from Crypto.Util.number import *
from gmpy2 import *

flag = b'******'
m = bytes_to_long(flag)

assert m.bit_length() == 351
p = getPrime(1024)
b = getPrime(1024)
c = getPrime(400)

a = (b*m + c) % p

print(f'a = {a}')
print(f'b = {b}')
print(f'p = {p}')

'''
a = 92716521851427599147343828266552451834533034815416003395170301819889384044273026852184291232938197215198124164263722270347104189412921224361134013717269051168246275213624264313794650441268405062046423740836145678559969020294978939553573428334198212792931759368218132978344815862506799287082760307048309578592
b = 155530728639099361922541063573602659584927544589739208888076194504495146661257751801481540924821292656785953391450218803112838556107960071792826902126414012831375547340056667753587086997958522683688746248661290255381342148052513971774612583235459904652002495564523557637169529882928308821019659377248151898663
p = 100910862834849216140965884888425432690937357792742349763319405418823395997406883138893618605587754336982681610768197845792843123785451070312818388494074168909379627989079148880913190854232917854414913847526564520719350308494462584771237445179797367179905414074344416047541423116739621805238556845903951985783
'''

推导：

根据题目给出的数的大小，我们尽量将m，c这类小数字放在规约后的基向量中，因此构造格：

$\left(\begin{matrix}1&0&a\\0&1&-b\\0&0&p\end{matrix}\right)$

这样得到的基向量为(1,m,c)显然维度不均衡，进行配平：

$\left(\begin{matrix}2^{400}&0&a\\0&1&-b\\0&0&p\end{matrix}\right)$

from Crypto.Util.number import *

a = 92716521851427599147343828266552451834533034815416003395170301819889384044273026852184291232938197215198124164263722270347104189412921224361134013717269051168246275213624264313794650441268405062046423740836145678559969020294978939553573428334198212792931759368218132978344815862506799287082760307048309578592
b = 155530728639099361922541063573602659584927544589739208888076194504495146661257751801481540924821292656785953391450218803112838556107960071792826902126414012831375547340056667753587086997958522683688746248661290255381342148052513971774612583235459904652002495564523557637169529882928308821019659377248151898663
p = 100910862834849216140965884888425432690937357792742349763319405418823395997406883138893618605587754336982681610768197845792843123785451070312818388494074168909379627989079148880913190854232917854414913847526564520719350308494462584771237445179797367179905414074344416047541423116739621805238556845903951985783

ge=Matrix(ZZ,[[2**400,0,a],[0,1,-b],[0,0,p]])
tg=ge.LLL()[0].list()
print(long_to_bytes(abs(tg[1])))

6.

from Crypto.Util.number import *

flag = b'******'
flag = bytes_to_long(flag)
d = getPrime(400)


for i in range(4):
    p = getPrime(512)
    q = getPrime(512)
    n = p * q
    e = inverse(d, (p-1)*(q-1))
    c = pow(flag, e, n)
    print(f'e{i} =', e)
    print(f'n{i} =', n)
    print(f'c{i} =', c)

给了四组以相同私钥生成的公钥，每一组大概能表示成下面的形式：

$e_id-k_in_i=1+k_is_i(其中s_i=1-p_i-q_i)$

IJCSI-9-2-1-311-314.pdf

检索到论文（使用关键词lattice common private)

根据论文构造格即可：

from Crypto.Util.number import *
import gmpy2
print(max([n0,n1,n2,n3]))
M=int(gmpy2.iroot(n0,2)[0])
ge=Matrix(ZZ,[[M,e0,e1,e2,e3],[0,-n0,0,0,0],[0,0,-n1,0,0],[0,0,0,-n2,0],[0,0,0,0,-n3]])
tg=ge.LLL()[0].list()[0]
d=abs(tg)//M
m=pow(c0,d,n0)
print(m)
print(long_to_bytes(int(m)))

7.

from Crypto.Util.number import *

flag = b'******'
flag = bytes_to_long(flag)

p = getPrime(512)
q = getPrime(512)
n = p * q
c = pow(flag, 65537, n)
print(f'n =', n)
print(f'c =', c)
for i in range(2):
    d = getPrime(350)
    e = inverse(d, (p-1)*(q-1))
    print(f'e{i} =', e)

这是一道扩展维纳攻击的题目

利用脚本即可

from Crypto.Util.number import *
def wienerAttack2(N, e1, e2):
    a = 5/14
    D = diagonal_matrix(ZZ, [N, int(N^(1/2)), int(N^(1+a)), 1])
    M = matrix(ZZ, [[1, -N, 0, N^2], [0, e1, -e1, -e1*N], [0, 0, e2, -e2*N], [0, 0, 0, e1*e2]])*D
    L = M.LLL()
    B = vector(ZZ, L[0])
    A = B * M^(-1)
    phi = int(A[1]/A[0]*e1)
    d1 = inverse_mod(e1, phi)
    d2 = inverse_mod(e2, phi)
    p = var('p', domain=ZZ)
    roots = solve(p ** 2 + (phi - N - 1) * p + N, p)
    if len(roots) == 2:
        # possible p, q
        p, q = roots
        if p * q == N:
            return p, q, d1, d2
    raise ValueError('Could not factor N!')

p, q, d1, d2 = wienerAttack2(n, e0, e1)
print(p)
phi=(p-1)*(q-1)
print(phi)
d=inverse(65537,int(phi))
print(d)
m=pow(c,d,n)
print(m)
print(long_to_bytes(2806865643354785578450609045733131286744118434356323182772206641287491355913070780758914698246985892323709))

8.

from Crypto.Util.number import *

flag = b'******'
m = bytes_to_long(flag)

p = getPrime(512)
s = [getPrime(32) for i in range(3)]
a = [getPrime(512) for i in range(3)]

c = (a[0]*s[0]**2*s[1]**2 + a[1]*s[0]*s[2]**2 + a[2]*s[1]*s[2]) % p

flag = m*s[0]*s[1]*s[2]
print(f'c = {c}')
print(f'flag = {flag}')
print(f'a = {a}')
print(f'p = {p}')

预期的解法应该是利用格相关的操作求出s0s1s2后得到m，（虽然非预期可以直接分解flag啊喂）

按照预期打一下，造了一个非官方解的格：

$\left(\begin{matrix}1&0&0&a_0&0\\0&1&0&a_1&0\\0&0&1&a_2&0\\0&0&0&-p&0\\0&0&0&c&1\end{matrix}\right)$

使用左乘矩阵可以得到

很明显基向量的维度不匹配，为了满足LLL的特性，进行配平：

$\left(\begin{matrix}1&0&0&a_0&0\\0&2^{32}&0&a_1&0\\0&0&2^{64}&a_2&0\\0&0&0&-p&0\\0&0&0&c&2^{128}\end{matrix}\right)$

from Crypto.Util.number import *
import gmpy2

ge=Matrix(ZZ,5,5)
for i in range(3):
    ge[i,i]=2**(32*i)
    ge[i,-2]=a[i]
ge[-1,-1]=2**128
ge[-2,-2]=-p
ge[-1,-2]=c

tg=ge.LLL()
for row in tg:
    if(abs(row[-1]))==2**128:
        ls=row.list()
        print(ls)
        break
ls=[abs(i) for i in ls]
s=1
for i in ls[:3]:
    s*=i
p=gmpy2.iroot(s//(2**96),3)[0]
print(p)
flag=flag//p
print(long_to_bytes(flag))