Attacks on Predicting Polynomial Congruential Generators

SageMath implementation of cryptanalytic attacks presented in FNPZ26 that predict the output of polynomial congruential generators (PCGs) from arbitrarily long sequences of consecutive truncated outputs.

The attacks reduce the prediction problem to solving a system of modular polynomial equations, which is handled by Coppersmith's method enhanced with an automated Newton-polytope framework (MN23, FLCNP25).

This is a research implementation and uses AI techniques to speed up the process for code generation.

Five generator scenarios are supported (v_{i+1} denotes the next state, all arithmetic modulo p):

Each attack works with truncated outputs in three modes:

• msb — the high k bits are revealed
• lsb — the low k bits are revealed
• mixed — each position is msb or lsb at random

• SageMath (9.5 used for development)
• flatter (optional but recommended; falls back to Sage's LLL automatically)

sage -python pcg_attack.py qcg_ka_ub

You will be prompted for l, k, n, m, the output mode (mixed/msb/lsb), and for perturbed_power, the exponent e.

sage -python pcg_attack.py all

This runs the first row of each attack's test dataset (from test_data.py) in msb mode and prints a summary table of all results.

sage -python run_test_data.py

Iterates over all rows in test_data.py (one trial per row, msb mode). Each successful trial's detailed log is written to test_data.log; a failed row is retried up to 5 times.

test_data.py holds the experiment parameters extracted from the paper's validation tables. All rows use prime bit-length l = 256. Each row maps directly to a generate_*() call:

• QCG_KA_UB — qcg_ka_ub (k = 203 / 190 / 184, n = 2 / 3 / 4, m = 2)
• QCG_UA_KB — qcg_ua_kb (k = 234 / 230 / 228, n = 2 / 3 / 4, m = 2)
• POLLARD — pollard (k = 202 / 187 / 182, n = 2 / 3 / 4, m = 3)
• POWER_PERTURBED — perturbed_power (e = 3, k = 230 / 224 / 221, n = 2 / 3 / 4, m = 2)
• LCG — lcg (k = 201 / 187 / 183, n = 2 / 3 / 4, m = 3)

The delta column is the experimental bound (l - k) / l; omega is the number of shift polynomials / monomials (the lattice dimension); time is the reported running time in seconds.

PCG/
├── pcg_attack.py             # Main implementation (all 5 attacks + CLI)
├── test_data.py              # Test parameters extracted from the paper tables
├── run_test_data.py          # Reproduction script -> test_data.log
├── pcg_attack.log            # Per-run debug/INFO log (generated)
├── test_data.log             # Detailed logs of all reproduced runs (generated)
├── test_data.txt             # Record of all reproduced runs
└── README.md                 # This file

For every run the terminal shows the parameter header, the construction stage, the lattice dimension (omega), the reduction/root-extraction times, and a final summary line, e.g.

[Pollard Generator] ✓ SUCCESS
pollard  l=256  k=187  n=3  m=3  mode=msb  delta=0.270  omega=96  time=5.228s

The same information is written, in a staged INFO/DEBUG form, to pcg_attack.log.

Academic research code. Refer to the respective component licenses (SageMath, flatter) for redistribution terms.