Unit 1

Pseudorandom Number
Generators
 Random Numbers
• A number of network security algorithms and
protocols based on cryptography make use of random
binary numbers:
• Key distribution and reciprocal authentication schemes
• Session key generation
• Generation of keys for the RSA public-key encryption
algorithm
• Generation of a bit stream for symmetric stream
encryption

Randomness
There are two distinct
requirements for a
sequence of random
numbers:
Unpredictability
 Randomness
• The generation of a sequence of allegedly
random numbers being random in some well-
defined statistical sense has been a concern

Two criteria are used to validate that a

sequence of numbers is random:
Uniform distribution
• The frequency of occurrence of ones and zeros should
be approximately equal

Independence
• No one subsequence in the sequence can be inferred
from the others
 Unpredictability
• The requirement is not just that the sequence of
numbers be statistically random, but that the
successive members of the sequence are
unpredictable
• With “true” random sequences each number is
statistically independent of other numbers in the
sequence and therefore unpredictable
• True random numbers have their limitations, such as
inefficiency, so it is more common to implement
algorithms that generate sequences of numbers that
appear to be random
• Care must be taken that an opponent not be able to
predict future elements of the sequence on the basis of
earlier elements
Pseudorandom Numbers
• Cryptographic applications typically make use
of algorithmic techniques for random number
generation

• These algorithms are deterministic and

therefore produce sequences of numbers that
are not statistically random

• If the algorithm is good, the resulting

sequences will pass many tests of randomness
and are referred to as pseudorandom numbers
 True Random Number
Generator (TRNG)
• Takes as input a source that is effectively random
• The source is referred to as an entropy source and is
drawn from the physical environment of the computer
• Includes things such as keystroke timing patterns, disk
electrical activity, mouse movements, and instantaneous
values of the system clock
• The source, or combination of sources, serve as input to
an algorithm that produces random binary output

• The TRNG may simply involve conversion of an analog

source to a binary output
• The TRNG may involve additional processing to
overcome any bias in the source
 Pseudorandom Number
Generator (PRNG)
• Takes as input a fixed value,
called the seed, and produces a Two different forms of PRNG
sequence of output bits using a
deterministic algorithm
Pseudorandom Pseudorandom
• Quite often the seed is number generator function (PRF)
generated by a TRNG
• An algorithm that is • Used to produce a
• The output bit stream is used to produce an pseudorandom string
determined solely by the open-ended sequence
of bits
of bits of some fixed
length
input value or values, so an • Input to a symmetric • Examples are
adversary who knows the stream cipher is a symmetric encryption
algorithm and the seed can common application keys and nonces
for an open-ended
reproduce the entire bit sequence of bits
stream
• Other than the number of
bits produced there is no
difference between a PRNG
and a PRF
 PRNG Requirements
• The basic requirement when a PRNG or PRF is
used for a cryptographic application is that an
adversary who does not know the seed is
unable to determine the pseudorandom string
• The requirement for secrecy of the output of a
PRNG or PRF leads to specific requirements in
the areas of:
• Randomness
• Unpredictability
• Characteristics of the seed
 Randomness
• The generated bit stream needs to appear random
even though it is deterministic
• There is no single test that can determine if a PRNG
generates numbers that have the characteristic of
randomness
• If the PRNG exhibits randomness on the basis of multiple
tests, then it can be assumed to satisfy the randomness
requirement
• NIST SP 800-22 specifies that the tests should seek to
establish three characteristics:
• Uniformity
• Scalability
• Consistency
 Randomness Tests
• SP 800-22 lists 15
separate tests of Runs test
randomness • Focus of this test is the total
Maurer’s
number of runs in the sequence,
where a run is an uninterrupted universal
Frequency test sequence of identical bits statistical test
bounded before and after with a
• The most basic test bit of the opposite value • Focus is the number
and must be included of bits between
• Purpose is to determine whether
in any test suite matching patterns
the number of runs of ones and
• Purpose is to zeros of various lengths is as • Purpose is to detect
determine whether expected for a random sequence whether or not the
the number of ones sequence can be
and zeros in a significantly
sequence is compressed without
approximately the loss of information.
same as would be A significantly
expected for a truly compressible
random sequence
Three sequence is
considered to be
non-random
tests
 Unpredictability
• A stream of pseudorandom numbers should exhibit two forms of
unpredictability:

• Forward unpredictability
• If the seed is unknown, the next output bit in the sequence should be
unpredictable in spite of any knowledge of previous bits in the
sequence

• Backward unpredictability
• It should not be feasible to determine the seed from knowledge of
any generated values. No correlation between a seed and any value
generated from that seed should be evident; each element of the
sequence should appear to be the outcome of an independent
random event whose probability is 1/2

• The same set of tests for randomness also provides a test of

unpredictability
• A random sequence will have no correlation with a fixed value (the
seed)
 Seed Requirements
• The seed that serves as input to the PRNG
must be secure and unpredictable

• The seed itself must be a random or

pseudorandom number

• Typically the seed is generated by TRNG

Generation
of
Seed
Input
to
PRNG
 Algorithm Design
• Algorithms fall into two categories:
• Purpose-built algorithms
• Algorithms designed specifically and solely for
the purpose of generating pseudorandom bit
streams
• Algorithms based on existing cryptographic
algorithms
• Have the effect of randomizing input data
Three broad categories of cryptographic algorithms are
commonly used to create PRNGs:
• Symmetric block ciphers
• Asymmetric ciphers
• Hash functions and message authentication codes
Linear Congruential Generator
• An algorithm first proposed by Lehmer that is parameterized
with four numbers:
m the modulus m>0
a the multiplier 0 < a< m
c the increment 0≤ c < m
X0 the starting value, or seed 0 ≤ X0 < m

• The sequence of random numbers {Xn} is obtained via the following

iterative equation:
Xn+1 = (aXn + c) mod m

• If m , a , c , and X0 are integers, then this technique will produce a sequence

of integers with each integer in the range 0 ≤ Xn < m

• The selection of values for a , c , and m is critical in developing a

good random number generator
 Blum Blum Shub (BBS)
Generator
• Has perhaps the strongest public proof of its
cryptographic strength of any purpose-built
algorithm
• Referred to as a cryptographically secure
pseudorandom bit generator (CSPRBG)
• A CSPRBG is defined as one that passes the next-bit-
test if there is not a polynomial-time algorithm that,
on input of the first k bits of an output sequence, can
predict the (k + 1)st bit with probability significantly
greater than 1/2

• The security of BBS is based on the difficulty of

factoring n
 Table 7.1
Example Operation of BBS Generator
PRNG Using Block Cipher Modes of Operation

• Two approaches that use a block cipher to build a PNRG have gained
widespread acceptance:
• CTR mode (Counter )
Counter mode turns a block cipher into a stream cipher. It generates the
next keystream block by encrypting successive values of a "counter". The
counter can be any function which produces a sequence which is
guaranteed not to repeat for a long time, although an actual increment-by-
one counter is the simplest and most popular.
• Recommended in NIST SP 800-90, ANSI standard X.82, and RFC 4086
• OFB mode(Output Feedback)
The Output Feedback (OFB) mode makes a block cipher into a
synchronous stream cipher. It generates keystream blocks, which are
then XORed with the plaintext blocks to get the ciphertext.
• Recommended in X9.82 and RFC 4086
 Table 7.2

Example Results for PRNG Using OFB

 Table 7.3

Example Results for PRNG Using CTR

 ANSI X9.17 PRNG
Input
• One of the
strongest PRNGs is • Two pseudorandom inputs drive the
generator. One is a 64-bit representation
specified in ANSI of the current date and time. The other is
X9.17 a 64-bit seed value; this is initialized to
some arbitrary value and is updated
• A number of during the generation process.
applications
employ this
technique The algorithm makes use of
including
financial security triple DES for encryption.
applications and Ingredients are:
PGP
Keys
Output
• The generator makes use of three triple
• The output consists of a 64-bit DES encryption modules. All three make
pseudorandom number and a 64-bit seed use of the same pair of 56-bit keys, which
value. must be kept secret and are used only
for pseudorandom number generation.
 ANSI X9.17 PRNG

Dti = date and time