cryptanalysis of Linear Congruence Generators

what is it

generating random numbers by repeatedly calculating:
X[n+1] = X[n] * a + b (mod m)

Cryptanalyses of Linear Congruential Generators:

• Reeds, J. (1977), "Cracking" a Random Number Generator. Cryptologia. 1(1). (Also [41: 509-515].)
• Vahle, M. and L. Tolendino. (1982), Breaking a Pseudo Random Number Based Cryptographic Algorithm. Cryptologia. 6: 319-328.
• Frieze A. and Kannan R. and Lagarias J. (1984), Linear Congruential Generators Do Not Produce Random Sequences, FOCS 1984
• Hňstad J. and Shamir A. (1985), The Cryptographic Security of Truncated Linearly Related Variables, STOC 1985
• Knuth, D. (1985), Deciphering a Linear Congruential Encryption. IEEE Transactions on Information Theory. IT-31: 49-52.
• Stern J. (1987), Secret Linear Congruential Generators are not Cryptographically Secure, Proc of the IEEE Symposium on Foundations of Computer Science
• Frieze A. and Hňstad J. and Kannan R. and Lagarias J. and Shamir A. (1988), Reconstructing Truncated Integer Variables Satisfying Linear Congruences, SIAM J. Comput. 17

online lcg analysis

http://www.uni-mainz.de/~pommeren/Kryptologie/Bitstrom/2_Analyse/lcgc.html
how does it work: http://www.uni-mainz.de/~pommeren/Kryptologie/Bitstrom/2_Analyse/lkgunbek.pdf

schrage's algorithm

useful: multiply 2 nrs without overflows

# calc  a * x mod m
sub schragesmult { my (\$a, \$x, \$m)=@_;
my \$q= int(\$m/\$a);
my \$r= \$m % \$a;

my \$left= \$a * (\$x % \$q);
my \$right= \$r * int(\$x/\$q);
return \$left-\$right+(\$left<\$right)?\$m:0;
}