Re: linear congruential pseudorandom number generator question

From: David Wagner (daw_at_taverner.cs.berkeley.edu)
Date: 04/30/05 

Date: Sat, 30 Apr 2005 05:53:27 +0000 (UTC)

Korejwa wrote:
>If I have a sequence of numbers that I know were generated by a linear
>congruential pseudorandom number generator, how can I calculate the
>internal state of the generator?

>The pseudorandom number generator performs this function:
>
>Y = (A * X + C) MOD N
>return a value which reduces X to the range of a specified Min-Max value.
>
>A, C, and N are known constants. X is modified each time the function is
>called.

Given Y, it is trivial to learn X, since X = A^{-1} * (Y - C) mod N,
and inverses can be computed using the extended Euclidean algorithm.

Relevant Pages

  • Re: Leaking state
    ... Exactly which bits of the internal state are being returned is ... >> the generator so that it returns two of it's original output XOR'd ... then isn't your PRNG now simply have one more operation in it? ... bad thing" because an attacker would then know a specific portion of the ...
    (sci.crypt)
  • Leaking state
    ... Suppose I have a PRNG that returns 32-bit integers, ... Exactly which bits of the internal state are being returned is ... Do I have an automatic weakness in my generator since the ... the generator so that it returns two of it's original output XOR'd together. ...
    (sci.crypt)
  • Re: Leaking state
    ... Exactly which bits of the internal state are being returned is ... > non-determinable by the PRNG user without him knowing the internal state, ... > the generator so that it returns two of it's original output XOR'd together. ... I've gotten roughly those numbers wuth AES in CTR mode. ...
    (sci.crypt)
  • Re: threads do not get cpa
    ... > Also note that some implementations of drand48require a mutex to ... > protect the internal state of the random number generator. ...
    (comp.sys.sgi.misc)
  • linear congruential pseudorandom number generator question
    ... congruential pseudorandom number generator, ... Each consecutive output reduces the set of possible ... you calculate the reduced set of possible X values for each known ...
    (sci.crypt)