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
    how does it work:

    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;