
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.
Related posts
02 ENTRIEShttps://shulkwisec.github.io/04-CTF-Writeups/KnightCTF_2025/knightctf-2025-writeups-randomsenioradleman/
Printed 2026-11-15

