Key in the haystack

Introduction

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

from Crypto.Util import number
from base64 import b64encode

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


p = prime()
q = prime()
with open("flag.txt") as f:
	flag = f.readline().strip()

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

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

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

def add_hay(stack, straw):
	x = stack[0]
	for i in range(1, len(stack)):
		y = stack[i]
		stack[i] = y + (straw * x)
		x = y
	stack.append(straw * x)

stack = [1]
add_hay(stack, p)
add_hay(stack, q)
for straw in bale:
	add_hay(stack, straw)

print("size:", len(stack))
for x in stack:
	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 $pp$ and $qq$ used to create the modulus $nn$.

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 $pp$ and $qq$ are seen as variables, which I simulated using sagemath:

sage: from Crypto.Util.number import getPrime
....:
....: p, q = PolynomialRing(ZZ, 'p,q').gens()
....: bale = [p, q]
....: bale.extend(getPrime(512) for _ in range(1<<6))
....:
....: def add_hay(stack, straw):
....:     x = stack[0]
....:     for i in range(1, len(stack)):
....:         y = stack[i]
....:         stack[i] = y + (straw * x)
....:         x = y
....:     stack.append(straw * x)
....:
....: stack = [1]
....: add_hay(stack, p)
....: add_hay(stack, q)
....: for straw in bale:
....:     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 $pqpq$, with a simple gcd we can therefore recover $nn$. Looking now at the second and third to last entries (which I'll call $s_{2}s\_2$ and $s_{3}s\_3$ respectively) we can see that: $s_2=z{p}^2{q}^2+2c{p}^{2}q+2cp{q}^{2}s\_2\; =\; zp^2q^2\; +\; 2cp^2q\; +\; 2cpq^2$ $s_3=x{p}^2{q}^2+y{p}^{2}q+yp{q}^2+c{p}^2+wpq+c{q}^{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(\mathrm{m}\mathrm{o}\mathrm{d}{n}^2)}{n}=2cp+2cqv\_2\; :=\; \backslash frac\{s\_2\; \backslash pmod\{n^2\}\}\{n\}\; =\; 2cp\; +\; 2cq$ $v_3:\equiv c(p^2+q^2)(\mathrm{m}\mathrm{o}\mathrm{d}n)v\_3\; :\backslash equiv\; c(p^2\; +\; q^2)\; \backslash pmod\; n$

Then since $(p+q{)}^2\equiv p^2+q^2(\mathrm{m}\mathrm{o}\mathrm{d}n)(p\; +\; q)^2\; \backslash equiv\; p^2\; +\; q^2\; \backslash pmod\; n$ we have: $a:\equiv 2^{-1}{v}_2(\mathrm{m}\mathrm{o}\mathrm{d}n)\equiv c(p+q)(\mathrm{m}\mathrm{o}\mathrm{d}n)a\; :\backslash equiv\; 2^\{-1\}v\_2\; \backslash pmod\; n\; \backslash equiv\; c(p\; +\; q)\; \backslash pmod\; n$ $b:\equiv a^2(\mathrm{m}\mathrm{o}\mathrm{d}n)\equiv c^2(p^2+q^2)(\mathrm{m}\mathrm{o}\mathrm{d}n)b\; :\backslash equiv\; a^2\; \backslash pmod\; n\; \backslash equiv\; c^2\backslash left(p^2\; +\; q^2\backslash right)\; \backslash pmod\; n$

Finally we can recover $cc$, and therefore $\varphi (n)\backslash phi(n)$ with: $c\equiv b{v}_3^{-1}(\mathrm{m}\mathrm{o}\mathrm{d}n)c\; \backslash equiv\; bv\_3^\{-1\}\; \backslash pmod\; n$ $\varphi (n)=n-(a{c}^{-1}(\mathrm{m}\mathrm{o}\mathrm{d}n))+1\backslash phi(n)\; =\; n\; -\; \backslash left(ac^\{-1\}\; \backslash pmod\; n\backslash right)\; +\; 1$

from base64 import b64decode as bd
from math import gcd

ct = 0x7434d263623892ca660f4139c54ab02a8a14d87cd5c658fca9105f88f7ed5c888a744e949b716094c1d73fd8084eeaf72b23e97325829a69ca57a34e5e0b5272ddaf039bcc0aed2055968c8dfa7cd0373cca072c31123e6259659af03ce87b224bb7fdf13fb89b4ceb580d2d11524025ccb4f86560f3b006d99d86a63ab3aa5a
size = 69

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

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

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

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

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

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

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

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

flag: KSUS{6465726976617469766573206172652061206e69636520747269636b}