Confusion#

I’ve encrypted my secret message with RSA.

Easy stuff, right?

Well, I’m not giving you the key outright…

I’ve hidden it in a haystack!

Sure, a key is not a needle, and this haystack is not that big.

It shouldn’t take more than 10’ to find it, if you have an half-decent metal detector.

Good luck!

Introduction#

Confusion was a crypto CTF from K!nd4SUS CTF 2025.

1
from Crypto.Util import number
2
from base64 import b64encode
3

4
prime = lambda: number.getPrime(512)
5
def b64enc(x):
6
  h = hex(x)[2:]
7
  if len(h) % 2:
8
    h = '0' + h
9
  return b64encode(bytes.fromhex(h)).decode()
10

11

12
p = prime()
13
q = prime()
14
with open("flag.txt") as f:
15
  flag = f.readline().strip()
16

17
n = p * q
18
m = int(flag.encode().hex(), 16)
19
c = pow(m, 65537, n)
20

21
print("ciphertext:", hex(c)[2:])
22

23
bale = [p, q]
24
bale.extend(prime() for _ in range(1<<6))
25

26
def add_hay(stack, straw):
27
  x = stack[0]
28
  for i in range(1, len(stack)):
29
    y = stack[i]
30
    stack[i] = y + (straw * x)
31
    x = y
32
  stack.append(straw * x)
33

34
stack = [1]
35
add_hay(stack, p)
36
add_hay(stack, q)
37
for straw in bale:
38
  add_hay(stack, straw)
39

40
print("size:", len(stack))
41
for x in stack:
42
  print(b64enc(x))

The challenge encrypts the flag with RSA and constructs a stack via the add_hay function which we’re then given to try to recover the primes $p$ and $q$ used to create the modulus $n$ .

Solution#

The intended solution is to solve the list of equations provided by stack, this is why the description suggests it might take about 10 minutes. But I found out a much simpler solution by simply “looking” at what stack looks like if $p$ and $q$ are seen as variables, which I simulated using sagemath:

1
sage: from Crypto.Util.number import getPrime
2
....:
3
....: p, q = PolynomialRing(ZZ, 'p,q').gens()
4
....: bale = [p, q]
5
....: bale.extend(getPrime(512) for _ in range(1<<6))
6
....:
7
....: def add_hay(stack, straw):
8
....:     x = stack[0]
9
....:     for i in range(1, len(stack)):
10
....:         y = stack[i]
11
....:         stack[i] = y + (straw * x)
12
....:         x = y
13
....:     stack.append(straw * x)
14
....:
15
....: stack = [1]
16
....: add_hay(stack, p)
17
....: add_hay(stack, q)
18
....: for straw in bale:
19
....:     add_hay(stack, straw)

By looking at the end of stack it’s easy to see that both the last and second to last entries have a factor of $pq$ , with a simple gcd we can therefore recover $n$ . Looking now at the second and third to last entries (which I’ll call $s_2$ and $s_3$ respectively) we can see that: $s_2 = zp^2q^2 + 2cp^2q + 2cpq^2$ $s_3 = xp^2q^2 + yp^2q + ypq^2 + cp^2 + wpq + cq^2$

With some modular reduction (and a division): $v_2 := \frac{s_2 \pmod{n^2}}{n} = 2cp + 2cq$ $v_3 :\equiv c(p^2 + q^2) \pmod n$

Then since $(p + q)^2 \equiv p^2 + q^2 \pmod n$ we have: $a :\equiv 2^{-1}v_2 \pmod n \equiv c(p + q) \pmod n$ $b :\equiv a^2 \pmod n \equiv c^2\left(p^2 + q^2\right) \pmod n$

Finally we can recover $c$ , and therefore $\phi(n)$ with: $c \equiv bv_3^{-1} \pmod n$ $\phi(n) = n - \left(ac^{-1} \pmod n\right) + 1$

1
from base64 import b64decode as bd
2
from math import gcd
3

4
ct = 0x7434d263623892ca660f4139c54ab02a8a14d87cd5c658fca9105f88f7ed5c888a744e949b716094c1d73fd8084eeaf72b23e97325829a69ca57a34e5e0b5272ddaf039bcc0aed2055968c8dfa7cd0373cca072c31123e6259659af03ce87b224bb7fdf13fb89b4ceb580d2d11524025ccb4f86560f3b006d99d86a63ab3aa5a
5
size = 69
6

7
stack = []
8
with open('output.txt', 'r') as f:
9
    f.readline(); f.readline()
10
    for _ in range(size):
11
        stack.append(int.from_bytes(bd(f.readline().rstrip())))
12

13
n = gcd(stack[-1], stack[-2])
14

15
v2 = stack[-2] % (n*n) // n
16
v3 = stack[-3] % n
17

18
a = v2 * pow(2, -1, n) % n
19
b = pow(a, 2, n)
20

21
c = b * pow(v3, -1, n) % n
22

23
phi = n - (a * pow(c, -1, n) % n) + 1
24

25
d = pow(65537, -1, phi)
26
m = pow(ct, d, n)
27

28
print('flag:', m.to_bytes(-(m.bit_length()//-8)).decode())

flag: KSUS{6465726976617469766573206172652061206e69636520747269636b}