Crack the Power

• Description: We received an encrypted message. The modulus is built from primes large enough that factoring them isn't an option, at least not today. See if you can make sense of the numbers and reveal the flag.

---

🔎 Solution

In this challenge we were given the RSA ciphertext parameters c, n, and e. The usual RSA encryption formula is:

c = m^e mod n

However, if the plaintext integer m satisfies m^e < n, the modular reduction does nothing and c = m^e exactly. In that case, recovering m reduces to taking the integer e-th root of c (and checking it is exact).

Noting that in this challenge c < n, it is very likely the ciphertext is just m^20 without reduction, so the plaintext m is the exact 20th integer root of c. I therefore wrote a small Python script to compute the integer e-th root, verify exactness, and show the recovered message.

def integer_nth_root(a, n):
    if a < 0:
        raise ValueError("a must be non-negative")
    if a == 0:
        return 0, True
    high = 1 << ((a.bit_length() + n - 1) // n)
    low = 0
    while low < high:
        mid = (low + high) // 2
        p = mid ** n
        if p == a:
            return mid, True
        if p < a:
            low = mid + 1
        else:
            high = mid
    root = low - 1
    return root, root ** n == a

n = 330718482146262445073605087722432654892918089371316297828608531435318495797325544893455484820330540417867437775901131002123739343744102713874341884624023231667148846496198369587952102180559416241967776708669723410997495828547434243842194867719567072250235295255705964526221292735666018883372906362154810817936735541696458389689326013704820438696359885497330230044342928486947676116561490590554654063154421178945154613345094994330518435742569702144527778671856689337244945526337088647641007693765885884843227159828097212297286902015948375652710873033956468980727848246630605387227470811271610876803097780512254711953298066597002504393702809784111410987942862575126126815101421197400299660864580026113174129133361392328576536574980380482557871006808674903537490518872921610515369022508222926897145373528042806577932191628335060427383918556191234733548965545626921419742627077914522113357815843901578959052161869550469431695921855284051879592657194903088928945894156142849689705788857874755428262201254605782768414053660517827626995221057678268667732020536976367343641149269156246457872207843077790974318291328681460789169986131377732155787380796093138905137579477441259086808277542781362081932020391089714599403888107667808014752548743
e = 20
c = 640637430810406857500566702096274084170639990940796427452789530582646559503351994084630642819529512916638846054876997125498610672759860547044513026189155901787948484482403362927101626272687833687338975274586806476773521319051152565007700259664554159504729296349469197447878298780511371211790491139075259324198933821099017956702371413354628803295864874818977161515794899731393370464401493960680296137943038196051026420339668593694062087137688243381433212756006234063987908213474461679873772065186626550125172019387777864795077647708220020565875602005103342766617735797403630407673089294641211185784285212619751433812891114930402846218495033903895776530373162661788262770661056939054381211058086594610051339027542638474293177226685727990841844712534416552304889091929218453487599517664003095313175878470753143329804811225403499575412027738206715697431439846882937410842894303689755456370733764465958658500789630510555345208100742443149436428977702242274952026208528164224667869714848093393983835310607255359839284538944300791947123779789560912249158012656403415425561337179720951703957058384748262011159099547304088342818511440896654498113757280563601


if c < n:
    root, exact = integer_nth_root(c, e)
    if exact:
        m = root
        m_bytes = m.to_bytes((m.bit_length() + 7) // 8, 'big')
        print("Found m:", m)
        print("Plaintext:", m_bytes.decode('utf-8', errors='replace'))
    else:
        print("c is less than n but not a perfect e-th power.")
else:
    print("c >= n: ciphertext was reduced mod n; cannot get m by simple root.")

Running this script with the provided c, n, and e=20 returns the integer m. Converting m to bytes (big-endian) gave the hidden flag-the recovered plaintext is the challenge flag.

> python script.py
Found m: 2756326214127165272055984685514956805518362929135225102717
Plaintext: picoCTF{t1ny_e_ee65653a}

🚩Flag

picoCTF{t1ny_e_ee65653a}