Ralia Challenge — Writeup

This writeup details the solution for the “Ralia” cryptography/PPC challenge from ASIS CTF 2025 Finals. The challenge involves interacting with a remote “weird machine” and solving a system of equations to generate integers that satisfy specific bit-length, primality, and perfect square constraints.

Summary

The target is a remote Python script accessible via netcat. To retrieve the flag, we must survive 19 levels of increasing difficulty.

In each level, the server provides a random bit length, bitel. We are required to provide three integers—$x$, $y$, and $z$—that satisfy the following conditions:

1. Bit Length: All three numbers ($x, y, z$) must have exactly bitel bits.
2. Primality: $x$ and $z$ must be prime numbers.
3. Perfect Squares: The following expressions must result in perfect squares:
   • $x + y$
   • $y + z + 1$
   • $z + x + 5$

Key Code Snippets

The core logic of the challenge is found in ralia.py.

ralia.py (Constraint Checking):

1
# The server parses our input
2
try:
3
    x, y, z = [abs(int(_)) for _ in ans]
4
except:
5
    die(border, f"The input you provided is not valid!")
6

7
_b = False
8

9
# The Mathematical Constraints
10
# 1. Check if the sums are perfect squares
11
if is_persquat(x + y) and is_persquat(y + z + 1) and is_persquat(z + x + 5):
12
    # 2. Check if x and z are prime
13
    if isPrime(x) and isPrime(z):
14
        # 3. Check if they match the required bit length
15
        if x.bit_length() == y.bit_length() == z.bit_length() == bitel:
16
            _b = True

Analysis

This problem can be modeled as a system of linear equations. If we define the square roots of the required sums as integers $A$, $B$, and $C$, we get:

We have a system of 3 equations with 3 variables ($x$, $y$, $z$). We can solve for $x$, $y$, $z$ algebraically in terms of $A$, $B$, $C$.

Solving for $x$: Sum equation (1) and (3), then subtract (2):

Solving for $y$: Sum equation (1) and (2), then subtract (3):

Solving for $z$: Sum equation (2) and (3), then subtract (1):

Integer Constraints

For $x$, $y$, $z$ to be integers, the numerators must be divisible by 2 (even). Looking at $2x = A^2 - B^2 + C^2 - 4$, since 4 is even, we need $A^2 - B^2 + C^2$ to be even. In modular arithmetic modulo 2, $n^2 \equiv n$. Therefore, the constraint simplifies to:

The sum of the three roots must be even.

Exploitation and Flag Recovery

We cannot brute-force $x$, $y$, $z$ directly because finding primes that sum to squares is computationally expensive. However, generating $x$, $y$, $z$ from random values of $A$, $B$, $C$ is very fast.

1. Estimating the Range

We need $x \approx 2^{\text{bitel}}$. Since $x + y = A^2$, and $x \approx y$, then $2x \approx A^2$. So, $A \approx \sqrt{2 \cdot 2^{\text{bitel}}}$. This gives us the center of the search range for our random squares.

2. The Solver Script

The script performs the following steps for each level:

• Calculates the search center based on bitel.
• Generates random integers $A$ and $B$ near the center.
• Calculates the required parity for $C$ (so that $A+B+C$ is even).
• Iterates through possible values of $C$.
• Calculates $x$, $y$, $z$ and checks if they match the bitel and primality requirements.

1
#!/usr/bin/env python3
2
from pwn import *
3
from Crypto.Util.number import isPrime
4
from math import isqrt
5
import random
6

7
def solve_level(bitel):
8
    # Calculate search center: sqrt(2 * 2^bitel)
9
    center = isqrt(2 * (1 << bitel))
10
    width = center // 20
11

12
    while True:
13
        # Pick A and B randomly around the target center
14
        A = random.randint(center - width, center + width)
15
        B = random.randint(center - width, center + width)
16

17
        # C must satisfy (A + B + C) % 2 == 0
18
        parity_target = (A + B) % 2
19

20
        # Start searching for C
21
        C_start = random.randint(center - width, center + width)
22
        if C_start % 2 != parity_target:
23
            C_start += 1
24

25
        # Iterate C to find valid primes
26
        for C in range(C_start, C_start + 5000, 2):
27
            # Calculate numerators
28
            num_x = A*A + C*C - B*B - 4
29
            num_y = A*A + B*B - C*C + 4
30
            num_z = B*B + C*C - A*A - 6
31

32
            # Ensure positive results
33
            if num_x <= 0 or num_y <= 0 or num_z <= 0: continue
34

35
            x = num_x // 2
36
            y = num_y // 2
37
            z = num_z // 2
38

39
            # Check bit length constraints
40
            if x.bit_length() != bitel: continue
41
            if y.bit_length() != bitel: continue
42
            if z.bit_length() != bitel: continue
43

44
            # Check primality (most expensive op, do last)
45
            if isPrime(x) and isPrime(z):
46
                return x, y, z
47

48
def main():
49
    host = '65.109.194.34'
50
    port = 13377
51
    r = remote(host, port)
52

53
    try:
54
        while True:
55
            line = r.recvline().decode().strip()
56
            print(f"[Server] {line}")
57

58
            if "Congratz" in line:
59
                print(f"\n[+] Flag: {line}")
60
                break
61

62
            if "Please send" in line and "bitel =" in line:
63
                parts = line.split()
64
                try:
65
                    idx = parts.index("bitel")
66
                    bitel = int(parts[idx + 2].replace(":", ""))
67
                    print(f"[*] Solving for bitel: {bitel}...")
68

69
                    x, y, z = solve_level(bitel)
70

71
                    r.sendline(f"{x},{y},{z}".encode())
72
                except ValueError:
73
                    print("[!] Error parsing")
74
    finally:
75
        r.close()
76

77
if __name__ == '__main__':
78
    main()

3. Execution

We run the solver and wait for it to process all 19 levels.

[+] Opening connection to 65.109.194.34 on port 13377: Done
[Server] ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
...
[*] many levels and bitel are random for eac one and each level here but when solving level 19 you get the flag
[Server] Congratz! You got the flag: ASIS{n1C3_IMO_fr0m_4U5Tr4LiA!}

Final Result

Flag: ASIS{n1C3_IMO_fr0m_4U5Tr4LiA!}

Notes

The challenge demonstrates how arithmetic constraints can often be reversed using algebra to generate solutions efficiently, rather than filtering random numbers.

By controlling the generator variables ($A$, $B$, $C$), we ensured the perfect square constraints were met implicitly, leaving only the primality check as the computational hurdle.