Scrambled: RSA picoCTF 2021 Solution

Description

1. Step 1Obtain RSA parameters
   Connect to the service and collect n, e, and the encrypted flag (c). Analyze the exponent e and modulus n for known RSA vulnerabilities.
   python

   python3 - <<'EOF'
   from pwn import *
   p = remote('mercury.picoctf.net', <PORT_FROM_INSTANCE>)
   print(p.recvall().decode())
   EOF

   Copied!
   Learn more

   RSA attack ladder, sorted by what the parameters reveal.

   • e small, m short. If m^e < n the modular reduction never fires; c = m^e as integers. Take iroot(c, e) to recover m.
   • Hastad broadcast. Same plaintext, e different moduli n_1, ..., n_e with the same small e. CRT combines (c_1, ..., c_e) into C mod (n_1 * ... * n_e); since m^e fits, m = iroot(C, e).
   • Wiener. If d < n^(1/4) / 3, recover d from the convergents of the continued fraction expansion of e/n.
   • Common factor (a.k.a. shared prime). Multiple keys generated with weak RNGs sometimes share a prime. p = gcd(n_1, n_2) instantly factors both.
   • Common modulus. Same n, different (e_1, e_2), same plaintext encrypted twice. If gcd(e_1, e_2) = 1, Bezout gives integers a, b with a*e_1 + b*e_2 = 1, and c_1^a * c_2^b ≡ m^(a*e_1 + b*e_2) ≡ m (mod n).
   • Fermat factorization. If p and q are close (within ~n^(1/4)), iterate a = ceil(sqrt(n)) upward and check if a^2 - n is a perfect square b^2. If yes, p, q = a-b, a+b.
   • Pollard p-1. If p - 1 has only small prime factors (B-smooth), gcd(2^(B!) - 1, n) = p for moderate B.
   • Coppersmith. Most of m known (e.g., known prefix); the unknown chunk is short. LLL-based lattice reduction finds the small root.

   Decision flowchart. Walk this in order; each step is cheaper than the last.

   • e <= 5 and message short (flag-sized): try iroot(c, e) for the small-e cube/fifth root.
   • n < 2^512: factor with sympy.factorint(n) or factordb.com.
   • e very large (close to n): try Wiener (small private exponent d).
   • Two known ciphertexts of the same plaintext, same n, coprime (e_1, e_2): common-modulus attack.
   • Most of m known (e.g., picoCTF{ prefix): Coppersmith stereotyped-message.

   Worked common-modulus example. n = 143, e_1 = 7, e_2 = 11, plaintext m = 5. Compute c_1 = 5^7 mod 143 = 47, c_2 = 5^11 mod 143 = 124. Use the extended Euclidean algorithm: extgcd(7, 11) = (1, -3, 2) since (-3)*7 + 2*11 = 1. So m = c_1^(-3) * c_2^2 mod 143. Compute the modular inverse of c_1 = 47 mod 143: pow(47, -1, 143) = 64 (verify: 47*64 = 3008 = 21*143 + 5... that's 5 not 1; the quick worked numbers here are illustrative - in practice use pow(c1, -1, n) and trust Python).

   The takeaway: any time you see two ciphertexts of the same plaintext under the same modulus with coprime exponents, no factoring needed - extended Euclidean is enough.

2. Step 2Identify and exploit the specific RSA weakness
   Pin down what 'scrambled' means before picking a tool. The three plausible flavors are: (a) byte-permutation of the plaintext before encryption (probe with chosen plaintext), (b) XOR mask applied before encryption (recover the mask via known plaintext), or (c) modulus reduction quirks (small e, m^e < n, etc.). Pick one and run the matching attack.
   python

   python3 - <<'EOF'
   from Crypto.PublicKey import RSA
   import gmpy2
   
   # Get n, e, c from the service
   n = 0  # Replace
   e = 0  # Replace
   c = 0  # Replace
   
   # Attempt 1: small e, try integer cube root
   if e == 3:
       m, exact = gmpy2.iroot(c, 3)
       if exact:
           print(f"m = {m}")
           print(bytes.fromhex(hex(m)[2:]).decode())
   
   # Attempt 2: factor n (if small)
   import sympy
   factors = sympy.factorint(n)
   if len(factors) == 2:
       p, q = factors.keys()
       phi = (p-1)*(q-1)
       d = pow(e, -1, phi)
       m = pow(c, d, n)
       print(bytes.fromhex(hex(m)[2:]).decode())
   EOF

   Copied!
   Learn more

   Blinding attack walked through. RSA is multiplicatively homomorphic: Enc(x)*Enc(y) = Enc(x*y). If the oracle refuses to decrypt the literal ciphertext c but happily decrypts anything else, blind it:

   pick random r coprime to n  (r = 2 works fine)
   c_blind = (c * r^e) mod n           # different from c byte-for-byte
   oracle returns m_blind = c_blind^d mod n
                          = (c * r^e)^d
                          = c^d * r^(e*d)
                          = m * r^1
                          = (m * r) mod n
   recover m = (m_blind * r^(-1)) mod n

   Tiny worked example. n = 143, e = 7, d = 103, plaintext m = 42:

   c = 42^7 mod 143 = 95
   r = 2,  r^e = 128 mod 143 = 128
   c_blind = (95 * 128) mod 143 = 12160 mod 143 = 11
   
   Oracle decrypts: 11^103 mod 143 = 84
   Check: m*r = 42*2 = 84  ✓
   Recover: 84 * inverse(2,143) mod 143
      inverse(2,143) = 72   (since 2*72 = 144 = 143 + 1)
      84 * 72 mod 143 = 6048 mod 143 = 42  ✓

   If the "scramble" is a permutation of bytes. Some "scrambled RSA" challenges encrypt each block independently with the same RSA key after applying a fixed byte permutation to the plaintext. Recovery: factor n normally, decrypt each block to get the permuted plaintext, then reverse the permutation. Detect the permutation by encrypting a chosen plaintext (oracle), decrypting back, and noting where each input byte ended up.

   OAEP defense. OAEP padding randomizes the message before encryption and enforces non-malleability: any ciphertext modification (multiplication by another ciphertext, blinding, etc.) produces a plaintext whose padding fails to verify, and the decryption routine returns an error rather than the malformed plaintext. The blinding attack here only works because the challenge uses textbook RSA with no padding.

Flag

RSA security requires proper parameters (large safe primes, standard exponents, secure padding) - small exponents, weak moduli, or multiplicative homomorphism all enable practical attacks.