[crypto 200pts] babyrsa - DownUnderCTF

challnge

This is just RSA for babies!

from Crypto.Util.number import bytes_to_long, getPrime

flag = open('flag.txt', 'rb').read().strip()

p, q = getPrime(1024), getPrime(1024)
n = p*q
e = 0x10001

s = pow(557*p - 127*q, n - p - q, n)

c = pow(bytes_to_long(flag), e, n)

print(f'n = {n}')
print(f's = {s}')
print(f'c = {c}')

数式で表すと以下の通り。

$$n = p * q\\ s \equiv (557p - 127q)^{n - p - q} \bmod{n}\\ c \equiv flag ^e \bmod{n}\\$$

solution

$s$が明らかに怪しいし、肩に乗ってるのよく見る形じゃん

$$s \equiv (557p - 127q)^{n - p - q} \bmod{n}\\ s \equiv (577p - 127q)^{n - p - q \bmod{\varphi(n)}} \bmod{n}$$

$n - p - q \bmod{\varphi(n)}$は$\varphi(n) = (p-1)(q-1) = n - p - q + 1$より

$$\varphi(n) - 1 \bmod{\varphi(n)}$$

となる。これで

$$s \equiv (577p - 127q)^{\varphi(n) - 1 \bmod{\varphi(n)}} \bmod{n}\\ s \equiv (577p - 127q)^{- 1 \bmod{\varphi(n)}} \bmod{n}\\ s \equiv (577p - 127q)^{-1} \bmod{n}$$

となる。ひっくり返すと

$$557p - 127q \equiv s^{-1} \bmod{n}$$

ここで、$557p - 127q < n$は（bit数より）明らかなので、

$$557p - 127q = s^{-1}$$

となる。この式と$n = p * q$を使えば、連立方程式を解くことができる。sagemathに任せる。

solver

from Crypto.Util.number import long_to_bytes, inverse

n = 19574201286059123715221634877085223155972629451020572575626246458715199192950082143183900970133840359007922584516900405154928253156404028820410452946729670930374022025730036806358075325420793866358986719444785030579682635785758091517397518826225327945861556948820837789390500920096562699893770094581497500786817915616026940285194220703907757879335069896978124429681515117633335502362832425521219599726902327020044791308869970455616185847823063474157292399830070541968662959133724209945293515201291844650765335146840662879479678554559446535460674863857818111377905454946004143554616401168150446865964806314366426743287
s = 3737620488571314497417090205346622993399153545806108327860889306394326129600175543006901543011761797780057015381834670602598536525041405700999041351402341132165944655025231947620944792759658373970849932332556577226700342906965939940429619291540238435218958655907376220308160747457826709661045146370045811481759205791264522144828795638865497066922857401596416747229446467493237762035398880278951440472613839314827303657990772981353235597563642315346949041540358444800649606802434227470946957679458305736479634459353072326033223392515898946323827442647800803732869832414039987483103532294736136051838693397106408367097
c = 7000985606009752754441861235720582603834733127613290649448336518379922443691108836896703766316713029530466877153379023499681743990770084864966350162010821232666205770785101148479008355351759336287346355856788865821108805833681682634789677829987433936120195058542722765744907964994170091794684838166789470509159170062184723590372521926736663314174035152108646055156814533872908850156061945944033275433799625360972646646526892622394837096683592886825828549172814967424419459087181683325453243145295797505798955661717556202215878246001989162198550055315405304235478244266317677075034414773911739900576226293775140327580

inv_s = inverse(s, n)
p, q = var("p, q")
eq1 = p*q == n
eq2 = 557*p - 127*q == inv_s
sols = solve([eq1, eq2], p, q, solution_dict=True)
for sol in sols:
    sol_p = int(sol[p])
    sol_q = int(sol[q])
    if sol_p > 0 and sol_q > 0:
        assert sol_p * sol_q == n
        d = inverse(0x10001, n - sol_q - sol_p + 1)
        m = pow(c, d, n)
        print(long_to_bytes(m))
        break

$ sage solver.sage 
b'DUCTF{e4sy_RSA_ch4ll_t0_g3t_st4rt3d}'