TMC Presentation

Theory of Modern
Cryptography
-Nidhi Ramolia
-92300170004
• Pseudo randomness
• Pseudorandom Functions
• Pseudorandom Permutations
Randomness
• Random numbers play an important role in the use of encryption for

various network security applications.
• The use of random numbers in cryptography and network security and
then focus on the principles of pseudorandom number generation.
The Use of Random Numbers
• A number of network security algorithms and protocols based on
cryptography make use of random binary numbers. For example
1. Key distribution and reciprocal
2. Session key generation
3. Generation of keys for the RSA public-key encryption algorithm
4. Generation of a bit stream for symmetric stream encryption
Randomness
• Traditionally, the concern in the generation of a sequence of allegedly
random numbers has been that the sequence of numbers be random
in some well-defined statistical sense. The following two criteria are
used to validate that a sequence of numbers is random:
1. Uniform distribution: The distribution of bits in the sequence should
be uniform; that is, the frequency of occurrence of ones and zeros
should be approximately equal.
2. Independence: No one subsequence in the sequence can be inferred
from the others.
UNPREDICTABILITY
• In applications such as reciprocal authentication, session key generation,
and stream ciphers, 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.
• Although true random numbers are used in some applications, they have
their limitations, such as inefficiency.
• Thus, it is more common to implement algorithms that generate
sequences of numbers that appear to be random.
• In this latter case, care must be taken that an opponent not be able to
predict future elements of the sequence on the basis of earlier elements.
TRNGs, PRNGs, and PRFs
• 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. However, if the algorithm
is good, the resulting sequences will pass many tests of randomness.
• Such numbers are referred to as pseudorandom numbers.
• The same principle applies in statistical applications, in which a
statistician takes a sample of a population and assumes that the results
will be approximately the same as if the whole population were
measured.
TRNGs, PRNGs, and PRFs
TRNG
• A true random number generator (TRNG) with two forms of pseudorandom
number generators.
• A TRNG takes as input a source that is effectively random; the source is often
referred to as an entropy source.
• In essence, the entropy source is drawn from the physical environment of the
computer and could include 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.
PRNG
• In contrast, a PRNG takes as input a fixed value, called the seed, and
produces a sequence of output bits using a deterministic algorithm.
• Quite often, the seed is generated by a TRNG.
• There is some feedback path by which some of the results of the
algorithm are fed back as input as additional output bits are
produced.
• The important thing to note is that the output bit stream is
determined solely by the input value or values, so that an adversary
who knows the algorithm and the seed can reproduce the entire bit
stream.
Pseudorandom Functions
• A pseudo-random function (PRF) in cryptography is a deterministic
function that behaves like a random function. It takes an input (often
called a "key") and produces an output that appears to be random,
even though it's generated through a deterministic process.
• Given an efficient, length-preserving key function F: {0,1}k  {0,1}* 
{0,1}*, we say F is a pseudorandom function iff for all PPT
distinguisher D, there exists a negligible function negl such that
|Pr[DFk()(1n)=1] – Pr[Df() (1n)=1]|  negl(n)
• Where k{0,1}n is chosen uniformly at random and f is chosen uniformly at
random from Funcn.
• D is given oracle access to a function, and needs to tell whether the function
is a random one, or one from F.
Pseudorandom Permutation
• A Pseudorandom Permutation (PRP) is a keyed permutation that is

indistinguishable from a random permutation.
• We say that a length-preserving keyed function F: {0,1}k  {0,1}* 
{0,1}*, is a keyed permutation if and only if each Fk is a bijection
• A Strong PRP is a keyed permutation is indistinguishable from a
random permutation when the distinguisher is given access to both
the function and its inverse
• We assume block ciphers are PRP.

TMC Presentation

Uploaded by

Copyright:

Available Formats

TMC Presentation

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

TMC Presentation

Uploaded by

Copyright:

Available Formats

Theory of Modern

• Random numbers play an important role in the use of encryption for

• Cryptographic applications typically make use of algorithmic

• A Pseudorandom Permutation (PRP) is a keyed permutation that is

You might also like