2025N1CTFcrypto复现

近一个月都没有学习了，一些比赛也没有打，很惭愧自己还是处在刚放假时的水平啊，马上开学了，抓紧做一些训练来康复。 CheckIn import os from Crypto.Util.number import * from secret import FLAG p, q = getPrime(512), getPrime(512) n = p * q phi = (p - 1) * (q - 1) e = 65537 r = bytes_to_long(b'n1junior2025') gift = ((2025 * p + r * r) * p % phi) >> 750 msg = bytes_to_long(FLAG) ct = pow(msg, e, n) print(f"n = {n}") print(f"e = {e}") print(f"ct = {ct}") print(f"gift = {gift}") ''' n = 127060392619341060272126983366487069092712215979664340339428955285201267724168574813227106020122399594060458777939446978632526348867806863618885370221957087197582864380885199290793062293120324984868138488667017882272415668310242448870352699380394381756621677031459335310964085476227148301120850021800822495119 e = 65537 ct = 18305235107479382231970252522433686185039231184629854177334609960907102735540326234277108553640185845164498239822263821349544015918443334769445559622730315115384134147808359107914969010678607157349844717217781801237935737980608575612421610972048739840839726108493286994232100086338529591086935374295281642738 gift = 8312456126096895497368692810699639462746223116345115761188530231045483000989605820 '''

经典RSA，唯一的额外信息在gift，测一下发现r是90bit，gift在移位是273+750位，也就是1024位左右，也就是说等式两边可以画一个约等于符号，通过在实数域上的近似计算，可以恢复p的高位

from Crypto.Util.number import * from libnum import * n = 127060392619341060272126983366487069092712215979664340339428955285201267724168574813227106020122399594060458777939446978632526348867806863618885370221957087197582864380885199290793062293120324984868138488667017882272415668310242448870352699380394381756621677031459335310964085476227148301120850021800822495119 e = 65537 ct = 18305235107479382231970252522433686185039231184629854177334609960907102735540326234277108553640185845164498239822263821349544015918443334769445559622730315115384134147808359107914969010678607157349844717217781801237935737980608575612421610972048739840839726108493286994232100086338529591086935374295281642738 gift = 8312456126096895497368692810699639462746223116345115761188530231045483000989605820 r = bytes_to_long(b'n1junior2025') g=gift<<750 PR.<x> = PolynomialRing(RealField(1000)) for i in trange(2300,2400): f=g*x-2025*x^3-x^2*r^2-i*(x-1)*(n-x) root=f.roots() ph=int(root[-1][0])>>226<<226#总共就三组，都试试就可以用最后一组解出 PR.<y> = PolynomialRing(Zmod(n)) f=ph+y res=f.small_roots(X=2**226,beta=0.4) if res and res[0]!=0: p=int(res[0])+ph print(res,p) break q=n//p print(long_to_bytes(pow(ct,invmod(e,(p-1)*(q-1)),n)))