2025LilCTF -- Crypto -- WriteUp

沦嘻亟 · 昨天 00:49

2025LilCTF -- Crypto -- WriteUp

[WARM UP] 对称！Just Decrypt

task

"""Just Decrypt - A simple LilCTF warmup challenge."""
from random import Random
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
FLAG = b""
key = Random(2025).randbytes(16)
print(AES.new(key, AES.MODE_CBC, iv=FLAG[9:25]).encrypt(pad(FLAG, 16)).hex())
# ae39cfab1ba8d38fc3761216c393caf16e3c3f13fe57e2dedd52f1b13072fa93df405c7e731a193cabe5fd88ee3241f79aded62d139faba8c767a3b8efc5a855

复制代码

analysis

AES的key不变，我们只需要根据AES - CBC前后存在异或的性质进行求解即可。
- 已知flag前七个字节为LILCTF{ --> iv的前七个字节为flag[9:16] --> flag[9:16] = decrypt(ciphertext[:7]) ^ b'LILCTF{'
- 因此flag的第一段我们只缺少flag[7]与flag[8]两个可视化字符，我们进行一个爆破。
- iv = flag[:16] ^ decrypt(ciphertext[:16])，最后根据iv == flag[9:25]判定是否爆破成功。

exp

from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from pwn import xor
ciphertext = bytes.fromhex("ae39cfab1ba8d38fc3761216c393caf16e3c3f13fe57e2dedd52f1b13072fa93df405c7e731a193cabe5fd88ee3241f79aded62d139faba8c767a3b8efc5a855")
key = b'\xbc\xd8\xc8\x8e\x81\xf8+\x15\x82\x17V\xa5\xa3\x87h\xd6'
# print(len(ciphertext)) 64
aes1 = AES.new(key, AES.MODE_ECB)
# print(my_aes.decrypt(ciphertext))
temp = aes1.decrypt(ciphertext[:16])
for i in range(32, 127):
for j in range(32, 127):
mask = b'LILCTF{' + bytes([i]) + bytes([j])
message0 = mask + xor(temp[:7], b'LILCTF{')
iv = xor(temp, message0)
aes2 = AES.new(key, AES.MODE_CBC, iv)
flag = unpad(aes2.decrypt(ciphertext), 16)
if flag[9:25] == iv:
print(flag)
# b'LILCTF{b1a6labl4@#$%_H4v3_fUn_W1tH_y0Ur_sYmM3try_3NcRyPt10n!}'

复制代码

ez_math

task

from sage.all import *
from Crypto.Util.number import *
flag = b'LILCTF{test_flag}'[7:-1]
lambda1 = bytes_to_long(flag[:len(flag)//2])
lambda2 = bytes_to_long(flag[len(flag)//2:])
p = getPrime(512)
def mul(vector, c):
return [vector[0]*c, vector[1]*c]
v1 = [getPrime(128), getPrime(128)] # v1 = [a, b]
v2 = [getPrime(128), getPrime(128)] # v2 = [c, d]
A = matrix(GF(p), [v1, v2])
B = matrix(GF(p), [mul(v1, lambda1), mul(v2, lambda2)])
"""
A = [
[a, b],
[c, d]
]
B = [
[a * flag1, b * flag1],
[c * flag2, d * flag2]
]
[flag1, 0] [a, b]
B = *
[0, flag2] [c, d]
B = diag(flag1, flag2) * A --> C = A ^ -1 * B = A ^ -1 * diag(flag1, flag2) * A
diag(flag1, flag2) ~ C --> diag(flag1, flag2)的迹和行列式与C对应相等
"""
C = A.inverse() * B
print(f'p = {p}')
print(f'C = {str(C).replace(" ", ",").replace("\n", ",").replace("[,", "[")}')
# p = 9620154777088870694266521670168986508003314866222315790126552504304846236696183733266828489404860276326158191906907396234236947215466295418632056113826161
# C = [7062910478232783138765983170626687981202937184255408287607971780139482616525215270216675887321965798418829038273232695370210503086491228434856538620699645,7096268905956462643320137667780334763649635657732499491108171622164208662688609295607684620630301031789132814209784948222802930089030287484015336757787801],[7341430053606172329602911405905754386729224669425325419124733847060694853483825396200841609125574923525535532184467150746385826443392039086079562905059808,2557244298856087555500538499542298526800377681966907502518580724165363620170968463050152602083665991230143669519866828587671059318627542153367879596260872]

复制代码

analysis
一道简单的线性代数的问题，相关的分析在task的注释中。主要应用的就是相似矩阵的特性。
exp

from Crypto.Util.number import *
from gmpy2 import iroot
p = 9620154777088870694266521670168986508003314866222315790126552504304846236696183733266828489404860276326158191906907396234236947215466295418632056113826161
C = [
[7062910478232783138765983170626687981202937184255408287607971780139482616525215270216675887321965798418829038273232695370210503086491228434856538620699645,7096268905956462643320137667780334763649635657732499491108171622164208662688609295607684620630301031789132814209784948222802930089030287484015336757787801],
[7341430053606172329602911405905754386729224669425325419124733847060694853483825396200841609125574923525535532184467150746385826443392039086079562905059808,2557244298856087555500538499542298526800377681966907502518580724165363620170968463050152602083665991230143669519866828587671059318627542153367879596260872]
]
a, b, c, d = C[0][0], C[0][1], C[1][0], C[1][1]
# tr = flag1 + flag2
tr = (a + d) % p
# det = flag1 * flag2
det = (a * d - b * c) % p
temp = iroot(tr ** 2 - 4 * det, 2)[0]
flag1 = (tr + temp) // 2
flag2 = tr - flag1
flag = b'LILCTF{' + long_to_bytes(flag1) + long_to_bytes(flag2) + b'}'
print(flag)
# b'LILCTF{It_w4s_the_be5t_of_times_1t_wa5_the_w0rst_of_t1me5}'

复制代码

mid_math

task

from sage.all import *
from Crypto.Util.number import *
from tqdm import tqdm
from random import randint
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
flag = b'LILCTF{test_flag}'
p = getPrime(64)
P = GF(p)
key = randint(2 ** 62, p)
print(f"key = {key}")
def mul(vector, c):
return [vector[0] * c, vector[1] * c, vector[2] * c, vector[3] * c, vector[4] * c]
v1 = [getPrime(64), getPrime(64), getPrime(64), getPrime(64), getPrime(64)]
v2 = [getPrime(64), getPrime(64), getPrime(64), getPrime(64), getPrime(64)]
v3 = [getPrime(64), getPrime(64), getPrime(64), getPrime(64), getPrime(64)]
v4 = [getPrime(64), getPrime(64), getPrime(64), getPrime(64), getPrime(64)]
v5 = [getPrime(64), getPrime(64), getPrime(64), getPrime(64), getPrime(64)]
a, b, c, d, e = getPrime(64), getPrime(64), getPrime(64), getPrime(64), 0
A = matrix(P, [v1, v2, v3, v4, v5])
B = matrix(P, [mul(v1, a), mul(v2, b), mul(v3, c), mul(v4, d), mul(v5, e)])
C = A.inverse() * B
D = C ** key
"""
B = [
[a * v1[0], a * v1[1], a * v1[2], a * v1[3], a * v1[4]],
[b * v2[0], b * v2[1], b * v2[2], b * v2[3], b * v2[4]],
[c * v3[0], c * v3[1], c * v3[2], c * v3[3], c * v3[4]],
[d * v4[0], d * v4[1], d * v4[2], d * v4[3], d * v4[4]],
[0, 0, 0, 0, 0]
]
[a, 0, 0, 0, 0]
[0, b, 0, 0, 0]
B = [0, 0, c, 0, 0] * A
[0, 0, 0. d, 0]
[0, 0, 0, 0, 0]
C = A ^ -1 * B = A ^ -1 * diag(a, b, c, d, 0) * A --> C ~ diag(a, b, c, d, 0) -->
D = C ** key = A ^ -1 * diag(a, b, c, d, 0) ** key * A --> D ~ diag(a, b, c, d, 0) ** key --> D ~ diag(a ** key % p, b ** key % p, c ** key % p, d ** key % p, 0)
D.eigenvalue = C.eigenvalue ** key
"""
key = pad(long_to_bytes(key), 16)
aes = AES.new(key, AES.MODE_ECB)
msg = aes.encrypt(pad(flag, 64))
print(f"p = {p}")
print(f'C = {[i for i in C]}'.replace('(', '[').replace(')', ']'))
print(f'D = {[i for i in D]}'.replace('(', '[').replace(')', ']'))
print(f"msg = {msg}")
# p = 14668080038311483271
# C = [[11315841881544731102, 2283439871732792326, 6800685968958241983, 6426158106328779372, 9681186993951502212], [4729583429936371197, 9934441408437898498, 12454838789798706101, 1137624354220162514, 8961427323294527914], [12212265161975165517, 8264257544674837561, 10531819068765930248, 4088354401871232602, 14653951889442072670], [6045978019175462652, 11202714988272207073, 13562937263226951112, 6648446245634067896, 13902820281072641413], [1046075193917103481, 3617988773170202613, 3590111338369894405, 2646640112163975771, 5966864698750134707]]
# D = [[1785348659555163021, 3612773974290420260, 8587341808081935796, 4393730037042586815, 10490463205723658044], [10457678631610076741, 1645527195687648140, 13013316081830726847, 12925223531522879912, 5478687620744215372], [9878636900393157276, 13274969755872629366, 3231582918568068174, 7045188483430589163, 5126509884591016427], [4914941908205759200, 7480989013464904670, 5860406622199128154, 8016615177615097542, 13266674393818320551], [3005316032591310201, 6624508725257625760, 7972954954270186094, 5331046349070112118, 6127026494304272395]]
# msg = b"\xcc]B:\xe8\xbc\x91\xe2\x93\xaa\x88\x17\xc4\xe5\x97\x87@\x0fd\xb5p\x81\x1e\x98,Z\xe1n`\xaf\xe0%:\xb7\x8aD\x03\xd2Wu5\xcd\xc4#m'\xa7\xa4\x80\x0b\xf7\xda8\x1b\x82k#\xc1gP\xbd/\xb5j"

复制代码

analysis
C和D的特征值之间的离散对数关系可以求解key进行求解flag，证明在解题分析的时候也写在了task的注释中。
这道题相当于是ez_math的升级版，因为在ez_math中我利用的是相似方阵的迹和行列式相等。这里使用的是相似矩阵的特征值是相等的。两者都可以进行简单的证明，或许在线性代数的课程中我们都以结论的形式进行记忆。注意，因为在求解特征值的过程中，我们是经过特征多项式求解的，所以在顺序的对应关系上可能存在乱序的关系，所以exp中使用简单的组合避免了这一情况。
exp

from sage.all import *
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad, pad
import itertools
p = 14668080038311483271
C = [
[11315841881544731102, 2283439871732792326, 6800685968958241983, 6426158106328779372, 9681186993951502212],
[4729583429936371197, 9934441408437898498, 12454838789798706101, 1137624354220162514, 8961427323294527914],
[12212265161975165517, 8264257544674837561, 10531819068765930248, 4088354401871232602, 14653951889442072670],
[6045978019175462652, 11202714988272207073, 13562937263226951112, 6648446245634067896, 13902820281072641413],
[1046075193917103481, 3617988773170202613, 3590111338369894405, 2646640112163975771, 5966864698750134707]
]
D = [
[1785348659555163021, 3612773974290420260, 8587341808081935796, 4393730037042586815, 10490463205723658044],
[10457678631610076741, 1645527195687648140, 13013316081830726847, 12925223531522879912, 5478687620744215372],
[9878636900393157276, 13274969755872629366, 3231582918568068174, 7045188483430589163, 5126509884591016427],
[4914941908205759200, 7480989013464904670, 5860406622199128154, 8016615177615097542, 13266674393818320551],
[3005316032591310201, 6624508725257625760, 7972954954270186094, 5331046349070112118, 6127026494304272395]
]
msg = b"\xcc]B:\xe8\xbc\x91\xe2\x93\xaa\x88\x17\xc4\xe5\x97\x87@\x0fd\xb5p\x81\x1e\x98,Z\xe1n`\xaf\xe0%:\xb7\x8aD\x03\xd2Wu5\xcd\xc4#m'\xa7\xa4\x80\x0b\xf7\xda8\x1b\x82k#\xc1gP\xbd/\xb5j"
P = GF(p)
C = matrix(P, C)
D = matrix(P, D)
eigC = C.eigenvalues()
eigD = D.eigenvalues()
eigC = [lam for lam in eigC if lam != P(0)]
eigD = [mu for mu in eigD if mu != P(0)]
for lc, ld in itertools.product(eigC, eigD):
try:
key = discrete_log(ld, lc)
if C ** key == D:
print(f"key = {key}")
break
except (ValueError, ArithmeticError):
continue
key = pad(long_to_bytes(int(key)), 16)
my_aes = AES.new(key, mode = AES.MODE_ECB)
flag = unpad(my_aes.decrypt(msg), 64)
print(flag)
"""
key = 5273966641785501202
b'LILCTF{Are_y0u_5till_4wake_que5t1on_m4ker!}'
"""

复制代码

baaaaaag

task

from Crypto.Util.number import *
import random
from Crypto.Cipher import AES
import hashlib
from Crypto.Util.Padding import pad
from secret import flag
p = random.getrandbits(72)
assert len(bin(p)[2:]) == 72
a = [getPrime(90) for _ in range(72)]
b = 0
t = p
for i in a:
temp = t % 2
b += temp * i
t = t >> 1
key = hashlib.sha256(str(p).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
flag = pad(flag,16)
ciphertext = cipher.encrypt(flag)
print(f'a = {a}')
print(f'b = {b}')
print(f"ciphertext = {ciphertext}")
'''
a = [965032030645819473226880279, 699680391768891665598556373, 1022177754214744901247677527, 680767714574395595448529297, 1051144590442830830160656147, 1168660688736302219798380151, 796387349856554292443995049, 740579849809188939723024937, 940772121362440582976978071, 787438752754751885229607747, 1057710371763143522769262019, 792170184324681833710987771, 912844392679297386754386581, 906787506373115208506221831, 1073356067972226734803331711, 1230248891920689478236428803, 713426848479513005774497331, 979527247256538239116435051, 979496765566798546828265437, 836939515442243300252499479, 1185281999050646451167583269, 673490198827213717568519179, 776378201435505605316348517, 809920773352200236442451667, 1032450692535471534282750757, 1116346000400545215913754039, 1147788846283552769049123803, 994439464049503065517009393, 825645323767262265006257537, 1076742721724413264636318241, 731782018659142904179016783, 656162889354758353371699131, 1045520414263498704019552571, 1213714972395170583781976983, 949950729999198576080781001, 1150032993579134750099465519, 975992662970919388672800773, 1129148699796142943831843099, 898871798141537568624106939, 997718314505250470787513281, 631543452089232890507925619, 831335899173370929279633943, 1186748765521175593031174791, 884252194903912680865071301, 1016020417916761281986717467, 896205582917201847609656147, 959440423632738884107086307, 993368100536690520995612807, 702602277993849887546504851, 1102807438605649402749034481, 629539427333081638691538089, 887663258680338594196147387, 1001965883259152684661493409, 1043811683483962480162133633, 938713759383186904819771339, 1023699641268310599371568653, 784025822858960757703945309, 986182634512707587971047731, 1064739425741411525721437119, 1209428051066908071290286953, 667510673843333963641751177, 642828919542760339851273551, 1086628537309368288204342599, 1084848944960506663668298859, 667827295200373631038775959, 752634137348312783761723507, 707994297795744761368888949, 747998982630688589828284363, 710184791175333909291593189, 651183930154725716807946709, 724836607223400074343868079, 1118993538091590299721647899]
b = 34962396275078207988771864327
ciphertext = b'Lo~G\xf46>\xd609\x8e\x8e\xf5\xf83\xb5\xf0\x8f\x9f6&\xea\x02\xfa\xb1_L\x85\x93\x93\xf7,`|\xc6\xbe\x05&\x85\x8bC\xcd\xe6?TV4q'
'''

复制代码

analysis

显而易见，我们拿到的数据有a，b以及flag经过AES加密之后的密文，解决问题的关键就是获得p以得到key对ciphertext进行AES的解密获取flag。
根据题目名称以及b的计算过程，可以知晓这就是一个背包问题。针对于这个背包问题，其实就是根据a，b去还原p的二进制位，我们构造方程式的格求解即可。
注意，针对于GF(2)中的格，我们采用2x - 1令其定义域为{-1, 1}提高规约效率。这里我先使用了LLL进行规约，发现并不能准确地规约出我们想要地结果；之后BKZ进行规约结果优化，记得适当调整block_size的大小，不断地进行增大以增加规约的准确性。如果前者没有针对于2x-1的变化，block_size增大到一定量的时候也是可以准确规约出p的。
针对于BKZ规约之后的结果，我们进行p的检验。
- 最后一列必须为0 --> （sum(x_i*a_i*C) - b*C = 0 → sum(x_i*a_i) = b）
- 前n列元素绝对值≤1（对应2x_i - 1 ∈ {-1,1}，即x_i = (元素 + 1) // 2）

exp
[code]from sage.all import Matrix, ZZfrom Crypto.Util.number import *from Crypto.Cipher import AESimport hashlibfrom Crypto.Util.Padding import unpada = [965032030645819473226880279, 699680391768891665598556373, 1022177754214744901247677527, 680767714574395595448529297, 1051144590442830830160656147, 1168660688736302219798380151, 796387349856554292443995049, 740579849809188939723024937, 940772121362440582976978071, 787438752754751885229607747, 1057710371763143522769262019, 792170184324681833710987771, 912844392679297386754386581, 906787506373115208506221831, 1073356067972226734803331711, 1230248891920689478236428803, 713426848479513005774497331, 979527247256538239116435051, 979496765566798546828265437, 836939515442243300252499479, 1185281999050646451167583269, 673490198827213717568519179, 776378201435505605316348517, 809920773352200236442451667, 1032450692535471534282750757, 1116346000400545215913754039, 1147788846283552769049123803, 994439464049503065517009393, 825645323767262265006257537, 1076742721724413264636318241, 731782018659142904179016783, 656162889354758353371699131, 1045520414263498704019552571, 1213714972395170583781976983, 949950729999198576080781001, 1150032993579134750099465519, 975992662970919388672800773, 1129148699796142943831843099, 898871798141537568624106939, 997718314505250470787513281, 631543452089232890507925619, 831335899173370929279633943, 1186748765521175593031174791, 884252194903912680865071301, 1016020417916761281986717467, 896205582917201847609656147, 959440423632738884107086307, 993368100536690520995612807, 702602277993849887546504851, 1102807438605649402749034481, 629539427333081638691538089, 887663258680338594196147387, 1001965883259152684661493409, 1043811683483962480162133633, 938713759383186904819771339, 1023699641268310599371568653, 784025822858960757703945309, 986182634512707587971047731, 1064739425741411525721437119, 1209428051066908071290286953, 667510673843333963641751177, 642828919542760339851273551, 1086628537309368288204342599, 1084848944960506663668298859, 667827295200373631038775959, 752634137348312783761723507, 707994297795744761368888949, 747998982630688589828284363, 710184791175333909291593189, 651183930154725716807946709, 724836607223400074343868079, 1118993538091590299721647899]b = 34962396275078207988771864327ciphertext = b'Lo~G\xf46>\xd609\x8e\x8e\xf5\xf83\xb5\xf0\x8f\x9f6&\xea\x02\xfa\xb1_L\x85\x93\x93\xf7,`|\xc6\xbe\x05&\x85\x8bC\xcd\xe6?TV4q'n = 72C = 2 ** 100 # C > sum(a) 2 ** (90 + 6) --> 2 ** 100# print(C > sum(a))L = Matrix(ZZ, n + 1, n + 1)for i in range(n): L[i, i] = 2 L[i, -1] = a * Cfor i in range(n): L[-1, i] = -1L[-1, -1] = -b * C# L = L.LLL()# print(L)L = L.BKZ(block_size = 26)# print(L)for idx, row in enumerate(L): # 1. 最后一列必须为0 --> （sum(x_i*a_i*C) - b*C = 0 → sum(x_i*a_i) = b） # 2. 前n列元素绝对值≤1（对应2x_i - 1 ∈ {-1,1}，即x_i = (元素 + 1) // 2） if row[-1] != 0: continue if not all(abs(x)

账号		自动登录	找回密码
密码			立即注册

2025LilCTF -- Crypto -- WriteUp

相关帖子

签约作者

2025LilCTF -- Crypto -- WriteUp

相关帖子

相关推荐

签约作者