backdoor? just go from the back then?

import json
import base64

from typing import Dict, Optional, Tuple, Iterable
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from fastecdsa.curve import P256
from fastecdsa.point import Point

# Constants from challenge
OUT_BYTES = 30
OUT_MASK = (1 << (8 * OUT_BYTES)) - 1
D_BITS = 32

def tonelli_shanks(n: int, p: int) -> Optional[int]:
"""Compute a modular square root of n modulo prime p using Tonelli-Shanks.
Returns one root r with r*r % p == n, or None if no root exists.
"""

if n == 0:
	return 0

if p == 2:
	return n

# Legendre symbol
ls = pow(n, (p - 1) // 2, p)

if ls == p - 1:
	return None

if ls == 0:
	return 0

# Factor p-1 = q * 2^s with q odd
q = p - 1
s = 0

while q % 2 == 0:
	q //= 2
	s += 1

# If s == 1, we can compute directly

if s == 1:
	return pow(n, (p + 1) // 4, p)

# Find a quadratic non-residue z
z = 2

while pow(z, (p - 1) // 2, p) != p - 1:
	z += 1
	c = pow(z, q, p)
	r = pow(n, (q + 1) // 2, p)
	t = pow(n, q, p)
	m = s

while t % p != 1:
	# Find the smallest i (0 < i < m) such that t^(2^i) == 1
	i = 1
	t2i = (t * t) % p

	while t2i % p != 1:
		t2i = (t2i * t2i) % p
		i += 1
		if i == m:
			return None

	b = pow(c, 1 << (m - i - 1), p)
	r = (r * b) % p
	t = (t * b * b) % p
	c = (b * b) % p
	m = i

return r


def decompress_points_from_low30(low30: int, curve: P256) -> Iterable[Point]:
	"""Yield all curve points whose x-coordinate's low 30 bytes equal low30."""

	p = curve.p
	a = curve.a
	b = curve.b
	shift = 8 * OUT_BYTES # 240

	for hi in range(1 << (32 - OUT_BYTES * 8 % 32)):
		x = (hi << shift) | low30

		if x >= p:
			continue
		rhs = (pow(x, 3, p) + (a * x) + b) % p
		y = tonelli_shanks(rhs, p)

		if y is None:
			continue

		yield Point(x, y, curve=curve)
		if y != 0:
			yield Point(x, (p - y) % p, curve=curve)


def bsgs_small_d(P_point: Point, Q_point: Point, max_d_exclusive: int) -> Optional[int]:
"""Solve for small d such that d*Q = P using baby-step giant-step up to max_d_exclusive.
Returns d if found, else None.
"""

	m = int(max_d_exclusive ** 0.5) + 1

	# Baby steps: j*Q for j in [1, m]
	baby: Dict[Tuple[int, int], int] = {}

	current = Q_point

	for j in range(1, m + 1):
		baby[(current.x, current.y)] = j
		current = current + Q_point

	mQ = Q_point * m
	neg_mQ = -mQ

	# Giant steps: P - i*m*Q
	current = P_point

	for i in range(0, m + 1):
		key = (current.x, current.y)

		if key in baby:
			d = i * m + baby[key]

			if 2 <= d < max_d_exclusive:
				return d

		current = current + neg_mQ
	return None


def int_to_bytes_be(n: int, length: int) -> bytes:
	return n.to_bytes(length, 'big')

def bytes_high(b: bytes, n: int) -> bytes:
	return b[:n]

def main() -> None:
	with open('Not a backdoor/challenge.json', 'r') as f:
		challenge = json.load(f)

	curve = P256

	# Points P and Q from the challenge
	Px = int(challenge['P']['x'], 16)
	Py = int(challenge['P']['y'], 16)
	Qx = int(challenge['Q']['x'], 16)
	Qy = int(challenge['Q']['y'], 16)

	P_point = Point(Px, Py, curve=curve)
	Q_point = Point(Qx, Qy, curve=curve)
	observed_hex = challenge['observed']

	# Use only the last observed entry to get outputs[4] and the top-2 bytes of outputs[5]
	last_obs = int(observed_hex[-1], 16)
	out4 = last_obs >> 16
	top2_out5 = last_obs & 0xFFFF

	# Recover small d via BSGS
	max_d = 1 << D_BITS
	d = bsgs_small_d(P_point, Q_point, max_d)

	if d is None:
		raise RuntimeError('Failed to recover small d')

	# Compute e = d^{-1} mod q for fast generator multiplication
	q = curve.q
	e = pow(d, -1, q)

	# Precompute: number of candidates expected is small after filtering by top2_out5
	# Enumerate all candidate points for R4 from out4
	p = curve.p
	a = curve.a
	b = curve.b

	shift = 8 * OUT_BYTES # 240

	ct = base64.b64decode(challenge['ciphertext'])
	iv = base64.b64decode(challenge['iv'])

	found = False

	flag_bytes: Optional[bytes] = None

	for hi in range(1 << 16):
		x4 = (hi << shift) | out4

		if x4 >= p:
			continue

		rhs = (pow(x4, 3, p) + (a * x4) + b) % p
		y = tonelli_shanks(rhs, p)

		if y is None:
			continue

		for y4 in (y, (p - y) % p):

			R4 = Point(x4, y4, curve=curve)

			# s5 = x(d * R4)
			S5_point = R4 * d
			s5 = S5_point.x

			# R5 = (s5 * e) * P (generator mult is faster)
			k = (s5 * e) % q
			R5 = P_point * k
			out5 = R5.x & OUT_MASK

			if (out5 >> (8 * (OUT_BYTES - 2))) != top2_out5:
				continue

			# Derive AES key from out5
			out5_bytes = int_to_bytes_be(out5, OUT_BYTES)
			key = out5_bytes[:16]

			try:
				cipher = AES.new(key, AES.MODE_CBC, iv)
				pt = unpad(cipher.decrypt(ct), AES.block_size)
			except Exception:
				continue

			if b'07CTF{' in pt:
				flag_bytes = pt
				found = True
				break

		if found:
			break

	if not found:
		raise RuntimeError('Failed to recover the flag; no candidate matched')

	print(flag_bytes.decode(errors='replace'))

if __name__ == '__main__':
	main()