New Year CTF 2025

复现一下西电平台的题目

See you again

from random import*

import string

from Crypto.Util.number import *

from sage.all import*

flag = b'flag{XXXXXXXXXXXXX}'

ext_len = 4*23 - len(flag)

flag += ''.join(choice(string.printable) for _ in range(ext_len))

def my_rsa_encrypt():

  p = getPrime(512)

  q = getPrime(512)

  n = p * q

  data = []

  for i in range(4):

    data.append(bytes_to_long(flag[23*i:23*(i+1)].encode()))

  M = Matrix(Zmod(n), [data[i:i+2] for i in range(0, len(data), 2)])

  e = 65537

  C = M**e

  x1=randint(0,2**11)

  y1=randint(0,2**114)

  x2=randint(0,2**11)

  y2=randint(0,2**514)

  hint1=x1*p+y1*q

  hint2=x2*p+y2*q

  

  print("hint1 =", hint1)

  print("hint2 =", hint2)

  print("n =", n)

  return C

C = my_rsa_encrypt()

print("C =", C)

'''

hint1 = 168265279404811256277233395102642358475458409482403711393035752197600859883963939768385846094966123277287664746626323932557461116229847433749541823928128333856483359321776317487696165625065

hint2 = 388525731960756845976560311958832822501361876609762739131361346349184345486942393347353228412856257245501810230005909157804781984160852691049705221909148849268628655156230494562410040271685185427100514456092002902461455124227295965928975113228265630904429459035860216889967825964526267040037892094324439719411

n = 73072541902206871020737492238712393160727227031674788366854370087046494314953414149210811810993251599137993812618059430654795580640655927531189983107761278404614174799313759634478308102715209502959314132742690028687179640727016334879648957747421327650216141691465903844138851357328611067635106605344718049129

C = [ 6310748775703051581154234569431184868982413857734351142080359008436987630184616677942361392389551047027017330071293367514311142151815936199483256586417636348041649876709276752266778499479183523443148337562720814581572407854278542331966812940447535783779656684256297221348716866635101085755860498353339242115  5144330870923367619389647825281339367482009106753859407075628907488466365472218688907933875894666639770145465222088465870419295906638236631404037390832689261596431619354248820909813429665843949224111735121883894006720533494334946354541598413794931072951879543749090953489715640123785787585906571296066228337]

[33291873086307192132352453738238356328226272776193653137970607851693478963529798496768193693023879049338380362901921264407689229849253505523956752578525472920304538365514116510285387059498125392190213470841105539220357787132908727038425638513550855537375794144340611979256932750425138088529265202217417349326  8710391985351492354130113806218295166875250333985231739921757023007679201614662002300751925094702862907693146762459566351810351082709246293390023137646644466382528873636039529534916744087376534336847024714465012051303713158199842172134865427319373041223732135032837752292040371239661190751800891412327395907]

'''

这里拿到题目先观察加密方式

这里我们发现是矩阵RSA，这里是将明文分为四段放入矩阵当中

这里先贴个论文

要想知道具体的加密过程就要先了解什么是一般线性群

image-20250421121658062

单位矩阵 I 属于 GL_s(ℤ_n)，矩阵乘法满足结合律，矩阵行列式与 n 互质即 GL_s(ℤ_n) 中每一个元素都有乘法逆元，所以构成一个群。

那么要想解密也很容易

只要求出d C^d = m mod  (n) 那么这里d要怎么求

image-20250421122936304

论文中给出了明确的求法，我们phi不再是之前了而是（p² − 1）(p² − p)(q² − 1)(q² − q)

那么现在我们要求的是p,q了

但是对于这题来说有个小小的非预期，phi好像怎么取值都行，原本我的理解是M的阶刚好是（p − 1）（q − 1）

但是，这里真的好像取啥都行，问了其他师傅，说是数据给的有问题

回到题目我们要怎么求p,q呢

x1=randint(0,2**11)

y1=randint(0,2**114)

x2=randint(0,2**11)

y2=randint(0,2**514)

hint1=x1*p+y1*q

hint2=x2*p+y2*q

这里还是很简单的

我们会发现x1，x2都不是很大，那么可以选择爆破

将第一式乘x2，第二式乘x1

$$ hint1*x_{2}=x_{2}*(x_{1}*p+y_{1}*q) \\ hint2*x_{1}=x_{1}*(x_{2}*p+y_{2}*q) $$

现在再将两式相减

hint1 * x₂ − hint2 * x₁ = (x₁y₂ − x₂y₁)q

即

A = Bq

那么接下来只要做个gcd就可以得到q了

n = 73072541902206871020737492238712393160727227031674788366854370087046494314953414149210811810993251599137993812618059430654795580640655927531189983107761278404614174799313759634478308102715209502959314132742690028687179640727016334879648957747421327650216141691465903844138851357328611067635106605344718049129

hint1 = 168265279404811256277233395102642358475458409482403711393035752197600859883963939768385846094966123277287664746626323932557461116229847433749541823928128333856483359321776317487696165625065

hint2 = 388525731960756845976560311958832822501361876609762739131361346349184345486942393347353228412856257245501810230005909157804781984160852691049705221909148849268628655156230494562410040271685185427100514456092002902461455124227295965928975113228265630904429459035860216889967825964526267040037892094324439719411
for i in range(2**11):

  for j in range(2**11):

    temp = hint1  * i - hint2  * j

    if gmpy2.gcd(temp,n) != 1:

      p = gmpy2.gcd(temp,n)

      if n % p ==0:

        q = n // p

        print("p=",p)

        print("q=",q)

加下来就是恢复M了，上面也说过了

import gmpy2

from Crypto.Util.number import *

n = 73072541902206871020737492238712393160727227031674788366854370087046494314953414149210811810993251599137993812618059430654795580640655927531189983107761278404614174799313759634478308102715209502959314132742690028687179640727016334879648957747421327650216141691465903844138851357328611067635106605344718049129

p = 9840199651059680279315545552078195603933414815185149988850805053207130958990873093781755127037056517374437691746406285746154497813695817556539648065445111

q = 7425920661511961227328493926307082700428726975369330043535693658853751767178547931292974567810134212365247300045094600690928968177216378782623096259591839

C = Matrix(Zmod(n), [

  [6310748775703051581154234569431184868982413857734351142080359008436987630184616677942361392389551047027017330071293367514311142151815936199483256586417636348041649876709276752266778499479183523443148337562720814581572407854278542331966812940447535783779656684256297221348716866635101085755860498353339242115, 

   5144330870923367619389647825281339367482009106753859407075628907488466365472218688907933875894666639770145465222088465870419295906638236631404037390832689261596431619354248820909813429665843949224111735121883894006720533494334946354541598413794931072951879543749090953489715640123785787585906571296066228337],

  [33291873086307192132352453738238356328226272776193653137970607851693478963529798496768193693023879049338380362901921264407689229849253505523956752578525472920304538365514116510285387059498125392190213470841105539220357787132908727038425638513550855537375794144340611979256932750425138088529265202217417349326, 

   8710391985351492354130113806218295166875250333985231739921757023007679201614662002300751925094702862907693146762459566351810351082709246293390023137646644466382528873636039529534916744087376534336847024714465012051303713158199842172134865427319373041223732135032837752292040371239661190751800891412327395907]

])

e = 65537

\#phi=(p^2-1)*(p^2-p)*(q^2-1)*(q^2-q)

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

d=gmpy2.invert(e,phi)

M = C**d

m = b''.join(long_to_bytes(int(y)) for x in M for y in x)

print(m)

hnnnnnp

from Crypto.Util.number import *

flag = b'flag{XXXXXXXXXXXXXXXX}'

len(bin(bytes_to_long(flag))) = 241 

m = bytes_to_long(flag)

q = getPrime(256)

A = []

B = []

for i in range(40):

  a = getRandomInteger(256)

  A.append(a)

  b = (a * m % q) >> 246

  B.append(b)

print('q = ',q)

print('A = ',A)

print('B = ',B)

"""

q =  79114087378317225954892022480252117763918921251508274813632988119040558081957

A =  [99293334762228409415871581396212237412953404357126780770028017803413316507688, 2500480840704745075911410946123687629524432551367413638642986009358154787372, 80685558004752117053336613030689142016338319732790152841247856882805636400967, 63290001864400721248272352929255137611989584118097077958408567982128698234534, 5048332633026992532834890641901394670789207101467603380531070147563959907435, 98345158033169941273559370561319923206165641360286918926165722533747367869044, 91661185592644662634101002232848898241014068680383461946834577089141708799408, 35883539106260317692857231527467938791115349400928738495153295603754797497003, 18850448551910645282253407416422777216080885714433351260880371928669115264186, 86803241348387239192288300857910031249784969059106976374312551858268245857442, 113779438160927993654998705272524709206271659504623230967447802327094495796781, 13735459600754846538171144203957927429136626155419829429669861649940998894997, 46280418602037825886010980190704083111219707606955301840430515744873877438775, 16278994219375932354158092674595809845774952941618307320565305777822420450943, 74927876286842101149511766920644259934347532918716712290257161737641674460298, 42178202650652528099749516560693500619443362792978884623518490495115906200316, 19151047172626938357474963053807928227857518257319920099967861099963796480418, 21787599078683620242310742514553440060243832982887133694157543001440264793591, 34075119848054572416068714633191349442086346533132115388443988285733183568037, 70884300905035090978863770641828348559532542870751550058652309789615992321329, 56638844602601914284538086316463617187093124581243824454129547501609966433533, 63173126643011517652232352750442686295089111186360350917063529989062125715462, 28513769949842169592533398466043837164454663770876296609570694346056935679972, 78576986164864622274471458294234572339552498559596959190642129314202635344362, 29040128818027182812085632623851615750950738459702000094747611239508626643986, 24643036623783907525543153714744708140593035044888678308137488533907283671880, 114371475713932020306500291701047080632524480018017816508069308216548075509192, 41900448697162816841352108181063898351906757401259309332438722605718438845658, 54568329635023979120173438773482273886435623791438511491045655663987235054396, 75001704264552278370093948911424867598236273326722937206696873331699786435512, 26706895892299062149149150389452432539968783870299486337639175716389699841556, 97377367425189290583063973155451138814295009389822857196761177411699410905996, 1232863831096632130472661739812011549745300164338793700648153670333514662537, 26269418325008581770232430581427109657764847410045079633943766642502404580438, 24030674773281787758235075763804799489668709537838088140878504368601473605962, 86811629367335760989061373668208214074416802123960391077272719421979492321722, 4705372930912236219640794828821928446476233836995906942068634486045889421427, 3780622760283474933545118612904995151472952554666209520142018462683489410492, 32331832055598312449459015904562983681658454867302312991024083766727098901481, 82703349291431759834259791616748332088687686947094717519824850606996211446209]

B =  [644, 397, 406, 577, 263, 595, 180, 125, 492, 64, 15, 521, 303, 244, 481, 338, 323, 410, 562, 344, 117, 43, 171, 381, 300, 4, 427, 163, 141, 315, 454, 163, 197, 282, 650, 690, 5, 598, 355, 352]

"""

第一眼以为是简单的hnp，但是仔细观察后发现并没有那么简单，题目中泄露的是高10位

那么肯定是要构造格的

具体的过程就不说了

鸡块师傅博客有讲过类似的，他说的肯定比我好

这里贴我自己的exp

A =  [99293334762228409415871581396212237412953404357126780770028017803413316507688, 2500480840704745075911410946123687629524432551367413638642986009358154787372, 80685558004752117053336613030689142016338319732790152841247856882805636400967, 63290001864400721248272352929255137611989584118097077958408567982128698234534, 5048332633026992532834890641901394670789207101467603380531070147563959907435, 98345158033169941273559370561319923206165641360286918926165722533747367869044, 91661185592644662634101002232848898241014068680383461946834577089141708799408, 35883539106260317692857231527467938791115349400928738495153295603754797497003, 18850448551910645282253407416422777216080885714433351260880371928669115264186, 86803241348387239192288300857910031249784969059106976374312551858268245857442, 113779438160927993654998705272524709206271659504623230967447802327094495796781, 13735459600754846538171144203957927429136626155419829429669861649940998894997, 46280418602037825886010980190704083111219707606955301840430515744873877438775, 16278994219375932354158092674595809845774952941618307320565305777822420450943, 74927876286842101149511766920644259934347532918716712290257161737641674460298, 42178202650652528099749516560693500619443362792978884623518490495115906200316, 19151047172626938357474963053807928227857518257319920099967861099963796480418, 21787599078683620242310742514553440060243832982887133694157543001440264793591, 34075119848054572416068714633191349442086346533132115388443988285733183568037, 70884300905035090978863770641828348559532542870751550058652309789615992321329, 56638844602601914284538086316463617187093124581243824454129547501609966433533, 63173126643011517652232352750442686295089111186360350917063529989062125715462, 28513769949842169592533398466043837164454663770876296609570694346056935679972, 78576986164864622274471458294234572339552498559596959190642129314202635344362, 29040128818027182812085632623851615750950738459702000094747611239508626643986, 24643036623783907525543153714744708140593035044888678308137488533907283671880, 114371475713932020306500291701047080632524480018017816508069308216548075509192, 41900448697162816841352108181063898351906757401259309332438722605718438845658, 54568329635023979120173438773482273886435623791438511491045655663987235054396, 75001704264552278370093948911424867598236273326722937206696873331699786435512, 26706895892299062149149150389452432539968783870299486337639175716389699841556, 97377367425189290583063973155451138814295009389822857196761177411699410905996, 1232863831096632130472661739812011549745300164338793700648153670333514662537, 26269418325008581770232430581427109657764847410045079633943766642502404580438, 24030674773281787758235075763804799489668709537838088140878504368601473605962, 86811629367335760989061373668208214074416802123960391077272719421979492321722, 4705372930912236219640794828821928446476233836995906942068634486045889421427, 3780622760283474933545118612904995151472952554666209520142018462683489410492, 32331832055598312449459015904562983681658454867302312991024083766727098901481, 82703349291431759834259791616748332088687686947094717519824850606996211446209]

B =  [644, 397, 406, 577, 263, 595, 180, 125, 492, 64, 15, 521, 303, 244, 481, 338, 323, 410, 562, 344, 117, 43, 171, 381, 300, 4, 427, 163, 141, 315, 454, 163, 197, 282, 650, 690, 5, 598, 355, 352]

def matrix_overview(BB):

  for ii in range(BB.dimensions()[0]):

    a = ('%02d ' % ii)

    for jj in range(BB.dimensions()[1]):

      if BB[ii, jj] == 0:

        a += ' '

      else:

        a += 'X'

      if BB.dimensions()[0] < 60:

        a += ' '

    print(a)

m = 256

s = 10

AAA = [x for x in A]

BBB = [x for x in B]

A = [x for x in AAA]

B = [x for x in BBB]

\#B = [x << (m-s) for x in B]

B = [(x << (m-s)) + (1 << (m-s-1)) for x in B]

assert len(A) == len(B)

q = 79114087378317225954892022480252117763918921251508274813632988119040558081957

n = len(A)-1

AA = [x for x in A]

BB = [x for x in B]

for choice in range(n):

  A = [x for x in AA]

  B = [x for x in BB]

  if A[choice] % 2 != 1:

    continue

  A0 = A[choice]

  A0i = A0.inverse_mod(q)

  B0 = B[choice]

  del A[choice]

  del B[choice]

  assert gcd(A0, q) == 1

  Mt = matrix(ZZ, n+2)

  for i in range(n):

    Mt[i, i]  = -q

    Mt[-2, i] = A0i*A[i] % q

    Mt[-1, i] = A0i*(A[i]*B0 - A0*B[i]) % q

  Mt[-2, -2] = 1

  R = 2^(m-s-1)

  Mt[-1, -1] = R

  L = Mt.BKZ()

  for l in L:

    if l[-1] == R:

      b = vector(l)

      b0 = b[-2]

      x0 = (B0+b0) * A0.inverse_mod(q) % q

      test1 = [bi >> (m-s) for bi in B] 

      test2 = [(ai*x0 % q) >> (m-s) for ai in A]

      if test1 == test2:

        print('get: %d' % x0)

  break

Before Sunset

from Crypto.Util.number import *

from hashlib import sha256

from Crypto.Cipher import AES

from random import *

from Crypto.Util.Padding import *

flag = b'flag{XXXXXXXXX}'

note = b'Before_Sunset*xt'

keys = []

for i in range(4):

  key = bytes(choices(note,k=3))

  keys.append(sha256(key).digest())

cipher = b'happy_newyear!!!'

for i in range(4):

  cipher = AES.new(keys[i], AES.MODE_ECB).encrypt(cipher) 

enkey = sha256(b"".join(keys)).digest()

enflag = AES.new(enkey,AES.MODE_ECB).encrypt(pad(flag,AES.block_size))

print(f'cipher = {cipher}')

print(f'enflag = {enflag}')

"""

cipher = b'4\xf6\x89\x81:\xd7\xf4\xc4\xad\xb1)\x99\xb1l\xe2\x7f'

enflag = b'\x964\xdcq\xcc\xe9\xde\xfe=\xfb\x08\\\x9e\xe3\xf5\xef^\x9c\x11\xaa\xb8\x97\xe61\x1ee\xe4dV\x0c\x1c\xf7 \xabX]\x92\xd6\xa3\xdegD\xbb\xbd\x98\x90\xeb~'

"""

没什么好说的两次加密，和SHCTF有相同的

那么很自然想到利用mitm攻击来打

import itertools

from Crypto.Cipher import AES

from Crypto.Util.Padding import unpad

from hashlib import sha256

import binascii

import sys

\# 已知信息

note = b'Before_Sunset*xt'

leak = b'happy_newyear!!!'

cipher = b'4\xf6\x89\x81:\xd7\xf4\xc4\xad\xb1)\x99\xb1l\xe2\x7f' # 从赛题中获取

enc_flag = b'\x964\xdcq\xcc\xe9\xde\xfe=\xfb\x08\\\x9e\xe3\xf5\xef^\x9c\x11\xaa\xb8\x97\xe61\x1ee\xe4dV\x0c\x1c\xf7 \xabX]\x92\xd6\xa3\xdegD\xbb\xbd\x98\x90\xeb~'

BLOCK_SIZE = 16

def generate_all_possible_keys(note):

  """

  生成所有可能的3字节密钥

  """

  return [bytes(p) for p in itertools.product(note, repeat=3)]

def precompute_forward(leak, possible_keys):

  """

  前向加密：对leak进行两层AES-ECB加密

  返回中间密文到 (key1, key2) 的映射

  """

  forward_map = {}

  total = len(possible_keys) ** 2

  count = 0

  print("开始前向加密预计算...")

  for key1 in possible_keys:

    sha_key1 = sha256(key1).digest()

    cipher1 = AES.new(sha_key1, AES.MODE_ECB).encrypt(leak)

    for key2 in possible_keys:

      sha_key2 = sha256(key2).digest()

      cipher2 = AES.new(sha_key2, AES.MODE_ECB).encrypt(cipher1)

      forward_map[cipher2] = (key1, key2)

      count += 1

      if count % 1000000 == 0:

        print(f"前向加密进度: {count}/{total}")

  print("前向加密预计算完成。")

  return forward_map

def precompute_backward(cipher, possible_keys):

  """

  后向解密：对cipher进行两层AES-ECB解密

  返回中间密文到 (key3, key4) 的映射

  """

  backward_map = {}

  total = len(possible_keys) ** 2

  count = 0

  print("开始后向解密预计算...")

  for key4 in possible_keys:

    sha_key4 = sha256(key4).digest()

    decrypted1 = AES.new(sha_key4, AES.MODE_ECB).decrypt(cipher)

    for key3 in possible_keys:

      sha_key3 = sha256(key3).digest()

      decrypted2 = AES.new(sha_key3, AES.MODE_ECB).decrypt(decrypted1)

      backward_map[decrypted2] = (key3, key4)

      count += 1

      if count % 1000000 == 0:

        print(f"后向解密进度: {count}/{total}")

  print("后向解密预计算完成。")

  return backward_map

def find_matching_keys(forward_map, backward_map):

  """

  查找前向加密和后向解密的中间密文是否匹配

  """

  print("开始查找匹配的中间密文...")

  for intermediate in forward_map:

    if intermediate in backward_map:

      key1, key2 = forward_map[intermediate]

      key3, key4 = backward_map[intermediate]

      print("找到匹配的密钥组合！")

      return key1, key2, key3, key4

  return None

def main():

  possible_keys = generate_all_possible_keys(note)

  print(f"总共生成了 {len(possible_keys)} 个可能的3字节密钥。")

  \# 前向加密预计算

  forward_map = precompute_forward(leak, possible_keys)

  \# 后向解密预计算

  backward_map = precompute_backward(cipher, possible_keys)

  \# 查找匹配的密钥组合

  keys = find_matching_keys(forward_map, backward_map)

  if keys:

    key1, key2, key3, key4 = keys

    print(f"Key 1: {key1}")

    print(f"Key 2: {key2}")

    print(f"Key 3: {key3}")

    print(f"Key 4: {key4}")

    \# 生成 enc_key

    concatenated_hashes = sha256(key1).digest() + sha256(key2).digest() + sha256(key3).digest() + sha256(key4).digest()

    enc_key = sha256(concatenated_hashes).digest()

    print(f"生成的 enc_key: {binascii.hexlify(enc_key)}")

    \# 解密 enc_flag

    cipher_enc_flag = AES.new(enc_key, AES.MODE_ECB)

    decrypted_flag_padded = cipher_enc_flag.decrypt(enc_flag)

    try:

      decrypted_flag = unpad(decrypted_flag_padded, BLOCK_SIZE)

      print(f"解密后的 Flag: {decrypted_flag.decode()}")

    except ValueError:

      print("填充错误，无法解密 Flag。")

  else:

    print("未找到匹配的密钥组合。")

if __name__ == "__main__":

  main()