2024年第四届“网鼎杯”网络安全比赛---朱雀组Crypto- WriteUp

前言：本次比赛已经结束，用于赛后复现，欢迎大家交流学习！

Crypto：

Crypto-2：

给出了p的高256位，爆破8位即可用copersmith

from Crypto.Util.number import *

from tqdm import trange

import gmpy2



n = 0x00b8cb1cca99b6ac41876c18845732a5cbfc875df346ee9002ce608508b5fcf6b60a5ac7722a2d64ef74e1443a338e70a73e63a303f3ac9adf198595699f6e9f30c009d219c7d98c4ec84203610834029c79567efc08f66b4bc3f564bfb571546a06b7e48fb35bb9ccea9a2cd44349f829242078dfa64d525927bfd55d099c024f

p_high = 0xe700568ff506bd5892af92592125e06cbe9bd45dfeafe931a333c13463023d4f

pbits = 512

e = 0x10001

c = bytes_to_long(open('flag.enc','rb').read())





for i in trange(2**8):

     p4 = p_high<<8			#这里需要先爆破8位，使得知道264位以后再恢复p

     p4 = p4 + i

     kbits = pbits - p4.nbits()

     p4 = p4 << kbits

     R.<x> = PolynomialRing(Zmod(n))

     f = x + p4

     x = f.small_roots(X=2^kbits, beta=0.4, epsilon=0.01)

     if x:

         p = p4 + int(x[0])

         q = n // p

         d = gmpy2.invert(e,(p-1)*(q-1))

         m = pow(c,d,n)

         print(long_to_bytes(int(m)))

         break

Crypto-3：

from Crypto.Util.number import *

import gmpy2

import sys



def HGCD(a, b):

    if 2 * b.degree() <= a.degree() or a.degree() == 1:

        return 1, 0, 0, 1

    m = a.degree() // 2

    a_top, a_bot = a.quo_rem(x^m)

    b_top, b_bot = b.quo_rem(x^m)

    R00, R01, R10, R11 = HGCD(a_top, b_top)

    c = R00 * a + R01 * b

    d = R10 * a + R11 * b

    q, e = c.quo_rem(d)

    d_top, d_bot = d.quo_rem(x^(m // 2))

    e_top, e_bot = e.quo_rem(x^(m // 2))

    S00, S01, S10, S11 = HGCD(d_top, e_top)

    RET00 = S01 * R00 + (S00 - q * S01) * R10

    RET01 = S01 * R01 + (S00 - q * S01) * R11

    RET10 = S11 * R00 + (S10 - q * S11) * R10

    RET11 = S11 * R01 + (S10 - q * S11) * R11

    return RET00, RET01, RET10, RET11

    

def GCD(a, b):

    print(a.degree(), b.degree())

    q, r = a.quo_rem(b)

    if r == 0:

        return b

    R00, R01, R10, R11 = HGCD(a, b)

    c = R00 * a + R01 * b

    d = R10 * a + R11 * b

    if d == 0:

        return c.monic()

    q, r = c.quo_rem(d)

    if r == 0:

        return d

    return GCD(d, r)



sys.setrecursionlimit(500000)



n1 = 46994335119752756509295563273644018207372437765472265663641969615870434649870172687711336119178476731707184071004952832066023502817858922050333696147278803794579361275375126259907918549399847213059844795524428354261714653121692582331027749211493858306453667935016549085360033613631067207061043880115121598962110616155562901846204247465460970460199073739292905462216078043392395114502994197819280075092818942982603177739751892161678322940701448492756420067768637842557026865307595566180909536549522253144031734977212534244571704403691638817139603787139183257554425149405808562098424603264387155486261738291201472340352391

n2 = 16976940907141191524915804499951951599097024510818489668879976514721679457799770728089555354636545350649925890442528319161801605921579588526654791259724057279137519961488033020252287291656224996559845743701416369311612554321667335443418374008955791237572115480942740883337659354946753897515362968288787775973679663087549902052834470568223797434895230309683907862913802778136943295386037545850573702404179634561691835378455616724949344536695840131493043451083253876120316451193093943057146831832699116608334542232364997054535258690377988973313999659509515527448391939826560776605356310573531843676266398565276101510029

n22 = 36411530853306134650264922004243230789578567724848633072235567209396268937793967740840652891507150988934473209257678404824253786278354088188390849648230052408289839466487412221995353670688546953660918964880243399052047334774328642066482644759267410757068380646549682108897462561270352289713894825761682839541110704279580406677692145731871923819604104525631319112589270885702852325198972148331330622015745319864858600319231335192994724027402115404237271512429501511126745777802735039211692592419147477615289600437180622597687832926895508311856277663498164572827860273972198929500903338268219335130382722268336214976042

n3 = 21226342903519534285704039882517125493795254854398682031383220268196433752075453643793049930458409496501461364842263780716599044573472994756306842377996628221505793163345085310959982378400333469066510661862233433012101801971093682929377066833668523917150410559059871941217104903416187874137499834716703973567800989192226779852732764629767211879833127201510149229683409885749849769992849238187983773625783302822977444881786880085459631032114161881530793073480211272526557216580382426240205299262699361842634152273785508127206291906598310431383694685205902446688152373743788426712423020706959735024415865092732865293579

n = 19200751218807086109753585680575754542082218941447307423137776192000278638223531900870979886440646382572944765791998502777800968087411516141316151136038574929174075944033279652394413631362165307728020601616420974300745352308691582297884104984804426129732048593928551212972068865439525515893127416831193018078920195294960658070386235303119382941397098688638535311813138494565312063872100234086554220918850216072480857287537545501163451784114917247368012496289240698205942331461841811192853876743048133216069555958862196216052716205918188818909294300568480346854813619378406414745549741993309728072933212639965842420209

c1 = 12141687753092765754669783940675830448713581449163645536701718573773069294641533345315774400524395912993282498354768039945837224261487080475299072168517385713156203158247568336654731834308671872786353160933613619005116377874975161570966140277643874697751373054295698713456796119408728017676683503913534440646385085389636575390015489314292617682540872972440031779129422252433290117697330366830572038270337066299696360385868714809628744897197112890179467453713145233723691881680439517219988389546696789593902726903494192576858861380642835270848700081419409960522215088312481748912596701475019010221975400877543191195027

c2 = 18671344975076988512476107719711622987157049217462407071825706570480527181436147001821738820485566989301383448587621862627034353591129052899016475842991199430712285197912470481262314752372552644754537903335502976906151622416039395240789105429194458158873730659899128044024578932624430327308839049226169398974549593196858893169326628555925601866140682257990896398722170890530721702632112280595631922141382527353635243846673957989765181865712175794172200610424145223744315723737355016529480510122584370575790398823526020995975020616450936696444211881773753140054718402336533120422812171276792369946574521223325184154908

e = 2999



# factor n1

t1 = gmpy2.iroot(n1 // 2024,2)[0]

for i in range(-100000,100000):

    p1 = t1 + i

    if n1 % p1 == 0:

        q1 = n1 // p1

        break

if p1 > q1:

    p1,q1 = q1,p1



# factor n2

p_add_q = gmpy2.iroot(n22 + 2*n2,2)[0]

p_sub_q = gmpy2.iroot(n22 - 2*n2,2)[0]

p2 = (p_add_q + p_sub_q) // 2

q2 = n2 // p2



if p2 > q2:

    p2,q2 = q2,p2

    

# factor n3

t3 = 2*gmpy2.iroot(n3,2)[0] + 2

p_add_q = t3

p_sub_q = gmpy2.iroot((p_add_q)**2 - 4*n3,2)[0]

p3 = (p_add_q + p_sub_q) // 2

q3 = (p_add_q - p_sub_q) // 2



if p3 > q3:

    p3,q3 = q3,p3



p1,q1 = int(p1),int(q1)

p2,q2 = int(p2),int(q2)

p3,q3 = int(p3),int(q3)



###### Franklin-Reiter

R.<x> = PolynomialRing(Zmod(n))

f = (p1 * x * x + p2 * x + p3)^e - c1

g = (q1 * x * x + q2 * x + q3)^e - c2



res = GCD(f,g)



m = -res.monic().coefficients()[0]

print(m)

flag = long_to_bytes(int(m))

print(flag)