Notes

Chapter 10: Processes of Perception and Analysis

Section 10: Cryptography and Cryptanalysis


[Cryptanalysis of] linear congruential generators

Cryptanalysis of linear congruential generators is fairly straightforward. Given only an output list NestList[Mod[a #, m]&, x, n] parameters {a, m} that generate the list can be found for sufficiently large n from

With[{α = Apply[(#2 . Rest[list]/#1) &, Apply[ExtendedGCD, Drop[list, -1]]]}, {Mod[α, #], #} &[ Fold[GCD[#1, If[#1 == 0, #2, Mod[#2, #1]]] &, 0, ListCorrelate[{α, -1}, list]]]]

With slightly more effort both x and {a, m} can be found just from First[IntegerDigits[list, 2, p]].


From Stephen Wolfram: A New Kind of Science [citation]