格密码

作为后量子密码，可以用来抵抗量子攻击

向量

带有方向的线段

u⃗ = (1, 2)

向量的运算

向量的运算满足平行四边形法则

u⃗ + v⃗ = w⃗

ku⃗ = (k, 2k),也就是将长度扩大k倍(k ∈ ℤ)

向量空间

向量的集合，运算的空间 $\text { 1. } a \in V, b \in V \text {, 则 } a+b \in V \\$ 2. a ∈ V, k ∈ ℝ, 则 ka ∈ V 。

也就是满足封闭性

向量正交与施密特(Schmidt)正交化

当 $ a , b $ 时，当 ((a, b) = 0)，即 ( a^T b = 0 ) 时，称向量 ( a, b ) 正交。

由两两正交的非零向量组成的向量组称为正交向量组，由单位向量组成的正交向量组称为标准正交向量组。

( n ) 维欧氏空间求解正交基，一组基底为 (α₁, α₂, ⋯, α_n)

Step 1: 令 β₁ = α₁

Step 2: 计算 α₂ 在 β₁ 方向上的投影，并做差得到 $$ \beta_2 = \alpha_2 - \frac{( \beta_1, \alpha_2 )}{( \beta_1, \beta_1 )} \beta_1 $$ Step 3: 计算 α₃ 在向量 β₁, β₂ 方向的投影，继续做差得到 β₃

格

系数为整数的向量空间，完整定义：m维欧式空间R^m的n(m≥n)个线性无关向量$\vec{v_i}$的所有整系数的线性组合

$$ L(V) = \left\{ \sum_{i=1}^{n} k_i \mathbf{v}_i \ \middle| \ k_i \in \mathbb{Z}, 1 \leq i \leq n \right\} $$ 其实格就是系数k必须是整数的向量空间

这上面的就是一个格，可以表示为 $$ L =\begin{bmatrix} 0 & 1\\ 1 & 0 \end{bmatrix} $$ 这里每一个整数点都是格点，由所有的格点组成了格

Hermite定理

这个定理给出了最短向量的上界

对于n维的格L，都有一个非零向量v属于L，满足 $$ \| \mathbf{v} \| \leq \sqrt{n} \cdot \det(L)^{\frac{1}{n}} $$

解释一下||v||表示格基的数量积，n为维度，det(L)为格L(矩阵)的行列式

这里公式的证明过程就不再赘述了，感兴趣的师傅可以去这里看看

格基规约

这里就是为了找到最接近正交基的基向量

这里有个对Hermite定理的拓展，Hermite定理讨论的是最短向量的上界，这里对于一组基而言也有定理给出了上界 ∥v₁∥∥v₂∥⋯∥v_n∥ ≤ n^n/2det (L) 同时还有Hadamard不等式给出了下界 ∥v₁∥∥v₂∥⋯∥v_n∥ ≥ det (L) 们引入Hadamard比率，定义为 $$ {\cal H}({\cal B}) = \left(\frac{\det(L)}{\|v_1\|\|v_2\|\cdots\|v_n\|}\right)^{1/n} $$ 当${\cal H}({\cal B})$越接近1，则这组基向量越接近正交基

利用LLL算法来找到这组基

格密码的应用

1.NTRU

模：p

私钥：(f,g)

公钥：h = f⁻¹g mod p

临时密钥：r

加密： c ≡ rh + m ≡ rf⁻¹g + m (mod p) 解密： fc ≡ rg + fm ≡ fm (mod p) 再乘上f⁻¹即可得到m

这里构造格 $$ L =\begin{bmatrix} 1 &h \\ 0 &p \end{bmatrix} $$ 我们还知道hf + kp = g

那么我们可以发现（f,g）是格点 (f, k)L = (f, fh + pk) = (f, g) 则如果我们能够找到(f,k)则可以得到(f,g)

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
'''

题目给出的条件是 h ≡ f⁻¹g (mod p)

c ≡ rf⁻¹g + m (mod p)

fc ≡ rg + fm (mod p)

fc − rg ≡ fm (mod p)

两边同时模g fm ≡ (fc mod p) mod g

m ≡ (fc mod p)f⁻¹ mod g

显然当rg+fm<p,m<rg+fm<p,m<g时才能正确解密

所以 $$ \begin{pmatrix} {f} &-k \end{pmatrix}\begin{bmatrix} 1 &h \\ 0 &p \end{bmatrix}=\begin{pmatrix} {f} & g \end{pmatrix} $$ 这里判断是否满足Hermite定理,如果满足则可以直接求出最短的向量



import gmpy2

from Crypto.Util.number import *

p = getPrime(1024)  

f = flag = getPrime(400)  

g = getPrime(512)

print(f.bit_length())  

temp = gmpy2.iroot(2  * p, 2)[0]  

print(temp.bit_length()) 

temp2 = gmpy2.iroot(f**2+(g)**2, 2)[0]  

print(temp2.bit_length())  

if temp.bit_length() >= temp2.bit_length():

  print("true")

else:

  print("false")

这里显然是满足的

import libnum
import gmpy2

p = 170990541130074930801165526479429022133700799973347532191727614846803741888876816210632483231997413973919037199883422312436314365293577997262903161076615619596783971730864586404602951191341733308807254112018161897113881363794353050758324742415299277578203838160939521046655099610387485947145087271531951477031
h = 19027613518333504891337723135627869008620752060390603647368919831595397216728378486716291001290575802095059192000315493444659485043387076261350378464749849058547797538347059869865169867814094180939070464336693973680444770599657132264558273692580535803622882040948521678860110391309880528478220088107038861065
c = 75639016590286995205676932417759002029770539425113355588948888258962338419567264292295302442895077764630601149285564849867773180066274580635377957966186472159256462169691456995594496690536094824570820527164224000505303071962872595619159691416247971024761571538057932032549611221598273371855762399417419551483

L = Matrix(ZZ,[[h,1],[p,0]])
print(L.LLL())
g,f = L.LLL()[0]
g,f = abs(g),abs(f)

m = ((f*c%p)*gmpy2.invert(f,g)) % g
print(libnum.n2s(int(m)))

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

f = bytes_to_long(flag)
p = getPrime(512)
g = getPrime(128)
h = gmpy2.invert(f+20192020202120222023, p) * g % p

print('h =', h)
print('p =', p)
"""
h = 2230300126583677861466927910427460605336142000604400796769019169330805327830058127399640469637301157563524664730082687590109425103649095203274991089542329
p = 6950733137747588463708927295050453925761832477377823596882238234496472403054344156839969133381577140118982692621000380716326275220824006196311323447685281
"""

这里可以看到f就是我们要求的flag h ≡ (f + 20192020202120222023)⁻¹g (mod p) 这里我们不妨令f^′ = f + 20192020202120222023 h ≡ (f^′)⁻¹g (mod p)

hf^′ ≡ g (mod p)

g = hf^′ − kp

那么现在我们就可以构造出格 $$ \begin{pmatrix} {f}' &k \end{pmatrix}\begin{bmatrix} 1 &h \\ 0 &p \end{bmatrix}=\begin{pmatrix} {f}' & g \end{pmatrix} $$ 这里的向量$\begin{pmatrix}{f}' & g\end{pmatrix}$就是我们的最短向量

我们通过LLL算法，将这组基向量(1,h),(0,p)变成正交化程度最大的基，$\begin{pmatrix}{f}' & g\end{pmatrix}$则是最短的向量

Hermite定理给出了这是最短向量的证明 $$ \| \mathbf{v} \| \leq \sqrt{n} \cdot \det(L)^{\frac{1}{n}} $$ 在本题中 $$ | \mathbf{\overrightarrow{v} } \| \leq \sqrt{2} \cdot \det(p)^{\frac{1}{2}} $$ 这里向量v的范数 $$ \sqrt{f'^{2}+g^2} $$ 现在就看能不能满足下式了 $$ \sqrt{f' ^{2} + g^{2}} \leq \sqrt{2p} $$ 题目给出了

1 2	p = getPrime(512) g = getPrime(128)

这里我们知道flag的长度一般都是40~45左右也就是255bit左右

b = 2**128

print(b)

import gmpy2

from Crypto.Util.number import *

flag = b'flag{Do_you_like_Lattice?Addoil}'

f = bytes_to_long(flag)

print(f.bit_length())  # 255

p = getPrime(512)

g = getPrime(128)

g = g

temp = gmpy2.iroot(2 * p, 2)[0]

print(temp.bit_length()) # 257

f = f + 20192020202120222023  

temp2 = gmpy2.iroot(f**2+(b*g)**2, 2)[0]  

 

print(temp2.bit_length())

这里是满足该定理的，所以我们不需要配平可以直接求解

import libnum

h = 2230300126583677861466927910427460605336142000604400796769019169330805327830058127399640469637301157563524664730082687590109425103649095203274991089542329
p = 6950733137747588463708927295050453925761832477377823596882238234496472403054344156839969133381577140118982692621000380716326275220824006196311323447685281

Ge = Matrix(ZZ,[[1,h],[0,p]])
print(Ge.LLL())
f,g = Ge.LLL()[0]
f,g = abs(f),abs(g)

print(libnum.n2s(int(f-20192020202120222023)))

easyLattice

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

assert len(flag) == 47

f = bytes_to_long(flag)
p = getPrime(512)
g = getPrime(128)
h = gmpy2.invert(f, p) * g % p

print('h =', h)
print('p =', p)

"""
h = 9848463356094730516607732957888686710609147955724620108704251779566910519170690198684628685762596232124613115691882688827918489297122319416081019121038443
p = 11403618200995593428747663693860532026261161211931726381922677499906885834766955987247477478421850280928508004160386000301268285541073474589048412962888947     
"""

同样的我们先列出加密等式 h ≡ f⁻¹g (mod p)

hf = g + kp

g = hf − kp

我们可以列出格 $$ \begin{pmatrix} {f} &k \end{pmatrix}\begin{bmatrix} 1 &h \\ 0 &p \end{bmatrix}=\begin{pmatrix} {f} & g \end{pmatrix} $$ 接下来要判断是否满足Hermite定理

那么按照题目给出的条件，我们知道p是512bit，g是128bit，flag的长度是47 $$ \sqrt{(f')^{2}+g^2} \leq \sqrt{2p} $$


import gmpy2

from Crypto.Util.number import *

flag = b'flag{6102e15e-a82d-46aa-bdb4-9e82679710f243433}'

print(len(flag))

f = bytes_to_long(flag)

print(f.bit_length()) 

p = getPrime(512)

g = getPrime(128)



temp = gmpy2.iroot(2 * p, 2)[0]

print(temp.bit_length()) # 257

temp2 = gmpy2.iroot(f**2+g**2,2)[0] 

print(temp2.bit_length())  #375

这里显然是不满足Hermite定理的，所以我们需要配平

b = 2**256

print(b)

import gmpy2

from Crypto.Util.number import *

flag = b'flag{6102e15e-a82d-46aa-bdb4-9e82679710f243433}'

print(len(flag))

f = bytes_to_long(flag)

print(f.bit_length()) 

p = getPrime(512)

g = getPrime(128)

g =g

temp = gmpy2.iroot(2 * p * b, 2)[0]

print(temp.bit_length()) # 385

temp2 = gmpy2.iroot(f**2+(g)**2,2)[0] 

print(temp2.bit_length())  #375

配平后就满足了Hermite定理，也就是存在最短向量，此时的格变为 $$ \begin{bmatrix} 1 &h *b \\ 0 &p * b \end{bmatrix} $$

import libnum
from Crypto.Util.number import *
h = 9848463356094730516607732957888686710609147955724620108704251779566910519170690198684628685762596232124613115691882688827918489297122319416081019121038443
p = 11403618200995593428747663693860532026261161211931726381922677499906885834766955987247477478421850280928508004160386000301268285541073474589048412962888947  
b = 2**256
Ge = Matrix(ZZ,[[1,h * b ],[0,p * b]])
print(Ge.LLL())
f,g = Ge.LLL()[0]
f,g = abs(f),abs(g)
print(f)
print(long_to_bytes(f))

对于格来说最短向量的界限是比较模糊的，有时候可能出现满足Hermite定理但就是求不出最短向量，这个时候可以考虑高斯启发式

高斯启发式是对Hermite定理的进一步缩小，假设L是n维格，高斯所期望的最短的长度是 $$ \sigma(L) = \sqrt{\tfrac{n}{2\pi e}} (Det(L))^{\tfrac{1}{n}} $$ 高斯启发式表示，在一个“随机选择的格”中的最短非零向量满足 ∥v⃗_shortest∥ ≈ σ(L)

2.背包密码

参数

私钥为一个超递增数列{a_n},满足 $$ a_i\sum_{k=1}^{i-1} a_k $$ 模数m，满足 $$ m>\sum_{i=1}^{n}a_i $$ 乘数w,满足gcd⁡(w,m)=1

公钥{b_i},满足 b_i ≡ wa_i (mod m) 加密

设明文为{v_i},v_i ∈ (0, 1) $$ c = \sum_{i=1}^{n}b_iv_i \pmod(m) $$ 解密 $$ v = w^{-1}c \equiv \sum_{i=1}^n v_i a_i \pmod{m} $$ 构造格 $$ L = \begin{bmatrix} 1 & 0 & 0 & \cdots & 0 & b_1 \\ 0 & 1 & 0 & \cdots & 0 & b_2 \\ 0 & 0 & 1 & \cdots & 0 & b_3 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 1 & b_n \\ 0 & 0 & 0 & \cdots & 0 & -c \end{bmatrix} $$ 这里的格点是v=(v1,v2,v3,…,vn,1) (v₁, v₂, ⋯, v_n, 1) × L = (v₁, v₂, ⋯, v_n, 0) 同样有 $$ \|v\| = \sqrt{\sum v_i^2} < \sqrt{n} $$

from Crypto.Util.number import *

import random

from gmpy2 import *

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

flag = bin(flag)[2:]  #将flag转为二进制

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])  #生成m大于超递增序列

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)

这里就是非常标准的背包密码了

from Crypto.Util.number import *

b = [...]
c = ...

n = len(b)
print(n)
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 i in range(n + 1):
    M = res.row(i).list()
    flag = True
    for m in M:
        if m != 0 and m != 1:
            flag = False
            break
    if flag:
        print(i, M)

# flag =  [1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1]

# flag = int(''.join(list(map(str, flag))), 2)

# print(long_to_bytes(flag))

题目

p3

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}')

'''

c = 78168998533427639204842155877581577797354503479929547596593341570371249960925614073689003464816147666662937166442652068942931518685068382940712171137636333670133426565340852055387100597883633466292241406019919037053324433086548680586265243208526469135810446004349904985765547633536396188822210185259239807712

a = 134812492661960841508904741709490501744478747431860442812349873283670029478557996515894514952323891966807395438595833662645026902457124893765483848187664404810892289353889878515048084718565523356944401254704006179297186883488636493997227870769852726117603572452948662628907410024781493099700499334357552050587

b = 1522865915656883867403482317171460381324798227298365523650851184567802496240011768078593938858595296724393891397782658816647243489780661999411811900439319821784266117539188498407648397194849631941074737391852399318951669593881907935220986282638388656503090963153968254244131928887025800088609341714974103921219202972691321661198135553928411002184780139571149772037283749086504201758438589417378336940732926352806256093865255824803202598635567105242590697162972609

'''

和上面的题目相似，这里变成了解RSA，那么我们就需要求出p，q，对于p,q给出了一个关系式，那么我们就可以用格来求出p，q

1 2	r = random.randint(214, 215) ((p-r) * a + q) % b < 50

这里可以发现r和关系式并没有给出大小，但是给出了范围，这里显然是可以用爆破来解决的因为都不是很大

这里我们不妨碍令x = ((p-r) * a + q) % b,p^′ = (p − r)那么就有 x = (p^′ * a + q) + kb

x − kb = p^′ * a + q

那么我们可以造格 $$ L = \begin{bmatrix} 1 & a\\ 0 & b \end{bmatrix} $$ 那么就有 $$ \begin{pmatrix} {p}' & k \end{pmatrix}\begin{bmatrix} 1 & a\\ 0 & b \end{bmatrix}=\begin{pmatrix} {p}' & x-q \end{pmatrix} $$ 还是要先判断是否满足Hermite定理



import gmpy2

from Crypto.Util.number import *

b = getPrime(1536)  

f = flag = getPrime(225)  

p = getPrime(512)

q = getPrime(512)

r = getPrime(2**15)

print(f.bit_length())  

temp = gmpy2.iroot(2  * b, 2)[0]  

print(temp.bit_length()) 

temp2 = gmpy2.iroot((p-r)**2+(50-q)**2, 2)[0]  

print(temp2.bit_length())  

if temp.bit_length() >= temp2.bit_length():

  print("true")

else:

  print("false")

#513

#512

#true

这里是满足的，那么就直接LLL规约了

a = 

b = 

L = Matrix(ZZ,[[1,a ],[0, b]])

print(L.LLL())

f,g = L.LLL()[0]

f,g = abs(f),abs(g)

print(f)
#11296178014269303494837745604378279247866909144617752153545368028888626096702713262852534563523632474606208277782361536096982136624743993713145172222722488

这里我们就求出了(p-r)和(x-q)的值，后面爆破r和x即可

e=

c = 

p_r=

q_x=

for r in range(2**14,2**15):

  for x in range(50):

    p = p_r + r

    q = q_x + x

    phi = (p-1)*(q-1)

    if gmpy2.gcd(phi, 65537) != 1:

      continue

    m = pow(c, gmpy2.invert(65537, phi), p * q)

    flag = long_to_bytes(m)

    if b"NSSCTF" in flag :

      print(flag)

      break
#NSSCTF{0fc9dee6-ebfb-40bd-b800-b3ebe440be70}

P4

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}')

'''

a = 

p = 

'''

还是先列出等式 a = r⁻¹ * flag + kp

flag = r * a + kp

构造格 $$ L = \begin{bmatrix} 1 & a\\ 0 & p \end{bmatrix} $$

$$ \begin{pmatrix} r & k \end{pmatrix}\begin{bmatrix} 1 & a\\ 0 & p \end{bmatrix}=\begin{pmatrix} r & flag \end{pmatrix} $$

还是先判断是否满足Hermite定理

#python

import gmpy2

from Crypto.Util.number import *

p = getPrime(1024) 

f = flag = getPrime(225)  

r = getPrime(175)

print(f.bit_length())  

temp = gmpy2.iroot(2  * p, 2)[0]  

print(temp.bit_length()) 

temp2 = gmpy2.iroot(r**2+f**2, 2)[0]  

print(temp2.bit_length())  

if temp.bit_length() >= temp2.bit_length():

  print("true")

else:

  print("false")

# 513

# 225

# true

这里是满足的，那就能直接规约了

from Crypto.Util.number import *

import gmpy2

a = 79047880584807269054505204752966875903807058486141783766561521134845058071995038638934174701175782152417081883728635655442964823110171015637136681101856684888576194849310180873104729087883030291173114003115983405311162152717385429179852150760696213217464522070759438318396222163013306629318041233934326478247

p = 90596199661954314748094754376367411728681431234103196427120607507149461190520498120433570647077910673128371876546100672985278698226714483847201363857703757534255187784953078548908192496602029047268538065300238964884068500561488409356401505220814317044301436585177722826939067622852763442884505234084274439591

L = Matrix(ZZ,[[1,a ],[0, p]])

print(L.LLL())

f,g = L.LLL()[0]

f,g = abs(f),abs(g)

print(f)

print(g)

print(long_to_bytes(g))

#b'NSSCTF{e572546b-abb5-4358-8970-471abc12b7ef}'

p5

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 = b * m + c + kp

c = a − b * m + kp

造格 $$ \begin{pmatrix} 1&m &k \end{pmatrix}\begin{bmatrix} 1 & 0 & a\\ 0 & 1 & -b \\ 0 & 0 & p \end{bmatrix}=\begin{pmatrix} 1& m&c \end{pmatrix} $$ 现在还是要先看是否满足Hermite定理

import gmpy2

from Crypto.Util.number import *

b = 2 ** 0  #这是不断调整配平用的

f = flag = getPrime(351)  

p = getPrime(1024)

b = getPrime(1024)

c = getPrime(400)

n = 3

det = p 

temp = gmpy2.iroot(n, 2)[0] * gmpy2.iroot(det, n)[0]  

print(temp.bit_length()) 

temp2 = gmpy2.iroot(f**2+(c)**2, 2)[0]  

print(temp2.bit_length())  

if temp.bit_length() >= temp2.bit_length():

  print("true")

else:

  print("false")
#342
#400
#false

这里是不满足的Hermite定理的

所以我们需要配平，也就是平衡格基，尽量让基的数量级接近

import gmpy2

from Crypto.Util.number import *

b = 2 ** 0  #这是不断调整配平用的

f = flag = getPrime(351)  

p = getPrime(1024)

b = getPrime(1024)

c = getPrime(400)

n = 3

det = p * 2**350

temp = gmpy2.iroot(n, 2)[0] * gmpy2.iroot(det, n)[0]  

print(temp.bit_length()) 

temp2 = gmpy2.iroot(f**2+(c)**2, 2)[0]  

print(temp2.bit_length())  

if temp.bit_length() >= temp2.bit_length():

  print("true")

else:

  print("false")
#458
#400
#true

最后得到 $$ \begin{pmatrix} 1&m &k \end{pmatrix}\begin{bmatrix} 2^{350} & 0 & a\\ 0 & 1 & -b \\ 0 & 0 & p \end{bmatrix}=\begin{pmatrix} 2^{350}& m&c \end{pmatrix} $$

from Crypto.Util.number import *

import gmpy2

a = 

b = 

p = 

L = Matrix(ZZ,[[2^350, 0, a],

        [0, 1, -b],

        [0, 0, p]])

print(L.LLL())

t,m,c = L.LLL()[0]

t,m,c = abs(t),abs(m),abs(c)

print(long_to_bytes(m))

#b'NSSCTF{ee5cb1a5-257a-48b0-9d62-9ef56ff0651a}'

p6

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)

'''

e0 = 14663634286442041092028764808273515750847961898014201055608982250846018719684424125895815390624536073501623753618354026800118456911536861815261996929625814961086913500837475340797921236556312296934664701095834187857404704711288771338418177336783911864595983563560080719582434186801068157426993026446515265411

n0 = 104543450623548393448505960506840545298706691237630183178416927557780858213264769135818447427794932329909731890957245926915280713988801182894888947956846369966245947852409172099018409057129584780443712258590591272371802134906914886744538889099861890573943377480028655951935894660286388060056770675084677768397

c0 = 66400441793466385558399002350812383744096354576421495899465166492721568297592616443643465864544107914461044325088868615645524260480104397769130582397209585192620565774001015221725536884170662700337565613181799442382460047295553807602785067421981837709831158111951991854109179278733629950271657405211417740374

e1 = 62005504700456859456675572895620453845623573672275890584145949847469951381521709553504593023003977393014834639251022203398533914340078480147377747715528821418445514563871411209895815634752533151145061594791024551625615960423026244560340983481137777162236719939420428613005457949228517914830194749293637917667

n1 = 89410873947410184231222334229470195622685051370058935269198780539059522679122059486414591834635266301335656798768270022060656655274640699951736588085471509424575027153387518893978494158981314217195561629375189515702124478687925014362857206223379284909134299260355456357407022417434961226383007916607728238843

c1 = 75133250536426006056029454024900058936095761927174304108454764308417889983571094946046507426319589437822458959089546795698076608690695326741772662156830944126301658579142020817338297043884836598263468494533324693019866746045910394812656639124276516075062088756043949581789436307373276242558429450971458945061

e2 = 5365316217065391632204029784515519544882379449147835081003675696051077792179684123668298103660153980837519314114793091112163153158510344440829742753002176560016265852613076363394396640641504813912550948776926622696268531691467015580417575287779607009068332802842890478748171958455354463809356050553832863427

n2 = 53325942266099921615667538877103327425435396909592382386684073177331528393295928518724880712900970020425481561110366696624090824641115147978830715508666547064446891727446073538022824237798568413003419382767587742032676311751819789672319289920011033523044026418650515529084031754775286163358926609712626506433

c2 = 22289960513520782629306709529908652726794465066357062923684089176607114605563538085483920152508469429311012652149406853144200001391310165612163442404181970125704785325670969551080086517236489885046039799676581310781945432599048686184762485374030278657826206433571162451649808912276118945302558580745346371321

e3 = 57257245945110486431680573908783487217316546039634811903637650579658516537372808464426294780698320301497615457264001148504941375058983426920721566040576604013497311914160175024860226623138659970105781812246471618831032554729317463745699993647224910498474869868186318188994237457335796911524629938029123055027

n3 = 97233843381238063550322854422952777734101562842513647224354265328843953949189054347560960321126304504554067163501318212533606313039536188796999575130115659250566231010092273206623114900781284076452654791214088764465615154940874231056251107863895697778665275804663487113266180838319536762473697586368100928379

c3 = 56606672064789484727896188434430896229911224588055894584797861263107870392831242138537980507537270618683458635389444257040355313948352917061971042629958646854593628522401074068536976581232979947149230764268377747754284783531803366391759725774562719884482404532619163798580872386794273190532863916038929461465

'''

这里是个论文题，需要找到paper

文中指出了格应该如何构造

这里给出了我们的格也就是 $$ (d, k_1, k_2, , k_r)

= (dM, 1 - k_1 s_1, , 1 - k_r s_r) $$ 这里的M满足条件$M=\sqrt{N_{max}}$

现在就可以根据现有的条件来求出私钥d了

在论文中已经给出了证明是最短向量，所以也就不需要看是否满足了Hermite定理

from Crypto.Util.number import *

import gmpy2

e0 = 

n0 = 

c0 = 

e1 = 

n1 = 

c1 = 

e2 = 

n2 = 

c2 = 

e3 = 

n3 = 

c3 = 

n = [n0,n1,n2]

M = isqrt(max(n))

     

L = 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]

        ])

d_M = L.LLL()[0][0]

d = d_M //M

m = power_mod(c0, d, n0)

print(long_to_bytes(m))

#b'NSSCTF{12514adb-2c14-4777-96ff-90e95bc2b5cb}'

p7

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)

'''

n = 

c = 

e0 = 

e1 = 

'''

这里同样是个论文题，paper是这个，也就是讲了关于拓展维纳攻击

这里具体的推导就不详细赘述了，CTFWiki中有对论文的说明

根据论文中所述我们可以构造出矩阵 $$ D = \begin{pmatrix} N & & & \\ & N^{1/2} & & \\ & & N^{1 + \alpha_2} & \\ & & & 1 \end{pmatrix} $$ 最后得到 $$ L = \begin{pmatrix} 1 & -N & 0 & N^2 \\ & e_1 & -e_1 & -e_1N \\ & & e_2 & -e_2N \\ & & & e_1e_2 \end{pmatrix} \times D $$ 最后$φ(N)=\frac{edg}{k} -\frac{g}{k}$

from Crypto.Util.number import *
n = 
c = 
e0 = 
e1 = 
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, e0, -e0, -e0*n],
                [0,  0, e1,  -e1*n],
                [0,  0,  0,  e0*e1]])*D
L = M.LLL()
t = vector(ZZ, L[0])
x = t * M^(-1)

x * M = t
phi = int(x[1]/x[0]*e0)

d = inverse_mod(65537, phi)
m = power_mod(c, d, n)
print(long_to_bytes(m))

关于三个指数攻击的题目在HGAME 2023中也是有道题目的

p8

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}')

'''

c = 740925064346371394698186587854547113606276228956443989781507592148712696471120454242180757282913190509143771235457885619359315384722931529795071829165028

flag = 68803130911709451943985629442913968356735244797651554293510331427148284907075221530061581131130283569506280604032687824733336171953927

a = [8205051800134728054685810600921116779466017139080528864745521629232854690213051609775306424843961090482436503418278207286549634492623172279113808752825877, 7656695314164580223033364292542508972053206838456547579023164583502640699225283686572923544677077467571265812610524520719197913305928971777756847148151453, 12016313094941119621096276870216129960285946825332008187797823075795491053640261786033376211694851951499688886358239835607622191418940486434225440651886891]

p = 9725369974716521164256395525866212215114818770667579116304398350357785690930260317036889742178436308598088096925530431498664796728861093872628194022265573

'''

这道题目也不难看懂，最主要是求出s[0]，s[1]，s[2]

同时题目中也是给出了它们的线性表达式 c = a₀ * s₀² * s₁² + a₁ * s₀ * s₂² + a₂ * s₁ * s₂ + kp 这里还是先将未知量放到等式的一侧

将两边同时乘上a₂⁻¹,那么就有 s₁ * s₂ = a₀ * a₂⁻¹ * s₀² * s₁² + a₁ * a₂⁻¹ * s₀ * s₂² − c * a₂⁻¹ + kp 那么可以构造格 $$ \begin{bmatrix} 1 & 0 & 0 &a_0*a_2^{-1} \\ 0& 1 & 0 & a_1*a_2^{-1}\\ 0& 0 & 1 &-c*a_2^{-1} \\ 0& 0 & 0 &p \end{bmatrix} $$ 那么就有 $$ \begin{pmatrix} s_0^{2}*s_1^{2}&s_0*s_2^{2} &1 &k & \end{pmatrix}\begin{bmatrix} 1 & 0 & 0 &a_0*a_2^{-1} \\ 0& 1 & 0 & a_1*a_2^{-1}\\ 0& 0 & 1 &-c*a_2^{-1} \\ 0& 0 & 0 &p \end{bmatrix}= \begin{pmatrix} s_0^{2}*s_1^{2}&s_0*s_2^{2} &1 &s_1*s_2 & \end{pmatrix} $$ 那么下面还要看是否满足Hermite定理,这里不放测试的数据了，因为后面的基明显需要配2¹²⁸来平衡格基

所以最后的格应该是 $$ \begin{pmatrix} s_0^{2}*s_1^{2}&s_0*s_2^{2} &1 &k & \end{pmatrix}\begin{bmatrix} 1 & 0 & 0 &a_0*a_2^{-1} \\ 0& 2^{32} & 0 & a_1*a_2^{-1}\\ 0& 0 & 2^{128} &-c*a_2^{-1} \\ 0& 0 & 0 &p*2^{64} \end{bmatrix}= \begin{pmatrix} s_0^{2}*s_1^{2}&s_0*s_2^{2} &1 &s_1*s_2 & \end{pmatrix} $$ 也就是乘上一个对角线矩阵 $$ \begin{bmatrix} 1 & & & \\ & 2^{32} & & \\ & & 2^{128} & \\ & & &2^{64} \end{bmatrix} $$

from Crypto.Util.number import *

c = 740925064346371394698186587854547113606276228956443989781507592148712696471120454242180757282913190509143771235457885619359315384722931529795071829165028
flag = 68803130911709451943985629442913968356735244797651554293510331427148284907075221530061581131130283569506280604032687824733336171953927
a = [8205051800134728054685810600921116779466017139080528864745521629232854690213051609775306424843961090482436503418278207286549634492623172279113808752825877, 7656695314164580223033364292542508972053206838456547579023164583502640699225283686572923544677077467571265812610524520719197913305928971777756847148151453, 12016313094941119621096276870216129960285946825332008187797823075795491053640261786033376211694851951499688886358239835607622191418940486434225440651886891]
p = 9725369974716521164256395525866212215114818770667579116304398350357785690930260317036889742178436308598088096925530431498664796728861093872628194022265573

ia = inverse_mod(a[2], p)

L = Matrix(ZZ, [[1, 0, 0, a[0]*ia%p],
                [0, 1, 0, a[1]*ia%p],
                [0, 0, 1,   -c*ia%p],
                [0, 0, 0,         p]]) * diagonal_matrix(ZZ, [1, 2^32, 2^128, 2^64])

v = L.LLL()[0]
s0s1 = isqrt(abs(v[0]))
s1s2 = abs(v[3]) >> 64   #因为在对角矩阵中乘上了2^64要把这个除掉，其实在对角矩阵中不乘2^64也是可以的
s1 = gcd(s0s1, s1s2) #都有因子s1,所以取个GCD即可
s0 = s0s1 // s1
s2 = s1s2 // s1

flag = flag // s0 // s1 // s2
print(long_to_bytes(flag))

#b'NSSCTF{30636075-1942-49e7-acf2-721e3b587188}'