rsand

第一段想复杂了...无语...

由两个hint \[ \begin{cases} x_1p+y_1q=h_1\\ x_2p+y_2q=h_2 \end{cases} \] 消去 \(p\) 得到 \[ (x_2y_1-x_1y_2)q=x_2hint_1-x_1hint_2 \] 因为 \(x_1\) 和 \(x_2\) 的位数很小，所以可以直接爆破等式右边，与 \(n\) 的最大公因数为 \(q\)

exp如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import *
from gmpy2 import *

n = 15362411588902771813202478635066445941567868219581080563115075898286474259882954338389793970699719911440130093205665853149410649953666749040198875967674392222163203507355594406743187111917695130252508256218749978621308541602497724665219449744861537283780518527254216366922466302326499402578109162330236444246061693469594478198741804520250626169244657971542999522991366630193919018630909161404721555664080170638132633626413255410410137099959334489280964350052541921478423372394540832436892310584104528058862537859512612948202958012151863722620647893665739096431795849153054455097180239006325840211260579467505866213321
c = 11002534477657652912372810848926482391887092190932469703165894690536229876745380661840257117009642277835336802865534980565178417018115086283494566571591522074247199913911415717085915100575473598649881133900396287499714340304262409043666909170720737038101830037153191272567843715155840570872019827741812315121448500605071700446687466870430406768450579933501297054990457726974127775349625204465934169150186539616296542755004869578536990613527055300928552638596456866596750833563115593781526966755165582546123990308808800667406917385312002041186603020503841256329991750190455878250894582571115111718135613960552099796906
hint1 = 2039159895585947475068088143527275690469909689185999604715451064124585853630752695470054673165419252527995240269327198412911807393416868235368504436584431412703134163959877202830050029989666528799391256150468576467273354859421767605446501398147668264017311245664408370173372269180865579591613828331745440553844035856076454341552544551052879486
hint2 = 6170476515613158918019570212115499947887402741180020964652659349816460675494790538630642858309783692527180075685596707268292572208320861367215001657838600707154243013775820727645118716675494532280326540990164077009804842182349494755380713591859893639814050512143156159959577957276848467778079473027018795376680418523444184725355227808205707370866889222282260917819411661336280572584451528321234887370803975647102920033004478195544414068866619365914629166753794432
e=0x10001
hint1+=0x114
hint2+=0x514
for x1 in range(2**11):
    for x2 in range(2**11):
        res=x2*hint1-x1*hint2
        if gcd(res,n)>1:
            q=gcd(res,n)
            p=n//q
            if p!=1:
                phi=(p-1)*(q-1)
                d=pow(e,-1,phi)
                m=pow(c,d,n)
                print(long_to_bytes(m))

第二段提示 \[ hint=(514p-114q)^{n-p-q}\bmod n \] 即 \[ hint\equiv(514p-114q)^{\varphi(n)-1}\bmod n \] 由费马小定理 \[ (514p-114q)^{\varphi(n)}\equiv1 \bmod n \] 则 \[ hint\equiv(514p-114q)^{-1}\bmod n \] 即 \[ 514p-114q\equiv hint^{-1}\bmod n \] 解方程即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import *
from sympy import Symbol, solve

n = 14613502360939407863364589690812693501576922015366807002210962584460047350845537764142210352130233032135473294184344072762436542434785585224020831394084565036716418109919829033258196217882864669635415609075818243971882912549353576386629515720087100016370772011955973283744723438549870916347709178589685193909321524165748288924202669548997517884387638918344738115457689717826344603929580127755701760308381010681916266274710602238395858963186594803904347234435058557970115334425105855525301386358186797915365594182735744972183207024004366005265160795393027146790753599490397272129760611365574650461896794485251729339917
c = 1844299912672016932426822018833591085972208214783086872799988395704845279022708684226230192763503364790682896395124939765874012896515678571101394384566426713336825986122985858527735235893804112680673539457392905480276483747257452448710122851740312060422274512680127131210147225237259230461111904664003292861437196651263996367017511863966042537545885725061709851975490202090882311310946885913288853818824443330638704672526383498619649083972724846675126742542408080719532231101926732115530039151296805345109979024130657946665108954753958579773073032661897027538002118347463185013469149637882883237217493993357422403232
hint = 13881623050018793449740724432472477579431028423415489113042909440292945176076047853295489683282566216707368640412032428065710793944727730364882781802686441001675541059762893646159952263021674742992116858706764042023688870351813641289345431554332438056975389690221360841234949127345504351560719482921978464850482655935841596020088119189343494640190529315960401842837394588319749239763935273823187981223500526826390486325704018528146085661848118036219964549751708955060489798414604842478314300870914329120804301300258551132812139046559458174322633995586180526756105707630647105997143636109998519361514738555163378927000

res=pow(hint,-1,n)
p = Symbol('p')
q = Symbol('q')
p, q = solve([p*q-n, 514*p-114*q-res], [p, q])[1]
p = int(p)
q = int(q)
e = 0x10001
phi=(p-1)*(q-1)
d=pow(e,-1,phi)
m=pow(c, d, n)
flag2=long_to_bytes(m)
print(flag2)