CUSTOMMediumCrypto

Грааль (Grail)

XESXOR9/2/20264 min read

#crypto#custom#medium#coppersmith_method#known_high_bits_of_p#lattice_reduction

Грааль (Grail)

Platform: CUSTOM | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: N/A | **Author: XESXOR Techniques: coppersmith_method, known_high_bits_of_p, lattice_reduction

Summary

Walkthrough of the CUSTOM Crypto Грааль (Grail). 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.

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

Parameter	Value
N	2047 bits (RSA modulus)
e	65537 (standard)
p_revealed	1024 bits, but with 448 zero lower bits
Known bits of p	576 high bits
Unknown bits of p	448 low bits

Theme to Cryptography Mapping

Heroes III	Cryptography
8 Obelisks	1024 bits of prime p (128 bits × 8)
6 of 8 visited	576 of 1024 bits known (high bits)
Fog of War	448 unknown low bits
Grail	Flag
RSA spell	RSA encryption
‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

Identifying the Attack Vector

p_revealed has 448 zero lower bits in binary representation (112 zero hex characters) — this means 576 high bits out of 1024 are known.
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!
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
#!/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:

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

Practical SageMath Parameters

 python read-only • copy allowed
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 ‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

Key Takeaways / Lessons

Mastering coppersmith_method, known_high_bits_of_p, lattice_reduction was key to this challenge.
Always check for common misconfigurations and verify assumptions.

Crafted by XESXOR Research • 2026-02-22 • CUSTOM • Грааль (Grail) • Difficulty: Medium