强网杯 2019 copperstudy

拖拖拉拉终于把这题复现了…

开局计算哈希, 爆破爆破

from Crypto.Util.number import *
import hashlib
from pwn import *
import gmpy2

r = remote('node3.buuoj.cn', 26182)
r.recvuntil("hexdigest()=")
digest = r.recvline()
r.recvuntil("'hex')=")
skr5 = r.recvline()[:-1]

def proof(skr5, digest):
    for i in range(64*256*256, 256*256*256):
        result = hashlib.sha256(skr5.decode('hex') + long_to_bytes(i)).hexdigest()
        if result == digest:
            print("found it!")
            return ((skr5.decode('hex')+long_to_bytes(i)).encode('hex'))
            

skr = proof(skr5, digest)
r.recvuntil("encode('hex')=")
r.sendline(skr)
r.interactive()

challenge1

n
e
c
m的高位

解

n = 13112061820685643239663831166928327119579425830632458568801544406506769461279590962772340249183569437559394200635526183698604582385769381159563710823689417274479549627596095398621182995891454516953722025068926293512505383125227579169778946631369961753587856344582257683672313230378603324005337788913902434023431887061454368566100747618582590270385918204656156089053519709536001906964008635708510672550219546894006091483520355436091053866312718431318498783637712773878423777467316605865516248176248780637132615807886272029843770186833425792049108187487338237850806203728217374848799250419859646871057096297020670904211 
e = 3
c = 15987554724003100295326076036413163634398600947695096857803937998969441763014731720375196104010794555868069024393647966040593258267888463732184495020709457560043050577198988363754703741636088089472488971050324654162166657678376557110492703712286306868843728466224887550827162442026262163340935333721705267432790268517
m_high = 2519188594271759205757864486097605540135407501571078627238849443561219057751843170540261842677239681908736

kbits = 72
PR.<x> = PolynomialRing(Zmod(n))
f = (m_high + x)^e - c
solv = f.small_roots(X=2^kbits, beta=1)[0]
print("x: %s" % hex(int(solv)))

challenge2

n
e
c
p的高位

能在n的因子的整数域中等于0也可以构造方程

n=12784625729032789592766625203074018101354917751492952685083808825504221816847310910447532133616954262271205877651255598995305639194329607493047941212754523879402744065076183778452640602625242851184095546100200565113016690161053808950384458996881574266573992526357954507491397978278604102524731393059303476350167738237822647246425836482533150025923051544431330502522043833872580483142594571802189321599016725741260254170793393777293145010525686561904427613648184843619301241414264343057368192416551134404100386155751297424616254697041043851852081071306219462991969849123668248321130382231769250865190227630009181759219 
e=65537
c=627824086157119245056478875800598959553774250161670787506083253960788230737588761787385686125828765665617567887904228030839535317987589608761534500003128247164233774794784231518212804270056404565710426613938264302998015421153393879729263551292024543756422702956470022959537221269172084619081368498693930550456153543628170306324206266216348386707008661128717431426237486511309767286175518238620230507201952867261283880986868752676549613958785288914989429224582849218395471672295410036858881836363364885164276983237312235831591858044908369376855484127614933545955544787160352042318378588039587911741028067576722790778
p_high128 = 97522826022187678545924975588711975512906538181361325096919121233043973599759518562689050415761485716705615149641768982838255403594331293651224395590747133152128042950062103156564440155088882592644046069208405360324372057140890317518802130081198060093576841538008960560391380395697098964411821716664506908672

pbits = 128
PR.<x> = PolynomialRing(Zmod(n))
f = p_high128 + x
x0 = f.small_roots(X=2^pbits, beta=0.3)[0]
p = p_high128 + int(x0)
q = n // p
print("p: %s" % p)
print("q: %s" % q)

然后解出明文即可

challenge3

n
e
c
d的低512位

就硬套


def partial_p(p0, kbits, n):
    PR.<x> = PolynomialRing(Zmod(n))
    nbits = 1024

    f = 2^kbits*x + p0
    f = f.monic()
    roots = f.small_roots(X=2^(nbits//2-kbits), beta=0.2) 
    if roots:
        x0 = roots[0]
        p = gcd(2^kbits*x0 + p0, n)
        return ZZ(p)

def find_p(d0, kbits, e, n):
    X = var('X')

    for k in xrange(1, e+1):
        results = solve_mod([e*d0*X - k*X*(n-X+1) + k*n == X], 2^kbits)
        for x in results:
            p0 = ZZ(x[0])
            p = partial_p(p0, kbits, n)
            if p:
                return p

if __name__ == "__main__":
    n=92896523979616431783569762645945918751162321185159790302085768095763248357146198882641160678623069857011832929179987623492267852304178894461486295864091871341339490870689110279720283415976342208476126414933914026436666789270209690168581379143120688241413470569887426810705898518783625903350928784794371176183
    e=3
    c=56164378185049402404287763972280630295410174183649054805947329504892979921131852321281317326306506444145699012788547718091371389698969718830761120076359634262880912417797038049510647237337251037070369278596191506725812511682495575589039521646062521091457438869068866365907962691742604895495670783101319608530
    d = 787673996295376297668171075170955852109814939442242049800811601753001897317556022653997651874897208487913321031340711138331360350633965420642045383644955

    nbits = n.nbits()
    kbits = 512
    d0 = d & (2^kbits-1)
    p = find_p(d0, kbits, e, n)
    print "found p: %d" %p
    q = n // p
    print "d: %d" % inverse_mod(e, (p-1)*(q-1))

解出明文发送

challenge4

n1
c1
n2
c2
n3
c3
e=3

常规的广播攻击, 使用中国剩余定理

import gmpy2
from Crypto.Util.number import *

e=3
n1=78642188663937191491235684351005990853149481644703243255021321296087539054265733392095095639539412823093600710316645130404423641473150336492175402885270861906530337207734106926328737198871118125840680572148601743121884788919989184318198417654263598170932154428514561079675550090698019678767738203477097731989
c1=23419685303892339080979695469481275906709035609088426118328601771163101123641599051556995351678670765521269546319724616458499631461037359417701720430452076029312714313804716888119910334476982840024696320503747736428099717113471541651211596481005191146454458591558743268791485623924245960696651150688621664860
n2=98174485544103863705821086588292917749386955237408645745685476234349659452606822650329076955303471252833860010724515777826660887118742978051231030080666542833950748806944312437614585352818344599399156268450521239843157288915059003487783576003027303399985723834248634230998110618288843582573006048070816520647
c2=72080679612442543693944655041130370753964497034378634203383617624269927191363529233872659451561571441107920350406295389613006330637565645758727103723546610079332161151567096389071050158035757745766399510575237344950873632114050632573903701015749830874081198250578516967517980592506626547273178363503100507676
n3=91638855323231795590642755267985988356764327384001022396221901964430032527111968159623063760057482761918901490239790230176524505469897183382928646349163030620342744192731246392941227433195249399795012672172947919435254998997253131826888070173526892674308708289629739522194864912899817994807268945141349669311
c3=22149989692509889061584875630258740744292355239822482581889060656197919681655781672277545701325284646570773490123892626601106871432216449814891757715588851851459306683123591338089745675044763551335899599807235257516935037356212345033087798267959242561085752109746935300735969972249665700075907145744305255616

assert(gmpy2.gcd(n1, n2)==1)
assert(gmpy2.gcd(n1, n3)==1)

def chinese_remainder(N, C):
    all_n = reduce(lambda a,b: a*b, N)
    result = 0
    for i in range(len(C)):
        ni = all_n // N[i]
        ni_inv = gmpy2.invert(ni, N[i])
        result += ni_inv * C[i] * ni
    
    return result % all_n


N = [n1, n2, n3]
C = [c1, c2, c3]

result = chinese_remainder(N, C)
all_n = reduce(lambda a,b: a*b, N)
# print all_n

i = 0
while True:
    root, exact = gmpy2.iroot(result+i*all_n, 3)
    if exact:
        print root
        exit(0)
    i+=1

challenge5

c = encrypt(m)
x = encrypt(m+1)
n
e=3

相关消息攻击, 套ctfwiki的公式

import gmpy2

p1=1
p2=0
c2 =112992730284209629010217336632593897028023711212853788739137950706145189880318698604512926758021533447981943498594790549326550460216939216988828130624120379925895123186121819609415184887470233938291227816332249857236198616538782622327476603338806349004620909717360739157545735826670038169284252348037995399308
c1 =112992730284209629010217336632593897028023711212853788739137950706145189880318698604512926758021552486915464025361447529153776277710423467951041523831865232164370127602772602643378592695459331174613894578701940837730590029577336924367384969935652616989527416027725713616493815764725131271563545176286794438175
n =113604829563460357756722229849309932731534576966155520277171862442445354404910882358287832757024693652075211204635679309777620586814014894544893424988818766425089667672311645586528776360047956843961901352792631908859388801090108188344342619580661377758180391734771694803991493164412644148805229529911069578061
a = 1
b = p1-p2


def getmessage(a, b, c1, c2, n):
    b3 = gmpy2.powmod(b, 3, n)
    part1 = b * (c1 + 2 * c2 - b3) % n
    part2 = a * (c1 - c2 + 2 * b3) % n
    part2 = gmpy2.invert(part2, n)
    return part1 * part2 % n


message = getmessage(a, b, c1, c2, n) -p2
print message
message = hex(message)[2:]

print message

challenge6

e
c
n
assert(d<n的0.27次方)

只要d小于n的0.292次方就有Boneh and Durfee attack

https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/boneh_durfee.sage

改改数据, 跑一下就有了

整合

from Crypto.Util.number import *
import os
import hashlib
from pwn import *
import gmpy2

r = remote('node3.buuoj.cn', 26182)
r.recvuntil("hexdigest()=")
digest = r.recvline()
r.recvuntil("'hex')=")
skr5 = r.recvline()[:-1]

def proof(skr5, digest):
    for i in range(64*256*256, 256*256*256):
        result = hashlib.sha256(skr5.decode('hex') + long_to_bytes(i)).hexdigest()
        if result == digest:
            print("found it!")
            return ((skr5.decode('hex')+long_to_bytes(i)).encode('hex'))
            

skr = proof(skr5, digest)
r.recvuntil("encode('hex')=")
r.sendline(skr)
# r.interactive()

x0 = 0x35343237323432377dL
m_high = 2519188594271759205757864486097605540135407501571078627238849443561219057751843170540261842677239681908736
ans1 = long_to_bytes(x0 + m_high).encode('hex')

r.recvuntil("encode('hex')=")
r.sendline(ans1)

p = 97522826022187678545924975588711975512906538181361325096919121233043973599759518562689050415761485716705615149641768982838255403594331293651224395590747133152128042950062103156564440155088882592644046069208405360324372057140890317518802130081198060093576841538008960560661715295741651653499691458486798196487
q = 131093675711613661161476275473445206682597559447006571385482255727609238786596952165801814021602699749876712682307789568113374768689632642728986573211776526473651771104432443501294668372441525987174391472994271054873305324343666279426741897612827889525440428582592216151586138881806196331920758968403508531637
e=65537
c = 627824086157119245056478875800598959553774250161670787506083253960788230737588761787385686125828765665617567887904228030839535317987589608761534500003128247164233774794784231518212804270056404565710426613938264302998015421153393879729263551292024543756422702956470022959537221269172084619081368498693930550456153543628170306324206266216348386707008661128717431426237486511309767286175518238620230507201952867261283880986868752676549613958785288914989429224582849218395471672295410036858881836363364885164276983237312235831591858044908369376855484127614933545955544787160352042318378588039587911741028067576722790778
d = gmpy2.invert(e, (q-1)*(p-1))
m = long_to_bytes(pow(c, d, p*q)).encode('hex')
r.recvuntil("encode('hex')=")
r.sendline(m)

d = 61931015986410954522379841763963945834108214123439860201390512063842165571430799255094107119082046571341221952786658415661511901536119262974324197242727901361853519060099176095718398341546521709753140715090423775413590463159715914497625346364363050316931779727154988269576808476796380941227956316802411370267
n=92896523979616431783569762645945918751162321185159790302085768095763248357146198882641160678623069857011832929179987623492267852304178894461486295864091871341339490870689110279720283415976342208476126414933914026436666789270209690168581379143120688241413470569887426810705898518783625903350928784794371176183
c=56164378185049402404287763972280630295410174183649054805947329504892979921131852321281317326306506444145699012788547718091371389698969718830761120076359634262880912417797038049510647237337251037070369278596191506725812511682495575589039521646062521091457438869068866365907962691742604895495670783101319608530
m = long_to_bytes(pow(c, d, n)).encode('hex')
r.recvuntil("encode('hex')=")
r.sendline(m)


m = 2519188594271759205757864486234199030368509477419996746572813835802776507456368520243429255706508061522045
m = long_to_bytes(m).encode('hex')
r.recvuntil("encode('hex')=")
r.sendline(m)

m = "464c41477b325e3872736133393863663864663763323636363162623763623635623262396661653235657d"
r.recvuntil("encode('hex')=")
r.sendline(m)

d = 776765455081795377117377680209510234887230129318575063382634593357724998207571
c=0xe3505f41ec936cf6bd8ae344bfec85746dc7d87a5943b3a7136482dd7b980f68f52c887585d1c7ca099310c4da2f70d4d5345d3641428797030177da6cc0d41e7b28d0abce694157c611697df8d0add3d900c00f778ac3428f341f47ecc4d868c6c5de0724b0c3403296d84f26736aa66f7905d498fa1862ca59e97f8f866cL

n = 0xbadd260d14ea665b62e7d2e634f20a6382ac369cd44017305b69cf3a2694667ee651acded7085e0757d169b090f29f3f86fec255746674ffa8a6a3e1c9e1861003eb39f82cf74d84cc18e345f60865f998b33fc182a1a4ffa71f5ae48a1b5cb4c5f154b0997dc9b001e441815ce59c6c825f064fdca678858758dc2cebbc4d27L

m = long_to_bytes(pow(c,d,n)).encode('hex')
r.recvuntil("encode('hex')=")
r.sendline(m)
r.interactive()

image-20211114141951612