Cryptography Reference
In-Depth Information
True Random Number Generators (TRNG)
True random number generators (TRNGs) are characterized by the fact that their
output cannot be reproduced. For instance, if we flip a coin 100 times and record the
resulting sequence of 100 bits, it will be virtually impossible for anyone on Earth
to generate the same 100 bit sequence. The chance of success is 1 / 2 100 , which is
an extremely small probability. TRNGs are based on physical processes. Examples
include coin flipping, rolling of dice, semiconductor noise, clock jitter in digital
circuits and radioactive decay. In cryptography, TRNGs are often needed for gener-
ating session keys, which are then distributed between Alice and Bob, and for other
purposes.
(General) Pseudorandom Number Generators (PRNG)
Pseudorandom number generators (PRNGs) generate sequences which are com-
puted from an initial seed value. Often they are computed recursively in the follow-
ing way:
s 0 = seed
s i +1 = f ( s i ) , i = 0 , 1 ,...
A generalization of this are generators of the form s i +1 = f ( s i , s i 1 ,..., s i t ), where
t is a fixed integer. A popular example is the linear congruential generator :
s 0 = seed
s i +1
as i + b mod m , i = 0 , 1 ,...
where a , b , m are integer constants. Note that PRNGs are not random in a true sense
because they can be computed and are thus completely deterministic. A widely used
example is the rand() function used in ANSI C. It has the parameters:
s 0 = 12345
s i +1
1103515245 s i + 12345 mod 2 31 , i = 0 , 1 ,...
A common requirement of PRNGs is that they possess good statistical proper-
ties, meaning their output approximates a sequence of true random numbers. There
are many mathematical tests, e.g., the chi-square test, which can verify the statistical
behavior of PRNG sequences. Note that there are many, many applications for pseu-
dorandom numbers outside cryptography. For instance, many types of simulations
or testing, e.g., of software or of VLSI chips, need random data as input. That is the
reason why a PRNG is included in the ANSI C specification.
Search WWH ::




Custom Search