Искусство войны (The Art of War)

Platform: hackerlab | Category: Crypto | Type: Challenge | Difficulty: Easy | OS: NA | Author: XESXOR | Date: 2025-12-30 | Status: Solved Techniques: Chinese Remainder Theorem (CRT) for solving system of congruences, Integer to bytes conversion, XOR decryption with recovered key

Summary

Task: System of modular congruences with XOR-encrypted flag. Solution: Apply Chinese Remainder Theorem (CRT) to find the key, then XOR decrypt the ciphertext.

Искусство войны (The Art of War) - hackerlab

Description

На войне все средства хороши. Что насчет криптографии? (In war, all means are good. What about cryptography?)

File task.txt:

x ≡ 7 mod 17
x ≡ 4 mod 23
x ≡ 9 mod 37
x ≡ a mod 14467
cyphertext = flag ^ a = 25183524468752482838730336135334402772668615375346038

Analysis

1. Task name - "Искусство войны" (The Art of War) - is a reference to Sun Tzu, the Chinese military strategist. This is also a hint towards the Chinese Remainder Theorem (CRT). ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

2. System of congruences - we are given three equations with moduli 17, 23, 37, which are pairwise coprime numbers.

3. Goal - find x, then calculate a = x mod 14467, and use a as the key for XOR decryption.

Solution

Step 1: Applying CRT

The Chinese Remainder Theorem allows us to find a unique solution x in the range [0, 172337) = [0, 14467):

 python read-only • copy allowed Copy
from sympy.ntheory.modular import crt

moduli = [17, 23, 37]
remainders = [7, 4, 9]

x, _ = crt(moduli, remainders)
print(f"x = {x}")  # x = 3339

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Step 2: Calculating key a

 python read-only • copy allowed Copy
a = x % 14467  # a = 3339

Since 17 * 23 * 37 = 14467, and x < 14467, then a = x = 3339.

Step 3: XOR decryption

 python read-only • copy allowed Copy
cyphertext = 25183524468752482838730336135334402772668615375346038
flag_int = cyphertext ^ a

# Convert to string
flag_bytes = flag_int.to_bytes((flag_int.bit_length() + 7) // 8, 'big')
print(flag_bytes.decode())  # CODEBY{REDACTED}

Full solution script

 python read-only • copy allowed Copy
#!/usr/bin/env python3
"""
Искусство войны (The Art of War) - hackerlab CTF
Chinese Remainder Theorem + XOR decryption
"""
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

from sympy.ntheory.modular import crt

# System of congruences from task.txt
moduli = [17, 23, 37]
remainders = [7, 4, 9]

# Solve using Chinese Remainder Theorem
x, _ = crt(moduli, remainders)
print(f"CRT solution: x = {x}")

# Calculate key a = x mod 14467
# Note: 17 * 23 * 37 = 14467, so a = x
a = x % 14467
print(f"Key a = {a}")

# XOR decrypt the ciphertext
cyphertext = 25183524468752482838730336135334402772668615375346038
flag_int = cyphertext ^ a

# Convert integer to bytes
flag_bytes = flag_int.to_bytes((flag_int.bit_length() + 7) // 8, 'big')
print(f"Flag: {flag_bytes.decode()}")

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Output:

CRT solution: x = 3339
Key a = 3339
Flag: CODEBY{REDACTED}

Theory: Chinese Remainder Theorem

CRT states that if m1, m2, ..., mk are pairwise coprime, then the system:

x ≡ r1 (mod m1)
x ≡ r2 (mod m2)
...
x ≡ rk (mod mk)

has a unique solution modulo M = m1 * m2 * ... * mk.

In this task: M = 17 * 23 * 37 = 14467, which matches the last modulus - this is a hint that the CRT solution is the key we're looking for. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍