Challenge Description#

The Riddler wasn’t very delighted by the previous challenge. His encryption wasn’t as clever as he thought! So, he concocted this new challenge for you.

Analysis#

The provided chall.py looked like normal RSA at first glance, but one line immediately made it suspicious: it generated a 256-bit private exponent d first, and then computed e = inverse(d, phi). For a 1024-bit modulus, that is classic small-private-exponent territory, so Wiener’s attack is the first thing to try.

python solve_wiener.py

[+] Wiener success: d=76381617665639887224595810537426977909971937293760169916794015421409354433769
b'rentry.co/actf1'

That decrypted output gave a clue URL chain rather than the final flag, and the chain had intentional trolling/decoy branches. The interesting part was that one valid signed branch eventually reached a page with an RSA script that obfuscated outputs with XOR masks (N ^ k ^ c, e ^ k ^ l, c ^ e ^ l). The 10-bit prime mask l was the weak point: once l is brute-forced, the hidden ciphertext is recovered uniquely.

import requests,html,re,gmpy2
from bs4 import BeautifulSoup
from Crypto.Util.number import long_to_bytes

session=requests.Session()

def parse_vals(url):
    src=session.get(url,timeout=20).text
    s=BeautifulSoup(src,'html.parser')
    art=s.find('article')
    txt=html.unescape(art.get_text('\n',strip=True) if art else s.get_text('\n',strip=True))
    vals={}
    for k,v in re.findall(r'\b([ANercp])\s*=\s*(\d+)',txt):
        if k not in vals:
            vals[k]=int(v)
    return txt,vals

# someunrealatedbsname -> lemon
_,v=parse_vals('https://rentry.co/someunrealatedbsname')
m,_=gmpy2.iroot(v['p'],3)
pt=long_to_bytes(int(m)).decode()
next_url=pt if pt.startswith('http') else 'https://'+pt
print('next_from_someunrealatedbsname =',next_url)

# lemon equations
text,_=parse_vals(next_url)
N_out=int(re.search(r'#\s*N\s*=\s*(\d+)',text).group(1))
e_out=int(re.search(r'#\s*e\s*=\s*(\d+)',text).group(1))
c_out=int(re.search(r'#\s*c\s*=\s*(\d+)',text).group(1))
N=N_out ^ e_out ^ c_out
X=N_out ^ N
Y=e_out ^ 65537
Z=c_out ^ 65537

l=None
for cand in range(512,1024):
    if gmpy2.is_prime(cand)==0:
        continue
    k=Y^cand
    c=Z^cand
    if c>=N or k.bit_length()!=512:
        continue
    if gmpy2.is_prime(k)==0:
        continue
    if (k^c)!=X:
        continue
    l=cand
    break

print('recovered_l =',l)

next_from_someunrealatedbsname = https://rentry.co/lemonyrick67691
recovered_l = 971

When l = 971 dropped out uniquely, it confirmed the branch was real and not another fake path.

Decrypting that recovered ciphertext pointed to nakedcitrus21, where the final RSA instance used e = 3 and looked like standard RSA again, except direct cube root failed. That’s exactly where the low-exponent relation m^3 = c + kN matters: if plaintext is small enough, a relatively small k exists and exact cube root works on c + kN.

I did burn time on decoy routes and wrong-looking endpoints before committing to this arithmetic route, which was exactly the challenge’s troll design.

Once I switched to brute-forcing k and testing exact cube roots, the flag appeared instantly at k = 41.

Solution#

import gmpy2
from Crypto.Util.number import long_to_bytes

N=61335101030478919720870258161372353921031836932008941567053217346527987820466076329261287463549421023809770372764569882735210394312462119856344422486841273928867940096663293663837886684820260400512030980133100917131135731484950367326809489778133379519412767375186265844153579533926857758944406865260292926799
c=22940309699977793906056877062420112639761767581900180883624329834487505119909951332117055492787889879690909162380572981397616990971145682582277715812733237198794876740691081318300157652208914119477544854893277826277566422100085011803508179920690747948460594038047416895021666000373415917463719352822333151422

for k in range(5_000_001):
    x=c + k*N
    m,exact=gmpy2.iroot(x,3)
    if exact:
        print(f"k={k}")
        print(long_to_bytes(int(m)).decode('latin1','ignore'))
        break

python solve_final.py

k=41
apoorvctf{_h3h3_ma0r_RSA_f4ilur33_modes_67}