
T
HE
I
NTEL
®
R
ANDOM
N
UMBER
G
ENERATOR
C
RYPTOGRAPHY
R
ESEARCH
, I
NC
. W
HITE
P
APER PREPARED FOR
I
NTEL
C
ORPORATION
Benjamin Jun and Paul Kocher
April 22, 1999
Information in this white paper is provided without guarantee or warranty of any kind. This review represents the
opinions of Cryptography Research and may or may not reflect opinions of Intel Corporation. Characteristics of the
Intel RNG may vary with design or process changes. © 1999 by Cryptography Research, Inc. and Intel Corporation.
1. Introduction
Good cryptography requires good random
numbers. This paper evaluates the hardware-
based Intel Random Number Generator (RNG)
for use in cryptographic applications.
Almost all cryptographic protocols require
the generation and use of secret values that must
be unknown to attackers. For example, random
number generators are required to generate
public/private keypairs for asymmetric (public
key) algorithms including RSA, DSA, and
Diffie-Hellman. Keys for symmetric and hybrid
cryptosystems are also generated randomly.
RNGs are also used to create challenges, nonces
(salts), padding bytes, and blinding values. The
one time pad – the only provably-secure
encryption system – uses as much key material
as ciphertext and requires that the keystream be
generated from a truly random process.
Because security protocols rely on the
unpredictability of the keys they use, random
number generators for cryptographic
applications must meet stringent requirements.
The most important is that attackers, including
those who know the RNG design, must not be
able to make any useful predictions about the
RNG outputs. In particular, the apparent entropy
of the RNG output should be as close as
possible to the bit length.
According to Shannon
1
, the entropy
H
of
any message or state is:
1
Shannon, C.E., “A Mathematical Theory of
Communication,”
The Bell System Technical Journal,
vol. 27, p. 379-423, July 1948.
,log
1
∑
=
−=
n
i
ii
ppKH
where
p
i
is the probability of state
i
out of
n
possible states and
K
is an optional constant to
provide units (e.g.,
)2log(
1
bit). In the case of a
random number generator that produces a
k
-bit
binary result,
p
i
is the probability that an output
will equal
i
, where
k
i
20
<≤
. Thus, for a
perfect
random number generator,
p
i
= 2
-k
and
the entropy of the output is equal to
k
bits. This
means that all possible outcomes are equally
(un)likely, and on average the information
present in the output cannot be represented in a
sequence shorter than
k
bits. In contrast, the
entropy of typical English alphabetic text is 1.5
bits per character.
2
An RNG for cryptographic applications
should appear to computationally-bounded
adversaries to be close as possible to a perfect
RNG. For this review, we analyze whether there
is any feasible way to distinguish the Intel RNG
from a perfect RNG.
2. Pseudorandomness
Most “random” number sources actually
utilize a pseudorandom generator (PRNG).
PRNGs use deterministic processes to generate
a series of outputs from an initial seed state.
Because the output is purely a function of the
seed data, the actual entropy of the output can
never exceed the entropy of the seed. It can,
2
Menezes, Oorschot, and Vanstone,
Handbook of Applied Cryptography
,
Ch.7, CRC Press, 1997.