shulkwisec
KnightCTF 2025/CTF Writeups//3 min read

KnightCTF 2025: cracking RSA with a predictable prime

The challenge handed us a textbook RSA cryptosystem with one modification: the prime was not given to us, it was generated by the challenge author with a custom procedure. The procedure had a weakness, and the weakness was hiding in the hints.

If you know how the prime was generated, you can regenerate it. That is the whole solve.

What we are given

q = 81950208731605030173072901497240676460946134422613059941413476068465656250011
e = 15537
c = 4744275480125761149475439652189568532719997985297643024045625900665305682630452044004013647350658428069718952801828651333880186841289630294789054322237585

q is a known 256-bit prime, e is the public exponent, and c is the ciphertext. We are missing p, and with it the private exponent d.

The hints are three plain strings:

usedistofindouttheseed
thisisthekeytogetyourseed
anothersecrethere

Why a seeded prime breaks RSA

RSA’s security rests on one assumption: the prime factors of the modulus are unpredictable. An attacker with the public key has to find them by factoring a 512-bit number, which is out of reach for anyone without a very large budget.

The moment the prime comes from a deterministic generator instead of the system’s randomness, that assumption is gone. If the seed is short, or derived from published material, the whole keyspace collapses from astronomical to a few thousand values.

So the hunt is not for a mathematical weakness in RSA. It is for the generator.

Recovering the seed

Three hints, one seed, and the phrase “Axe-Ore swirl” pointing at XOR. The natural reading is that the three strings are combined with XOR and then hashed into a seed:

import hashlib

phrases = [
    "usedistofindouttheseed",
    "thisisthekeytogetyourseed",
    "anothersecrethere",
]

blobs = [phrase.encode() for phrase in phrases]
xored = bytes(x ^ y ^ z for x, y, z in zip(*blobs))
seed = int.from_bytes(hashlib.sha256(xored).digest(), "big")

The three phrases have different lengths, and zip truncates to the shortest, which is the intended behaviour here: the tail of the longest phrase is simply not part of the seed material. That detail is easy to get wrong if you pad the inputs instead.

Regenerating the prime

Now the prime. The seed goes into Python’s PRNG, the PRNG produces a 256-bit candidate, and the candidate is bumped to the next prime:

import random
from sympy import nextprime

random.seed(seed)
candidate = random.getrandbits(256)
p = nextprime(candidate)

This is the part that decides whether the challenge is solvable. random.seed with an integer is deterministic across platforms and Python versions for the Mersenne Twister, and random.getrandbits(256) is the first 256 bits it produces. If the author used this exact pair of calls, we get the exact same candidate, and nextprime is a pure function of the candidate.

Decrypting

With both primes in hand the rest is standard RSA:

n = p * q
phi = (p - 1) * (q - 1)
d = mod_inverse(e, phi)
m = pow(c, d, n)
plaintext = m.to_bytes((m.bit_length() + 7) // 8, "big")

The full solve

import hashlib
import random

from sympy import mod_inverse, nextprime

q = 81950208731605030173072901497240676460946134422613059941413476068465656250011
e = 15537
c = 4744275480125761149475439652189568532719997985297643024045625900665305682630452044004013647350658428069718952801828651333880186841289630294789054322237585

phrases = [
    "usedistofindouttheseed",
    "thisisthekeytogetyourseed",
    "anothersecrethere",
]

blobs = [phrase.encode() for phrase in phrases]
xored = bytes(x ^ y ^ z for x, y, z in zip(*blobs))
seed = int.from_bytes(hashlib.sha256(xored).digest(), "big")

random.seed(seed)
p = nextprime(random.getrandbits(256))

n = p * q
phi = (p - 1) * (q - 1)
d = mod_inverse(e, phi)

m = pow(c, d, n)
print(m.to_bytes((m.bit_length() + 7) // 8, "big").decode())

What this teaches

The cryptography here was never the hard part. RSA with a known q is a solved problem the moment you can produce p, and the challenge author was kind enough to describe exactly how p came into existence.

The transferable lesson is about how key material gets generated in real systems, because the same failure shows up outside CTFs:

  • A PRNG seeded from anything an attacker can guess, derive, or observe produces keys an attacker can reproduce. random.seed(42) is the toy version; a seed derived from a timestamp, a hostname, or a public commit hash is the version that reaches production.
  • The seed space matters more than the algorithm. SHA-256 in the middle looks like it adds entropy, but hashing a public string does not create secrecy. It only hides the input from a casual reader.
  • If you write the key generation, write down how many possible keys exist. “512-bit RSA” says nothing if the effective generator has 32 bits of state.

A reviewer reading a key-generation routine should be able to answer one question in a sentence: how many candidates can the attacker try? If the answer is not “all of them”, the key is not secure.