[LitCTF 2023]baby_xor

Problem: [LitCTF 2023]baby_xor

思路

• 比赛里面有flag头的话应该是不用爆破的，这里一眼顶针一下，直接开爆

EXP

from sage.all import *
from sage.parallel.multiprocessing_sage import parallel_iter
from tqdm import tqdm

# https://tover.xyz/p/2024-wdb-RSA/#Part-4-%E5%A4%9A%E8%BF%9B%E7%A8%8B%E7%9A%84%E5%B7%B2%E7%9F%A5p%E9%AB%98%E4%BD%8D%E5%88%86%E8%A7%A3
def gao(n, ph, pl=1, pbits=512):
  global tqdm
  hbits = Integer(ph).nbits()
  lbits = Integer(pl).nbits()
  PR = PolynomialRing(Zmod(n), 'x')
  x = PR.gen()
  f = ph * 2**(pbits-hbits) + x * 2**lbits + pl
  f = f.monic()
  # p:512 ph:262
  roots = f.small_roots(X=2**(pbits-hbits-lbits+1), beta=0.48, epsilon=0.0103)
  if roots:
    pm = Integer(roots[0])
    p = ph * 2**(pbits-hbits) + pm * 2**lbits + pl
    if n % p == 0:
      q = n // p
      print()
      print('p = %d' % p)
      print('q = %d' % q)
      return p, q
  return None


def mgao(n, ph, T=16, gmax=262):
  hbits = Integer(ph).nbits()
  gbits = gmax - hbits
  ph = ph << gbits
  N = 2**gbits
  for i in tqdm(range(N//T + 1)):
    pars = []
    for j in range(T):
      pars += [((n, ph+(T*i+j), 1, 512), {})]
    res = list(parallel_iter(T, gao, pars))
    for r in res:
      if r[1] != None:
        return r[1]

n = 139167681803392690594490403105432649693546256181767408269202101512534988406137879788255103631885736461742577594980136624933914700779445704490217419248411578290305101891222576080645870988658334799437317221565839991979543660824098367011942169305111105129234902517835649895908656770416774539906212596072334423407
c1 = 11201139662236758800406931253538295757259990870588609533820056210585752522925690049252488581929717556881067021381940083808024384402885422258545946243513996
c2 = 112016152270171196606652761990170033221036025260883289104273504703557624964071464062375228351458191745141525003775876044271210498526920529385038130932141551598616579917681815276713386113932345056134302042399379895915706991873687943357627747262597883603999621939794450743982662393955266685255577026078256473601

ph = Integer(c1 >> (32 * 8))
p, q = mgao(n, ph)

'''
p = 11201139662236758800406931253538295757259990870588609533820056210585752522925662842097418194280333596411677923137891577493678147771013147838272857867768049
q = 12424421621362254864782413228469515345308247470456624398540470175059150716333040192456446204137661402539755207547729612335510757239538816257558087362587743
'''

e = 65537
phi = (p - 1) * (q - 1)
d = Integer(e).inverse_mod(phi)
m = pow(c2, d, n)
flag = m.to_bytes(1997)
print(flag)

总结

• 对该题的考点总结