Challenge: Fun With RSA · CTF: DalCTF 2026 · Category: Crypto · Difficulty: Hard

“Made my own rsa implementation. Hoping its safe enough that no one can crack it. I even xored things to make it safer”

Whenever a challenge description brags about a homemade RSA implementation and “xored things to make it safer,” you can be pretty confident the crypto is about to roll over. Let’s dig in.

The Challenge

We’re given the encryption script and its output.

FunWithRSA.py

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

from Cryptodome import *
from Cryptodome.Util.number import *
from pwn import *

FLAG = b"dalctf{REDACTED}"

e = 65537

m = bytes_to_long(FLAG)

while True:
    p = getPrime(256)
    q = getPrime(256)
    n = p*q
    phi = (p-1) * (q-1)

    d = inverse(e, phi)
    if (math.gcd(d,e) == 1):
        break

dp = d % (p-1)
dq = d % (q-1)
qinv = inverse(q, p)

sp = pow(m, dp, p)
sq = pow(m, dq, q)

h = (qinv * (sp - sq)) % p
s = sq + h*q

spz = sp ^ 1

hf = (qinv * (spz - sq)) % p
spz = sq + hf*q


c = pow(m,e,n)
ct = int(xor(bin(c), bin(p), bin(q)),2)

print(f"n = {n}")
print(f"e = {e}")
print(f"ct = {ct}")
print(f"s = {s}")
print(f"spz = {spz}")

fwr.txt

1
2
3
4
5

n  = 5216528649875826746373274623709911527907930166016984164533272620692599945581004244622652640509156720922738730017397970929856922904389747851230187154375161
e  = 65537
ct = 1769561623039780835813534940346776273175000099891521520378974868184264352157081415449182707720490727295376770632579942515719007563037959358184643750159804
s  = 1220125626995232022797746032625764407124557835619605483513423136472322667738087444211114063128377505634674691423794338554652601901132201128484832327199237
spz= 2144640816488997996880355081959057062388718728036090601522167913668193535885347340870230640225749237841665830391473546117213483723045473075426308182703379

Step 1 — Read the code, not the README

The first thing to notice is that this isn’t really an encryption challenge — it’s a signing challenge. The script computes a ciphertext c = pow(m, e, n), sure, but it never gives c to us directly (it hides it inside ct). Instead, the values we actually receive are s and spz, which are produced by an RSA-CRT signing routine.

Let’s unpack what CRT signing does.

A quick refresher on RSA-CRT

Plain RSA decryption/signing is s = m^d mod n. That modular exponentiation over the full modulus n is slow, so real implementations use the Chinese Remainder Theorem (CRT) to do it ~4× faster. They precompute:

1
2
3

dp   = d mod (p-1)
dq   = d mod (q-1)
qinv = q^(-1) mod p

Then they compute the signature mod each prime separately and glue them back together (this is Garner’s formula):

1
2
3
4

sp = m^dp mod p          # the "p half"
sq = m^dq mod q          # the "q half"
h  = qinv * (sp - sq) mod p
s  = sq + h*q            # full signature  ==  m^d mod n

This is exactly what the challenge does to produce s. So:

1

s = m^d mod n

s is nothing more than the textbook RSA signature of the flag.

Step 2 — The free win (signature ↔ message)

Here’s the thing that makes this challenge fall apart in one line.

RSA signing and verifying are inverse operations. Signing with the private exponent d and then verifying with the public exponent e brings you right back to the message:

1

s^e mod n = (m^d)^e mod n = m^(d·e) mod n = m mod n

We have s, e, and n. So we can recover the message without factoring anything:

1

m = pow(s, e, n)

1
2
3
4
5
6

n = 5216528649875826746373274623709911527907930166016984164533272620692599945581004244622652640509156720922738730017397970929856922904389747851230187154375161
e = 65537
s = 1220125626995232022797746032625764407124557835619605483513423136472322667738087444211114063128377505634674691423794338554652601901132201128484832327199237

m = pow(s, e, n)
print(m.to_bytes((m.bit_length() + 7) // 8, "big"))

Output:

1

b'dalctf{s3gf4u17_r54_m1x3d_w17h_x0r}'

Done. dalctf{s3gf4u17_r54_m1x3d_w17h_x0r}

That’s the fastest path — but the flag name (“segfault RSA”) is a big hint that the intended solution is something juicier: a fault-injection attack. Let’s do it the intended way too, because it’s a beautiful, classic attack.

Step 3 — The intended solution: the Bellcore / RSA-CRT fault attack

Look again at this block:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

sp = pow(m, dp, p)
sq = pow(m, dq, q)

h  = (qinv * (sp  - sq)) % p
s  = sq + h*q            # CORRECT signature

spz = sp ^ 1             # <-- one bit of sp is flipped (a "fault")

hf  = (qinv * (spz - sq)) % p
spz = sq + hf*q          # FAULTY signature

The script gives us two signatures of the same message:

  • s — computed normally.
  • spz — computed with a corrupted sp. The line spz = sp ^ 1 XORs the p-half with 1, flipping its lowest bit. This simulates a hardware fault injection (a glitch, a cosmic ray, a Rowhammer bit-flip — exactly the kind of thing the Bellcore attack was designed to exploit).

This is the textbook setup for the RSA-CRT fault attack, and it’s catastrophic.

Why one faulty signature breaks everything

Look carefully at where the fault lands. The faulty signature is built from a corrupted sp but a correct sq. So:

  • Modulo q: both signatures used the correct sq and only differ by multiples of q. The error term h*q and hf*q both vanish mod q. Therefore:

    1

    s ≡ spz   (mod q)        →   s - spz ≡ 0 (mod q)

  • Modulo p: the fault changed sp, so the two signatures genuinely disagree:

    1

    s ≢ spz   (mod p)        →   s - spz ≢ 0 (mod p)

Put those together: s - spz is a multiple of q but not a multiple of p. That means the greatest common divisor of (s - spz) and n = p·q is exactly q:

1

gcd(s - spz, n) = q

We just factored a 512-bit modulus with a single gcd. 💀

1
2
3
4
5
6
7

from math import gcd

q = gcd(s - spz, n)
p = n // q
assert p * q == n
print("q =", q)
print("p =", p)

1
2

q divides n: True
q = 58283758774964263077689530394775429444499650453384515190628347257294498606089

Once you have p and q, the rest is standard RSA:

1
2
3
4
5
6

from Crypto.Util.number import inverse, long_to_bytes

phi = (p - 1) * (q - 1)
d   = inverse(e, phi)
m   = pow(s, d, n)          # or recover c from ct first — see below
print(long_to_bytes(m))

Step 4 — What about that XOR’d ciphertext?

The “I even xored things to make it safer” line refers to this:

1
2

c  = pow(m, e, n)
ct = int(xor(bin(c), bin(p), bin(q)), 2)

The author takes the real ciphertext c, converts it (and p and q) to binary strings with bin(...), XORs all three together using pwntools’ xor, and prints the result as ct. The idea was to hide c so you couldn’t just decrypt it.

But this “protection” is hollow:

  1. XOR is trivially reversible. a ⊕ b ⊕ c ⊕ b ⊕ c = a. Once you know p and q (which we recovered in Step 3), you simply XOR them back out to recover c:

    1
2
3
4
5

    from pwn import xor
# ct = c ^ p ^ q  (over their binary string representations)
c = int(xor(bin(ct), bin(p), bin(q)), 2)
m = pow(c, d, n)
print(long_to_bytes(m))   # dalctf{s3gf4u17_r54_m1x3d_w17h_x0r}

  2. And as we saw in Step 2, you never even needed c at all — s already leaks the message via s^e mod n.

So the XOR layer adds zero security. It just gives the flag its name: RSA segfault mixed with XOR.

Full Solver

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

from math import gcd
from Crypto.Util.number import inverse, long_to_bytes
from pwn import xor

n  = 5216528649875826746373274623709911527907930166016984164533272620692599945581004244622652640509156720922738730017397970929856922904389747851230187154375161
e  = 65537
ct = 1769561623039780835813534940346776273175000099891521520378974868184264352157081415449182707720490727295376770632579942515719007563037959358184643750159804
s  = 1220125626995232022797746032625764407124557835619605483513423136472322667738087444211114063128377505634674691423794338554652601901132201128484832327199237
spz= 2144640816488997996880355081959057062388718728036090601522167913668193535885347340870230640225749237841665830391473546117213483723045473075426308182703379

# --- One-liner shortcut: s is just m^d mod n, so m = s^e mod n ---
print(long_to_bytes(pow(s, e, n)))

# --- Intended: RSA-CRT fault attack ---
q   = gcd(s - spz, n)          # faulty & correct sig agree mod q  ->  gcd leaks q
p   = n // q
phi = (p - 1) * (q - 1)
d   = inverse(e, phi)

# undo the XOR layer to recover the real ciphertext, then decrypt
c   = int(xor(bin(ct), bin(p), bin(q)), 2)
print(long_to_bytes(pow(c, d, n)))

Both paths print:

1

dalctf{s3gf4u17_r54_m1x3d_w17h_x0r}

Takeaways

  • Roll-your-own crypto loses. The “homemade RSA” warning in the description is the whole challenge.
  • Never expose two CRT signatures of the same message when one might be faulty. A single faulty RSA-CRT signature lets an attacker factor n with one gcd — this is the real-world Bellcore attack, and it’s why production libraries verify every CRT signature (s^e ≟ m) before releasing it. The fix is one line: recompute and reject if the result doesn’t verify.
  • XOR is not encryption. Obfuscating a value by XORing it with other values you also leak (here p and q) provides no security whatsoever.
  • Signatures and ciphertexts are dual. Handing out m^d mod n is handing out the decryption oracle output for that message. s^e mod n gives m straight back.

Flag: dalctf{s3gf4u17_r54_m1x3d_w17h_x0r}