signin
https://blog.csdn.net/figfig55/article/details/127283671
连分数逼近data3，得到data1,data2
#sage
data3 = 1.42870767357206600351348423521722279489230609801270854618388981989800006431663026299563973511233193052826781891445323183272867949279044062899046090636843802841647378505716932999588
cf = continued_fraction(data3)
alist = cf.convergents()
for i in alist:
a = str(i).split('/')
if len(a)>1 and gcd(int(a[0]),int(a[1])) == 1 and is_prime(int(a[0])) and is_prime(int(a[1])) and int(a[0]).bit_length()==256 and int(a[1]).bit_length()==256:
print(a)data1=97093002077798295469816641595207740909547364338742117628537014186754830773717
data2=67958620138887907577348085925738704755742144710390414146201367031822084270769求p-q
#sage
data1=97093002077798295469816641595207740909547364338742117628537014186754830773717
data2=67958620138887907577348085925738704755742144710390414146201367031822084270769
leak = 1788304673303043190942544050868817075702755835824147546758319150900404422381464556691646064734057970741082481134856415792519944511689269134494804602878628
phi1 = (data1-1)*(data2-1)
d1 = inverse_mod(data1,phi1)
p_q = int(pow(leak,d1,data1*data2))
print(p_q)
#p-q=57684649402353527014234479338961992571416462151551812296301705975419997474236然后解方程求p,q,RSA求flag
#python
import sympy
import gmpy2
from Crypto.Util.number import *
e=65537
c=1046004343125860480395943301139616023280829254329678654725863063418699889673392326217271296276757045957276728032702540618505554297509654550216963442542837
n=2793178738709511429126579729911044441751735205348276931463015018726535495726108249975831474632698367036712812378242422538856745788208640706670735195762517
p_q=57684649402353527014234479338961992571416462151551812296301705975419997474236
data2=67958620138887907577348085925738704755742144710390414146201367031822084270769
p=sympy.Symbol('p')
q=sympy.Symbol('q')
f1=p*q-n
f2=p-q-p_q
result=sympy.solve([f1,f2],[p,q])
p=result[1][0]
q=result[1][1]
phi=(p-1)*(q-1)
d=gmpy2.invert(e,int(phi))
m=pow(c,d,n)
print(long_to_bytes(int(m)-data2))
# SYC{a00338c150aa3a5163dbf404100e6754}CrazyTreat
方法一：
参考3te✌的思路
首先根据高位攻击爆破还原p
n = 12825979286271601683918945967807205713681672633015477696159535370583942888048057147306644638421752298716177752495337338096075416000876578271187444577819882839569779788443632687747140886774518365218964866144412523144471165524247882599528355994868389110054745818639473862141065572155619677445147335927188794120959
p4 = 13053422630763887754872929794631414002868675984142851995620494432706465523574529389771830464455212126838976863742628716168391373019631629866746550551576576
for i in range(200,256):
PR.<x> = PolynomialRing(Zmod(n))
f = p4+x
roots = f.small_roots(X=2^i, beta=0.4)
if roots!=[]:
p = p4+int(roots[0])
print(f'p = {p}')
break
q = n//p
print('q=',q)p = 13053422630763887754872929794631414002868675984142851995620494432706465523574529389771830464531559991042565319610790540616696456104018890243275374098291711
q= 9825759610390416003138880321039057063786120681277009947660201742655391150627525256689197020107593156663696181775606008771199371337506657207530847665591719求得了第一个函数的p,q也就是最后的P,Q
但是发现P,Q都是512位，R是256位可以尝试不用R，直接用P,Q,RSA求flag
import gmpy2
import libnum
p = 13053422630763887754872929794631414002868675984142851995620494432706465523574529389771830464531559991042565319610790540616696456104018890243275374098291711
q= 9825759610390416003138880321039057063786120681277009947660201742655391150627525256689197020107593156663696181775606008771199371337506657207530847665591719
c = 10585127810518527980133202456076703601165893288538440737356392760427497657052118442676827132296111066880565679230142991175837099225733564144475217546829625689104025101922826124473967963669155549692317699759445354198622516852708572517609971149808872997711252940293211572610905564225770385218093601905012939143618159265562064340937330846997881816650140361013457891488134685547458725678949
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,p*q)
print(libnum.n2s(int(m)))方法二：
首先利用和方法一一样的方法求出P,Q
然后利用cooper求出R
$P \equiv m^p mod n $
$Q \equiv m^q mod n $
$R \equiv m^r mod n $
然后根据费马小定理
$P \equiv m mod n $
$Q \equiv m mod n $
$R \equiv m mod n $
P=kn+m
Q=hn+m
R=bn+m
$(P-m)(Q-m)(R-m)=khbn^3$
即(P-m)(Q-m)(R-m) =0 mod n
n = 924936528644761261915490226270682878749572154775391302241867565751616615723850084742168094776229761548826664906020127037598880909798055174894996273670320006942669796769794827782190025101253693980249267932225152093301291975335342891074711919668098647971235568200490825183676601392038486178409517985098598981313504275523679007669267428032655295176395420598988902864122270470643591017567271923728446920345242491655440745259071163984046349191793076143578695363467259
P = 569152976869063146023072907832518894975041333927991456910198999345700391220835009080679006115013808845384796762879536272124713177039235766835540634080670611913370463720348843789609330086898067623866793724806787825941048552075917807777474750280276411568158631295041513060119750713892787573668959642318994049493233526305607509996778047209856407800405714104373282610244944206314614906974275396096712817649817035559000245832673082730407216670764400076473183825246052
Q = 600870923560313304359037202752076267074889238956345564584928427345594724253036201151726541881494799597966727749590645445697106549304014936202421316051605075583257261728145977582815350958084624689934980044727977015857381612608005101395808233778123605070134652480191762937123526142746130586645592869974342105683948971928881939489687280641660044194168473162316423173595720804934988042177232172212359550196783303829050288001473419477265817928976860640234279193511499
R = 502270534450244040624190876542726461324819207575774341876202226485302007962848054723546499916482657212105671666772860609835378197021454344356764800459114299720311023006792483917490176845781998844884874288253284234081278890537021944687301051482181456494678641606747907823086751080399593576505166871905600539035162902145778102290387464751040045505938896117306913887015838631862800918222056118527252590990688099219298296427609455224159445193596547855684004680284030
PR.<m> = PolynomialRing(Zmod(n))
f=(P-m)*(Q-m)*(R-m)
f=f.monic()
m=f.small_roots()
print(m)
# m=105960538296223496551922954965164644267919720177702173352061963871195469608683然后P,Q,R都有了RSA求flag就行
import gmpy2
import libnum
p = 13053422630763887754872929794631414002868675984142851995620494432706465523574529389771830464531559991042565319610790540616696456104018890243275374098291711
q = 9825759610390416003138880321039057063786120681277009947660201742655391150627525256689197020107593156663696181775606008771199371337506657207530847665591719
r = 105960538296223496551922954965164644267919720177702173352061963871195469608683
c = 10585127810518527980133202456076703601165893288538440737356392760427497657052118442676827132296111066880565679230142991175837099225733564144475217546829625689104025101922826124473967963669155549692317699759445354198622516852708572517609971149808872997711252940293211572610905564225770385218093601905012939143618159265562064340937330846997881816650140361013457891488134685547458725678949
e=65537
phi=(p-1)*(q-1)*(r-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,p*q*r)
print(libnum.n2s(int(m)))
# SYC{N0b0dy_Kn0vvs_CryPt0_be7t3r_7haN_Me}Alexei needs help
只需求出ans然后AES解密即可
import gmpy2 as gp
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import md5
from binascii import *
n = 2023
a = 12760960185046114319373228302773710922517145043260117201359198182268919830481221094839217650474599663154368235126389153552714679678111020813518413419360215
b = 10117047970182219839870108944868089481578053385699469522500764052432603914922633010879926901213308115011559044643704414828518671345427553143525049573118673
m = 9088893209826896798482468360055954173455488051415730079879005756781031305351828789190798690556659137238815575046440957403444877123534779101093800357633817
seq = [1588310287911121355041550418963977300431302853564488171559751334517653272107112155026823633337984299690660859399029380656951654033985636188802999069377064, 12201509401878255828464211106789096838991992385927387264891565300242745135291213238739979123473041322233985445125107691952543666330443810838167430143985860, 13376619124234470764612052954603198949430905457204165522422292371804501727674375468020101015195335437331689076325941077198426485127257539411369390533686339, 8963913870279026075472139673602507483490793452241693352240197914901107612381260534267649905715779887141315806523664366582632024200686272718817269720952005, 5845978735386799769835726908627375251246062617622967713843994083155787250786439545090925107952986366593934283981034147414438049040549092914282747883231052, 9415622412708314171894809425735959412573511070691940566563162947924893407832253049839851437576026604329005326363729310031275288755753545446611757793959050, 6073533057239906776821297586403415495053103690212026150115846770514859699981321449095801626405567742342670271634464614212515703417972317752161774065534410, 3437702861547590735844267250176519238293383000249830711901455900567420289208826126751013809630895097787153707874423814381309133723519107897969128258847626, 2014101658279165374487095121575610079891727865185371304620610778986379382402770631536432571479533106528757155632259040939977258173977096891411022595638738, 10762035186018188690203027733533410308197454736009656743236110996156272237959821985939293563176878272006006744403478220545074555281019946284069071498694967]
ct = 0x37dc072bdf4cdc7e9753914c20cbf0b55c20f03249bacf37c88f66b10b72e6e678940eecdb4c0be8466f68fdcd13bd81
def seqsum(i):
ans = 0
for j in range(len(seq)):
ans += gp.powmod(i,j,m)*seq[j]
return ans
def homework(i):
if i == 1:
return 1
if i == 2:
return 1
else:
p1,p2=1,1
for i in range(3,n+1):
p1,p2=(a*p1+b*p2+seqsum(i))%m,p1
return p1
ans = homework(n)
k = unhexlify(md5(str(ans).encode()).hexdigest())
aes = AES.new(k,AES.MODE_ECB)
flag=aes.decrypt(long_to_bytes(ct))
print(flag)
# b"c7ceedc7197a0d350025fff478f667293ebbaa6b'\x00\x00\x00\x00\x00\x00\x00"
