Kidds Crypto - Crypto

Points: 103 | Flag: BCCTF{y0U_h4V3_g0T_70_b3_K1DD1n9_Me} | Solved by: Smothy @ 0xN1umb

what we got

single file kidd.txt with RSA params:

captain kidd sending us RSA with e = 3... hmm ok standard small exponent attack right? ...right??

the solve

attempt 1 - cube root go brr

first thought: e=3, just take the cube root of c lol

from gmpy2 import iroot
m, exact = iroot(c, 3)
# exact = False... nope

ok so m^3 > n. tried c + k*n for k up to 10000, still nothing. captain kidd aint making this easy

attempt 2 - factor n

n is only ~93 digits which is kinda sus for RSA. threw it at factordb and uhhhh

import requests
r = requests.get(f"http://factordb.com/api?query={n}")
# status: 'FF' (fully factored)

13 prime factors lmaooo:

multi-prime RSA with 13 tiny primes. classic captain kidd move fr

attempt 3 - but wait theres more

so naturally tried computing phi(n) and doing d = e^-1 mod phi:

phi = product(p - 1 for p in factors)
d = pow(3, -1, phi)
# ValueError: base is not invertible for the given modulus

bruh. gcd(e, phi(n)) != 1 because every single (p-1) is divisible by 3. so theres no standard RSA inverse. captain kidd really said layers of trolling

the actual solve

gotta compute cube roots modulo each prime individually then CRT everything together. each prime gives 3 possible cube roots = 3^13 = ~1.6 million combinations total

from Crypto.Util.number import long_to_bytes
from sympy.ntheory import nthroot_mod
from sympy.ntheory.modular import crt
from itertools import product

factors = [8532679, 9613003, 9742027, 10660669, 11451571,
           11862439, 11908471, 13164721, 13856221, 14596051,
           15607783, 15840751, 16249801]

# get all cube roots mod each prime
roots_per_prime = []
for p in factors:
    roots = nthroot_mod(c % p, 3, p, all_roots=True)
    roots_per_prime.append(roots)

# CRT over all combos, look for the flag
for combo in product(*roots_per_prime):
    result, _ = crt(factors, list(combo))
    candidate = long_to_bytes(int(result))
    if b'BCCTF' in candidate:
        print(candidate.decode())
        break

and out pops the flag ngl i audibly laughed when i read it

flag

BCCTF{y0U_h4V3_g0T_70_b3_K1DD1n9_Me}

the flag literally says "you have got to be kidding me" which is exactly what i said after the third layer of trolling. multi-prime RSA + non-invertible exponent + pirate themed puns. captain kidd got jokes

tl;dr: not your grandmas RSA. n = 13 small primes, e=3 not invertible mod phi, compute cube roots per prime + CRT through 1.6M combos. ez once you see it but the misdirects were lowkey fire

smothy out ✌️