Post cover image

November 1, 2026

It’s Not My Fault 1 —picoCTF 2021 Cryptography writeup

Challenge by rkm0959

By GhostPacket

7 min read

description:

What do you mean RSA with CRT has an attack that's not a fault attack?

None

Another fun challenge. I really enjoyed this one so let's get start on how to solve this.

Challenge Overview:

When I launch the instance as we can see it need to connect to the server and it given the source code for the encryption program.

None

Here it asked for a string that starts with a certain number that can creates an md5 hash that ends in with those six hex digits. But we don't know what comes next so let's look at the program.

Analyze the given program:

So the challenge basically has three stages:

  1. proof of work (PoW): find the string that satifies the MD5 condition
  2. RSA key generation: the server generate two 512-bits primes and reveals a public modulus and a clue
  3. Recover the primes: submit the sum p+q to receive the flag

so Let's through each one:

Understanding the MD5 proof of work

before we get into the RSA vulnerability, we need to pass the server's Proof of Work check.

vals1 = "".join([random.choice(string.digits) for _ in range(5)])
vals2 = "".join([random.choice(string.hexdigits.lower()) for _ in range(6)])
user_input = input("Enter a string that starts with \"{}\" (no quotes) which creates an md5 hash that ends in these six hex digits: {}\n".format(vals1, vals2))
user_hash = hashlib.md5(user_input.encode()).hexdigest()

if user_input[:5] == vals1 and user_hash[-6:] == vals2:
 p, q = gen_key()
 n = p * q
 print("Public Modulus : ", n)
 get_clue(p, q, 20)
 get_flag(p, q)

The server generates two random values:

vals1 — five digit numeric string that the input must start with

vals2 — six characters hexadecimal string that the MD5 hash must end with

But we don't know what characters should follow the required prefix, so we need to search for the valid input.

How does the MD5 condition work?

The program calculates the MD5 hash of our input: The encode() converts the string into bytes and hexdigest() returns the resulting hash as a hexadecimal string.

It checks two conditions: 1. user_input[:5] == vals1 and 2. user_input[-6:] == vals2

The first checks whether our input starts with the required five digits and second check whether the last six hexadecimal characters of the MD5 hash match the target.

since hexadecimal has 16 possible values, the number of possible six-character suffixes is: 16**6 = 16,777,216. So there's a random candidate has a probability of 1/16,777,216 of satisfying the hash condition. Here we can just automate it with python if the candidate found then we will submitted it to the server to continue to the next step:

import socket
import re
import hashlib

chunk_size = 100_000

# connect to the server for the given host and port
def connection(host, port):
    client_socket = socket.socket(socket.AF_INET, socket.SOCK_STREAM)

    try:
        print(f"CONNECTING to {host} on port {port}...")
        client_socket.connect((host, port))
        print("CONNECTED successfully!")

        while True:
            response = client_socket.recv(4096)

            if not response:
                break

            text = response.decode('utf-8', errors='replace')
            print("RECEIVED from server:", text)

            decode(text, client_socket)

    except ConnectionRefusedError:
        print(f"ERROR: Could not connect to {host}:{port}")

    except Exception as e:
        print(f"An unexpected error occurred: {e}")

    finally:
        client_socket.close()
        print("CONNECTION closed.")

# received the response from the server
def decode(text, client_socket):
    match = re.search(r'"([^"]+)".*?([0-9a-fA-F]{6})', text, re.S)

    if match:
        prefix = match.group(1)
        target = match.group(2)

        print("Prefix:", prefix)
        print("Target MD5 suffix:", target)

        result = search(0, prefix, target)

        if result:
            candidate, md5_hash = result

            print("* Candidate:", candidate)
            print("* MD5:", md5_hash)

            # send the result to the server
            client_socket.sendall((candidate + "\n").encode())

# brute force to find the match prefix to the target hash
def search(start, prefix, target):
    while True:
        for i in range(start, start + chunk_size):
            candidate = prefix + str(i)

            h = hashlib.md5(
                candidate.encode()
            ).hexdigest()

            if h.endswith(target):
                return candidate, h

        start += chunk_size

if __name__ == "__main__":
    host = "your host here"
    port = port

    connection(host, port)

As you can see here it works and it gives us the clue for the next step:

(Reminder! Everytime you reconnected to the server the value change!)

None None

Okay we got the Public Modulus (N) and Clue (e) let's move on to the next step.

RSA key generation

After passing the MD5 proof of work, the server generates two prime numbers using the gen_key()

def gen_key():
 while True:
  p = getPrime(512)
  q = getPrime(512)
  if GCD(p-1, q-1) == 2:
   return p, q

The function generates two 512-bit prime numbers, (p) and (q). It also checks that the greatest common divisor (GCD) of (p-1) and (q-1) is 2. Once this condition is met, the server returns both primes.

The RSA modulus is then calculated: n = p * q

The server gives us (N), but it does not reveal the two primes. Normally, finding (p) and (q) from a large RSA modulus is very difficult. However, this challenge gives us another piece of information that can help.

Understanding the CRT values

def get_clue(p, q, BITS):
 while True:
  d_p = random.randint(1, 1 << BITS)
  d_q = random.randint(1, q - 1)
  # Ensure d_p is coprime with p-1
  if GCD(d_p, p - 1) != 1:
   continue

  # Ensure d_q is coprime with q-1
  if GCD(d_q, q - 1) != 1:
   continue

  if d_p % 2 == d_q % 2:
   d = CRT(d_p, p - 1, d_q, q - 1)
   e = inverse(d, (p - 1) * (q - 1))
   print("Clue : ", e)
   return

The server generate two values:

  • d_p = A small number between 1 and 2**20
  • d_q = A much larger number bitween 1 and q-1

The program then check the coprime to their respective prime-minus-one values. These make sure that the values can be used in the next calculation. The program requires d_p and d_q to have the same parity. This helps ensure that the CRT result d is coprime to (p-1)(q-1), so the modular inverse used to calculate e exists.

The server combines d_p and d_q using the CRT(Chinese Remainder Theorem) to creates a new value d. So the d has the same remainder as d_p when divided by p — 1 and the same remainder as d_q when divided by q — 1.

The server creates d first, then calculates e as its modular inverse. Because d_p is small, the public exponent e gives us a way to recover a factor of N.

Why is this a problem?

We know that: d and d_p have the same remainder when divided by p — 1.

Multiplying d by e gives a remainder of 1 when divided by (p — 1) * (q — 1). This means that multiplying d_p by e also gives a remainder of 1 when divided by p — 1.

In Python, we can write this as: (e * d_p) % (p — 1) == 1

This is the key to the attack.

Since d_p is only 20 bits long, we can test its possible values and use the public exponent to find the prime p.

Recovering the RSA primes

We know that d_p is a small number between 1 and 2^20.

Instead of trying to factor the entire RSA modulus, we can use this small value to recover one of the primes. From the previous section, we know that: (e * d_p) % (p — 1) == 1

This means e * d_p — 1 is a multiple of p — 1. For the correct value of d_p, 2^(e * d_p — 1) — 1 is therefore divisible by p.

We can test the possible values of d_p and use the public exponent to find a value that helps us recover a factor of the RSA modulus.

This avoids factoring the entire RSA modulus directly.

How does the code recover the primes?

The factor_rsa() function uses the public exponent to calculate two values:

multiplier = pow(2, 2 * e, N) value = pow(2, e — 1, N)

It then repeatedly updates value and calculates: factor = gcd(value — 1, N). The greatest common divisor (GCD) can reveal a prime factor of N.

If the result is greater than 1 but smaller than N, we have found a factor.

The program then calculates the other prime and checks whether their product equals the original modulus.

Once the factorization is verified, it submits the sum of the primes to the server.

This is how we recover the RSA primes without directly factoring the 1024-bit modulus.

Once we recover p, finding q is easy: q = N // p

Finally, we submit the sum of both primes: p + q to receive the flag.

Full code:

import socket
import re
import hashlib
from math import gcd

chunk_size = 100_000

data = {
    "N": None,
    "e": None,
    "pow_solved": False,
    "submitted": False
}

def connection(host, port):
    client_socket = socket.socket(socket.AF_INET, socket.SOCK_STREAM)

    try:
        print(f"CONNECTING to {host} on port {port}...")
        client_socket.connect((host, port))
        print("CONNECTED successfully!!!!")

        while True:
            response = client_socket.recv(4096)
            if not response:
                break

            text = response.decode('utf-8', errors='replace')
            print("RECEIVED from server: ", text)
            decode(text, client_socket)

    except ConnectionRefusedError:
        print(f"ERROR: Could not connect to {host} {port}")
    except Exception as e:
        print(f"An unexpected error occurred: {e}")

    finally:
        client_socket.close()
        print("CONNECTION closed.")

def decode(text, client_socket):

    global data

    if not data["pow_solved"]:
        match = re.search(r'"([^"]+)".*?([0-9a-fA-F]{6})', text, re.S)

        if match:
            prefix = match.group(1)
            target = match.group(2)

            result = search(0, prefix, target)

            if result:
                candidate, md5_hash = result

                print("[+] Candidate:", candidate)
                print("[+] MD5:", md5_hash)

                client_socket.sendall((candidate + "\n").encode())

                data["pow_solved"] = True

    # Extract N
    match = re.search(r"Public Modulus\s*:\s*(\d+)", text)

    if match:
        data["N"] = int(match.group(1))
        print("[+] N received")

    # Extract e
    match = re.search(r"Clue\s*:\s*(\d+)", text)

    if match:
        data["e"] = int(match.group(1))
        print("[+] e = ", data["e"])

    # Factor RSA
    if (data["N"] is not None and data["e"] is not None and not data["submitted"]):
        result = factor_rsa(data["N"], data["e"])

        if result:
            p, q = result
            answer = p + q

            print("[+] Submitting:", answer)

            data["submitted"] = True
            client_socket.sendall((str(answer) + "\n").encode())

def search(start, prefix, target):
    while True:
        for i in range(start, start + chunk_size):
            candidate = prefix + str(i)
            h = hashlib.md5(candidate.encode()).hexdigest()

            if h.endswith(target):
                return candidate, h
        start += chunk_size

def factor_rsa(N, e):
    print("* Starting RSA factorization...")

    multiplier = pow(2, 2 * e, N)
    value = pow(2, e - 1, N)

    # Each step represents the next odd dp:
    # value = 2^(e*dp - 1) mod N
    for dp in range(1, 2**20 + 1, 2):

        factor = gcd(value - 1, N)

        if 1 < factor < N:
            p = factor
            q = N // p

            print("[+] Factor FOUND!")
            print("p =", p)
            print("q =", q)
            print("p + q =", p + q)

            print("VERIFICATION for p and q...")
            if p * q == N:
                print("* Factorization verified!")
                return p, q
            else:
                print("Invalid factorization!")
                return None

        value = (value * multiplier) % N

    print("[-] Factor NOT found!")
    return None

if __name__ == "__main__":
    host = "YOUR HOST HERE"
    port = YOUR PORT HERE

    connection(host, port)

And there's the flag

None

Conclusion

This challenge shows how a small CRT private exponent can make RSA vulnerable. Although the modulus is 1024 bits long, the public exponent is related to a small CRT value. Testing its possible values lets us recover a prime factor, calculate p + q, and obtain the flag. The lesson is that RSA security depends not only on the modulus size, but also on how its private key is generated.

Happy CTF!