[2024-12 CISCN 长城杯] Crypto

fffffhash

【也可以看这题，一样的：https://github.com/DownUnderCTF/Challenges_2023_Public/blob/main/crypto/fnv/solve/solution_joseph_LLL.sage】

题目描述：

import os
from Crypto.Util.number import *
def giaogiao(hex_string):base_num = 0x6c62272e07bb014262b821756295c58d # 129x = 0x0000000001000000000000000000013b # 91bit 128 - 91 = 37MOD = 2**128for i in hex_string:base_num = (base_num * x) & (MOD - 1) base_num ^= ireturn base_numgiao=201431453607244229943761366749810895688print("1geiwoligiaogiao")
hex_string = int(input(),16)
s = long_to_bytes(hex_string)if giaogiao(s) == giao:print(os.getenv('FLAG'))
else:print("error")

题目分析：

异或的数很小，范围在0-255之间，故我们可以看成加了一个小数 $b_i$

得到以下关系式：
$$\begin{gathered} h_1\equiv x{h}_0+b_0(\mathrm{mod}M) \\ {h}_2\equiv x{h}_1+b_1(\mathrm{mod}M) \\ {h}_3\equiv x{h}_2+b_2(\mathrm{mod}M) \\ ⋮ \\ {h}_{16}\equiv x{h}_{15}+b_{15}(\mathrm{mod}M) \\ \Rightarrow c=h_{16}\equiv x^{16}{h}_0+x^{15}{b}_0+x^{14}{b}_1+...+x{b}_{14}+b_{15} \end{gathered}$$

故构造如下格：
$$M=\left(\begin{array}{cccccccc}1& & & & & & & x^0\\ & 1& & & & & & x^1\\ & & & \ddots & & & & ⋮\\ & & & & 1& & & x^{15}\\ & & & & & 1& & x^{16}{h}_0\\ & & & & & & 1& -c\\ & & & & & & & mod\end{array}\right)$$
$(b_{15},b_{14},...,b_1,b_0,1,1,k)\ast M=(b_{15},b_{14},...,b_1,b_0,1,1,0)$

为了平衡向量，我们乘上一些数，得到如下格：
$$M^{\prime }=\left(\begin{array}{cccccccc}{2}^4& & & & & & & x^{0}K\\ & 2^4& & & & & & x^{1}K\\ & & & \ddots & & & & ⋮\\ & & & & 2^4& & & x^{15}K\\ & & & & & 2^8& & x^{16}{h}_{0}K\\ & & & & & & 2^8& -cK\\ & & & & & & & mod\ast K\end{array}\right)$$
(为什么要乘这些数，在这道题中中间那些数其实不乘也可以，因为得到的每个b都非常小，不超过50，如果是这种本来就很小的数据不乘也能得到结果，因为结果本来就相差不大，但当我试着用自己的测试数据时，得到的b就不是这样了，它会分布在0-255之间，此时就得乘了【测试时对每个b乘个4刚刚好】，因为分布不平均很可能格不出我们想要的结果，总之就是多尝试)

exp1:

h0 = 0x6c62272e07bb014262b821756295c58d
x = 0x0000000001000000000000000000013b
c = 326108812442769584751438450141653646793
mod = 2 ** 128
n = 16
M = matrix(ZZ, n + 3, n + 3)for i in range(n):M[i, i] = 1M[i, -1] = x ** i
M[-3, -1] = x ** n * h0
M[-2, -1] = -c
M[-2, -2] = 1
M[-3, -3] = 1
M[-1, -1] = modQ = Matrix.diagonal([4] * n + [2 ** 8] * 2 + [2^20])
M *= Q
M = M.LLL()
M /= Q
print(M)
for r in M:if r[-1] == 0 and abs(r[-2]) == 1:r *= (r[-3] // 1)good = r[:-3]print(good)res = []t = x * h0h1 = (x * h0 + good[-1]) % modfor i in range(n):for j in range(256):h1_ = (t ^^ j) % modif h1 == h1_:print('good', i, j)res.append(j)if i < n - 1:h1 = (x * h1 + good[n - i - 2]) % modt = (t ^^ j) * x % modbreakelse:print('bad', i)print(bytes(res).hex())

还可以构造如下格：
$$(b_{15},b_{14},...,b_1,b_0,1,k)\ast \left(\begin{array}{cccccc}1& & & & & x^0\\ & 1& & & & x^1\\ & & & \ddots & & ⋮\\ & & & & 1& x^{15}\\ & & & & & x^{16}{h}_0-c\\ & & & & & mod\end{array}\right)=(b_{15},b_{14},...,b_1,b_0,1,0)$$

都是大同小异的，关键点在于后续的乘数

exp2:

h0 = 0x6c62272e07bb014262b821756295c58d
x = 0x0000000001000000000000000000013b
c = 201431453607244229943761366749810895688
mod = 2 ** 128
n = 16
tmp = 1
M = matrix(ZZ, n + 2, n + 2)for i in range(n):M[i, i] = 1M[i, -1] = x ** i
M[-2, -1] = -c + x ** 16 * h0
M[-2, -2] = tmp
M[-1, -1] = mod
Q = Matrix.diagonal([4] * n + [2^8] + [2^20])
M *= Q
M = M.LLL()
M /= Qfor r in M:if r[-1] == 0 and abs(r[-2]) == tmp:r *= (r[-2] // 1)good = r[:-2]res = []t = x * h0h1 = (x * h0 + good[-1]) % modfor i in range(n):for j in range(256):h1_ = (t ^^ j) % modif h1 == h1_:print('good', i, j)res.append(j)if i < n - 1:h1 = (x * h1 + good[n - i - 2]) % modt = (t ^^ j) * x % modbreakelse:print('bad', i)print(bytes(res).hex())

浅记一下：开始以为我构造的有问题，总是得不到结果，测试也总是得不到结果，后面通过比对发现，好吧，赛后说这些有点风凉，总之就是乘数没考虑到位，没想到b会这么小，在b这么小的基础上我还又添了个256进去、、可以预想到结果

还能发现一点，测试结果显示我们可以得到不止一个结果，只要你构造的到位

比如 如果我的 c = 326108812442769584751438450141653646793 我在exp1下可以得到一个解，但我在exp2下可以得到两个解

虽然这是道原题，但不妨碍我学习知识

贴一下原题官方wp：

TARGET = 201431453607244229943761366749810895688
h0 = 0x6c62272e07bb014262b821756295c58d
p = 0x0000000001000000000000000000013b
MOD = 2^128n = 16
M = Matrix.column([p^(n - i - 1) for i in range(n)] + [-(TARGET - h0*p^n), MOD])
M = M.augment(identity_matrix(n+1).stack(vector([0] * (n+1))))
Q = Matrix.diagonal([2^128] + [2^4] * n + [2^8])
M *= Q
M = M.BKZ()
M /= Q
for r in M:if r[0] == 0 and abs(r[-1]) == 1:r *= r[-1]good = r[1:-1]print(good)break
inp = []
y = int(h0*p)
t = (h0*p^n + good[0] * p^(n-1)) % MOD
for i in range(n):for x in range(256):y_ = (int(y) ^^ int(x)) * p^(n-i-1) % MODif y_ == t:print('good', i, x)inp.append(x)if i < n-1:t = (t + good[i+1] * p^(n-i-2)) % MODy = ((int(y) ^^ int(x)) * p) % MODbreakelse:print('bad', i)
print(bytes(inp).hex())

【n为什么会是16，猜的，本来最大也就128bit，一个字节8bit，128/8 = 16】

rasnd

题目描述：

from Crypto.Util.number import getPrime, bytes_to_long
from random import randint
import osFLAG = os.getenv("FLAG").encode()
flag1 = FLAG[:15]
flag2 = FLAG[15:]def crypto1():p = getPrime(1024)q = getPrime(1024)n = p * qe = 0x10001x1=randint(0,2**11)y1=randint(0,2**114)x2=randint(0,2**11)y2=randint(0,2**514)hint1=x1*p+y1*q-0x114hint2=x2*p+y2*q-0x514c = pow(bytes_to_long(flag1), e, n)print(n)print(c)print(hint1)print(hint2)def crypto2():p = getPrime(1024)q = getPrime(1024)n = p * qe = 0x10001hint = pow(514*p - 114*q, n - p - q, n)c = pow(bytes_to_long(flag2),e,n)print(n)print(c)print(hint)
print("==================================================================")
crypto1()
print("==================================================================")
crypto2()
print("==================================================================")

题目分析：

part1:
$$\begin{gathered} h_1+0x114=x_1\ast p+y_1\ast q \\ {h}_2+0x514=x_2\ast p+y_2\ast q \\ {x}_2(h_1+0x114)=x_1{x}_{2}p+y_1{x}_{2}q \\ {x}_1(h_2+0x514)=x_1{x}_{2}p+y_2{x}_{1}q \\ {x}_2(h_1+0x114)-x_1(h_2+0x514)=kq \\ 故q=gcd(x_2(h_1+0x114)-x_1(h_2+0x514),n) \end{gathered}$$
x1，x2比较小，直接爆破就行，之后常规解rsa即可得到flag1

exp1:

from gmpy2 import *
from Crypto.Util.number import *
n1 = 19550398679199171355018004284705345831602208290042474784612338613062970714776943637479685253524898279192236420618734606823953471064311899184880185274097724247890933607672936937976343282675360107144603681774183486899721764670769749865558525011366489113284202255527734770802793907818326482859113597455288516793989957872140882998347523728374283661160094118393600351475972296995895001581374445715909585151679666815401668974812845051155888384490289076700622884312488260572160842083737732450262979494435183750794585238380287475064853705421950731757738145499621262538008778424971549965311354697572409460128526074018372193703
c1 = 1445768053401138879008727685929758012338830581230901189545394202084081860319570496698848003040811183721816232548447769540712305984113674327994225867027531604978069945308962604863467636824037250779678348485964200729721622573019556452700851108544255265861204544762701000468984258353543049699918873082616589742476391703489977859459524636676388263683035891758778197610418113073060935818103216852834883367063681926905198813742108275678256663245071388757512869312500517126431575985768501710066783878693365055732720465059062734800367334589377880253333150324084329900127822153371523754289462126320011226374539852180182995618
hint1 = 813542503091295081287493164872446878934392928426922865104231880307385374368952287193304611656415176271928595261342566657834820294181861708034270808501289644790406787178703045894209727125997591605767623931428607155192577220591330199081405402681802499094605199141195480576336523693310632536732545700711113342193794084094254862019506352095825719
hint2 = 7528651983722210863630908934171235549296592448562886990393901839909961624136868186639810404871638077336656902574878110892877215871970964292391724736885504775126217047497032708586574952094609611201526374630433515016038326941777629522443981331709536162946088429676115144611715762104787235604603012421054812847475750306135061782352511131206527134841676516186504934345177843010645843472996830390497472673832658344900666219492454287243446890052938074847052402814989289e = 0x10001
for x1 in range(2 ** 11):for x2 in range(2 ** 11):q = gcd(x2 * (hint1 + 0x114) - x1 * (hint2 + 0x514), n1)if q != 1:d = invert(e, (q - 1))print(long_to_bytes(pow(c1, d, q)))

part2:
$$\begin{gathered} h\equiv (514p-114q{)}^{phi-1}\equiv (514p-114q{)}^{-1}(\mathrm{mod}n) \\ \Rightarrow h^{-1}\equiv 514p-114q(\mathrm{mod}n) \\ 又n=pq，故解方程即可得到p,q，接着常规解rsa即可得到flag \end{gathered}$$
exp2:

from gmpy2 import *
from Crypto.Util.number import *n2 = 24761052749271042743577796871496924502211856051465714421290877074553058681051739300766573552587688944000632486351629739711081206777791468293960146319148158324072168710012386854713028960775892888737587411543903250529440399534770996094946780175972522437525186912543166249914957632483127888465810558343315610626932795779194844992423526668521164087703353951996902583283385685281388060576356823350815676405778642964340308385108905362678081540056697010276475561590905873418396516100304245593564177655719459280258840621329699344777887925747160638394834090463096259431090105073414923478648922712812422016506817550912872953277
c2 = 4213283632686597288766767081111747695257194539323646817510270884332313510205686339837278995517876985442415563559682791729617083768947686133216927935379616506657091463290325015120374090452937517998990966347196013368213296228758906976996868508154903793691096322394694124849051517232001811866489457985124391446126369813285058032618104546938370778717678091629123937170499331338381675980334763797238596820938461506847766493262020772620214681226198476969502534851764637598652166973446277853755416778280428985911857667227401628399352356240661408717497789727712284957617789421742533790942676133544566337019348064268742413310
hint = 24278952281899490734988062266672557402757265895678621624691473985013830825982229890244539934056924698080867378470969144929434909846949318877936288855892912161935463384532624926267280305178500699295089548595574683675836191794069155851775410127729089204477751160361394366439321454470958284853439295859397112434975116192293896614156956417149656779574627467180878958079347110965915586404621561069989346566300527516723781873907830932044078093574842200056398777724780115063508040193535778072456581436416361741273661495963056953601731830832132295408355132914608105189316701375343369359239407359984122685133572958845031399848
e = 65537# var('p q')
# eq1 = 514 * p - 114 * q - inverse_mod(hint, n2)
# eq2 = p * q - n2
# print(solve([eq1, eq2], [p, q]))
p = 114560163390146560402450572371651069608711450458690030742233116800229060305345605587810377896798770562981698051912578139480556164563067579373952571416807910700342277714006778181627545356521815916688694141833290921829184225462406906087753112189296447698155330004097331801979276991274798773126320742455878456759
q = 124961832724068977700959045751478671095539161271562049894983250724226117428532427282592969816289237477981797134522465671680378548983024325311171713534444394004784849786554756970447254266537283741040754903457084937303723618062716949648884598378899153908179560836882476294225339684353137479928471047311121283691
phi = (p - 1) * (q - 1)
print(long_to_bytes(int(pow(c2, int(inverse_mod(e, phi)), n2))))

其他题的话没做了
end