Noisy EC-LCG x-recovery (high-level)

Archived research-oriented notes (HackMD title “ok”) about a cryptography challenge. Actionable solver recipes, lattice attack procedures, and flag-recovery steps are omitted.

Problem theme

• An elliptic-curve related generator exposes noisy x-coordinates $S_i = x_i - r_i$ with bounded noise $|r_i| \le \Delta$
• The checker ultimately asks for a correct base point x-coordinate (equality gate / “ok” path)
• Public literature on EC-LCG predictability (e.g. Gutierrez–Ibeas, Mérai) assumes cleaner or differently shaped observations than this high-noise, x-only setting—so those results are directional, not drop-in breaks

Conceptual reduction (non-actionable)

The notes argue the useful research target is closer to a one-variable bounded rational-residue recovery problem: find a small $E$ such that related modular rational residues stay inside a small centered interval for each sample index. That sits near classical Hidden Number Problem / modular residue intuition, not “paste a public EC-LCG solver.”

Why it is hard (abstract)

• Noise magnitude on the order of a large fraction of the field size weakens simple Coppersmith / low-dimensional lattice templates
• Exact recurrence identities help verify candidates more than they magically produce the secret under heavy noise
• Multivariate or discriminant-linearization ideas appear in the notebook as research directions, not as a finished public exploit

Lessons / what to check in real systems

• If you ship noisy elliptic samples, treat residual structure as sensitive; prefer conservative noise and key sizes aligned with current lattice cryptanalysis guidance
• Do not assume “EC-LCG paper exists ⇒ this parameter set is broken”; match the observation model carefully
• For CTF design, equality checks on recovered coordinates are fine teaching oracles; for production, use vetted KEMs/signatures instead of home-grown generators

Solve steps and PoC omitted.