(Non optimal) Implementation of lattice reduction attacks on LCG and PCG
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
README.md
attack.ipynb

README.md

PCG_attack

(Non optimal) Implementation in Sage of lattice reduction attacks on LCG and PCG

This is a proof of concept of Frieze, Hastad, Kannan et al.'s paper (Reconstructing truncated integer variables satisfying linear congruences). It can be used on a multiplicative LCG, or a general LCG. Exemples are given at the end of the source code.

Moreover, I added support for an attack on PCG (PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation). Even though resolution is quite slow on this generator (and my code could be greatly optimized), the computational security does not exceed 2^62 bits, way under the recommandations of the NIST (112 bits).