picoCTF Solutions
picoCTF 2021CryptographyMedium

No Padding, No Problem

Published: April 2, 2026

Description

Oracles can be your best friend, do you know what the decryption oracle is? Connect to the service to get the flag.

Setup

Remote

Connect via netcat to receive n, e, and c from the oracle.

nc mercury.picoctf.net <PORT>

Solution

  1. Step 1Collect n, e, and c from the oracle
    Connect to the service. It prints the public key (n, e) and the encrypted flag ciphertext c. Copy these values. The oracle also allows you to decrypt any ciphertext -- except c itself.
    Learn more

    A decryption oracle is a service that decrypts ciphertexts on demand. Real-world examples include padding oracle attacks on TLS and RSA PKCS#1 v1.5. The restriction here -- refusing to decrypt the target ciphertext directly -- is the defender's only guard. RSA's multiplicative homomorphism lets us work around it.

  2. Step 2Blind the ciphertext using RSA homomorphism
    RSA is multiplicatively homomorphic: Enc(a) * Enc(b) mod n = Enc(a*b) mod n. Encrypt 2 using the public key to get c2 = pow(2,e,n), then compute c_new = c * c2 % n. The oracle will decrypt c_new (it is not the original c), returning 2*m mod n.
    python3 << 'EOF' n = <n> e = <e> c = <c> # Blind: multiply ciphertext by encryption of 2 c2 = pow(2, e, n) c_new = (c * c2) % n print("Submit this to the oracle:", c_new) EOF
    Learn more

    Multiplicative homomorphism means that Enc(x) * Enc(y) mod n = Enc(x*y) mod n. This follows directly from the RSA definition: (x^e * y^e) mod n = (xy)^e mod n. By multiplying the target ciphertext by Enc(2), you create a new ciphertext that decrypts to 2*m -- a related but different plaintext the oracle is willing to return.

    This technique is called blinding and is used both offensively (to extract information from oracles) and defensively (RSA blinding in implementations to prevent timing side-channels during decryption).

  3. Step 3Submit to oracle and divide by 2 to recover m
    Paste c_new into the oracle. It returns 2*m mod n. Divide by 2 modulo n using the modular inverse: m = (2*m) * pow(2, -1, n) % n. Convert the integer to bytes to read the flag.
    python3 << 'EOF' from Crypto.Util.number import long_to_bytes n = <n> two_m = <oracle_response> # oracle's decryption of c_new m = (two_m * pow(2, -1, n)) % n print(long_to_bytes(m).decode()) EOF

Flag

picoCTF{...}

RSA is multiplicatively homomorphic -- multiplying ciphertexts multiplies plaintexts. Blind the target ciphertext to get the oracle to decrypt it.

More Cryptography