cryptanalysis of Linear Congruence Generators

what is it

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

see http://mathworld.wolfram.com/LinearCongruenceMethod.html

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;
}