Грааль (Grail)

Platform: caplag | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: Linux | Author: XESXOR | Date: 2026-02-22 | Status: Solved Techniques: coppersmith_method, known_high_bits_of_p, lattice_reduction

Summary

Task: RSA with 576 high bits of prime p revealed (p_revealed has 448 trailing zero bits). Solution: Coppersmith small_roots method to recover the unknown low bits and factor N.

Грааль (Grail) — CapLag CTF

Description

Слухи в Таверне гласят: кто найдет Грааль, тот получит бесконечный запас маны и золота.

Некромант Сандро путешествует по Эрафии в поисках Грааля. Координаты сокровища надежно зашифрованы могущественным заклинанием RSA. Чтобы снять защиту, нужно знать точное расположение всех Обелисков, которые формируют секретный магический фокус. Сандро успел посетить 6 из 8 Обелисков. Теперь он знает старшие биты магической координаты, но правый нижний угол карты все еще скрыт «Туманом войны». Не сумев полностью открыть карту, некромант в ярости бросил зашифрованный свиток и обрывок карты с открытыми Обелисками.

Разведчики передали эти данные вам. Сможете ли вы рассеять Туман войны, восстановить координату полностью и забрать Грааль до того, как Сандро вернется с армией скелетов? ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Theme: Heroes of Might and Magic III (Sandro, Erathia, Obelisks, Grail, Fog of War).

Files: task.txt — contains N, e, c, p_revealed.

Analysis

Parameters

Theme to Cryptography Mapping

Identifying the Attack Vector

1. p_revealed has 448 zero lower bits in binary representation (112 zero hex characters) — this means 576 high bits out of 1024 are known.

2. Coppersmith's method is applicable when the number of unknown bits is less than N^β²:

   • Unknown bits: 448
   • N^0.25 ≈ 512 bits
   • 448 < 512 ✓ — attack is possible!

3. Polynomial f(x) = x + p_high has a small root x₀ modulo the unknown divisor p of N.

Solution

SageMath: Coppersmith small_roots

 python read-only • copy allowed Copy
#!/usr/bin/env sage
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

N = 10478327092484087119158811738002527881601133392230605359728636777609815579869678283867331428873702230467781035800930319302134425662634483320132982489385831425841142683276245240139807770094242769842712285436324254272792640567220605759816440095519657990655930770697233495280191856795686977028814794477226478424022094334917595550943153970859743416443075466307652568512202801367425261698533904718831085305741122872685782348491901469147144819542733684143982118060593950861934225209591938661726842353411448979388331957984491039941720316208753034352185033359022438790970437880769652134820269624136545195696512412902086547737
e = 65537
c = 2371908478747310630059898986871876272895367385836679471620653994043895929391935759268461102073140210469448513517093388784915155590867680910861238126882230573331605292181787234136901129322001225804993239553253815115175454153650336400717451897405778509283155936103207023688258230128247475695422393595702338795973073870189334970154365471517517328052432202583617568778188997290909337026276528139911107673782208700833801910261741350704957213863331988920136397794697512939924729956005535011011328130093021943779761037406840279182736278184729352019628495185205816545145747722511667416937357754661788964429902091376671458313
p_high = 103537519170277717476703855704210234988984256477016725267975201195283786500355490562158033894185780133509016924890164868577876427195910662513213720292660530388165461591925825231155280679347647383014480743406031945282107222824466834575211761120068458069640414044465161781503967875409303695137308078472563785728
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Number of unknown bits
unknown_bits = 448

# Build polynomial f(x) = x + p_high in ring Z/NZ
P.<x> = PolynomialRing(Zmod(N))
f = x + p_high
f = f.monic()

# Find small roots using Coppersmith's method
# beta=0.5 — p ≈ sqrt(N), epsilon=0.02 — precision
roots = f.small_roots(X=2^unknown_bits, beta=0.5, epsilon=0.02)
print(f"Found roots: {roots}")

# Recover p
x0 = int(roots[0])
p = p_high + x0
q = N // p
assert p * q == N, "Factorization failed!"
print(f"p = {p}")
print(f"q = {q}")

# Decrypt
phi = (p - 1) * (q - 1)
d = inverse_mod(e, phi)
m = power_mod(c, d, N)
flag = bytes.fromhex(hex(m)[2:])
print(f"Flag: {flag.decode()}")

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

Result

Coppersmith's method found the root on the first attempt with epsilon=0.02. Factorization of N → p, q succeeded, after which standard RSA decryption yielded the flag.

Theoretical Background

Coppersmith's Method

Theorem (Coppersmith, 1996): Let N be a composite number, p an unknown divisor of N, |p| ≥ N^β. If f(x) is a univariate polynomial of degree δ with root x₀ mod p, and |x₀| < N^(β²/δ), then x₀ can be found in polynomial time.

Application to this task:

• β = 0.5 (p ≈ √N for standard RSA)
• δ = 1 (linear polynomial f(x) = x + p_high)
• Bound: |x₀| < N^(0.25) ≈ 2^512
• Our unknowns: 2^448 < 2^512 ✓ ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Inside the method:

1. A lattice is constructed from shifts of polynomial f(x)
2. LLL reduction finds a short vector
3. The short vector corresponds to a polynomial with a small root over Z
4. The root is found using standard methods

Practical SageMath Parameters

 python read-only • copy allowed Copy
f.small_roots(X=bound, beta=0.5, epsilon=0.02)

• X — upper bound of the root (2^unknown_bits)
• beta — N^beta ≤ p (0.5 for standard RSA)
• epsilon — affects lattice size and runtime (smaller = more precise, but slower) ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Notes

• Running required a Linux x86_64 VDS, as SageMath doesn't work natively on macOS ARM
• The Heroes of Might and Magic III theme maps perfectly to the cryptographic concepts of the task
• Classic task, but beautifully presented through a game metaphor ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍