Generating Unique Keys

[Chad Netzer]

On Monday 27 January 2003 14:25, Skip Montanaro wrote:
> Chad> If you see a sequence of
> Chad> random numbers, it is possible (in principle) to 'solve' the
> seed and sequence, and start predicting the next random
> numbers.

> Is this also true for the new-in-2.3 random number generator
> (Mersenne Twister)?  I'm not trying to pick nits with your arguments,
> just asking.  I know nothing about cryptography or random number
> generation.

While not an expert on the Mersenne Twister algorithm, I've looked at 
some (python) implementation code, and it seems as though it would also 
be "solvable" given not too much data.  It may take a fairly long 
sequence before being able to predict the future values, however.

Cryptographic Hash functions (and random number generators based on 
them) go much further, in that they are attempts to produce a "one-way" 
function.  They are based on ciphers, which always have some non-linear 
operations in their design (non-linear substitutions, or one-way 
sequences of operations).  They then typically do these operations over 
many 'rounds', which is where the non-reversability comes in (each 
round of one-way operations produces many one-to-many mappings of 
input).

It is a complex subject, and I'm no expert (but I have done some 
graduate studies on it), but basically, hashes are secure because they 
are designed to be, and they typically do LOTS of operations per input, 
compared to most PRNGs (which try to appear random, but are more 
concerned with speed of calculation; they have different design goals).

-- 
Bay Area Python Interest Group - http://www.baypiggies.net/

Chad Netzer
(any opinion expressed is my own and not NASA's or my employer's)