MiniRSA

🔐 Mini RSA

Category	Author
🔐 Cryptography	Sara

Challenge Prompt

What happens if you have a small exponent? There is a twist though, we padded the plaintext so that (M ** e) is just barely larger than N. Let’s decrypt this: Values:

N: 1615765684321463054078226051959887884233678317734892901740763321135213636796075462401950274602405095138589898087428337758445013281488966866073355710771864671726991918706558071231266976427184673800225254531695928541272546385146495736420261815693810544589811104967829354461491178200126099661909654163542661541699404839644035177445092988952614918424317082380174383819025585076206641993479326576180793544321194357018916215113009742654408597083724508169216182008449693917227497813165444372201517541788989925461711067825681947947471001390843774746442699739386923285801022685451221261010798837646928092277556198145662924691803032880040492762442561497760689933601781401617086600593482127465655390841361154025890679757514060456103104199255917164678161972735858939464790960448345988941481499050248673128656508055285037090026439683847266536283160142071643015434813473463469733112182328678706702116054036618277506997666534567846763938692335069955755244438415377933440029498378955355877502743215305768814857864433151287
e: 3
ciphertext (c): 5709720175026317841944505166332182779419760031115432215563425901875620052791608163398750297304277886495537367793006288112991932717211066611899319963701838062828209254458935983141207100322897221021063116398621664612418813778554568264340430225832578491114653771121708580262264085968492732626559392615882541267670045570974444907542776294075571558085100930760760722416252378077610954367547852126659348372505030936460878940046808104816042562380177143194070773417030106158693436848897733795588156153439353374354378946281556140400056185498147808737766921652179963585037964078150136578302230878368862263000059181416416783313808950923297557514158129515879758935765781055731969330005473022370060498393105532201494698762244481915406880607127300210095672274400200661881861043562650754163743246330438392531433701024389754537178000821754581449881408420282753987132115940027280372196160429387747427183641264436940827271631231510105131701780747726012636466088768725514820344357055715523621362143648027363044170885031058505704

Problem Type

• RSA
• Cube Root Attack

Solve

In RSA, encryption is performed using this formula:
c ≡ m^e(modN)

Where c is the ciphertext, m is the plaintext message (the flag in our case here), and N is the massive modulus.

When the exponent is extremely small (for example, e = 3), the formula becomes:
c≡m³(modN)

If the original message m is relatively short (which CTF flags usually are), then m³ might actually be smaller than N.

If m³<N, the modulo operation (the “wrap-around” effect of the clock math) never actually happens. The modulus N becomes completely irrelevant, and the encryption accidentally degrades into simple middle-school algebra:
c=m³

So to get the flag, we don’t need to factor N. We just need to calculate the integer cube root of the ciphertext.
m=&cupbrt;c​

from Cryptodome.Util.number import long_to_bytes

# The value from challenge
c = 5709720175026317841944505166332182779419760031115432215563425901875620052791608163398750297304277886495537367793006288112991932717211066611899319963701838062828209254458935983141207100322897221021063116398621664612418813778554568264340430225832578491114653771121708580262264085968492732626559392615882541267670045570974444907542776294075571558085100930760760722416252378077610954367547852126659348372505030936460878940046808104816042562380177143194070773417030106158693436848897733795588156153439353374354378946281556140400056185498147808737766921652179963585037964078150136578302230878368862263000059181416416783313808950923297557514158129515879758935765781055731969330005473022370060498393105532201494698762244481915406880607127300210095672274400200661881861043562650754163743246330438392531433701024389754537178000821754581449881408420282753987132115940027280372196160429387747427183641264436940827271631231510105131701780747726012636466088768725514820344357055715523621362143648027363044170885031058505704

def integer_cube_root(x):
    """Finds exact integer cube root using binary search."""
    low = 0
    high = x
    
    while low < high:
        mid = (low + high) // 2
        if mid**3 < x:
            low = mid + 1
        else:
            high = mid
            
    return low

# 1. Calculate the integer cube root of the ciphertext
m = integer_cube_root(c)

# 2. Check our work (if this is true, the attack succeeded)
if m**3 == c:
    # 3. Convert the integer message back into readable text
    flag = long_to_bytes(m)
    print("Flag:", flag.decode('utf-8', errors='ignore'))
else:
    print("Not a perfect cube.")

When we run the Python using our numbers from the challenge, we find that our c was susceptible to the Cube Root Attack: