【CTF-Crypto】格密码基础（例题较多，非常适合入门！）

格密码相关

格密码基本概念（属于后量子密码）

后量子密码指的是对抗未来量子计算快速解决的问题

==向量空间：==

==格：==

格本身就是一个系数为整数的向量空间

• 一系列向量集合（vector）v₁ , v₂ , v₃ , v_n

• 一系列整数a₁ , a₂ ,…, a_n

• 上面两个东西进行向量的线性组合就得到了格子（Lattices）即L = {a₁v₁+…+a_nv_n}

直观感受一个最简单的格：

在上面这个图中，每一个交点都是格上的一个格点，其基向量是（0,1）和（1,0）

该格用数学符号表示为：

$L= \begin{bmatrix} 0&1\\ 1&0\\ \end{bmatrix}$

根据不同的基向量，我们可以得到不同的格点：

比如选择（1，1）和（1，-1）作为基向量，因为系数要取整数，所以（1,0）这个点就是这两个基向量张成的格中不存在的格点

格的维数：即向量的个数，上面这个就表示二维的格

然后根据整数系数a的不同 就可以形成很多个不同的L集合

假定v₁ , v₂ , … , v_n （称为张成空间）是格L的基 然后存在不同个集合属于L 即w₁ , w₂ ,… , w_m

则有（属于线性组合）

到此格的问题转化为矩阵的运算

线性无关（linearly independence）v₁ , v₂ , … , v_n线性无关，当且仅当方程a₁v₁+…+a_nv_n=0的唯一解是a全部为0；否则线性相关（linearly dependent）

正交基（orthogonal basis）v₁ , v₂ , … , v_n 中任意不同的两个v点积的结果为0

规范正交（orthonormal） 上面的每一个v的**欧几里得范数(类似于模 长度)**为1

据此在上面的w的||w||² = 所有系数a的平方和

基础的格运算（行列式运算）

举栗子：

选定基向量生成格子L：

将其作为行向量写成矩阵：

假设L的其他向量组为：

提取其系数a 形成矩阵：

得到w的值（对应每一列列向量代表w）：

B = （w1,w2,w3）

所以A = B * U^-1

故v1 = 4w1 -2w2 -w3

代码验证：

#sage
v1 = [2, 1, 3]
v2 = [1, 2, 0]
v3 = [2, -3, -5]

A = matrix([v1, v2, v3])
print(A)
# [ 2  1  3]
# [ 1  2  0]
# [ 2 -3 -5]

U = matrix([[1, 0, 1], [1, -1, 2], [1, 2, 0]])
print(U)
# [ 1  0  1]
# [ 1 -1  2]
# [ 1  2  0]
print(U.det())
# -1

B = U*A
print(B)
# [ 4 -2 -2]
# [ 5 -7 -7]
# [ 4  5  3]

inv_U = U.inverse() #求矩阵的逆
print(inv_U)
# [ 4 -2 -1]
# [-2  1  1]
# [-3  2  1]

assert inv_U * B == A

SVP（shortest Vector Problem）最短向量问题

我们根据开篇的内容可以看到一个格L这个集合中会存在无线多个向量集合v

所以最短向量问题 就是指在这一个格L中最短的非零向量 即寻找一个v满足欧几里得范数最小（指该集合的每一个元素的平方和再开方）范数就是指长度

此外格中的最短向量可能不止一个，举个例子:

向量（0,1）和（1,0）张成的格

求解前置知识：

==基：==

在向量空间的每一个点，都可以通过对基的线性组合变化得到，叫做基向量

一个格可能会有很多个基 不唯一

==正交基：==

基相互垂直，就是正交基

==格基规约：==

目的就是：找到最接近正交基的基向量

random basis也是一组基，可以构成这个格子中的所有点 但是不是正交基

通过LLL或BKZ算法 得到正交基或者是最接近正交基

此时思考：我们找这个正交基目的是什么，为什么要找这个正交基呢，它有什么用吗？

目的在于：寻找最短向量v 也就是SVP问题

先找到正交基或者最接近正交基的基 进而证明我们的最短向量一定在这组基上

存在两种关系：

1. 假设v是这个基中的某个向量，在其他向量上的投影长度为0，两两垂直，符合SVP
2. 假设v不是基中的向量，此刻该向量一定可以通过在其他基向量方向的投影来得到一个更短的向量

垂直投影更短

CVP（Closet Vector Problem）最近向量问题

格外向量w和格内向量v的差值的欧几里得范数最小

• 与SVP的关系：有些问题可以通过对CVP加上一维之后转变为SVP问题，因为SVP相比CVP稍微简单一些

做题要点（Key）超重点！！！！！！ 明白这个到底是在干什么

经过前面基础知识的铺垫与学习，下面就要进行实战操作了，但是在实战开始之前，我们得把我们学到的内容转化成武器，这一过程非常重要。

首先在求解格密码的问题的时候，我们经常用到LLL算法，但是我们需要思考这个LLL算法的本质，为什么通过 LLL算法后得到的结果，就是我们想要得到的结果，这个进行LLL算法的格有什么要求吗，如何构造这样一个格呢，如果每次看到题目套模板，能做的题目真的是寥寥无几，所以要明白这个算法到底是在干什么的，如何去构造！

下面的学习内容是从DexterJie师傅的博客

task.py

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

$f' = f +20192020202120222023 \\ h = invert(f',p)*g\%p \\ h = f'^{-1}*g~(mod~p) \\ h = f'^{-1}*g + kp \\ g = hf' - kp \\ 构造格 \\ \left(\begin {array}{c} f' &-k \\ \end{array}\right) \left(\begin {array}{c} 1 &h \\ 0 &p \\ \end{array}\right) = \left(\begin {array}{c} f' &g \\ \end{array}\right)$

构造完这个式子之后，对二维矩阵进行LLL算法的结果就是我们想求的值

那么为什么会这样呢

这个时候就要回顾到LLL算法的作用，把（1，h）和（0，p）这组基变成正交化程度最大的一组基，去求解最短向量，所以只需要证明这个（f‘，g）是最短向量，那么我们上面的式子就全部讲的通了

Hermite定理

引入Hermite定理，给出了最短向量的上界 参考：格密码笔记

其中n表示维度，也就是基向量的个数，在本题中n = 2

det(L) = 行列式的值 = 1 * p = p

故：

$||v|| \leq \sqrt {np} = \sqrt {2p}$

向量v = （f’， g）

其长度为

$len = \sqrt {f'^2+g^2}$

其中 p = 512bit g = 128bit

一般flag长度43左右（uuid） 即f’约等于 335bit 但是很不幸 这个题目不是这样的

demo：

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  #对于bit没有 影响 因为f接近255
temp2 = gmpy2.iroot(f**2+(b*g)**2, 2)[0]  #主要在于f g没有太大影响
#此外一定要注意 在python中 ^是异或  **才是平方 
print(temp2.bit_length())  #255  乘b = 256

满足该定理，所以是可解的

所以这个长度len是我们可以构造的，而上界是固定的，越接近上界，值越精确，所以可以通过系数调整len的值从而使得和上界更接近，但是存在问题，如果系数过大，使得长度超过了上界，则无法求解

注意我们的行列式也在乘b进行变化

b = 2**248
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 * b * p, 2)[0]  #bit = (248 + 512) / 2
print(temp.bit_length()) # 381

f = f + 20192020202120222023  #对于bit没有 影响 因为f接近255
temp2 = gmpy2.iroot(f**2+(b*g)**2, 2)[0]  #主要在于f g没有太大影响
#此外一定要注意 在python中 ^是异或  **才是平方 
print(temp2.bit_length())  #376

如：

但是可以根据bit适当扩大,当过于大 比如1024bit的时候

会发现下面的值变大了 也就不满足Hermite定理了，所以也就无法求解咯

为了更好的理解这个道理，继续看下面的这个例题，easyLattice就需要进行配平

格相关的大类型

NTRU密码

该密码类似于RSA、DSA也是属于一种密码体系

easyLattice

考点：格密码 NTRU 配平

解题：

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

普通的NTRU入门格是解不了的

因为f太大，找不到，这就涉及到一个非常巧妙的构造格的方法了，那就是对格中的基向量进行配平，使得各方向长度接近一点。

那么什么情况下才能配平成功，就要搬出我们上面学习的Hermite定理咯，这里非常贴心的公布了flag的长度47

那么bit数大约是375左右

如果不配平的话，使用我们的Hermite测试demo！！保存 去测试发现是不满足的

257 < 375

存一下Hermite测试板：

import gmpy2
from Crypto.Util.number import *

b = 2 ** 0
flag = b'flag{Do_you_like_Laooooooo00000ooottice?Addoil}'
print(len(flag))
f = bytes_to_long(flag)
print(f.bit_length())  
p = getPrime(512)
g = getPrime(128)
g = g

#行列式的值
temp = gmpy2.iroot(2 * b * p, 2)[0]  #bit = (248 + 512) / 2
print(temp.bit_length()) 

#最短向量的值
temp2 = gmpy2.iroot(f**2+(b*g)**2, 2)[0]  #主要在于f g没有太大影响
#此外一定要注意 在python中 ^是异或  **才是平方 
print(temp2.bit_length())  

所以进行配平

此时满足Hermite定理，可以进行求解

exp：

def GaussLatticeReduction(v1, v2):
    while True:
        if v2.norm() < v1.norm():
            v1, v2 = v2, v1
        m = round( v1*v2 / v1.norm()^2 )
        if m == 0:
            return (v1, v2)
        v2 = v2 - m*v1

h = 9848463356094730516607732957888686710609147955724620108704251779566910519170690198684628685762596232124613115691882688827918489297122319416081019121038443
p = 11403618200995593428747663693860532026261161211931726381922677499906885834766955987247477478421850280928508004160386000301268285541073474589048412962888947     
c = 6388077150013017095358415295704360631706672647932184267739118115740221804173068089559645506533240372483689997499821300861865955720630884024099415936433339512125910973936154713306915269365877588850574948033131161679256849814325373882706559635563285860782658950169507940368219930971600522754831612134153314448445006958300840618894359885321144158064446236744722180819829183828290798747455324761671198097712539900569386477647697973195787663298318786718012522378981137877863153067057280649127202971806609339007027052518049995341356359016898069863799529357397514218249272201695539181908803360181347114492616706419618151757
print(h.nbits(),p.nbits())
D = 2^256  #配平数与位数相关 需要学习补充 237-256次方均可解
# Construct lattice.
v1 = vector(ZZ, [1, D * h])
v2 = vector(ZZ, [0, D * p])
m = matrix([v1,v2]);

import libnum

# Solve SVP.
shortest_vector = m.LLL()[0]
f, g = shortest_vector
print(f, g)
#BKZ
L = m.BKZ(block_size=2)
shortest_vector = L[0]
f, g = shortest_vector
print(f, g)
print(libnum.n2s(int(abs(f))))
import gmpy2
#验证
print(QQ((f**2+g**2)**0.5))
print(QQ((p/2)**0.5))

flag：

512 512
-50073894085033274448337202692453522746880698077702322983028272289946704698284083256500537353714697134260425361796 -923598439793643506521260484208891374490129477915686911192431263509527780701021177518396468225804284049504314851328
-50073894085033274448337202692453522746880698077702322983028272289946704698284083256500537353714697134260425361796 -923598439793643506521260484208891374490129477915686911192431263509527780701021177518396468225804284049504314851328
b'SICTF{e3fea01c-18f3-4638-9544-9201393940a9}A\xf0\x89\x84'
924954849091614614580872247749080872466147164448631556705831800681208387067055421806078719613226163736775252508672
75510324462935505386352201496661374657272071149690974092911803081859274899457

Reference：

https://xenny.wiki/posts/crypto/Lattice/lattice-based.html#ntru

https://0xffff.one/d/1641

---

学完LLL的作用之后再回顾，给出了更简洁的实现脚本

import libnum
h = 9848463356094730516607732957888686710609147955724620108704251779566910519170690198684628685762596232124613115691882688827918489297122319416081019121038443
p = 11403618200995593428747663693860532026261161211931726381922677499906885834766955987247477478421850280928508004160386000301268285541073474589048412962888947 

b = 2^256
print(b)
Ge = Matrix(ZZ,[[1,b*h],
                [0,b*p]])
print(Ge.LLL())
f,g = Ge.LLL()[0]
f,g = abs(f),abs(g)

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

ez_ntru

做爽了，再来一题，这是2024山警黄河流域的题目

task.py

from secret import flag
import libnum

bits = 2048
while True:
  q = random_prime(2^bits, lbound=2^(bits - 1))
  f = random_prime(2^(3*bits//4 - 1))
  g = random_prime(2^(bits//4 - 1))
  if gcd(f, q*g) == 1:
    h = f.inverse_mod(q) * g % q
    break

r = random_prime(2^(3*bits//4 - 1))
m = libnum.s2n(flag)
assert m < 2^(bits//4)
c = (r * h + m) % q

print('q = %d' % q)
print('h = %d' % h)
print('c = %d' % c)
q = 24445829856673933058683889356407393860808522483552243481673407476395441107312130500945533047834993780864465577896968035259377721441466959027298166974554621753030728893320770628116412892838297326949997096948374940319126319050202262831370086992122741039059235809755486170276098658609363789670834482459758766315965501103856358827004129316458293962968758091319313119139703281758409686502729987426264868783862562150543872477975124482520151991822540312287812454562890993596447391870392038170902308036014733295394468384998808411243690466996284064331048659179342050962003962851315539367769981491650514319735943099663094899893
h = 4913183942329791657370364901346185016154546804260113829799181697126245901054001842015324265348151984020885129647620152505641164596983663274947698263948774663097557712000980632171097748594337673511102227336174939704483645747401790373320060474777199502879236509921155985395351647045776678540066383822814858118010995298071799515355111562392871675582742450331679030377003011729873888234401630551097244308473512890467393558048369156638425711104036276296581364374424105121033213701940135560177615395895359023414249846471332180098181632276243857635719541258706892559869642925945927703702696983949003370155033272664851406633
c = 23952867341969786229998420209594360249658731959635047659110331734424497403162506614140213749790708068086973241468969253395309243550869149482017583754015801740198734485871141965939993554966887039832701333623276590311516052334557237678750680087492306461195312290860900992532859827406262394480605001436094705579158919540851727801502678160085863180222123880690741582667929660533985778430252783414931317574267109741748071838599712027351385462245528001743693258053631099442571041984251010436099847588345982312217135023484895981833846397834589554744611429133085987275209019352039744743479972391909531680560125335638705509351

题目思路是一模一样的，

首先梳理一下该题中解决ntru问题的各bit数

q = 2048bit

f = 1535

g = 511

如果不配平，显然不符合Hermite定理，所以要配平

显然 当配上1024bit的系数 1535 < 1537 这个格子的最短向量可求，符合Hermite定理。

解决完上面的ntru 拿到了f和g 继续进行Part2，其中

r = random_prime(2^(3*bits//4 - 1))
m = libnum.s2n(flag)
assert m < 2^(bits//4)
c = (r * h + m) % q

推导：

$h = f^{-1}*g~(mod~q) \\ c = r * h + m ~(~mod~ q) \\ c = r * f^{-1}*g + m~(mod~q)\\ fc = rg + fm~(mod~q) \\ 对式子模g，得\\ m = (fc~(mod~q))*f^{-1}~(mod~g)$

尤其注意一个点，就是在mod q的情况下继续模g 注意区分开，最终的f的-1次方是在模g下的逆元

拿下：

完整exp：

import libnum
q = ...
h = ...
c = ...
b = 2^1024
Ge = Matrix(ZZ,[[1,b*h],
                [0,b*q]])
#结果为 （f b*g）
# print(Ge.LLL())
f,g = Ge.LLL()[0]
f,g = abs(f),abs(g)//b
print(f, g)

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

#写法二  额额 一模一样
a = f*c % q % g
m = a * inverse_mod(f, g) % g
print(bytes.fromhex(hex(m)[2:]))

b'flag{7c95453a-e577-40d8-9ad0-993655b83b69}'

Easy_3L

题目源代码：

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

m = bytes_to_long(flag)


def get_key():
    p = getPrime(1400)
    f = getRandomNBitInteger(1024)
    while True:
        q = getPrime(512)
        if gcd(f, q) != 1:
            continue
        else:
            break
    h = (invert(f, p) * q) % p
    return p, h


def encrypt1(m):
    a = getPrime(250)
    b = getRandomNBitInteger(240)
    n = getPrime(512)
    seed = m
    s = [0] * 6
    s[0] = seed
    for i in range(1, 6):
        s[i] = (s[i - 1] * a + b) % n
    return s


def encrypt2(msg, p, h):
    s = getRandomNBitInteger(512)
    c = (s * h + msg) % p
    return c


s = encrypt1(m)
print("S1 =", s[1])
print("S2 =", s[2])
print("S4 =", s[4])
print("S5 =", s[5])

p, h = get_key()
c = encrypt2(s[3], p, h)
print("p =", p)
print("h =", h)
print("c =", c)

# S1 = 28572152986082018877402362001567466234043851789360735202177142484311397443337910028526704343260845684960897697228636991096551426116049875141
# S2 = 1267231041216362976881495706209012999926322160351147349200659893781191687605978675590209327810284956626443266982499935032073788984220619657447889609681888
# S4 = 9739918644806242673966205531575183334306589742344399829232076845951304871478438938119813187502023845332528267974698273405630514228632721928260463654612997
# S5 = 9755668823764800147393276745829186812540710004256163127825800861195296361046987938775181398489372822667854079119037446327498475937494635853074634666112736
# p = 25886434964719448194352673440525701654705794467884891063997131230558866479588298264578120588832128279435501897537203249743883076992668855905005985050222145380285378634993563571078034923112985724204131887907198503097115380966366598622251191576354831935118147880783949022370177789175320661630501595157946150891275992785113199863734714343650596491139321990230671901990010723398037081693145723605154355325074739107535905777351
# h = 2332673914418001018316159191702497430320194762477685969994411366563846498561222483921873160125818295447435796015251682805613716554577537183122368080760105458908517619529332931042168173262127728892648742025494771751133664547888267249802368767396121189473647263861691578834674578112521646941677994097088669110583465311980605508259404858000937372665500663077299603396786862387710064061811000146453852819607311367850587534711
# c = 20329058681057003355767546524327270876901063126285410163862577312957425318547938475645814390088863577141554443432653658287774537679738768993301095388221262144278253212238975358868925761055407920504398004143126310247822585095611305912801250788531962681592054588938446210412897150782558115114462054815460318533279921722893020563472010279486838372516063331845966834180751724227249589463408168677246991839581459878242111459287

对题目进行分析 很明显get_key一点用没有直接忽略

然后在encrypt1中捕捉到关键代码：

s[0] = seed
for i in range(1, 6):
	s[i] = (s[i - 1] * a + b) % n

这是一个lcg流密码伪随机数生成

其中已知s1、s2、s4、s5

然后最终的flag就是s0

想要恢复出初始的种子seed 就需要有连续的lcg生成数

所以锁定目标，求解s3

从而进入到encrypt2进行解密获得s3

c = (s * h + msg) % p

关键加密代码如上

进行变形：c = s * h + m - k * p

已知c，h，p 并且这三项位数相同 是1400位 比较大

然后s未知是512位

需要构建格密码求解m

将已知的内容作为构建格子M的内容 其系数提取到该格子的系数进行相乘

c - s * h + k * p = m

构造格子：

$M=\begin{pmatrix} 1&0&-h\\ 0&2^{512}&c\\ 0&0&p \end{pmatrix}\\\\$

其系数：

$\begin{pmatrix} s&1&k \end{pmatrix}\\\\$

两矩阵相乘结果：

$\begin{pmatrix} s&2^{512}&m \end{pmatrix}\\\\$

我们构造盒子的标准在于其生成的结果要接近，且较小，起初使用2行2列的格式构建格子我们发现c会在结果中出现，因为c的长度过大，所以无法生成合适的规约数！！

代码实现：

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

p = 25886434964719448194352673440525701654705794467884891063997131230558866479588298264578120588832128279435501897537203249743883076992668855905005985050222145380285378634993563571078034923112985724204131887907198503097115380966366598622251191576354831935118147880783949022370177789175320661630501595157946150891275992785113199863734714343650596491139321990230671901990010723398037081693145723605154355325074739107535905777351
h = 2332673914418001018316159191702497430320194762477685969994411366563846498561222483921873160125818295447435796015251682805613716554577537183122368080760105458908517619529332931042168173262127728892648742025494771751133664547888267249802368767396121189473647263861691578834674578112521646941677994097088669110583465311980605508259404858000937372665500663077299603396786862387710064061811000146453852819607311367850587534711
c = 20329058681057003355767546524327270876901063126285410163862577312957425318547938475645814390088863577141554443432653658287774537679738768993301095388221262144278253212238975358868925761055407920504398004143126310247822585095611305912801250788531962681592054588938446210412897150782558115114462054815460318533279921722893020563472010279486838372516063331845966834180751724227249589463408168677246991839581459878242111459287

M = matrix(ZZ, [[1, 0,-h], [0, 2**512,c],[0,0,p]])
M = M.LLL()

print(M[0][2])
#10700695166096094995375972320865971168959897437299342068124161538902514000691034236758289037664275323635047529647532200693311709347984126070052011571264606

到此获得s3

最后根据s1到上s5反推s0

from Crypto.Util.number import *
def gcd(a,b): 
    if(b==0): 
        return a 
    else: 
        return gcd(b,a%b) 
s =  [S1,S2,S3,S4,S5]
t = []
for i in range(1,5):
    t.append(s[i]-s[i-1]) 
all_n = []
for i in range(2):
    all_n.append(gcd((t[i+1]*t[i-1]-t[i]*t[i]), (t[i+2]*t[i]-t[i+1]*t[i+1]))) 

MMI = lambda A, n,s=1,t=0,N=0: (n < 2 and t%N or MMI(n, A%n, t, s-A//n*t, N or n),-1)[n<1] #逆元计算
for n in all_n:
    n=abs(n)
    if n==1:
        continue
    a=(s[2]-s[1])*MMI((s[1]-s[0]),n)%n
    ani=MMI(a,n)
    b=(s[1]-a*s[0])%n
    seed = (ani*(s[0]-b))%n
    plaintext=seed
    print(long_to_bytes(plaintext))

#b'\x00'
#b'DASCTF{NTRU_L0G_a6e_S1mpLe}'

简单的NTRU(只有常数项)

#构造格就行
h = 
p = 
c = 

v1 = vector(ZZ, [1, h])
v2 = vector(ZZ, [0, p])
m = matrix([v1,v2]);
f, g = m.LLL()[0]
print(f, g)

#按题目推导 和ez_ntru的相同
a = f*c % p % g
m = a * inverse_mod(f, g) % g
print(bytes.fromhex(hex(m)[2:]))

一般多项式NTRU

构造的格仍然是
[
	[1,h],
	[0,p]
]

N =
p =
q =
Q.<x> = Zmod(q)[]
P.<y> = Zmod(p)[]

ex = 
hx = 

print('-------decrypt------')
qq = x^N-1
pp = y^N-1
hn = [int(x) for x in hx.coefficients()]
n = len(hn)
A1 = matrix.identity(n)
A0 = matrix.zero(n)
Aq = matrix.identity(n) * q
Ah = matrix(ZZ, [hn[-i:] + hn[:-i] for i in range(n)])
M = block_matrix([A1,Ah,A0,Aq],nrows=2)
L = M.LLL()
v = L[0]
f = list(v)[:n]
g = list(v)[n:]
fx = Q(f)
fy = P(f)
gx = Q(g)
Fqx = fx.inverse_mod(qq)
Fpy = fy.inverse_mod(pp)

#hxx = (Fqx*gx).mod(x^N-1)
#print(hxx==hx)

ax = (fx*ex).mod(qq)
an = [int(x) for x in ax.coefficients()]
#中心提升(centerlift)，使域范围从[0,q)变换到(-q/2,q/2)
for i in range(len(an)):
	if an[i] > q//2:
		an[i] -= q
ax = P(an)
print(ax)
out = (Fpy * ax).mod(pp)
print(out)

print(bytes(out.coefficients()))

脚本2

from Crypto.Util.number import *

n = 160
d = 30
p = 3
q = 65536
PR = PolynomialRing(ZZ, name = 'x')
x = PR.gen()
R = PR.quotient_ring(x ^ n - 1, names = 'y')
y = R.gen()

pubkey = -11891*x^159 + 16347*x^158 - 32137*x^157 + 14988*x^156 + 16657*x^155 - 25785*x^154 - 21976*x^153 - 31745*x^152 - 4232*x^151 + 29569*x^150 + 27140*x^149 + 19617*x^148 - 16656*x^147 + 8925*x^146 + 8728*x^145 - 8802*x^144 - 10794*x^143 - 28159*x^142 - 6454*x^141 - 10259*x^140 - 19169*x^139 - 14357*x^138 + 3501*x^137 + 9885*x^136 - 7441*x^135 + 18268*x^134 - 27183*x^133 + 26085*x^132 + 19147*x^131 + 17153*x^130 - 22887*x^129 + 32476*x^128 - 21698*x^127 + 19138*x^126 + 11585*x^125 + 22755*x^124 - 5920*x^123 + 7581*x^122 + 25973*x^121 + 13787*x^120 - 22762*x^119 + 29207*x^118 - 17916*x^117 - 11502*x^116 + 18275*x^115 + 318*x^114 - 6890*x^113 - 22751*x^112 - 27677*x^111 - 11114*x^110 + 8623*x^109 - 15725*x^108 - 6835*x^107 - 8288*x^106 - 5235*x^105 - 28697*x^104 + 10696*x^103 + 17117*x^102 + 24696*x^101 - 7801*x^100 - 31874*x^99 - 17668*x^98 - 11204*x^97 + 19147*x^96 + 24644*x^95 - 29380*x^94 - 26237*x^93 - 27390*x^92 + 19982*x^91 + 4074*x^90 - 17248*x^89 - 11027*x^88 - 32690*x^87 + 5124*x^86 - 20823*x^85 - 11779*x^84 + 13781*x^83 + 29356*x^82 - 9740*x^81 - 31484*x^80 - 540*x^79 + 32360*x^78 + 24795*x^77 - 8864*x^76 + 17363*x^75 + 9670*x^74 + 32268*x^73 + 17961*x^72 + 6388*x^71 + 580*x^70 + 128*x^69 + 339*x^68 + 3412*x^67 - 4519*x^66 - 25056*x^65 + 6096*x^64 + 18720*x^63 - 5338*x^62 + 16910*x^61 + 3353*x^60 + 15433*x^59 - 28053*x^58 - 18883*x^57 + 7688*x^56 - 31198*x^55 + 9950*x^54 - 9388*x^53 + 21235*x^52 + 2847*x^51 + 24383*x^50 + 19431*x^49 + 21244*x^48 - 8498*x^47 - 28998*x^46 + 962*x^45 + 20579*x^44 + 28002*x^43 - 6040*x^42 + 4241*x^41 + 11655*x^40 - 32419*x^39 + 21531*x^38 + 7348*x^37 - 5503*x^36 + 29820*x^35 + 28896*x^34 + 8754*x^33 + 17978*x^32 + 7552*x^31 + 27240*x^30 - 29515*x^29 - 20322*x^28 + 2201*x^27 + 8857*x^26 - 50*x^25 - 3780*x^24 - 12138*x^23 + 10893*x^22 + 23133*x^21 + 6142*x^20 - 23798*x^19 - 15236*x^18 + 32564*x^17 + 25683*x^16 - 24010*x^15 - 4355*x^14 + 22552*x^13 - 27155*x^12 + 27649*x^11 + 17781*x^10 + 7115*x^9 + 27465*x^8 - 4369*x^7 + 24882*x^6 - 11675*x^5 - 612*x^4 + 12361*x^3 + 20120*x^2 + 6190*x - 10843
pubkey = R(pubkey)
c = -26801*x^159 - 25103*x^158 + 29811*x^157 - 12251*x^156 - 13386*x^155 - 28030*x^154 - 16511*x^153 + 23761*x^152 + 28329*x^151 - 16406*x^150 + 30931*x^149 + 5326*x^148 + 19877*x^147 - 23165*x^146 - 31540*x^145 - 7923*x^144 + 5880*x^143 - 27078*x^142 - 25436*x^141 - 17162*x^140 + 1471*x^139 + 14486*x^138 + 7702*x^137 - 29890*x^136 + 29315*x^135 + 558*x^134 - 22429*x^133 - 361*x^132 + 19049*x^131 - 30437*x^130 - 32610*x^129 - 3024*x^128 - 4313*x^127 + 29174*x^126 - 2837*x^125 - 2812*x^124 + 13450*x^123 - 15001*x^122 - 25791*x^121 - 8702*x^120 - 4968*x^119 - 15340*x^118 + 31744*x^117 - 32478*x^116 + 19737*x^115 - 12629*x^114 - 27847*x^113 + 27322*x^112 - 31375*x^111 + 14777*x^110 + 29825*x^109 - 25883*x^108 - 13335*x^107 + 32517*x^106 + 14871*x^105 - 7287*x^104 + 13398*x^103 - 32710*x^102 + 20805*x^101 + 29734*x^100 - 14579*x^99 + 17483*x^98 - 16864*x^97 - 26745*x^96 + 3254*x^95 + 7280*x^94 - 29046*x^93 - 7531*x^92 - 8791*x^91 + 15033*x^90 - 1125*x^89 - 14713*x^88 - 12273*x^87 + 8616*x^86 + 2486*x^85 + 31810*x^84 + 27795*x^83 - 21731*x^82 + 21743*x^81 - 27595*x^80 - 3592*x^79 - 27206*x^78 - 32156*x^77 + 32124*x^76 - 11212*x^75 - 6662*x^74 - 23103*x^73 - 3660*x^72 - 31043*x^71 - 17131*x^70 + 24544*x^69 - 32326*x^68 - 31047*x^67 + 19814*x^66 + 10874*x^65 - 8449*x^64 + 11744*x^63 + 2245*x^62 - 967*x^61 + 9120*x^60 + 8983*x^59 - 24573*x^58 + 24885*x^57 + 15649*x^56 - 18970*x^55 + 7354*x^54 - 12282*x^53 - 22474*x^52 + 4395*x^51 + 8428*x^50 - 32592*x^49 + 25980*x^48 - 4599*x^47 + 16310*x^46 + 18559*x^45 + 22897*x^44 + 19080*x^43 - 26065*x^42 - 9*x^41 + 29202*x^40 + 2121*x^39 - 5004*x^38 + 5299*x^37 - 28301*x^36 - 13519*x^35 + 24241*x^34 + 529*x^33 - 20574*x^32 - 27391*x^31 + 31976*x^30 + 22824*x^29 - 31410*x^28 - 20976*x^27 + 21661*x^26 - 15132*x^25 + 1905*x^24 - 30870*x^23 + 18109*x^22 - 17373*x^21 + 5342*x^20 - 22447*x^19 + 1893*x^18 - 17545*x^17 + 30097*x^16 - 21731*x^15 + 17390*x^14 + 10991*x^13 - 5384*x^12 + 15960*x^11 + 24268*x^10 - 29867*x^9 + 22532*x^8 + 10133*x^7 - 26576*x^6 - 5742*x^5 - 16252*x^4 + 13019*x^3 - 25984*x^2 + 14004*x + 22500
c = R(c)

def balance_mod(f, q):
    g = list(((f[i] + q // 2) % q) - q // 2 for i in range(n))
    return R(g)

def invert_mod_prime(f, p):
    T = R.base().change_ring(Integers(p)).quotient(x ^ n - 1)
    return R(1 / T(f))

def dec(c, prikey):
    f, fp = prikey
    a = balance_mod(c * f, q)
    return balance_mod(a * fp, p)

def crack(pubkey, c):
    A = Matrix(ZZ, 2 * n, 2 * n)
    hp = inverse(p, q) * pubkey
    hp_list = list(hp)
    for i in range(n):
        A[i, i] = q
    for i in range(n, 2 * n):
        for j in range(n):
            A[i, j] = hp_list[(j - i) % n]
        A[i, i] = 1
    AL = A.BKZ()
    for row in AL:
        try:
            f = R(row[n:].list())
            fp = invert_mod_prime(f, p)
            return dec(c, (f, fp))
            break # may failed with shortest vector(return more if failed)
        except:
            pass
        
m = crack(pubkey, c)

m = m.list()
for i in range(len(m)):
    m[i] += 1
    m[i] = str(m[i])
str1 = "".join(m[::-1])
temp = int(str1,3)
print(long_to_bytes(temp))

ntru变形

重新推一下关系式构造格 不变形的ntru是

c 同余 rf^-1g + m mod p

构造[[1,h],[0,p]]

能解出f g 然后数学推导回m就行

背包密码

参数：

• 私钥：超递增序列 每一个数要比前面的全部数之和还要大
• 模数：m 大于超递增序列的全部和
• 乘数：w 满足和模数m互素 即gcd(w,m)=1
• 公钥：b 同余 wai mod m

超递增序列举个例子：

1、2、4、8、16 这个你可以发现每个数都是大于前面的全部和

加密

明文是一系列的0和1组成的二进制数据v

生成一个大整数c c是选入的超级递增序列私钥的和 再模m

解密

恢复v

构造格：把问题 归结到格上

HNP

基于DSA签名算法生成公式：

M相当于构造格子的基向量 然后乘系数m 得到的结果就是一系列格子的基向量

构造格子的注意事项

M = matrix(QQ,40,40)  #表示在有理数域中创建40*40的格子 默认初始为0

for i in range(38):
    M[i,i] = p  #对角线
    M[-2,i] = b[i] * inv #倒数第二行
    M[-1,i] = -r[i] * inv #倒数第一行

举个栗子：

MTCTF2022 strange_rsa3

from Crypto.Util.number import *
from secret import flag3
 
 
qBits = 2048
pBits = 512
num = 2
q = getPrime(qBits)
p = [getPrime(pBits) for _ in range(num)]
r = [getRandomRange(1, 2**(pBits * 2))]
 
a = getRandomRange(1, 2**pBits)
b = getRandomRange(1, 2**pBits)
gift = (p[0] * a - p[1]) * inverse(b, p[0] * p[1]**2) % (p[0] * p[1]**2)
r.append(a * r[0] % p[1]**2)
 
n = [p[i] * q + r[i] for i in range(num)]
e = 0x10001
c = pow(bytes_to_long(flag3), e, q)
 
output = open('output.txt', 'w')
output.write('n = ' + str(n) + '\n')
output.write('c = ' + str(c) + '\n')
output.write('gift = ' + str(gift) + '\n')
 
 n = [334024028297795358428409534536782438908850190596668304865805437854374647984162763213581202801755428896203566172506219587266859416880045688129543855047675462354257676254231028533265496444966553195988075269677126779791155950793986187076641998741755872346979307739639779735262978907659727511419480461209503641512912873117056664008629779726881137366723127568036608925132936367006658464077463797854166622020483102972486974655232026096153672010479488999300909745157075526157596970246521452157940857495163175605553461432715056788388724755538433445976849818771932805940067427962262593386608298455471107791678224956504101174392785507134071131842103995133811964997751791768061100121699973057595724142612170517768245173187399850847945628945800042668385798893530527806229363060713249, 270672332309468804376393577492871858269490099887383011988714622534037610808764741901954257217313289938393835900354736668003700671505047142365053976908516056996483106174902631762442253779775073373220342445779447626486345253598470015470094856727845150372622299396840670432953284676150980428391739322739397783248924710490946083987879121564403742528241040454099534823772379455574658130173290640751198753015984316400694738114541263533626932367096040344071742474883684682734122111076840572805111010694147825191233741720325878397443178835435703420465683485344417909319591496135706730327376897531024858122747777315158814568580929655522627811650949169204543250919027738723235091257934106114809110289433115714333069841583284243937630033653684708127947780848521445941847102881070046]
 c = 24426016715355498456650532748209528249200902516644306644652290745346403378221744208791754411669322694597831272399935610924080672864361088045894354412944203199767471898920740773322967470374385635042086816010876203117884874681450622109443867183037282062248951073356702181165103759051513426785435705002047708435055880616309144483691648077981524802908185706596363674820857151388761087408514551645305031742705266691826719380663571699663832536944531865183586885154128228789310222929701360939023228059118720311899056620389378996862413971733056546988166759451010742768802840638380019172710929867945108511664271273569394689619
gift = 173299379625576798749821685155193435290573235640007530711924098468561852299646118206367598564087551037396665586630782838190274697684611102346492601699992667822233634078800006099513099432664305226448819277556828816420517850404262393535832488384876680039695417291460237594174659357055221582914415278609167623124281569332881993050546046852564902573985929794261636296569394448935231131668411811662581097119330330246497311885207256858435515769776396794250803110128999

首先对n0和n1进行分析

n0 = p0 * q + r0 512bits 2048bits 1024bits

n1 = p1 * q + r1

n0/n1 = p0/p1 +r0/q/r1/q 约等于p0/p1

第二个栗子：

NPUCTF2020-babyLCG

考点:closed_lock_with_key::LCG随机数生成器 AES加密 HNP

题目：

from Crypto.Util.number import *
from Crypto.Cipher import AES
from secret import flag

class LCG:
    #相当于java里面的构造方法 调用类名则执行
    def __init__(self, bit_length):
        m = getPrime(bit_length)
        a = getRandomRange(2, m)
        b = getRandomRange(2, m)
        seed = getRandomRange(2, m)
        self._key = {'a':a, 'b':b, 'm':m}
        self._state = seed
    #相当于java里面的成员方法  
    #第一次调用则是 s1 = a * seed + b % m  则seed = （s1 - b） * inverse（a，m） %m
    def next(self):
        self._state = (self._key['a'] * self._state + self._key['b']) % self._key['m']
        return self._state
    
    def export_key(self):
        return self._key


def gen_lcg():
    rand_iter = LCG(128)
    key = rand_iter.export_key()
    f = open("key", "w")
    f.write(str(key))
    return rand_iter


def leak_data(rand_iter):
    f = open("old", "w")
    for i in range(20):
        #写入的时候右移了64位 所以调用的时候要左移64位
        f.write(str(rand_iter.next() >> 64) + "\n")
    return rand_iter


def encrypt(rand_iter):
    f = open("ct", "wb")
    key = rand_iter.next() >> 64
    key = (key << 64) + (rand_iter.next() >> 64)
    #这是生成16字节 即128bits的密钥 从而如果key转化后长度不够则在末尾用指定字符\x00进行补充
    key = long_to_bytes(key).ljust(16, b'\x00')
    iv = long_to_bytes(rand_iter.next()).ljust(16, b'\x00')
    cipher = AES.new(key, AES.MODE_CBC, iv)
    pt = flag + (16 - len(flag) % 16) * chr(16 - len(flag) % 16)
    ct = cipher.encrypt(pt.encode())
    f.write(ct)


def main():
    rand_iter = gen_lcg()
    rand_iter = leak_data(rand_iter)
    encrypt(rand_iter)


if __name__ == "__main__":
    main()

首先是lcg随机数的生成

给出了密钥k m b

lcg随机数的生成公式：s_i+1 = a * s_i + b (mod m)

并且已知每一个随机数泄露的高64bits的数据

所以将s分为高位h和低位部分l

（h_i+1 + l_i+1) = a * (h_i + l_i)+ b (mod m)

l_i+1 = a * l_i + a * h_i + b - h_i+1 (mod m)

其中l_i+1 和 l_i 未知 其他均已知

每次相乘保证l_i存在则需要设置相应的A_i和B_i

构造为：

因为这个数是128bits的 然后高64位已知 所以低位l最大是64bits 右下角K是轮密钥的上界 所以构造格子

使得存在一个向量与M相乘 得到的结果向量内各元素大小接近

这样构建了格子之后 对格子使用LLL()算法 取出第0行倒数第二列的数值 成功获得第一个低位的数值

然后和高位拼接 恢复原始s1 从而获得seed

代码如下：

#sage
b=153582801876235638173762045261195852087
a=107763262682494809191803026213015101802
m=226649634126248141841388712969771891297

h = [0,7800489346663478448,11267068470666042741,5820429484185778982,6151953690371151688,548598048162918265,1586400863715808041,7464677042285115264,4702115170280353188,5123967912274624410,8517471683845309964,2106353633794059980,11042210261466318284,4280340333946566776,6859855443227901284,3149000387344084971,7055653494757088867,5378774397517873605,8265548624197463024,2898083382910841577,4927088585601943730]
for i in range(len(h)):
    h[i] <<= 64
A = [1]#首项为a
B = [0]#首项为a*h[i]+b-h[i+1]
for i in range(1, len(h)-1):
    A.append(a*A[i-1] % m)
    B.append((a*B[i-1]+a*h[i]+b-h[i+1]) % m)
A = A[1:]
B = B[1:]

# print(len(A))   长度为19 
# print(B)

# 利用A和B开始 构造格子  整数域 21*21
M = matrix(ZZ,21,21)
for i in range(19):
    M[i,i] = m
    M[20,i] = B[i]
    M[19,i] = A[i]
M[20,20] = 2 ** 64  
M[19,19] = 1
# print(M)
M = M.LLL()  #会获得很多组向量 一般取第一个
l1 = M[0][-2]
s1 = l1 + h[1]
# print(s1)
import gmpy2
#根据原式转换：seed = （s1 - b） * inverse（a，m） %m
seed = ((s1 - b)*gmpy2.invert(a,m))%m
print(seed)
#73991202721494681711496408225724067994

获取seed之后就是去解决AES问题了

注意AES是对称加密体系中的算法 所以其加密程序和解密程序是有非常密切的关系的

我们只需要和加密时使用相同的算法获得密钥key 和初始向量iv即可构建相同的AES密码器

from Crypto.Util.number import *
from Crypto.Cipher import AES
# from secret import flag

class LCG:
    def __init__(self, bit_length):
        #反向解题 就要把未知量换为已知 
        b = 153582801876235638173762045261195852087
        a = 107763262682494809191803026213015101802 
        m = 226649634126248141841388712969771891297
        seed = 73991202721494681711496408225724067994
        self._key = {'a':a, 'b':b, 'm':m}
        self._state = seed
        
    def next(self):
        self._state = (self._key['a'] * self._state + self._key['b']) % self._key['m']
        return self._state
    
    def export_key(self):
        return self._key


def gen_lcg():
    rand_iter = LCG(128)
    key = rand_iter.export_key()
    # f = open("key", "w")
    # f.write(str(key))
    return rand_iter


def leak_data(rand_iter):
    f = open("old", "w")
    for i in range(20):
        f.write(str(rand_iter.next() >> 64) + "\n")
    return rand_iter
def deleak_data(rand_iter):
    for i in range(20):
        rand_iter.next()
    return rand_iter


# def encrypt(rand_iter):
#     f = open("ct", "wb")

#     key = rand_iter.next() >> 64
#     key = (key << 64) + (rand_iter.next() >> 64)
#     key = long_to_bytes(key).ljust(16, b'\x00')
#     iv = long_to_bytes(rand_iter.next()).ljust(16, b'\x00')
#     cipher = AES.new(key, AES.MODE_CBC, iv)

#     pt = flag + (16 - len(flag) % 16) * chr(16 - len(flag) % 16)
#     ct = cipher.encrypt(pt.encode())
    # f.write(ct)
def decrypt(rand_iter):
    key = rand_iter.next() >> 64
    key = (key << 64) + (rand_iter.next() >> 64)
    key = long_to_bytes(key).ljust(16, b'\x00')
    iv = long_to_bytes(rand_iter.next()).ljust(16, b'\x00')
    cipher = AES.new(key, AES.MODE_CBC, iv)
    with open("C:\\Users\\jayq\\Desktop\\附件\\ct","rb") as f:
        ct = f.read()
    mt = cipher.decrypt(ct)
    print(mt)



def main():
    rand_iter = gen_lcg()
    rand_iter = deleak_data(rand_iter)
    decrypt(rand_iter)


if __name__ == "__main__":
    main()

    
#b'npuctf{7ruc4t3d-L(G-4nd-LLL-4r3-1nt3r3st1ng}\x04\x04\x04\x04'

第二个栗子:chestnut::

WMCTF-2023-Crypto signin

考点: p高位泄露

from Crypto.Util.number import *
from random import randrange
from secret import flag

def pr(msg):
    print(msg)

pr(br"""
                        ....''''''....                        
                     .`",:;;II;II;;;;:,"^'.                    
                  '"IlllI;;;;;;;;;;;;;Il!!l;^.                 
                `l><>!!!!!!!!iiiii!!!!!!!!i><!".               
             ':>?]__++~~~~~<<<<<<<<<<<<<<<<~~+__i".            
           .:i+}{]?-__+++~~~~~~<<<<<~~~~~~+_-?[\1_!^           
          .;<_}\{]-_++~<<<<<<<<<<<<<<<<<<<~+-?]\|]+<^          
          .!-{t|[?-}(|((){_<<<<<<<<<_}1)))1}??]{t|]_"          
           !)nf}]-?/\){]]]_<<<<<<<<<_]]}}{\/?-][)vf?`          
          '!tX/}]--<]{\Un[~~<<<<<~~<~-11Yz)<--?[{vv[".         
         .<{xJt}]?!ibm0%&Ci><<<<<<<<!0kJW%w+:-?[{uu)},         
          !1fLf}]_::xmqQj["I~<<<<<<>"(ZqOu{I^<?[{cc)[`         
          `}|x\}]_+<!<+~<<__~<<<<<<+_<<_+<><++-[1j/(>          
           !\j/{]-++___--_+~~<i;I>~~~__-______?}(jf}`          
            ;~(|}?_++++~~++~+]-++]?+++~~~~+++-[1/]>^           
              ;\([?__+_-?]?-_-----__-]?-_+++-]{/].             
               l||}?__/rjffcCQQQQQLUxffjf}+-]1\?'              
                ,[\)[?}}-__[/nzXXvj)?__]{??}((>.               
                 .I[|(1{]_+~~~<~~<<<~+_[}1(1+^                 
                    ,~{|\)}]_++++++-?}1)1?!`                   
                      ."!_]{11))1{}]-+i:'                      
                          .`^","^`'.                           
""".decode())

def gen_prime(bit):
    while 1:
        P = getPrime(bit)
        if len(bin(P)) - 2 == bit:
            return P

pq_bit = 512
offset = 16

P,Q = [gen_prime(pq_bit) for i in range(2)]
N = P * Q
gift = int(bin(P ^ (Q >> offset))[2+offset:],2)
pr(N)
pr(gift)

inpP = int(input())
if inpP != P:
    pr(b"you lose!")
    exit()

secret = randrange(0,P)
bs = [randrange(0,P) for _ in range(38)]

results = [(bi * secret) % P for bi in bs]
rs = [ri & (2 ** offset - 1)  for ri in results]

pr(bs)
pr(rs)
inpsecret = int(input())
if inpsecret == secret:
    pr(flag)

解题：

首先是获取p 高位泄露了十六位 虽然这16位未知 但是可以通过设置16bit长度的所有情况进行爆破

N = 73112325447718419004547130726695718285793085958231107892863489717428446716838799849309454056415849869930556787026583737635045001044331824958338557356039885155281113144595678795533444159689102603206422423835572911701365510630670709050480182217561850257781379648014791821272434711481938951190881233041060596523
gift1 = 115073356145766093260644381479331808320549133985413353306940738670775007719301812510687311522173487690937202937075087659433551944224376340973897790917
       
def get_p(gift1,N):
    for i in range(2**15,2**16):
        gift = int((bin(i)[2:] + '0' * (496-gift1.bit_length()) + bin(gift1)[2:]),2)
        # bin(gift1)[2:]也许并非496bits,可能前导0会省略，自行加上即可
        pbar = gift >> (512-16)
        print(i)
        while True:
            try:
                qbar = (N >> (1024 - pbar.bit_length()*2) )//pbar
                # print(qbar,qbar.bit_length())
                qbar = qbar>>6
                gifts = gift^(qbar<<(512-16-qbar.bit_length()))
                pbar = gifts >> (512-16-qbar.bit_length())
                # print(pbar,pbar.bit_length())
            except:
                break
            
        for i in range(64):
            # print(i)
            P = (pbar << 6) + i
            if N % P == 0:
                print(P)
                return P
get_p(gift1,N)
#9463395021022080495725625579099709864198202996192818493676075430361086175809577174253865589866353281287908307347544682931439681148579311956298173287376473

上面的脚本来源于DASCTF的比赛中

然后获得

bs = [5677770056347952821075508113035756036186750810935744246746174143756447222899456626676391801166125401365094827195531579218729867555316702975753784979244872, 2809620694316973743070419046517422880935575351562028606467262358149044880922143772187834653369648207268652362409857479009595884652141674028997687008458065, 3730270319847639205056610760089899175546681287012108868443801789244300006477333256569065708981917617890953379697372414414912864801523329022800590644960859, 5821308517313693876194723672109113624898735347480525042736754342702714857466473605555360227316768264216216522199834049459503113541382232261257078279373457, 7447756417909132324727804644545090515712348538866555221605506449994661595686624719179141597003925585021790315500290856582501600080206760793845807465435020, 2105762400848182586132539753964540320116345826242628146908489443753704312166929959947252892375240925912179106904028258517572657190458322323487967161677844, 154222298643104769325471310127340263916626139056136380962227349123299727085462094219564859503955889867523024467685219898520433147625254371592982600111385, 367828597395145770863382274648759911062421189249171333962353712349023993039851982532446913020406236969002463928822493235022843178244026427116420194632581, 1744200243856922563638772245369402677344028894603176201806040819068039225056278405389760818145017936368618817981571303260147110007739148296698937928843957, 5670406830778390730892641103362280301437252102865399395897422175624950243883078098199467864852521793872723428112979163916452992415911855252561215571391096, 4961373637791936223513400147782916563460190344580138422212799905208967588487213074873328658685093590342512783917670377711041783156851600713671476077404515, 5698904648841393994633450812750517199427982232619699696607698886438569980287267613186832256695574376500824006722753065479452944587472798782966294826498729, 2626611375827255664624275815248180600584539394441361715415622910267378140077728375819890115849477614869513835180911315948024350530246241990148027000003247, 4322432241215029052699237939341147131781420863250895517172680568672381909970064344040583613368923347568958321349659728727935451755378705244016710439641158, 1928419605038168764733449488709516192222335662921906459617704643151339384031358440020680276054871198671008628593620415807919003359787851822611275504761125, 758298969674788958681232125590769643791657077138037129139238209955794187834098615443521161703003644497548029106392839914740987840120821133758808191162464, 3026120713365180411884841936693672667286076351283725117739841509938175342066894932925924493822077276291978462795149635713410275262432016154092995131815069, 2639116385581133273068720849577714988914606374248136639831733592282012712583006465901110461383725143920082598753614952697933130060915300957054627629274585, 4938477885775391845441227660717435985351368416989649995935420783949796408027814914819890996906576154691050558257513298894204488415414648705103499910642769, 2586664093376881328787412631902927222753380482805791009422685269787127535644112074624071376797161243100602355098533019790821633292169346061029222356230765, 5553524741480099301054134204590300647682160064680815429649202130132178700086891659413819279328100036520027466610196402070124870933103957456304029253248732, 2827265379921181842866192519714225788148235787193890010891768669101713572608744951067703090450722162825909298999736141026042400464118472320665041675681263, 1882191527950117171689633117483662158586807501384802095608221879095319572751646959308080890743755189350869028885412995726442493419408160192448934636247969, 2624940783149957630052421415813956884561052534178680577595486675851951652761799600473953641982211067073776832889577908624789277943579205813592153885774787, 4557357589224938072027907497871251728077025399913277406228025890486316538978785358037884170649353496980491294290693236049954003081546235618935408233617781, 7503029892737975260686578470850749871382063215806103289417981959410942610953159314048524316989907513945454856136605901215014386958175836168455433495976840, 1481777615800981231353277825715461294317126131020372161819681326609658389423517292725626585141062920702092668619196067362128544725577006335263310427517720, 4195773140329253432252020288295924419191899561410667997498026712138128661788879368987893473405403124672999850771991585172310110744585123235362358448299402, 2003064111894296519054159734832793727058000516309777321077086228674560695531194066337528308841114906348141481465145488329210441174025042039646886744834307, 4508799626502269807611012496586770184190543351868505425146984121925038328927083771111700038861067084320342153568829171227980347727670336894671033305242053, 7141804680199937247962418027088222230735127547115123066765929692165221036432525181252245983667408692953252722174487387892809455275282654904239693974086313, 5386588055094784356165732781468142654808326535838628874938909372336169451891308083974558803497079135496650858231780699255029869995091026814783880851641095, 3782247624308335907897302856903747821512994875858417290191847604012849621190843084580777781441506763452934236540908617447821210352445344355717216720464659, 6527778172523455296666844889020389423098061136790050978799819429528238066483905902635991546245979582351890944412859630132736333005922929043047216254655955, 5307533726050766654822554741434396225884902691951304818603268654194614151318601582366056716061741240768755295434943924934683158909386226742299206040764766, 6680436528531848639646280824606034416195797982786801625729333386638769190461881575679794466409308819912401578516938662856219054823471163813941387223410656, 4887886672739126992557813239689644986751862892155246272416338920125998621231513182487516658592072003303553787101714685075776658032850821479355562756508038, 5265204245228171606770934463863274787963598538267041606291043095828239507419258123084718784524021414827606114852174671998385402424450055415134204339454340]
rs = [52066, 892, 50690, 29942, 23820, 24568, 19387, 20149, 46735, 35698, 53743, 48283, 2606, 61775, 18568, 38317, 52156, 52935, 23846, 10329, 24461, 64490, 1493, 36508, 32478, 65455, 43594, 57024, 50048, 15644, 52839, 22357, 14660, 51589, 19077, 26899, 32189, 17131]

利用hnp 获得secret

secret = randrange(0,P)
bs = [randrange(0,P) for _ in range(38)]

results = [(bi * secret) % P for bi in bs]
rs = [ri & (2 ** 16 - 1)  for ri in results]  #这里只是格式的规范化数值不变 与的内容是16bits的1 相当于对2的16次方取模

根据上式得到利用hnp的公式：ri % 2**16 = bi * secret (mod p)

ri = bi * secret % p % 2**16

ri = bi * secret + kp + l * 2**16

l * 2**16 = ri - bi * secret - kp

l = ri * inverse - bi * secret * inverse - kp (其中k和l以乘任何其他数都可以用k和l表示作为任意倍数关系)

inverse = inverse(2**16,p)

两边同时乘-1

l = bi * inverse * secret - ri * inverse + kp

ki = Ai * x + Bi 到此成功构造hnp式子

其中

p是512bits

bi secret 小于512bits

ri 16bits

l 小于 p bit位数就行 作为密钥 设为496bits

K是轮密钥的上界

构造格子

from gmpy2 import *

p = 9463395021022080495725625579099709864198202996192818493676075430361086175809577174253865589866353281287908307347544682931439681148579311956298173287376473
b = [6099745272052586004179912608738971034534930536137743613897081917185107394368705591323971750395506839750452649288267772188419489756675205679949408086451232, 3951191747812729045440242820895124607189480251095163295242628450942998752364973601131023646206377502005591988554681151953526704565202075013281769088815523, 1404420597554404030107272770922253996678162333687352195618251218863999850248824692838151822875031075053556888677319712477280556217652901167451648905364386, 4488294572333656708259420377539737505003996159677656468026097114601711607985567015550450770914323371829296766770532559711193361180597308950367687185966302, 5481102322187479419436505829074865646684095327365195150222467418442873465357487402747218531517017371054667814520443813042860956594726076176855372054132653, 2713802788133698269409249999536200419140314121130473258656206052429002170951741696862581935955915442467962543363756219468741646383480138223283730677285687, 4388471418937878873760244311226931102311967761139597301227595095454037495066960891301104963760391091058605030114648033892461656189445282496553583505973028, 736776464731641575781839292404124851285324500513593675528872423711514787996001241149637426869001948983773230073266488914216375314221965655672656410584443, 8708590989237325341864969642266721092908150322862807883501307022447092127465507299112990850265948137001397701186114982614486130822490540038423320215334626, 9267802304424548397960617736597723635936811251609846290761762903654804678628923862108480264307805107896646269881938313148864202456071920121260093838052525, 3247108183860325987343060073325154780063121072412546176464075975152503493018889336496636379292425449406827070404175667145192082945885628262842725864496476, 455724435639473173230575250620919313737714978926744740871167992567140510847659696368128186714204899204016766561731806278682654146614456839201295265351084, 9020040064239438957325652010732562703496153379776291386479249377336002129977498901663356523568148111515751758815532962162768918028366620424504879498916260, 7688416580027582769915116662018701330731542853610728083638475681090388890585799679692871117954618858316092856071130163834051800086038254809868956867017534, 2914081803071475210765607707004526189627879912343305436165346830733180111712927683631299251265551199278425089831815911602268284636090898745079700939295508, 1682447624444059192944751083327557927345592086507420627567050313041103192041463642408780131750529259046595170811376763889856062916108841799386014250209204, 5341034619247476123738204666831636378756603282709541857595527812139022510035477000927339770989486054395218479620330803691178416464134942884723827374332572, 8376329702107133848458122442144946089340952412870283575988871694491609215583935392751355281411100977914041577559011007450313560473364023276862308392837927, 9416263788845104843254295633755080717027180798661946550343273052573861692993756745844265654941124801439244186152547374828735493445699134588163894749640836, 2932216738770537817881515093909708415125754815604299999068133848728425671241756819969645781862996905460305910366082553247028095515273709817106865465122590, 8097717669926537250731305609873869963442989665404721303119492230921259587448045170648745406003491170455200904721392690716080842205006420218957357208236777, 2320095372469412381123081241813969183059217183055092564165616040030126466741691823966421813308525807455783827406201671916779545841711101790509143391460558, 2333972164269303480468982231430944844261058855427800172027932923131801032739273832904738225066210544462847760672864166563796956687623202151756145595323299, 9437506711046580131962727129679057367842176159058408153672713703801123411305447877847753662475828865148714651927615052959365575959980181945973888298104933, 5802961795945602293929959252989205060907182950209184792016006564685164829079522333038011701596715377738492900250485584441351844045455427769773524087524156, 529599427933984238231472476175004896612420169200926563371105835757115041890610229232923121353193340603425988395343027602415343623433336040543795697317090, 6402196372034668863055877348065973921962422590516519136977866652600902486323081042430853494022971845631884452544526687998575817840711058028440421779395606, 1230624307875405241534590705586346034433600380745178644341864997283918237998339933919925940523713299382838409046998100995049951280382526255707022024214853, 4939399750563474831690751351208621006534538497525744056731033390661498923441407195386308647381246454241105286776645577202434999611495000302402098783151142, 3991859998040542133259043036343592584436362790235923761833962209989024458819225460294422336721726048826788046849829864060207989750046644621835589699009365, 240857736341741610087615111623321249370900668053282004036464835672779328135852021912344864307291860960709711372109427660351057177543937799209410049857688, 3616083502398202892601882038165628001289992103457989351932690769228627486934029132426774534679657144138989265564646117621513540781010324410148517674825531, 5404612891952879264496112103405811484626424108411041737043110667122266883638660766432812414542841773559389510234873119005979364687689717241678676878972572, 2034451564894992453342874697889924929640864497213866812897528594902646690104681644785346511630568960798405400466505451930160617969903308178504532997741868, 6157490304505265465913231571555412606905748047618103662427174891510009729459475829640015546085845764226272377180939793932164111694580454672032316588788226, 4975964317099024183607476155053005595563615534064262974131837949918711606891694740515965242556735284295717544308022169459365947195601426949094207557584822, 5428476883706514219777167145065847042077736528683727164449312172005302805331073867565107042753732467573625669359225318663458427411189319424302379038071051, 1671914205500553673647970410143909519671590636952787351672356207441593565754364343607635690418391473360926097632568317796984733317042685849430234554815858]
r = [48997, 62415, 23955, 36908, 52443, 4523, 22645, 22555, 31815, 15691, 47858, 27532, 21464, 23465, 45849, 59181, 27490, 6614, 16702, 57463, 52700, 28969, 31173, 41233, 61893, 36368, 17734, 53549, 17913, 33308, 63024, 61345, 33511, 53005, 26113, 59084, 35720, 44204]

M = matrix(QQ,40,40)
inv = invert(2 ** 16,p)

for i in range(38):
    M[i,i] = p
    M[-2,i] = b[i] * inv  #Ai
    M[-1,i] = -r[i] * inv  #Bi
    
M[-2,-2] = 2 ** 496 / p   #K/p
M[-1,-1] = 2 ** 496   #K

L = M.LLL()

res = L[1][-2].numerator() / 2 ** 496
# 或 res = L[1][-2] / (2 ** 496 / p) % p
print(res)
# 1005444529226476196286726437221411001182466035947403146822894574200213482908472882296123424897230218596631139138335919912390102402492391521467426075919696
# wmctf{we1c0me_brOo0Oo!hope_y0u_h4v3_fun_iN_the_fTcmWWmcTf/}

M作为基向量 l作为系数a 相乘构建出L的其他基向量m （多解） 选择其中第二短的v

NSS工坊刷题

因是NSS工坊里面的题目，所以就不放数据啦，想学的师傅真心推荐去工坊买一下，十几块钱真的不贵，而且学格这一块，自己有数据多调调参数才有意义，自己拿到flag，才能提高学习的积极性，师傅们冲冲冲！

链接：https://www.nssctf.cn/problem/sheet/11086

P1 ：弱化版NTRU

task.py

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 = 。。。
h = 。。。
c = 。。。
'''

整个题目和上面的ez_ntru是完全一样的

首先是构造格 使用Hermite定理判断一下

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

b = 2 ** 0   #这是不断调整配平用的
p = getPrime(1024)  #已知
f = flag = getPrime(400)   
g = getPrime(512)


print(f.bit_length())  

#行列式的值 大于等于下面的即可
temp = gmpy2.iroot(2 * b * p, 2)[0]  #bit = (248 + 512) / 2
print(temp.bit_length()) 

#最短向量的值
temp2 = gmpy2.iroot(f**2+(b*g)**2, 2)[0]  #主要在于f g没有太大影响
#此外一定要注意 在python中 ^是异或  **才是平方 
print(temp2.bit_length())  

if temp.bit_length() >= temp2.bit_length():
    print("true")
else:
    print("false")

本身就满足 所以不需要调平

具体原理参考上面的ez_ntru

exp：

#sage
p = 。。。
h = 。。。
c = 。。。
print(h.nbits(),p.nbits())
D = 2^0  #配平数与位数相关 需要学习补充 237-256次方均可解

# 第一步 构造格 获取f和g
# Construct lattice.
v1 = vector(ZZ, [1, D * h])
v2 = vector(ZZ, [0, D * p])
m = matrix([v1,v2]);
print(1)
import libnum

# Solve SVP.
shortest_vector = m.LLL()[0]
f, g = shortest_vector
print(f, g)


#第二步 获得flag
import gmpy2
m = (f * c % p) * gmpy2.invert(f, g) % g
print(libnum.n2s(int(m)))

成功获得flag 注意是sage哦

P2 ：背包密码

task.py 注意注释是自己加的,可以根据注释了解一下背包密码加密的大体流程

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

flag = bytes_to_long(b'******')
flag = bin(flag)[2:]   #转化成二进制
n = len(flag)


#生成超递增序列a  其中s是所有元素的总和
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和w
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)

根据解密格

跑完后

可以发现对格Ge进行LLL之后 这个有无数组值 但是我们需要的是全部为0或者1的一组

特别需要注意 因为我们在构造格的时候是n+1 多加了一行 所以这一组值选出来之后 要去掉最后的一个数

在筛选的时候注意提取每一行的元素 有个地方需要注意一下，就是必须转换成列表才能对当前行的每一个元素操作，因为其本身是一个元组，没法提取单个元素

例如：

M = res.row(i).list()   #提取矩阵第i行转换成列表
print(M)
print(res.row(i))

[33, 184, 123, 68, -41, -182, 171, 330, 115, -108, -160, 252, -31, 163, -79, 96, -36, -90, 264, -174, 52, -43, -272, -129, 73, 7, 134, 75, -65, -272, -181, -42, 126, 69, -159, 52, -263, 45, 10, 13, -103, 161, -61, 47, 54, -77, -13, 124, -209, 204, 148, -85, -85, -62, 192, 84, -47, -99, 175, -338, -107, -45, -415, -245, -228, 125, 187, 267, -9, 170, -172, 39, 99, -47, -136, -80, -58, -87, 96, 161, -133, -18, 199, -245, 6, -46, -9, -110, -70, 17, -91, 68, 111, 44, 8, 40, 11, -12, -9, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
(33, 184, 123, 68, -41, -182, 171, 330, 115, -108, -160, 252, -31, 163, -79, 96, -36, -90, 264, -174, 52, -43, -272, -129, 73, 7, 134, 75, -65, -272, -181, -42, 126, 69, -159, 52, -263, 45, 10, 13, -103, 161, -61, 47, 54, -77, -13, 124, -209, 204, 148, -85, -85, -62, 192, 84, -47, -99, 175, -338, -107, -45, -415, -245, -228, 125, 187, 267, -9, 170, -172, 39, 99, -47, -136, -80, -58, -87, 96, 161, -133, -18, 199, -245, 6, -46, -9, -110, -70, 17, -91, 68, 111, 44, 8, 40, 11, -12, -9, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)

exp：

#sage
# 定义一个函数来从文件中读取变量
def load_variables(filename):
    with open(filename, 'r') as f:
        file_content = f.read()
    # 使用exec将文件内容执行，导入变量
    exec(file_content, globals())

# 调用函数加载变量b 和 c
load_variables('output')

#创建格
n = len(b)
print(n)
Ge = Matrix(ZZ, n + 1, n + 1)

for i in range(n):
    Ge[i, i] = 1       #对角线放1
    Ge[i, -1] = b[i]   #每行的最后一个元素

Ge[-1, -1] = -c        #最右下角的元素

res = Ge.LLL()

# print(len(res))

#筛选全是0或1的一行
for i in range(n + 1):
    M = res.row(i).list()   #提取矩阵第i行转换成列表
    flag = True
    for m in M:
        if m != 0 and m != 1:
            flag = False
            break
    if flag:
        print(i, M)   #成功找到全是0或1的

上面找到的结果 就是flag的二进制数据 拼起来即可

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

想要拼接 需要把列表内的东西转化成字符型 才能使用join 最后成功拿到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范围比较小 就几万种可能 也是可以爆破的
r = random.randint(2**14, 2**15)

#这个值在模下小于50  所以值更小 令式子为x  x可以爆破
assert ((p-r) * a + q) % b < 50

#下面为推导式
((p-r) * a + q) % b = x
#因为有模数 所以这是在一个有限域中 既然是有限域 就要去掉模符号
(p-r) * a + k * b = (x - q) 
[[1, a]
 [0, b]]
*
[[(p - r), k]]
=
[[(p-r), (x - q)]]

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

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

exp:

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

c = ...
a = ...
b = ...


#构造格子
Ge = Matrix(ZZ, [[1, a],
                 [0, b]])

p, q = Ge.LLL()[0]
#先变成绝对值
p, q = abs(p), abs(q)

#开始爆破
for r in tqdm(range(2 ** 14, 2 ** 15)):
    for h in range(50):
        pp = p + r
        qq = q + h
        phi = (pp - 1) * (qq - 1)
        if gcd(phi, 65537) != 1:
            continue
        m = power_mod(c, inverse_mod(65537, phi), pp * qq)
        if b"NSSCTF" in long_to_bytes(m):
            print(long_to_bytes(m))
            exit(0)

疑惑点

1. p和q的正负 和r与h的关系
2. 格子的构造 LLL之后结果的含义

P4 ：自己构造 本意需要调整一下格的值

task.py：

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

首先补充一个小知识点

r的位数是175 非常小 但是其在逆元下，p的位数非常大，所以逆元的结果其位数接近模数p的 1024位左右

$a=r^{-1} \times m + kp\\ m = ra + kp\\ (r ~~ k) \left( \begin{matrix} 1 & a\\ 0 & p\\ \end{matrix} \right)= \left( \begin{matrix} r & m\\ \end{matrix} \right)$

Hermite定理测试

import gmpy2
from Crypto.Util.number import *

b = 2 ** 0   #这是不断调整配平用的
p = getPrime(1024)  #已知
f = flag = getPrime(350)   
r = getPrime(175) 

a = inverse(r, p)
print(a.bit_length())  
print(3* 2**2)


print(f.bit_length())  

#行列式的值 大于等于下面的即可
temp = gmpy2.iroot(2 * b * p , 2)[0]  #bit = (248 + 512) / 2
print(temp.bit_length()) 

#最短向量的值
temp2 = gmpy2.iroot(f**2+(b*r)**2, 2)[0]  #主要在于f g没有太大影响
#此外一定要注意 在python中 ^是异或  **才是平方 
print(temp2.bit_length())  

if temp.bit_length() >= temp2.bit_length():
    print("true")
else:
    print("false")

满足的，所以证明构造这样一个格子就可以了 没有限制界

exp.sage：

#sage
from Crypto.Util.number import *
a = 。。。
p = 。。。

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

r, m = Ge.LLL()[0]
m = abs(m)
print(long_to_bytes(m))

P5 ：平衡格基（本质还是Hermite定理的应用）

task.py

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 = ...
p = ...
'''

构造格

$a = b \times m + c + kp\\=> \\ c = a - b \times m + kp \\ \left( \begin{matrix} 1 & m & k\\ \end{matrix} \right) \left( \begin{matrix} 1 & 0 & a\\ 0 & 1 & -b\\ 0 & 0 & p \end{matrix} \right)= \left( \begin{matrix} 1 & m & c \end{matrix} \right)\\ 这个时候可以发现结果基是不平衡的，其他位数都是300+ 但这里不是唯一的判断标注 \\真正想判断还是通过Hermite定理，不过使用时注意这是三维的格子了 \\最终解决思路是把最左上角的1进行调整$

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**190

#行列式的值 大于等于下面的即可
temp = gmpy2.iroot(n, 2)[0] * gmpy2.iroot(det, n)[0]  
print(temp.bit_length()) 

#最短向量的值
temp2 = gmpy2.iroot(f**2+(c)**2, 2)[0]  
#此外一定要注意 在python中 ^是异或  **才是平方 
print(temp2.bit_length())  

if temp.bit_length() >= temp2.bit_length():
    print("true")
else:
    print("false")

exp.sage:

from Crypto.Util.number import *
a = ...
b = ...
p = ...

Ge = Matrix(ZZ, [[2^190, 0, a],
                 [0, 1, -b],
                 [0, 0, p]])

t, m, c = Ge.LLL()[0]
print(m)
m = abs(m)
print(long_to_bytes(int(m)))

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 = ...
n0 = ...
c0 = ...
e1 = ...
n1 = ...
c1 = ...
e2 = ...
n2 = ...
c2 = ...
e3 = ...
n3 = ...
c3 = ...
'''

分析一下题目：

根本没给出什么其他条件，只有一个约束条件，多组公钥使用了一个相同的私钥

代码非常短，可能针对某个特定的问题

=>这种一般就确定了 要搜论文，用论文的深入研究的结果去解决问题

=>搜索方式：从题目中提取关键词 可以转化成英文

RSA、相同私钥、格基规约、格

=>锁定论文

Lattice Based Attack on Common Private Exponent RSA

https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=e84479b974927433e2fbc4d3e87c848e73537656

赛后细读论文

赛中直接看格子怎么构造的

P7 ：论文题（*）

没太懂怎么构造的 需要再读读论文

exp：

#sage
from Crypto.Util.number import *

n = 110697784133988071803253124431092603234028687101567047811203431433689306543322837414808117411806181193598553341878079973980865551938790090419082150555675782822484149943421418447579383449269148197087985041351210982545320569973241390962326458234562044133505940521052500278777242988196544039226173227204865907343
c = 3281096209929505523196793672137624804022934270452947405454462490250571524417033484978613243658208567511735641542935158434165363547355697159503378251318054879687577130170122911449101189974762808655638497967674004219512386442280269940950792767174561412932638740423542930763914255112354969122157915514816022159
e0 = 28562806554366667733480283991307446762365777397933141571728113235368201162305126722188842319240464207580134816039095093401651171977877327756351539588974913736802534970867173212883308325913939353140276201705478124488858328502643345172188729914731042179091733244225184522680724392375975935305371163502863968963
e1 = 28572469216883232254074869113744730984165641173439644880182528671699871929340616919028955398474678696802739685594548793470261306125219888911330937557582939811068530294470712859439149735950996866732508004061234613146407591546995439312326450834903885979660916965052092661398640105827442036234500556755520316031

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

Ge = M.LLL()
t = vector(ZZ, Ge[0])
x = t * M^(-1)

phi = int(x[1]/x[0] * e0)
d = inverse_mod(65537, phi)
m = power_mod(c, d, n)
print(long_to_bytes(m))

P8：格基规约

task.py:

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

分析构造过程：

exp:

from Crypto.Util.number import *

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

inv_a2 = inverse_mod(a[2], p)

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

re = L.LLL()[0]
s0s1 = isqrt(abs(re[1]))
s1s2 = abs(re[3]) >> 64  #对角矩阵的影响
s1 = gcd(s0s1, s1s2)
print(s1, s0s1, s1s2)
s2 = s1s2 // s1
s0 = s0s1 // s1
m = flag // s0 // s1 // s2
print(long_to_bytes(m))

---

格密码入门完结撒花 有点感觉了 但是还是得继续练

2023-08-23——2024-08-02