Real Eisenstein

Platform: cryptohack | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-06-22 | Status: Solved Techniques: lattice_construction_with_weight_column, lll_integer_relation, sum_of_sqrt_primes_recovery

Summary

Task: ciphertext = floor(16^64 * sum_i ord(flag[i]) * sqrt(PRIMES[i])). Solution: this is an integer-relation problem; build an LLL lattice whose rows are the identity (one per character) plus a heavily weighted column equal to round(16^64 * sqrt(prime_i)), with a final row carrying -ciphertext. LLL finds the short vector whose entries are the printable ASCII codes of the flag (crypto{REDACTED}).

Real Eisenstein — cryptohack (Mathematics)

Description

"I've hidden my secret among the primes. Reducing the number back down to the flag shouldn't be possible!"

File: real_eisenstein.py:

 python read-only • copy allowed Copy
from decimal import getcontext, Decimal
getcontext().prec = 100
PRIMES = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103]
h = Decimal(0.0)
for i, c in enumerate(FLAG):
    h += ord(c) * Decimal(PRIMES[i]).sqrt()
ct = math.floor(h * 16**64)
# ciphertext: 1350995397927355657956786955603012410260017344805998076702828160316695004588429433

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

The ciphertext is a high-precision encoding of Σ ord(flag[i]) · √(prime_i), scaled by 16^64.

Analysis

Each flag character c_i contributes ord(c_i) · √(prime_i). The √(prime_i) are linearly independent over the rationals, so the ciphertext is essentially an integer relation:

ct ≈ Σ c_i · round(16^64 · √(prime_i))

Greedy left-to-right recovery fails: dividing the running value by √2 does not isolate the first coefficient because all the other √-terms contaminate it. This is the classic setting for LLL lattice reduction. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Lattice construction

Build an (n+1) × (n+2) integer matrix (with n = flag length = 23):

• Rows 0..n-1: identity in the first n columns (one slot per character c_i), and in column n put s_i = round(16^64 · √(prime_i)).
• Row n: column n holds -ct; the last column n+1 holds 1 (an anchor).

LLL finds a short combination Σ c_i · s_i − ct ≈ 0; the coefficient block (c_0, …, c_{n-1}) of the short vector spells out the printable ASCII codes of the flag.

Solution

 python read-only • copy allowed Copy
from decimal import Decimal, getcontext
getcontext().prec = 200
from fpylll import IntegerMatrix, LLL
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

PRIMES = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103]
ct = 1350995397927355657956786955603012410260017344805998076702828160316695004588429433
n  = 23                         # flag length
K  = Decimal(16) ** 64

M = IntegerMatrix(n + 1, n + 2)
for i in range(n):
    M[i, i] = 1
    M[i, n] = int((Decimal(PRIMES[i]).sqrt() * K).to_integral_value())
M[n, n]     = -ct
M[n, n + 1] = 1

LLL.reduction(M)
for r in range(n + 1):
    row = [M[r, c] for c in range(n + 2)]
    if abs(row[n]) < 10**60:                 # near-zero value column -> the relation
        flag = ''.join(chr(abs(x)) for x in row[:n] if 0 < abs(x) < 256)
        if flag.startswith('crypto'):
            print(flag)

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

Output:

crypto{REDACTED}

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