2024长城杯的RandomRSA

做了今年长城杯的RandomRSA，并不是说这题有多难，只是当时搞的一个多线程爆破脚本感觉挺有意思的

其实就是个RSA，素数 $p$ 和 $q$ 是相邻的两个LCG

不妨令

$\begin{aligned} p &= x + \epsilon_p \\ q &= y + \epsilon_q \\ \end{aligned}$

其中 $\epsilon_p$ 和 $\epsilon_q$ 是next_prime产生的误差（理论上是可以枚举的值）

由于题目的变量名在乱搞，所以不妨令RSA的素数为 $p'$ 和 $q'$ ，那么就有

$\begin{aligned} p' &\equiv x + \epsilon_p \pmod p \\ q' &\equiv y + \epsilon_q \\ &\equiv a x + b + \epsilon_q \pmod p \\ n &\equiv p' q' \equiv (x + \epsilon_p)(a x + b + \epsilon_q) \pmod p \end{aligned}$

这样就有了一个二次方程

$a x^2 + (b + a \epsilon_p + \epsilon_q) x + (b \epsilon_p + \epsilon_p \epsilon_q - n) \equiv 0 \pmod p$

因为 $p$ 是素数，所以理论上方程可解

然后题目泄露了 $a$ 、 $b$ 和 $p$ ，而 $\epsilon_p$ 和 $\epsilon_q$ 都是可枚举的小数，所以只需要枚举 $\epsilon_p$ 和 $\epsilon_q$ 然后解方程即可分解

虽然 $\epsilon_p$ 和 $\epsilon_q$ 可以枚举，但是单线程枚举的速度还是很慢的，所以撸了个多线程

from tqdm import tqdm
from gmpy2 import powmod
from time import sleep
from libnum import sqrtmod
import multiprocessing
DONE = False

p = 170302223332374952785269454020752010235000449292324018706323228421794605831609342383813680059406887437726391567716617403068082252456126724116360291722050578106527815908837796377811535800753042840119867579793401648981916062128752925574017615120362457848369672169913701701169754804744410516724429370808383640129
a = 95647398016998994323232737206171888899957187357027939982909965407086383339418183844601496450055752805846840966207033179756334909869395071918100649183599056695688702272113280126999439574017728476367307673524762493771576155949866442317616306832252931038932232342396406623324967479959770751756551238647385191314
b = 122891504335833588148026640678812283515533067572514249355105863367413556242876686249628488512479399795117688641973272470884323873621143234628351006002398994272892177228185516130875243250912554684234982558913267007466946601210297176541861279902930860851219732696973412096603548467720104727887907369470758901838
n = 5593134172275186875590245131682192688778392004699750710462210806902340747682378400226605648011816039948262008066066650657006955703136928662067931212033472838067050429624395919771757949640517085036958623280188133965150285410609475158882527926240531113060812228408346482328419754802280082212250908375099979058307437751229421708615341486221424596128137575042934928922615832987202762651904056934292682021963290271144473446994958975487980146329697970484311863524622696562094720833240915154181032649358743041246023013296745195478603299127094103448698060367648192905729866897074234681844252549934531893172709301411995941527
c = 2185680728108057860427602387168654320024588536620246138642042133525937248576850574716324994222027251548743663286125769988360677327713281974075574656905916643746842819251899233266706138267250441832133068661277187507427787343897863339824140927640373352305007520681800240743854093190786046280731148485148774188448658663250731076739737801267702682463265663725900621375689684459894544169879873344003810307496162858318574830487480360419897453892053456993436452783099460908947258094434884954726862549670168954554640433833484822078996925040310316609425805351183165668893199137911145057639657709936762866208635582348932189646
print(p%4)

N = 1000
A = a
s = pow(2*a, -1, p)
def gao(epRange):
  global p, a, b, n
  global N, A, s, q
  global DONE
  for ep in range(epRange[0], epRange[1]):
    print(ep)
    if DONE:
      return None
    for eq in range(N):
      B = b + a * ep + eq
      C = b * ep + ep * eq - n
      r = powmod(B, 2, p) - 4 * A * C
      try:
        r = next(sqrtmod(r, {p:1}))
      except ValueError:
        continue
      x1 = (-B + r) * s % p
      x2 = (-B - r) * s % p

      if n % (x1+ep) == 0:
        x = x1 + ep
      elif n % (x2+ep) == 0:
        x = x2 + ep
      else:
        continue

      pp = int(x)
      qq = n // pp
      print(ep, eq)
      print('p = %d' % pp)
      print('q = %d' % qq)
      DONE = True
      return pp, qq

T = 16
pool = multiprocessing.Pool()
pars = []
for i in range(T):
  pars += [(N//T * i, N//T * (i+1))]
print(pars)
results = pool.map(gao, pars)

print(results)

'''
400 777
p = 38534082358492594770386164237787365358541687418861187872713633582773421830071965767156849758539753005265646728268013378441910869242213934859104106129143840904759207713228020635783396836155221721670963919289892982570525749738495868163606321994100244126498346427863605167635338350807757317686146416624471447241
q = 145147719368033844282055476069565277972450920661198182644003791399589781631985161208774216817150855883391584293197178994046722410469327488771575417556829488538952903702037649291614294000779585447470770239066095274911650207282781843656239171875690710453814808579707586828207293637047309086803838892823136753247
'''

理论上几分钟就可以爆出来了，比单线程快不少

有一个坑点是，因为 $p \equiv 1 \pmod 4$ ，所以不能用 $a ^ {(p+1)/4} \pmod p$ 的方式开平方，这里因为Sage的多线程有点问题，所以我选择用libnum的sqrtmod解

另一个坑点是，我一直以为Python的_thread是多线程，现在才知道那其实是假的多线程，真正的多线程其实要用multiprocessing…