ChristmasRSA

Platform: grodno_new_year_2026 | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-01-11 | Status: Solved Techniques: modular_square_root, prime_factorization_check, tonelli_shanks

Summary

Task: Non-standard RSA challenge where the modulus n is a prime number and the encryption exponent e=4. Solution: Computed the 4th root of the ciphertext modulo the prime using two successive applications of the Tonelli-Shanks square root algorithm, then checked which of the four roots decoded to a valid flag.

ChristmasRSA - Grodno New Year 2026

Description

Как можно встречать Новый Год без RSA? / How can you celebrate the New Year without RSA?

Files provided:

• ChristmasRSA.txt - Contains n and c values
• ChristmasRSA.py - Encryption script

Analysis

Initial Observations

Looking at the encryption script:

 python read-only • copy allowed Copy
E = 4

def choose_prime_with_quadratic_residue(message_int: int, bits: int = 512) -> Tuple[int, int]:
    attempts = 0
    while True:
        attempts += 1
        p = getPrime(bits)
        val = pow(message_int, E, p)
        if pow(val, (p - 1) // 2, p) == 1:  # Euler's criterion for QR
            return p, attempts
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def main() -> None:
    FLAG = b"REDACTED"
    m_int = bytes_to_long(FLAG)
    prime_n, tries = choose_prime_with_quadratic_residue(m_int, bits=512)
    ciphertext = pow(m_int, E, prime_n)

Key Insights

1. n is PRIME, not a product of two primes - This is NOT standard RSA!
2. e = 4 - The encryption exponent is 4
3. c = m^4 mod n - We need to find the 4th root of c modulo prime n
4. Quadratic residue check - The code ensures c is a quadratic residue mod n, meaning square roots exist ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Why Standard RSA Decryption Fails

In standard RSA with n = p*q, we compute d = e^(-1) mod phi(n) and decrypt as m = c^d mod n.

Here, n is prime, so phi(n) = n-1. But gcd(4, n-1) != 1 (since n is odd prime, n-1 is even), so the modular inverse of 4 doesn't exist in the usual sense.

Solution Approach

Since c = m^4 mod n and n is prime, we need to compute the 4th root of c modulo n.

Method: Take two successive square roots using the Tonelli-Shanks algorithm:

1. Find sqrt(c) mod n -> gives 2 values: r1, n-r1
2. For each value, find its square root -> gives up to 4 values total
3. Check which one decodes to a valid flag ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Solution

 python read-only • copy allowed Copy
#!/usr/bin/env python3
"""
ChristmasRSA Solver - Grodno New Year 2026 CTF
Finding 4th root modulo prime using Tonelli-Shanks
"""
from Crypto.Util.number import long_to_bytes

n = 13169078694919460635383928661575625181169334864757438398298903709298420936524007827607439606306140217827957404989078103821793651547869206591987281962796681
c = 3630107265622722432860113718901227107257778462530970277748300894821302240644191624151434409347535008286845806413323174289707080608209343558324355802697978
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def tonelli_shanks(n, p):
    """
    Find r such that r^2 = n (mod p) using Tonelli-Shanks algorithm.
    Returns None if n is not a quadratic residue mod p.
    """
    # Check if n is a quadratic residue using Euler's criterion
    if pow(n, (p - 1) // 2, p) != 1:
        return None
    
    # Factor out powers of 2 from p-1: p-1 = q * 2^s
    q = p - 1
    s = 0
    while q % 2 == 0:
        q //= 2
        s += 1
    
    # Find a quadratic non-residue z
    z = 2
    while pow(z, (p - 1) // 2, p) != p - 1:
        z += 1
    
    # Initialize
    m = s
    c_val = pow(z, q, p)
    t = pow(n, q, p)
    r = pow(n, (q + 1) // 2, p)
    
    # Main loop
    while True:
        if t == 1:
            return r
        
        # Find the least i such that t^(2^i) = 1
        i = 1
        temp = (t * t) % p
        while temp != 1:
            temp = (temp * temp) % p
            i += 1
        
        # Update values
        b = pow(c_val, 1 << (m - i - 1), p)
        m = i
        c_val = (b * b) % p
        t = (t * c_val) % p
        r = (r * b) % p
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def find_all_4th_roots(c, p):
    """
    Find all x such that x^4 = c (mod p).
    Takes two successive square roots.
    """
    roots = []
    
    # First square root: find y such that y^2 = c (mod p)
    sqrt1 = tonelli_shanks(c, p)
    if sqrt1 is None:
        return roots
    
    sqrt_c = [sqrt1, p - sqrt1]  # Both square roots of c
    
    # Second square root: for each y, find x such that x^2 = y (mod p)
    for s in sqrt_c:
        sqrt2 = tonelli_shanks(s, p)
        if sqrt2 is not None:
            roots.append(sqrt2)
            roots.append(p - sqrt2)
    
    return roots
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Find all 4th roots
roots = find_all_4th_roots(c, n)

print(f"Found {len(roots)} possible 4th roots")
print()

# Check each root for valid flag
for i, root in enumerate(roots):
    try:
        decoded = long_to_bytes(root)
        print(f"Root {i+1}: {decoded}")
        if b'grodno' in decoded:
            print(f"\n[+] FLAG FOUND: {decoded.decode()}")
    except:
        print(f"Root {i+1}: (not valid UTF-8)")

Execution

Found 4 possible 4th roots

Root 1: (garbage bytes)
Root 2: b'grodno{REDACTED}'
Root 3: (garbage bytes)
Root 4: (garbage bytes)
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

[+] FLAG FOUND: grodno{REDACTED}

Mathematical Background

Tonelli-Shanks Algorithm

The Tonelli-Shanks algorithm finds square roots modulo a prime p. Given n and prime p where n is a quadratic residue (i.e., n^((p-1)/2) = 1 mod p), it finds r such that r^2 = n (mod p).

Key steps:

1. Write p-1 = q * 2^s where q is odd
2. Find a quadratic non-residue z
3. Iteratively refine the solution using the structure of the multiplicative group

Why 4 Roots?

For x^4 = c (mod p) where p is prime:

• First, find y such that y^2 = c (mod p) -> 2 solutions: y, -y
• Then, find x such that x^2 = y (mod p) -> 2 solutions for each y
• Total: up to 4 solutions ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

The encryption code ensures c is a quadratic residue, guaranteeing solutions exist.

Alternative Approaches

1. SageMath: Mod(c, n).nth_root(4, all=True)
2. SymPy: nthroot_mod(c, 4, n, all_roots=True)
3. Manual: Use the formula for p = 3 (mod 4) if applicable

References

• Tonelli-Shanks Algorithm
• Quadratic Residues
• Modular Arithmetic ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍