高端商城网站建设,广州企业网站排名,个人做搜索网站违法吗,网站挂马解决格密码相关 文章目录 格密码相关格密码基本概念#xff08;属于后量子密码#xff09;基础的格运算#xff08;行列式运算#xff09;SVP#xff08;shortest Vector Problem#xff09;最短向量问题CVP#xff08;Closet Vector Problem#xff09;最近向量问题 做题要…格密码相关 文章目录 格密码相关格密码基本概念属于后量子密码基础的格运算行列式运算SVPshortest Vector Problem最短向量问题CVPCloset Vector Problem最近向量问题 做题要点Key超重点 明白这个到底是在干什么Hermite定理 格相关的大类型NTRU密码easyLatticeez_ntruEasy_3L简单的NTRU(只有常数项)一般多项式NTRUntru变形 背包密码HNPNPUCTF2020-babyLCGWMCTF-2023-Crypto signin NSS工坊刷题P1 弱化版NTRUP2 背包密码p3 自己构造P4 自己构造 本意需要调整一下格的值P5 平衡格基本质还是Hermite定理的应用P6 论文题P7 论文题*P8格基规约 格密码基本概念属于后量子密码
后量子密码指的是对抗未来量子计算快速解决的问题
向量空间 格
格本身就是一个系数为整数的向量空间 一系列向量集合vectorv1 , v2 , v3 , vn 一系列整数a1 , a2 ,…, an 上面两个东西进行向量的线性组合就得到了格子Lattices即L {a1v1…anvn}
直观感受一个最简单的格 在上面这个图中每一个交点都是格上的一个格点其基向量是0,1和1,0
该格用数学符号表示为 L [ 0 1 1 0 ] L \begin{bmatrix} 01\\ 10\\ \end{bmatrix} L[0110] 根据不同的基向量我们可以得到不同的格点 比如选择11和1-1作为基向量因为系数要取整数所以1,0这个点就是这两个基向量张成的格中不存在的格点 格的维数即向量的个数上面这个就表示二维的格
然后根据整数系数a的不同 就可以形成很多个不同的L集合
假定v1 , v2 , … , vn 称为张成空间是格L的基 然后存在不同个集合属于L 即w1 , w2 ,… , wm
则有属于线性组合 到此格的问题转化为矩阵的运算 线性无关linearly independencev1 , v2 , … , vn线性无关当且仅当方程a1v1…anvn0的唯一解是a全部为0否则线性相关linearly dependent 正交基orthogonal basisv1 , v2 , … , vn 中任意不同的两个v点积的结果为0 规范正交orthonormal 上面的每一个v的**欧几里得范数(类似于模 长度)**为1 据此在上面的w的||w||2 所有系数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())
# -1B 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 ASVPshortest Vector Problem最短向量问题
我们根据开篇的内容可以看到一个格L这个集合中会存在无线多个向量集合v
所以最短向量问题 就是指在这一个格L中最短的非零向量 即寻找一个v满足欧几里得范数最小指该集合的每一个元素的平方和再开方范数就是指长度
此外格中的最短向量可能不止一个举个例子: 向量0,1和1,0张成的格 求解前置知识
基
在向量空间的每一个点都可以通过对基的线性组合变化得到叫做基向量
一个格可能会有很多个基 不唯一
正交基
基相互垂直就是正交基 格基规约
目的就是找到最接近正交基的基向量 random basis也是一组基可以构成这个格子中的所有点 但是不是正交基
通过LLL或BKZ算法 得到正交基或者是最接近正交基 此时思考我们找这个正交基目的是什么为什么要找这个正交基呢它有什么用吗 目的在于寻找最短向量v 也就是SVP问题
先找到正交基或者最接近正交基的基 进而证明我们的最短向量一定在这组基上
存在两种关系
假设v是这个基中的某个向量在其他向量上的投影长度为0两两垂直符合SVP假设v不是基中的向量此刻该向量一定可以通过在其他基向量方向的投影来得到一个更短的向量 垂直投影更短
CVPCloset 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(f20192020202120222023, p) * g % pprint(h , h)
print(p , p)h 2230300126583677861466927910427460605336142000604400796769019169330805327830058127399640469637301157563524664730082687590109425103649095203274991089542329
p 6950733137747588463708927295050453925761832477377823596882238234496472403054344156839969133381577140118982692621000380716326275220824006196311323447685281分析一下题目
目标求f
构造完这个式子之后对二维矩阵进行LLL算法的结果就是我们想求的值
那么为什么会这样呢
这个时候就要回顾到LLL算法的作用把1h和0p这组基变成正交化程度最大的一组基去求解最短向量所以只需要证明这个f‘g是最短向量那么我们上面的式子就全部讲的通了
Hermite定理
引入Hermite定理给出了最短向量的上界 参考格密码笔记 其中n表示维度也就是基向量的个数在本题中n 2
det(L) 行列式的值 1 * p p
故 ∣ ∣ v ∣ ∣ ≤ n p 2 p ||v|| \leq \sqrt {np} \sqrt {2p} ∣∣v∣∣≤np 2p 向量v f’ g
其长度为 l e n f ′ 2 g 2 len \sqrt {f^2g^2} lenf′2g2 其中 p 512bit g 128bit
一般flag长度43左右uuid 即f’约等于 335bit 但是很不幸 这个题目不是这样的
demo
b 2**128
print(b)
import gmpy2
from Crypto.Util.number import *flag bflag{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()) # 257f 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 bflag{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()) # 381f 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 gmpy2assert len(flag) 47f bytes_to_long(flag)
p getPrime(512)
g getPrime(128)
h gmpy2.invert(f, p) * g % pprint(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 bflag{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, v1m round( v1*v2 / v1.norm()^2 )if m 0:return (v1, v2)v2 v2 - m*v1h 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_size2)
shortest_vector L[0]
f, g shortest_vector
print(f, g)
print(libnum.n2s(int(abs(f))))
import gmpy2
#验证
print(QQ((f**2g**2)**0.5))
print(QQ((p/2)**0.5))flag
512 512
-50073894085033274448337202692453522746880698077702322983028272289946704698284083256500537353714697134260425361796 -923598439793643506521260484208891374490129477915686911192431263509527780701021177518396468225804284049504314851328
-50073894085033274448337202692453522746880698077702322983028272289946704698284083256500537353714697134260425361796 -923598439793643506521260484208891374490129477915686911192431263509527780701021177518396468225804284049504314851328
bSICTF{e3fea01c-18f3-4638-9544-9201393940a9}A\xf0\x89\x84
924954849091614614580872247749080872466147164448631556705831800681208387067055421806078719613226163736775252508672
75510324462935505386352201496661374657272071149690974092911803081859274899457Reference 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 libnumbits 2048
while True:q random_prime(2^bits, lbound2^(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 % qbreakr random_prime(2^(3*bits//4 - 1))
m libnum.s2n(flag)
assert m 2^(bits//4)
c (r * h m) % qprint(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 ( m o d q ) c r ∗ h m ( m o d q ) c r ∗ f − 1 ∗ g m ( m o d q ) f c r g f m ( m o d q ) 对式子模 g 得 m ( f c ( m o d q ) ) ∗ f − 1 ( m o d g ) 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) hf−1∗g (mod q)cr∗hm ( mod q)cr∗f−1∗gm (mod q)fcrgfm (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:]))bflag{7c95453a-e577-40d8-9ad0-993655b83b69}
Easy_3L
题目源代码
from gmpy2 import *
from Crypto.Util.number import *
from secret import flagm bytes_to_long(flag)def get_key():p getPrime(1400)f getRandomNBitInteger(1024)while True:q getPrime(512)if gcd(f, q) ! 1:continueelse:breakh (invert(f, p) * q) % preturn p, hdef encrypt1(m):a getPrime(250)b getRandomNBitInteger(240)n getPrime(512)seed ms [0] * 6s[0] seedfor i in range(1, 6):s[i] (s[i - 1] * a b) % nreturn sdef encrypt2(msg, p, h):s getRandomNBitInteger(512)c (s * h msg) % preturn cs 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
已知chp 并且这三项位数相同 是1400位 比较大
然后s未知是512位
需要构建格密码求解m
将已知的内容作为构建格子M的内容 其系数提取到该格子的系数进行相乘
c - s * h k * p m
构造格子 M ( 1 0 − h 0 2 512 c 0 0 p ) M\begin{pmatrix} 10-h\\ 02^{512}c\\ 00p \end{pmatrix}\\\\ M 100025120−hcp 其系数 ( s 1 k ) \begin{pmatrix} s1k \end{pmatrix}\\\\ (s1k) 两矩阵相乘结果 ( s 2 512 m ) \begin{pmatrix} s2^{512}m \end{pmatrix}\\\\ (s2512m) 我们构造盒子的标准在于其生成的结果要接近且较小起初使用2行2列的格式构建格子我们发现c会在结果中出现因为c的长度过大所以无法生成合适的规约数
代码实现
#sage
from Crypto.Util.number import *
from gmpy2 import *p 25886434964719448194352673440525701654705794467884891063997131230558866479588298264578120588832128279435501897537203249743883076992668855905005985050222145380285378634993563571078034923112985724204131887907198503097115380966366598622251191576354831935118147880783949022370177789175320661630501595157946150891275992785113199863734714343650596491139321990230671901990010723398037081693145723605154355325074739107535905777351
h 2332673914418001018316159191702497430320194762477685969994411366563846498561222483921873160125818295447435796015251682805613716554577537183122368080760105458908517619529332931042168173262127728892648742025494771751133664547888267249802368767396121189473647263861691578834674578112521646941677994097088669110583465311980605508259404858000937372665500663077299603396786862387710064061811000146453852819607311367850587534711
c 20329058681057003355767546524327270876901063126285410163862577312957425318547938475645814390088863577141554443432653658287774537679738768993301095388221262144278253212238975358868925761055407920504398004143126310247822585095611305912801250788531962681592054588938446210412897150782558115114462054815460318533279921722893020563472010279486838372516063331845966834180751724227249589463408168677246991839581459878242111459287M 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(b0): 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[i1]*t[i-1]-t[i]*t[i]), (t[i2]*t[i]-t[i1]*t[i1]))) MMI lambda A, n,s1,t0,N0: (n 2 and t%N or MMI(n, A%n, t, s-A//n*t, N or n),-1)[n1] #逆元计算
for n in all_n:nabs(n)if n1:continuea(s[2]-s[1])*MMI((s[1]-s[0]),n)%naniMMI(a,n)b(s[1]-a*s[0])%nseed (ani*(s[0]-b))%nplaintextseedprint(long_to_bytes(plaintext))#b\x00
#bDASCTF{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],nrows2)
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(hxxhx)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 prikeya 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) * pubkeyhp_list list(hp)for i in range(n):A[i, i] qfor i in range(n, 2 * n):for j in range(n):A[i, j] hp_list[(j - i) % n]A[i, i] 1AL 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:passm crack(pubkey, c)m m.list()
for i in range(len(m)):m[i] 1m[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的格子 默认初始为0for 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 flag3qBits 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
考点:LCG随机数生成器 AES加密 HNP
题目
from Crypto.Util.number import *
from Crypto.Cipher import AES
from secret import flagclass 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 * inverseam %mdef next(self):self._state (self._key[a] * self._state self._key[b]) % self._key[m]return self._statedef export_key(self):return self._keydef gen_lcg():rand_iter LCG(128)key rand_iter.export_key()f open(key, w)f.write(str(key))return rand_iterdef 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_iterdef encrypt(rand_iter):f open(ct, wb)key rand_iter.next() 64key (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随机数的生成公式si1 a * si b (mod m)
并且已知每一个随机数泄露的高64bits的数据
所以将s分为高位h和低位部分l
hi1 li1) a * (hi li) b (mod m)
li1 a * li a * hi b - hi1 (mod m)
其中li1 和 li 未知 其他均已知
每次相乘保证li存在则需要设置相应的Ai和Bi
构造为 因为这个数是128bits的 然后高64位已知 所以低位l最大是64bits 右下角K是轮密钥的上界 所以构造格子 使得存在一个向量与M相乘 得到的结果向量内各元素大小接近 这样构建了格子之后 对格子使用LLL()算法 取出第0行倒数第二列的数值 成功获得第一个低位的数值
然后和高位拼接 恢复原始s1 从而获得seed
代码如下
#sage
b153582801876235638173762045261195852087
a107763262682494809191803026213015101802
m226649634126248141841388712969771891297h [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[i1]
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[i1]) % 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] mM[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 * inverseam %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 flagclass LCG:def __init__(self, bit_length):#反向解题 就要把未知量换为已知 b 153582801876235638173762045261195852087a 107763262682494809191803026213015101802 m 226649634126248141841388712969771891297seed 73991202721494681711496408225724067994self._key {a:a, b:b, m:m}self._state seeddef next(self):self._state (self._key[a] * self._state self._key[b]) % self._key[m]return self._statedef export_key(self):return self._keydef gen_lcg():rand_iter LCG(128)key rand_iter.export_key()# f open(key, w)# f.write(str(key))return rand_iterdef 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() 64key (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()#bnpuctf{7ruc4t3d-L(G-4nd-LLL-4r3-1nt3r3st1ng}\x04\x04\x04\x04第二个栗子:
WMCTF-2023-Crypto signin
考点: p高位泄露
from Crypto.Util.number import *
from random import randrange
from secret import flagdef 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 Ppq_bit 512
offset 16P,Q [gen_prime(pq_bit) for i in range(2)]
N P * Q
gift int(bin(P ^ (Q offset))[2offset:],2)
pr(N)
pr(gift)inpP int(input())
if inpP ! P:pr(byou 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 115073356145766093260644381479331808320549133985413353306940738670775007719301812510687311522173487690937202937075087659433551944224376340973897790917def 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 qbar6gifts gift^(qbar(512-16-qbar.bit_length()))pbar gifts (512-16-qbar.bit_length())# print(pbar,pbar.bit_length())except:breakfor i in range(64):# print(i)P (pbar 6) iif 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] pM[-2,i] b[i] * inv #AiM[-1,i] -r[i] * inv #BiM[-2,-2] 2 ** 496 / p #K/p
M[-1,-1] 2 ** 496 #KL 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 % pm b******
m bytes_to_long(m)c (r*h m) % pprint(fp {p})
print(fh {h})
print(fc {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(s1, 4**(ni)))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(fb {b}, filef)print(fc {c}, filef)根据解密格
跑完后 可以发现对格Ge进行LLL之后 这个有无数组值 但是我们需要的是全部为0或者1的一组
特别需要注意 因为我们在构造格的时候是n1 多加了一行 所以这一组值选出来之后 要去掉最后的一个数
在筛选的时候注意提取每一行的元素 有个地方需要注意一下就是必须转换成列表才能对当前行的每一个元素操作因为其本身是一个元组没法提取单个元素
例如
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 #对角线放1Ge[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 Truefor m in M:if m ! 0 and m ! 1:flag Falsebreakif 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 randomflag 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(fc {c})
print(fa {a})
print(fb {b})exp:
from Crypto.Util.number import *
from tqdm import tqdmc ...
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 rqq q hphi (pp - 1) * (qq - 1)if gcd(phi, 65537) ! 1:continuem power_mod(c, inverse_mod(65537, phi), pp * qq)if bNSSCTF in long_to_bytes(m):print(long_to_bytes(m))exit(0)疑惑点 p和q的正负 和r与h的关系格子的构造 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) % pprint(fa {a})
print(fp {p})a ...
p ...首先补充一个小知识点 r的位数是175 非常小 但是其在逆元下p的位数非常大所以逆元的结果其位数接近模数p的 1024位左右 a r − 1 × m k p m r a k p ( r k ) ( 1 a 0 p ) ( r m ) ar^{-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) ar−1×mkpmrakp(r k)(10ap)(rm)
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) % pprint(fa {a})
print(fb {b})
print(fp {p})
a ...
b ...
p ...构造格 a b × m c k p c a − b × m k p ( 1 m k ) ( 1 0 a 0 1 − b 0 0 p ) ( 1 m c ) 这个时候可以发现结果基是不平衡的其他位数都是 300 但这里不是唯一的判断标注 真正想判断还是通过 H e r m i t e 定理不过使用时注意这是三维的格子了 最终解决思路是把最左上角的 1 进行调整 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进行调整 ab×mckpca−b×mkp(1mk) 100010a−bp (1mc)这个时候可以发现结果基是不平衡的其他位数都是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 * qe inverse(d, (p-1)*(q-1))c pow(flag, e, n)print(fe{i} , e)print(fn{i} , n)print(fc{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?repidrep1typepdfdoie84479b974927433e2fbc4d3e87c848e73537656 赛后细读论文
赛中直接看格子怎么构造的 P7 论文题*
没太懂怎么构造的 需要再读读论文
exp
#sage
from Crypto.Util.number import *n 110697784133988071803253124431092603234028687101567047811203431433689306543322837414808117411806181193598553341878079973980865551938790090419082150555675782822484149943421418447579383449269148197087985041351210982545320569973241390962326458234562044133505940521052500278777242988196544039226173227204865907343
c 3281096209929505523196793672137624804022934270452947405454462490250571524417033484978613243658208567511735641542935158434165363547355697159503378251318054879687577130170122911449101189974762808655638497967674004219512386442280269940950792767174561412932638740423542930763914255112354969122157915514816022159
e0 28562806554366667733480283991307446762365777397933141571728113235368201162305126722188842319240464207580134816039095093401651171977877327756351539588974913736802534970867173212883308325913939353140276201705478124488858328502643345172188729914731042179091733244225184522680724392375975935305371163502863968963
e1 28572469216883232254074869113744730984165641173439644880182528671699871929340616919028955398474678696802739685594548793470261306125219888911330937557582939811068530294470712859439149735950996866732508004061234613146407591546995439312326450834903885979660916965052092661398640105827442036234500556755520316031a 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]]) * DGe 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]) % pflag m*s[0]*s[1]*s[2]
print(fc {c})
print(fflag {flag})
print(fa {a})
print(fp {p})
分析构造过程 exp:
from Crypto.Util.number import *c 740925064346371394698186587854547113606276228956443989781507592148712696471120454242180757282913190509143771235457885619359315384722931529795071829165028
flag 68803130911709451943985629442913968356735244797651554293510331427148284907075221530061581131130283569506280604032687824733336171953927
a [8205051800134728054685810600921116779466017139080528864745521629232854690213051609775306424843961090482436503418278207286549634492623172279113808752825877, 7656695314164580223033364292542508972053206838456547579023164583502640699225283686572923544677077467571265812610524520719197913305928971777756847148151453, 12016313094941119621096276870216129960285946825332008187797823075795491053640261786033376211694851951499688886358239835607622191418940486434225440651886891]
p 9725369974716521164256395525866212215114818770667579116304398350357785690930260317036889742178436308598088096925530431498664796728861093872628194022265573inv_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]]) * Dre 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
