Home Cryptography course assignment

Cryptography course assignment

Find an article that discusses attacks on Public Key encryption. Write a one to two page paper on the topic
Be sure to cite your sourcesBe sure to use APA format

https://getpocket.com/explore/item/the-woman-who-smashed-codes-the-untold-story-of-cryptography-pioneer-elizebeth-friedman?utm_source=pocket-newtab

Cryptography and Network Security: Principles and Practice

Seventh Edition

Chapter 8

Random Bit Generation and Stream Ciphers

If this PowerPoint presentation contains mathematical equations, you may need to check that your computer has the following installed:
1) MathType Plugin
2) Math Player (free versions available)
3) NVDA Reader (free versions available)
Lecture slides prepared for “Cryptography and Network Security”, 7/e, by William Stallings, Chapter 17 – “Transport-Level Security”.
Virtually all businesses, most government agencies, and many individuals now have
Web sites. The number of individuals and companies with Internet access is expanding
rapidly and all of these have graphical Web browsers. As a result, businesses are enthusiastic
about setting up facilities on the Web for electronic commerce. But the reality
is that the Internet and the Web are extremely vulnerable to compromises of various
sorts. As businesses wake up to this reality, the demand for secure Web services grows.
The topic of Web security is a broad one and can easily fill a book. In this chapter,
we begin with a discussion of the general requirements for Web security and then focus
on three standardized schemes that are becoming increasingly important as part of Web
commerce and that focus on security at the transport layer: SSL/TLS, HTTPS, and SSH.

Random Numbers (1 of 2)
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 R S A public-key encryption algorithm
Generation of a bit stream for symmetric stream encryption

A number of network security algorithms and protocols based on cryptography
make use of random binary numbers. For example,
• Key distribution and reciprocal (mutual) authentication schemes, such as
those discussed in Chapters 14 and 15. In such schemes, two communicating
parties cooperate by exchanging messages to distribute keys and/or authenticate
each other. In many cases, nonces are used for handshaking to prevent
replay attacks. The use of random numbers for the nonces frustrates an opponent’s
efforts to determine or guess the nonce, in order to repeat an obsolete
transaction.
• Session key generation. We will see a number of protocols in this book where
a secret key for symmetric encryption is generated for use for a particular
transaction (or session) and is valid for a short period of time. This key is
generally called a session key.
• Generation of keys for the RSA public-key encryption algorithm (described
in Chapter 9).
• Generation of a bit stream for symmetric stream encryption (described in this
chapter).
These applications give rise to two distinct and not necessarily compatible
requirements for a sequence of random numbers: randomness and unpredictability.
2

Random Numbers (2 of 2)
There are two distinct requirements for a sequence of random numbers:
Randomness
Unpredictability

Randomness (1 of 2)
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

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:
• 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.
• Independence: No one subsequence in the sequence can be inferred from the
others.
Although there are well-defined tests for determining that a sequence of bits
matches a particular distribution, such as the uniform distribution, there is no such
test to “prove” independence. Rather, a number of tests can be applied to demonstrate
if a sequence does not exhibit independence. The general strategy is to apply
a number of such tests until the confidence that independence exists is sufficiently
strong. That is, if each of a number of tests fails to show that a sequence of bits is
not independent, then we can have a high level of confidence that the sequence is in
fact independent.
4

Unpredictability (1 of 2)
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

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, as is discussed shortly. 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.
5

Unpredictability (2 of 2)
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

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 .
You may be somewhat uneasy about the concept of using numbers generated
by a deterministic algorithm as if they were random numbers. Despite what might be
called philosophical objections to such a practice, it generally works. That is, under
most circumstances, pseudorandom numbers will perform as well as if they were
random for a given use. The phrase “as well as” is unfortunately subjective, but the
use of pseudorandom numbers is widely accepted. 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
7

Figure 8.1 Random and Pseudorandom Number Generators

Figure 8.1 contrasts a true random number generator (TRNG) with two forms
of pseudorandom number generators.

True Random Number Generator (T R N G)
(1 of 2)
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

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; this is discussed in Section 8.6.

True Random Number Generator (T R N G)
(2 of 2)
The T R N G may simply involve conversion of an analog source to a binary output
The T R N G may involve additional processing to overcome any bias in the source

Pseudorandom Number Generator (P R N G)
(1 of 2)
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 T R N G
The output bit stream is determined solely by the input value or values, so an adversary who knows the algorithm and the seed can reproduce the entire bit stream
Other than the number of bits produced there is no difference between a P R N G and a P R F

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. Typically, as shown, 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.
Figure 8.1 shows two different forms of PRNGs, based on application.
• Pseudorandom number generator: An algorithm that is used to produce an
open-ended sequence of bits is referred to as a PRNG. A common application
for an open-ended sequence of bits is as input to a symmetric stream cipher, as
discussed in Section 8.4. Also, see Figure 4.1a.
• Pseudorandom function (PRF): A PRF is used to produced a pseudorandom
string of bits of some fixed length. Examples are symmetric encryption keys
and nonces. Typically, the PRF takes as input a seed plus some context specific
values, such as a user ID or an application ID. A number of examples of
PRFs will be seen throughout this book, notably in Chapters 17 and 18.
Other than the number of bits produced, there is no difference between a PRNG
and a PRF. The same algorithms can be used in both applications. Both require a seed
and both must exhibit randomness and unpredictability. Further, a PRNG application
may also employ context-specific input. In what follows, we make no distinction
between these two applications.
11

Pseudorandom Number Generator (P R N G)
(2 of 2)
Two different forms of P R N G
Pseudorandom number generator
An algorithm that is used to produce an open-ended sequence of bits
Input to a symmetric stream cipher is a common application for an open-ended sequence of bits
Pseudorandom function (P R F)
Used to produce a pseudorandom string of bits of some fixed length
Examples are symmetric encryption keys and nonces

P R N G Requirements
The basic requirement when a P R N G or P R F 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 P R N G or P R F leads to specific requirements in the areas of:
Randomness
Unpredictability
Characteristics of the seed

When a PRNG or PRF is used for a cryptographic application, then the basic
requirement is that an adversary who does not know the seed is unable to determine
the pseudorandom string. For example, if the pseudorandom bit stream is
used in a stream cipher, then knowledge of the pseudorandom bit stream would
enable the adversary to recover the plaintext from the ciphertext. Similarly, we
wish to protect the output value of a PRF. In this latter case, consider the following
scenario. A 128-bit seed, together with some context-specific values, are used
to generate a 128-bit secret key that is subsequently used for symmetric encryption.
Under normal circumstances, a 128-bit key is safe from a brute-force attack.
However, if the PRF does not generate effectively random 128-bit output values,
it may be possible for an adversary to narrow the possibilities and successfully use
a brute force attack.
This general requirement for secrecy of the output of a PRNG or PRF leads to
specific requirements in the areas of randomness, unpredictability, and the characteristics
of the seed. We now look at these in turn.
13

Randomness (2 of 2)
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

In terms of randomness, the requirement for a PRNG is that the generated
bit stream 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. The best that can be done is to apply a sequence of tests to the
PRNG. 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 the following three
characteristics.
• Uniformity: At any point in the generation of a sequence of random or pseudorandom
bits, the occurrence of a zero or one is equally likely, i.e., the probability
of each is exactly 1/2. The expected number of zeros (or ones) is n /2,
where n = the sequence length.
• Scalability: Any test applicable to a sequence can also be applied to subsequences
extracted at random. If a sequence is random, then any such extracted
subsequence should also be random. Hence, any extracted subsequence
should pass any test for randomness.
• Consistency: The behavior of a generator must be consistent across starting
values (seeds). It is inadequate to test a PRNG based on the output from a
single seed or an TRNG on the basis of an output produced from a single
physical output.
14

Randomness Tests (1 of 3)
S P 800-22 lists 15 separate tests of randomness
Three tests
Frequency test
The most basic test and must be included in any test suite
Purpose is to determine whether the number of ones and zeros in a sequence is approximately the same as would be expected for a truly random sequence

15
SP 800-22 lists 15 separate tests of randomness. An understanding of these
tests requires a basic knowledge of statistical analysis, so we don’t attempt a
technical description here. Instead, to give some flavor for the tests, we list three of
the tests and the purpose of each test, as follows.
• Frequency test: This is the most basic test and must be included in any test
suite. The purpose of this test is to determine whether the number of ones and
zeros in a sequence is approximately the same as would be expected for a truly
random sequence.
• Runs test: The focus of this test is the total number of runs in the sequence,
where a run is an uninterrupted sequence of identical bits bounded before
and after with a bit of the opposite value. The purpose of the runs test is to
determine whether the number of runs of ones and zeros of various lengths is
as expected for a random sequence.
• Maurer’s universal statistical test: The focus of this test is the number of bits
between matching patterns (a measure that is related to the length of a compressed
sequence). The purpose of the test is to detect whether or not the
sequence can be significantly compressed without loss of information. A significantly
compressible sequence is considered to be non-random.

Randomness Tests (2 of 3)
Runs test
Focus of this test is the total number of runs in the sequence, where a run is an uninterrupted sequence of identical bits bounded before and after with a bit of the opposite value
Purpose is to determine whether the number of runs of ones and zeros of various lengths is as expected for a random sequence
Maurer’s universal statistical test
Focus is the number of bits between matching patterns

16
SP 800-22 lists 15 separate tests of randomness. An understanding of these
tests requires a basic knowledge of statistical analysis, so we don’t attempt a
technical description here. Instead, to give some flavor for the tests, we list three of
the tests and the purpose of each test, as follows.
• Frequency test: This is the most basic test and must be included in any test
suite. The purpose of this test is to determine whether the number of ones and
zeros in a sequence is approximately the same as would be expected for a truly
random sequence.
• Runs test: The focus of this test is the total number of runs in the sequence,
where a run is an uninterrupted sequence of identical bits bounded before
and after with a bit of the opposite value. The purpose of the runs test is to
determine whether the number of runs of ones and zeros of various lengths is
as expected for a random sequence.
• Maurer’s universal statistical test: The focus of this test is the number of bits
between matching patterns (a measure that is related to the length of a compressed
sequence). The purpose of the test is to detect whether or not the
sequence can be significantly compressed without loss of information. A significantly
compressible sequence is considered to be non-random.

Randomness Tests (3 of 3)
Purpose is to detect whether or not the sequence can be significantly compressed without loss of information. A significantly compressible sequence is considered to be non-random

17
SP 800-22 lists 15 separate tests of randomness. An understanding of these
tests requires a basic knowledge of statistical analysis, so we don’t attempt a
technical description here. Instead, to give some flavor for the tests, we list three of
the tests and the purpose of each test, as follows.
• Frequency test: This is the most basic test and must be included in any test
suite. The purpose of this test is to determine whether the number of ones and
zeros in a sequence is approximately the same as would be expected for a truly
random sequence.
• Runs test: The focus of this test is the total number of runs in the sequence,
where a run is an uninterrupted sequence of identical bits bounded before
and after with a bit of the opposite value. The purpose of the runs test is to
determine whether the number of runs of ones and zeros of various lengths is
as expected for a random sequence.
• Maurer’s universal statistical test: The focus of this test is the number of bits
between matching patterns (a measure that is related to the length of a compressed
sequence). The purpose of the test is to detect whether or not the
sequence can be significantly compressed without loss of information. A significantly
compressible sequence is considered to be non-random.

Unpredictability (1 of 2)
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

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 also 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 provide a test of unpredictability. If the
generated bit stream appears random, then it is not possible to predict some bit or bit
sequence from knowledge of any previous bits. Similarly, if the bit sequence appears
random, then there is no feasible way to deduce the seed based on the bit sequence.
That is, a random sequence will have no correlation with a fixed value (the seed).
18

Unpredictability (2 of 2)
Each element of the sequence should appear to be the outcome of an independent random event
whose probability is

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 P R N G must be secure and unpredictable
The seed itself must be a random or pseudorandom number
Typically the seed is generated by T R N G

For cryptographic applications, the seed that serves as input to
the PRNG must be secure. Because the PRNG is a deterministic algorithm, if the
adversary can deduce the seed, then the output can also be determined. Therefore,
the seed must be unpredictable. In fact, the seed itself must be a random or pseudorandom
number.
20

Figure 8.2 Generation of Seed Input to P R N G

Typically, the seed is generated by a TRNG, as shown in Figure 8.2. This is the
scheme recommended by SP800-90. The reader may wonder, if a TRNG is available,
why it is necessary to use a PRNG. If the application is a stream cipher, then
a TRNG is not practical. The sender would need to generate a keystream of bits as
long as the plaintext and then transmit the keystream and the ciphertext securely to
the receiver. If a PRNG is used, the sender need only find a way to deliver the stream
cipher key, which is typically 54 or 128 bits, to the receiver in a secure fashion.
Even in the case of a PRF application, in which only a limited number of bits
is generated, it is generally desirable to use a TRNG to provide the seed to the
PRF and use the PRF output rather than use the TRNG directly. As is explained
in Section 8.6, a TRNG may produce a binary string with some bias. The PRF
would have the effect of “randomizing” the output of the TRNG so as to eliminate
that bias.
Finally, the mechanism used to generate true random numbers may not be
able to generate bits at a rate sufficient to keep up with the application requiring
the random bits.
21

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 P R N G s:
Symmetric block ciphers
Asymmetric ciphers
Hash functions and message authentication codes

Cryptographic PRNGs have been the subject of much research over the years,
and a wide variety of algorithms have been developed. These fall roughly into two
categories.
• Purpose-built algorithms: These are algorithms designed specifically and
solely for the purpose of generating pseudorandom bit streams. Some of these
algorithms are used for a variety of PRNG applications; several of these are
described in the next section. Others are designed specifically for use in a
stream cipher. The most important example of the latter is RC4, described in
Section 8.5.
• Algorithms based on existing cryptographic algorithms: Cryptographic algorithms
have the effect of randomizing input data. Indeed, this is a requirement
of such algorithms. For example, if a symmetric block cipher produced
ciphertext that had certain regular patterns in it, it would aid in the process of
cryptanalysis. Thus, cryptographic algorithms can serve as the core of PRNGs.
Three broad categories of cryptographic algorithms are commonly used to
create PRNGs:
—Symmetric block ciphers: This approach is discussed in Section 8.3.
—Asymmetric ciphers: The number theoretic concepts used for an asymmetric
cipher can also be adapted for a PRNG; this approach is examined in
Chapter 10.
—Hash functions and message authentication codes: This approach is examined
in Chapter 12.
Any of these approaches can yield a cryptographically strong PRNG.
A purpose-built algorithm may be provided by an operating system for general use.
For applications that already use certain cryptographic algorithms for encryption
or authentication, it makes sense to reuse the same code for the PRNG. Thus, all of
these approaches are in common use.
22

Linear Congruential Generator (1 of 2)
An algorithm first proposed by Lehmer that is parameterized with four numbers:
m the modulus

a the multiplier

c the increment

the starting value, or seed

The sequence of random numbers

is obtained via the
following iterative equation:

A widely used technique for pseudorandom number generation is an algorithm first
proposed by Lehmer [LEHM51], which is known as the linear congruential method.
The algorithm is parameterized with four numbers, as follows:
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. We would like m to be very large, so that there is the potential for producing a long series of distinct random numbers. A common criterion is that m be nearly equal to the maximum representable nonnegative integer for a given computer. Thus, a value of m near to or equal to 231 is typically chosen. 23 Linear Congruential Generator (2 of 2) If m , a , c , and are integers, then this technique will produce a sequence of integers with each integer in the range The selection of values for a , c , and m is critical in developing a good random number generator Copyright © 2017 Pearson Education, Inc. All Rights Reserved A widely used technique for pseudorandom number generation is an algorithm first proposed by Lehmer [LEHM51], which is known as the linear congruential method. The algorithm is parameterized with four numbers, as follows: 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. We would like m to be very large, so that there is the potential for producing a long series of distinct random numbers. A common criterion is that m be nearly equal to the maximum representable nonnegative integer for a given computer. Thus, a value of m near to or equal to 231 is typically chosen. 24 Blum Blum Shub (B B S) 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 (C S P R B G) A C S P R B G 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 The security of B B S is based on the difficulty of factoring n Copyright © 2017 Pearson Education, Inc. All Rights Reserved A popular approach to generating secure pseudorandom numbers is known as the Blum, Blum, Shub (BBS) generator (see Figure 8.3), named for its developers. It has perhaps the strongest public proof of its cryptographic strength of any purpose-built algorithm. The BBS is referred to as a cryptographically secure pseudorandom bit generator (CSPRBG). A CSPRBG is defined as one that passes the next-bit test , which, in turn, is defined as follows [MENE97]: A pseudorandom bit generator is said to pass 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. In other words, given the first k bits of the sequence, there is not a practical algorithm that can even allow you to state that the next bit will be 1 (or 0) with probability greater than 1/2. For all practical purposes, the sequence is unpredictable. The security of BBS is based on the difficulty of factoring n . That is, given n , we need to determine its two prime factors p and q . 25 Blum Blum Shub Block Diagram Copyright © 2017 Pearson Education, Inc. All Rights Reserved A popular approach to generating secure pseudorandom numbers is known as the Blum, Blum, Shub (BBS) generator (see Figure 8.3), named for its developers [BLUM86]. 26 Table 8.1 Example Operation of B B S Generator i Xi Bi 0 20749 blank 1 143135 1 2 177671 1 3 97048 0 4 89992 0 5 174051 1 6 80649 1 7 45663 1 8 69442 0 9 186894 0 10 177046 0 i Xi Bi 11 137922 0 12 123175 1 13 8630 0 14 114386 0 15 14863 1 16 133015 1 17 106065 1 18 45870 0 19 137171 1 20 48060 0 Copyright © 2017 Pearson Education, Inc. All Rights Reserved Table 8.1, shows an example of BBS operation. 27 P R N G Using Block Cipher Modes of Operation Two approaches that use a block cipher to build a P N R G have gained widespread acceptance: C T R mode Recommended in N I S T S P 800-90, A N S I standard X.82, and R F C 4086 O F B mode Recommended in X9.82 and R F C 4086 Copyright © 2017 Pearson Education, Inc. All Rights Reserved Two approaches that use a block cipher to build a PNRG have gained widespread acceptance: the CTR mode and the OFB mode. The CTR mode is recommended in NIST SP 800-90, in the ANSI standard X9.82 (Random Number Generation ), and in RFC 4086. The OFB mode is recommended in X9.82 and RFC 4086. 28 Figure 8.4 P R N G Mechanisms Based on Block Ciphers Copyright © 2017 Pearson Education, Inc. All Rights Reserved Figure 8.4 illustrates the two methods. In each case, the seed consists of two parts: the encryption key value and a value V that will be updated after each block of pseudorandom numbers is generated. Thus, for AES-128, the seed consists of a 128-bit key and a 128-bit V value. In the CTR case, the value of V is incremented by 1 after each encryption. In the case of OFB, the value of V is updated to equal the value of the preceding PRNG block. In both cases, pseudorandom bits are produced one block at a time (e.g., for AES, PRNG bits are generated 128 bits at a time). 29 Table 8.2 Example Results for P R N G Using O F B Output Block Fraction of One Bits Fraction of Bits that Match with Preceding Block 1786f4c7ff6e291dbdfdd90ec3453176 0.57 - 5e17b22b14677a4d66890f87565eae64 0.51 0.52 fdl 8284ac82251dfb3aa62c326cd46cc 0.47 0.54 c8e545198a758ef5dd86b41946389bd5 0.50 0.44 fe7bae0e23019542962e2c52d215a2e3 0.47 0.48 14fdf5ec99469598ae0379472803accd 0.49 0.52 6aeca972e5a3ef17bd1a1b775fc8b929 0.57 0.48 f7e97badf359d128f00d9b4ae323db64 0.55 0.45 Copyright © 2017 Pearson Education, Inc. All Rights Reserved For the OFB PRNG, Table 8.2 shows the first eight output blocks (1024 bits) with two rough measures of security. The second column shows the fraction of one bits in each 128-bit block. This corresponds to one of the NIST tests. The results indicate that the output is split roughly equally between zero and one bits. The third column shows the fraction of bits that match between adjacent blocks. If this number differs substantially from 0.5, that suggests a correlation between blocks, which could be a security weakness. The results suggest no correlation. 30 Table 8.3 Example Results for P R N G Using C T R Output Block Fraction of One Bits Fraction of Bits that Match with Preceding Block 1786f4c7ff6e291dbdfdd90ec34S3176 0.57 - 60809669a3e092a01b463472fdcae420 0.41 0.41 d4e6eI70b46b0573eedf88ee39bff33d 0.59 0.45 5f8fcfe5deca18ea246785d7fadc76f8 0.59 0.52 90e63ed27bb0786gc7S354Sbdd57ee28 0.53 0.52 0125856fdf4a17f747c7833695cS2235 0.50 0.47 f4be2d179bOf2548fd748c8fc7c81990 0.51 0.48 1151fc48f90eebac658a3911515c3c66 0.47 0.45 Copyright © 2017 Pearson Education, Inc. All Rights Reserved Table 8.3 shows the results using the same key and V values for CTR mode. Again, the results are favorable. 31 A N S I X9.17 P R N G (1 of 2) One of the strongest P R N G s is specified in A N S I X9.17 A number of applications employ this technique including financial security applications and P G P The algorithm makes use of triple D E S for encryption. Ingredients are: Input Two pseudorandom inputs drive the generator. One is a 64-bit representation of the current date and time. The other is a 64-bit seed value; this is initialized to some arbitrary value and is updated during the generation process. Copyright © 2017 Pearson Education, Inc. All Rights Reserved One of the strongest (cryptographically speaking) PRNGs is specified in ANSI X9.17. A number of applications employ this technique, including financial security applications and PGP (the latter described in Chapter 19). Figure 8.5 illustrates the algorithm, which makes use of triple DES for encryption. The ingredients are as follows. • Input: Two pseudorandom inputs drive the generator. One is a 64-bit representation of the current date and time, which is updated on each number generation. The other is a 64-bit seed value; this is initialized to some arbitrary value and is updated during the generation process. • Keys: The generator makes use of three triple DES encryption modules. All three make use of the same pair of 56-bit keys, which must be kept secret and are used only for pseudorandom number generation. • Output: The output consists of a 64-bit pseudorandom number and a 64-bit seed value. 32 A N S I X9.17 P R N G (2 of 2) Keys The generator makes use of three triple D E S encryption modules. All three make use of the same pair of 56-bit keys, which must be kept secret and are used only for pseudorandom number generation. Output The output consists of a 64-bit pseudorandom number and a 64-bit seed value. Copyright © 2017 Pearson Education, Inc. All Rights Reserved One of the strongest (cryptographically speaking) PRNGs is specified in ANSI X9.17. A number of applications employ this technique, including financial security applications and PGP (the latter described in Chapter 19). Figure 8.5 illustrates the algorithm, which makes use of triple DES for encryption. The ingredients are as follows. • Input: Two pseudorandom inputs drive the generator. One is a 64-bit representation of the current date and time, which is updated on each number generation. The other is a 64-bit seed value; this is initialized to some arbitrary value and is updated during the generation process. • Keys: The generator makes use of three triple DES encryption modules. All three make use of the same pair of 56-bit keys, which must be kept secret and are used only for pseudorandom number generation. • Output: The output consists of a 64-bit pseudorandom number and a 64-bit seed value. 33 Figure 8.5 A N S I X9.17 Pseudorandom Number Generator Copyright © 2017 Pearson Education, Inc. All Rights Reserved Figure 8.5 illustrates the algorithm, which makes use of triple DES for encryption. 34 N I S T C T R_D R B G Counter mode-deterministic random bit generator P R N G defined in N I S T S P 800-90 based on the C T R mode of operation Is widely implemented and is part of the hardware random number generator implemented on all recent Intel processor chips D R B G assumes that an entropy source is available to provide random bits Entropy is an information theoretic concept that measures unpredictability or randomness The encryption algorithm used in the D R B G may be 3D E S with three keys or A E S with a key size of 128, 192, or 256 bits Copyright © 2017 Pearson Education, Inc. All Rights Reserved We now look more closely at the details of the PRNG defined in NIST SP 800-90 based on the CTR mode of operation. The PRNG is referred to as CTR_DRBG (counter mode–deterministic random bit generator). CTR_DRBG is widely implemented and is part of the hardware random number generator implemented on all recent Intel processor chips (discussed in Section 8.6). The DRBG assumes that an entropy source is available to provide random bits. Typically, the entropy source will be a TRNG based on some physical source. Other sources are possible if they meet the required entropy measure of the application. Entropy is an information theoretic concept that measures unpredictability, or randomness; see Appendix F for details. The encryption algorithm used in the DRBG may be 3DES with three keys or AES with a key size of 128, 192, or 256 bits. 35 Table 8.4 C T R_D R B G Parameters Copyright © 2017 Pearson Education, Inc. All Rights Reserved Four parameters are associated with the algorithm: • Output block length (outlen ): Length of the output block of the encryption algorithm. • Key length (keylen ): Length of the encryption key. • Seed length (seedlen ): The seed is a string of bits that is used as input to a DRBG mechanism. The seed will determine a portion of the internal state of the DRBG, and its entropy must be sufficient to support the security strength of the DRBG. seedlen = outlen + keylen . • Reseed interval (reseed_interval ): Length of the encryption key. It is the maximum number of output blocks generated before updating the algorithm with a new seed. Table 8.4 lists the values specified in SP 800-90 for these parameters. 36 Figure 8.6 C T R_D R B G Functions Copyright © 2017 Pearson Education, Inc. All Rights Reserved Figure 8.6 shows the two principal functions that comprise CTR_DRBG. We first consider how CTR_DRBG is initialized, using the initialize and update function (Figure 8.6a). Recall that the CTR block cipher mode requires both an encryption key K and an initial counter value, referred to in SP 800-90 as the counter V . The combination of K and V is referred to as the seed . To start the DRGB operation, initial values for K and V are needed, and can be chosen arbitrarily. As an example, the Intel Digital Random Number Generator, discussed in Section 7.6, uses the values K = 0 and V = 0. These values are used as parameters for the CTR mode of operation to produce at least seedlen bits. In addition, exactly seedlen bits must be supplied from what is referred to as an entropy source . Typically, the entropy source would be some form of TRNG. With these inputs, the CTR mode of encryption is iterated to produce a Sequence of output blocks, with V incremented by 1 after each encryption. The process continues until at least seedlen bits have been generated. The leftmost seedlen bits of output are then XORed with the seedlen entropy bits to produce a new seed. In turn, the leftmost keylen bits of the seed form the new key and the rightmost outlen bits of the seed form the new counter value V . Once values of Key and V are obtained, the DRBG enters the generate phase and is able to generate pseudorandom bits, one output block at a time (Figure 7.6b). The encryption function is iterated to generate the number of pseudorandom bits desired. Each iteration uses the same encryption key. The counter value V is incremented by 1 for each iteration. To enhance security, the number of bits generated by any PRNG should be limited. CTR_DRGB uses the parameter reseed_interval to set that limit. During the generate phase, a reseed counter is initialized to 1 and then incremented with each iteration (each production of an output block). When the reseed counter reaches reseed_interval , the update function is invoked (Figure 8.6a). The update function is the same as the initialize function. In the update case the Key and V values last used by the generate function serve as the input parameters to the update function. The update function takes seedlen new bits from an entropy source and produces a new seed (Key, V ). The generate function can then resume production of pseudorandom bits. Note that the result of the update function is to change both the Key and V values used by the generate function. 37 Figure 8.7 Stream Cipher Diagram Copyright © 2017 Pearson Education, Inc. All Rights Reserved A typical stream cipher encrypts plaintext one byte at a time, although a stream cipher may be designed to operate on one bit at a time or on units larger than a byte at a time. Figure 8.7 is a representative diagram of stream cipher structure. In this structure, a key is input to a pseudorandom bit generator that produces a stream of 8-bit numbers that are apparently random. The output of the generator, called a keystream , is combined one byte at a time with the plaintext stream using the bitwise exclusive-OR (XOR) operation. 38 Stream Cipher Design Considerations (1 of 2) The encryption sequence should have a large period A pseudorandom number generator uses a function that produces a deterministic stream of bits that eventually repeats; the longer the period of repeat the more difficult it will be to do cryptanalysis The keystream should approximate the properties of a true random number stream as close as possible There should be an approximately equal number of 1s and 0s If the keystream is treated as a stream of bytes, then all of the 256 possible byte values should appear approximately equally often Copyright © 2017 Pearson Education, Inc. All Rights Reserved The stream cipher is similar to the one-time pad discussed in Chapter 3. The difference is that a one-time pad uses a genuine random number stream, whereas a stream cipher uses a pseudorandom number stream. [KUMA97] lists the following important design considerations for a stream cipher. 1. The encryption sequence should have a large period. A pseudorandom number generator uses a function that produces a deterministic stream of bits that eventually repeats. The longer the period of repeat the more difficult it will be to do cryptanalysis. This is essentially the same consideration that was discussed with reference to the Vigenère cipher, namely that the longer the keyword the more difficult the cryptanalysis. 2. The keystream should approximate the properties of a true random number stream as close as possible. For example, there should be an approximately equal number of 1s and 0s. If the keystream is treated as a stream of bytes, then all of the 256 possible byte values should appear approximately equally often. The more random-appearing the keystream is, the more randomized the ciphertext is, making cryptanalysis more difficult. 3. Note from Figure 8.7 that the output of the pseudorandom number generator is conditioned on the value of the input key. To guard against brute-force attacks, the key needs to be sufficiently long. The same considerations that apply to block ciphers are valid here. Thus, with current technology, a key length of at least 128 bits is desirable. With a properly designed pseudorandom number generator, a stream cipher can be as secure as a block cipher of comparable key length. A potential advantage of a stream cipher is that stream ciphers that do not use block ciphers as a building block are typically faster and use far less code than do block ciphers. The example in this chapter, RC4, can be implemented in just a few lines of code. In recent years, this advantage has diminished with the introduction of AES, which is quite efficient in software. Furthermore, hardware acceleration techniques are now available for AES. For example, the Intel AES Instruction Set has machine instructions for one round of encryption and decryption and key generation. Using the hardware instructions results in speedups of about an order of magnitude compared to pure software implementations [XU10]. One advantage of a block cipher is that you can reuse keys. In contrast, if two plaintexts are encrypted with the same key using a stream cipher, then cryptanalysis is often quite simple [DAWS96]. If the two ciphertext streams are XORed together, the result is the XOR of the original plaintexts. If the plaintexts are text strings, credit card numbers, or other byte streams with known properties, then cryptanalysis may be successful. For applications that require encryption/decryption of a stream of data, such as over a data communications channel or a browser/Web link, a stream cipher might be the better alternative. For applications that deal with blocks of data, such as file transfer, e-mail, and database, block ciphers may be more appropriate. However, either type of cipher can be used in virtually any application. A stream cipher can be constructed with any cryptographically strong PRNG, such as the ones discussed in Sections 8.2 and 8.3. In the next section, we look at a stream cipher that uses a PRNG designed specifically for the stream cipher. 39 Stream Cipher Design Considerations (2 of 2) A key length of at least 128 bits is desirable The output of the pseudorandom number generator is conditioned on the value of the input key The same considerations that apply to block ciphers are valid With a properly designed pseudorandom number generator a stream cipher can be as secure as a block cipher of comparable key length A potential advantage is that stream ciphers that do not use block ciphers as a building block are typically faster and use far less code than block ciphers Copyright © 2017 Pearson Education, Inc. All Rights Reserved The stream cipher is similar to the one-time pad discussed in Chapter 3. The difference is that a one-time pad uses a genuine random number stream, whereas a stream cipher uses a pseudorandom number stream. [KUMA97] lists the following important design considerations for a stream cipher. 1. The encryption sequence should have a large period. A pseudorandom number generator uses a function that produces a deterministic stream of bits that eventually repeats. The longer the period of repeat the more difficult it will be to do cryptanalysis. This is essentially the same consideration that was discussed with reference to the Vigenère cipher, namely that the longer the keyword the more difficult the cryptanalysis. 2. The keystream should approximate the properties of a true random number stream as close as possible. For example, there should be an approximately equal number of 1s and 0s. If the keystream is treated as a stream of bytes, then all of the 256 possible byte values should appear approximately equally often. The more random-appearing the keystream is, the more randomized the ciphertext is, making cryptanalysis more difficult. 3. Note from Figure 8.7 that the output of the pseudorandom number generator is conditioned on the value of the input key. To guard against brute-force attacks, the key needs to be sufficiently long. The same considerations that apply to block ciphers are valid here. Thus, with current technology, a key length of at least 128 bits is desirable. With a properly designed pseudorandom number generator, a stream cipher can be as secure as a block cipher of comparable key length. A potential advantage of a stream cipher is that stream ciphers that do not use block ciphers as a building block are typically faster and use far less code than do block ciphers. The example in this chapter, RC4, can be implemented in just a few lines of code. In recent years, this advantage has diminished with the introduction of AES, which is quite efficient in software. Furthermore, hardware acceleration techniques are now available for AES. For example, the Intel AES Instruction Set has machine instructions for one round of encryption and decryption and key generation. Using the hardware instructions results in speedups of about an order of magnitude compared to pure software implementations [XU10]. One advantage of a block cipher is that you can reuse keys. In contrast, if two plaintexts are encrypted with the same key using a stream cipher, then cryptanalysis is often quite simple [DAWS96]. If the two ciphertext streams are XORed together, the result is the XOR of the original plaintexts. If the plaintexts are text strings, credit card numbers, or other byte streams with known properties, then cryptanalysis may be successful. For applications that require encryption/decryption of a stream of data, such as over a data communications channel or a browser/Web link, a stream cipher might be the better alternative. For applications that deal with blocks of data, such as file transfer, e-mail, and database, block ciphers may be more appropriate. However, either type of cipher can be used in virtually any application. A stream cipher can be constructed with any cryptographically strong PRNG, such as the ones discussed in Sections 8.2 and 8.3. In the next section, we look at a stream cipher that uses a PRNG designed specifically for the stream cipher. 40 R C 4 Designed in 1987 by Ron Rivest for R S A Security Variable key size stream cipher with byte-oriented operations Based on the use of a random permutation Eight to sixteen machine operations are required per output byte and the cipher can be expected to run very quickly in software Used in the Secure Sockets Layer/Transport Layer Security (S S L/T L S) standards that have been defined for communication between Web browsers and servers Is also used in the Wired Equivalent Privacy (W E P) protocol and the newer WiFi Protected Access (W P A) protocol that are part of the I E E E 802.11 wireless LAN standard Copyright © 2017 Pearson Education, Inc. All Rights Reserved RC4 is a stream cipher designed in 1987 by Ron Rivest for RSA Security. It is a variable key size stream cipher with byte-oriented operations. The algorithm is based on the use of a random permutation. Analysis shows that the period of the cipher is overwhelmingly likely to be greater than 10100 [ROBS95a]. Eight to sixteen machine operations are required per output byte, and the cipher can be expected to run very quickly in software. RC4 is used in the Secure Sockets Layer/Transport Layer Security (SSL/TLS) standards that have been defined for communication between Web browsers and servers. It is also used in the Wired Equivalent Privacy (WEP) protocol and the newer WiFi Protected Access (WPA) protocol that are part of the IEEE 802.11 wireless LAN standard. RC4 was kept as a trade secret by RSA Security. In September 1994, the RC4 algorithm was anonymously posted on the Internet on the Cypherpunks anonymous remailers list. The RC4 algorithm is remarkably simple and quite easy to explain. A variable-length key of from 1 to 256 bytes (8 to 2048 bits) is used to initialize a 256-byte state vector S, with elements S[0], S[1], c , S[255]. At all times, S contains a permutation of all 8-bit numbers from 0 through 255. For encryption and decryption, a byte k (see Figure 8.7) is generated from S by selecting one of the 255 entries in a systematic fashion. As each value of k is generated, the entries in S are once again permuted. 41 Figure 8.8 R C 4 Copyright © 2017 Pearson Education, Inc. All Rights Reserved Figure 8.8 illustrates the RC4 logic. 42 Strength of R C 4 (1 of 2) A number of papers have been published analyzing methods of attacking R C 4 None of these approaches is practical against R C 4 with a reasonable key length A more serious problem is that the W E P protocol intended to provide confidentiality on 802.11 wireless L A N networks is vulnerable to a particular attack approach The problem is not with R C 4 itself, but the way in which keys are generated for use as input Copyright © 2017 Pearson Education, Inc. All Rights Reserved A number of papers have been published analyzing methods of attacking RC4 (e.g., [KNUD98], [FLUH00], [MANT01]). None of these approaches is practical against RC4 with a reasonable key length, such as 128 bits. A more serious problem is reported in [FLUH01]. The authors demonstrate that the WEP protocol, intended to provide confidentiality on 802.11 wireless LAN networks, is vulnerable to a particular attack approach. In essence, the problem is not with RC4 itself but the way in which keys are generated for use as input to RC4. This particular problem does not appear to be relevant to other applications using RC4 and can be remedied in WEP by changing the way in which keys are generated. This problem points out the difficulty in designing a secure system that involves both cryptographic functions and protocols that make use of them. 43 Strength of R C 4 (2 of 2) Problem does not appear to be relevant to other applications and can be remedied in W E P by changing the way in which keys are generated Problem points out the difficulty in designing a secure system that involves both cryptographic functions and protocols that make use of them Copyright © 2017 Pearson Education, Inc. All Rights Reserved A number of papers have been published analyzing methods of attacking RC4 (e.g., [KNUD98], [FLUH00], [MANT01]). None of these approaches is practical against RC4 with a reasonable key length, such as 128 bits. A more serious problem is reported in [FLUH01]. The authors demonstrate that the WEP protocol, intended to provide confidentiality on 802.11 wireless LAN networks, is vulnerable to a particular attack approach. In essence, the problem is not with RC4 itself but the way in which keys are generated for use as input to RC4. This particular problem does not appear to be relevant to other applications using RC4 and can be remedied in WEP by changing the way in which keys are generated. This problem points out the difficulty in designing a secure system that involves both cryptographic functions and protocols that make use of them. 44 Entropy Sources (1 of 2) A true random number generator (T R N G) uses a nondeterministic source to produce randomness Most operate by measuring unpredictable natural processes such as pulse detectors of ionizing radiation events, gas discharge tubes, and leaky capacitors Intel has developed a commercially available chip that samples thermal noise by amplifying the voltage measured across undriven resistors Copyright © 2017 Pearson Education, Inc. All Rights Reserved A true random number generator (TRNG) uses a nondeterministic source to produce randomness. Most operate by measuring unpredictable natural processes, such as pulse detectors of ionizing radiation events, gas discharge tubes, and leaky capacitors. Intel has developed a commercially available chip that samples thermal noise by amplifying the voltage measured across undriven resistors [JUN99]. LavaRnd is an open source project for creating truly random numbers using inexpensive cameras, open source code, and inexpensive hardware. The system uses a saturated CCD in a light-tight can as a chaotic source to produce the seed. Software processes the result into truly random numbers in a variety of formats. 45 Entropy Sources (2 of 2) LavaRnd is an open source project for creating truly random numbers using inexpensive cameras, open source code, and inexpensive hardware The system uses a saturated C C D in a light-tight can as a chaotic source to produce the seed; software processes the result into truly random numbers in a variety of formats Copyright © 2017 Pearson Education, Inc. All Rights Reserved A true random number generator (TRNG) uses a nondeterministic source to produce randomness. Most operate by measuring unpredictable natural processes, such as pulse detectors of ionizing radiation events, gas discharge tubes, and leaky capacitors. Intel has developed a commercially available chip that samples thermal noise by amplifying the voltage measured across undriven resistors [JUN99]. LavaRnd is an open source project for creating truly random numbers using inexpensive cameras, open source code, and inexpensive hardware. The system uses a saturated CCD in a light-tight can as a chaotic source to produce the seed. Software processes the result into truly random numbers in a variety of formats. 46 Possible Sources of Randomness (1 of 2) R F C 4086 lists the following possible sources of randomness that can be used on a computer to generate true random sequences: Sound/video input The input from a sound digitizer with no source plugged in or from a camera with the lens cap on is essentially thermal noise If the system has enough gain to detect anything, such input can provide reasonable high quality random bits Copyright © 2017 Pearson Education, Inc. All Rights Reserved RFC 4086 lists the following possible sources of randomness that, with care, easily can be used on a computer to generate true random sequences. • Sound/video input: Many computers are built with inputs that digitize some real-world analog source, such as sound from a microphone or video input from a camera. The “input” from a sound digitizer with no source plugged in or from a camera with the lens cap on is essentially thermal noise. If the system has enough gain to detect anything, such input can provide reasonably high quality random bits. • Disk drives: Disk drives have small random fluctuations in their rotational speed due to chaotic air turbulence [JAKO98]. The addition of low-level disk seek-time instrumentation produces a series of measurements that contain this randomness. Such data is usually highly correlated, so significant processing is needed. Nevertheless, experimentation a decade ago showed that, with such processing, even slow disk drives on the slower computers of that day could easily produce 100 bits a minute or more of excellent random data. There is also an online service (random.org), which can deliver random sequences securely over the Internet. 47 Possible Sources of Randomness (2 of 2) Disk drives Have small random fluctuations in their rotational speed due to chaotic air turbulence The addition of low-level disk seek-time instrumentation produces a series of measurements that contain this randomness There is also an online service (random.org) which can deliver random sequences securely over the Internet Copyright © 2017 Pearson Education, Inc. All Rights Reserved RFC 4086 lists the following possible sources of randomness that, with care, easily can be used on a computer to generate true random sequences. • Sound/video input: Many computers are built with inputs that digitize some real-world analog source, such as sound from a microphone or video input from a camera. The “input” from a sound digitizer with no source plugged in or from a camera with the lens cap on is essentially thermal noise. If the system has enough gain to detect anything, such input can provide reasonably high quality random bits. • Disk drives: Disk drives have small random fluctuations in their rotational speed due to chaotic air turbulence [JAKO98]. The addition of low-level disk seek-time instrumentation produces a series of measurements that contain this randomness. Such data is usually highly correlated, so significant processing is needed. Nevertheless, experimentation a decade ago showed that, with such processing, even slow disk drives on the slower computers of that day could easily produce 100 bits a minute or more of excellent random data. There is also an online service (random.org), which can deliver random sequences securely over the Internet. 48 Table 8.5 Comparison of P R N G s and T R N G s blank Pseudorandom Number Generators True Random Number Generators Efficiency Very efficient Generally inefficient Determinism Deterministic Nondeterministic Periodicity Periodic Aperiodic Copyright © 2017 Pearson Education, Inc. All Rights Reserved Table 8.5 summarizes the principal differences between PRNGs and TRNGs. PRNGs are efficient, meaning they can produce many numbers in a short time, and deterministic, meaning that a given sequence of numbers can be reproduced at a later date if the starting point in the sequence is known. Efficiency is a nice characteristic if your application needs many numbers, and determinism is handy if you need to replay the same sequence of numbers again at a later stage. PRNGs are typically also periodic, which means that the sequence will eventually repeat itself. While periodicity is hardly ever a desirable characteristic, modern PRNGs have a period that is so long that it can be ignored for most practical purposes. TRNGs are generally rather inefficient compared to PRNGs, taking considerably longer time to produce numbers. This presents a difficulty in many applications. For example, cryptography system in banking or national security might need to generate millions of random bits per second. TRNGs are also nondeterministic, meaning that a given sequence of numbers cannot be reproduced, although the same sequence may of course occur several times by chance. TRNGs have no period. 49 Conditioning (1 of 2) A T R N G may produce an output that is biased in some way (such as having more ones than zeros or vice versa) Biased N I S T S P 800-90B defines a random process as biased with respect to an assumed discrete set of potential outcomes if some of those outcomes have a greater probability of occurring than do others Entropy rate N I S T 800-90B defines entropy rate as the rate at which a digitized noise source provides entropy Copyright © 2017 Pearson Education, Inc. All Rights Reserved A TRNG may produce an output that is biased in some way, such as having more ones than zeros or vice versa. More generally, NIST SP 800-90B defines a random process as biased with respect to an assumed discrete set of potential outcomes (i.e., possible output values) if some of those outcomes have a greater probability of occurring than do others. For example, a physical source such as electronic noise may contain a superposition of regular structures, such as waves or other periodic phenomena, which may appear to be random, yet are determined to be non-random using statistical tests. In addition to bias, another concept used by SP 800-98B is that of entropy rate . SP 800-90B defines entropy rate as the rate at which a digitized noise source (or entropy source) provides entropy; it is computed as the assessed amount of entropy provided by a bit string output from the source, divided by the total number of bits in the bit string (yielding assessed bits of entropy per output bit). This will be a value between 0 (no entropy) and 1 (full entropy). Entropy rate is a measure of the randomness or unpredictability of a bit string. Another way of expressing it is that the entropy rate is k /n for a random source of length n bits and min-entropy k . Min-entropy is a measure of the number of random bits and is explained in Appendix F. In essence, a block of bits or a bit stream that is unbiased, and in which each bit and each group of bits is independent of all other bits and groups of bits will have an entropy rate of 1. For hardware sources of random bits, the recommended approach is to assume that there may be bias and/or an entropy rate of less than 1 and to apply techniques to further “randomize” the bits. Various methods of modifying a bit stream for this purpose have been developed. These are referred to as conditioning algorithms or deskewing algorithms . Typically, conditioning is done by using a cryptographic algorithm to “scramble” the random bits so as to eliminate bias and increase entropy. The two most common approaches are the use of a hash function or a symmetric block cipher. 50 Conditioning (2 of 2) Is a measure of the randomness or unpredictability of a bit string Will be a value between 0 (no entropy) and 1 (full entropy) Conditioning algorithms/deskewing algorithms Methods of modifying a bit stream to further randomize the bits Typically conditioning is done by using a cryptographic algorithm to scramble the random bits so as to eliminate bias and increase entropy The two most common approaches are the use of a hash function or a symmetric block cipher Copyright © 2017 Pearson Education, Inc. All Rights Reserved A TRNG may produce an output that is biased in some way, such as having more ones than zeros or vice versa. More generally, NIST SP 800-90B defines a random process as biased with respect to an assumed discrete set of potential outcomes (i.e., possible output values) if some of those outcomes have a greater probability of occurring than do others. For example, a physical source such as electronic noise may contain a superposition of regular structures, such as waves or other periodic phenomena, which may appear to be random, yet are determined to be non-random using statistical tests. In addition to bias, another concept used by SP 800-98B is that of entropy rate . SP 800-90B defines entropy rate as the rate at which a digitized noise source (or entropy source) provides entropy; it is computed as the assessed amount of entropy provided by a bit string output from the source, divided by the total number of bits in the bit string (yielding assessed bits of entropy per output bit). This will be a value between 0 (no entropy) and 1 (full entropy). Entropy rate is a measure of the randomness or unpredictability of a bit string. Another way of expressing it is that the entropy rate is k /n for a random source of length n bits and min-entropy k . Min-entropy is a measure of the number of random bits and is explained in Appendix F. In essence, a block of bits or a bit stream that is unbiased, and in which each bit and each group of bits is independent of all other bits and groups of bits will have an entropy rate of 1. For hardware sources of random bits, the recommended approach is to assume that there may be bias and/or an entropy rate of less than 1 and to apply techniques to further “randomize” the bits. Various methods of modifying a bit stream for this purpose have been developed. These are referred to as conditioning algorithms or deskewing algorithms . Typically, conditioning is done by using a cryptographic algorithm to “scramble” the random bits so as to eliminate bias and increase entropy. The two most common approaches are the use of a hash function or a symmetric block cipher. 51 Hash Function A hash function produces an n-bit output from an input of arbitrary length A simple way to use a hash function for conditioning is as follows: Blocks of m input bits, with are passed through the hash function and the n output bits are used as random bits To generate a stream of random bits, successive input blocks pass through the hash function to produce successive hashed output blocks Copyright © 2017 Pearson Education, Inc. All Rights Reserved A hash function produces an n -bit output from an input of arbitrary length. A simple way to use a hash function for conditioning is as follows. Blocks of m input bits, with m Ú n , are passed through the hash function and the n output bits are used as random bits. To generate a stream of random bits, successive input blocks pass through the hash function to produce successive hashed output blocks. Operating systems typically provide a built-in mechanism for generating random numbers. For example, Linux uses four entropy sources: mouse and keyboard activity, disk I/O operations, and specific interrupts. Bits are generated from these four sources and combined in a pooled buffer. When random bits are needed, the appropriate number of bits are read from the buffer and passed through the SHA-1 hash function [GUTT06]. A more complex approach is the hash derivation function specified in SP800-90A. Hash_df can be defined as follows: Parameters: input_string : The string to be hashed. outlen : Output length. no_of_bits_to_return : The number of bits to be returned by Hash_df. The maximum length (max_number_of_bits ) is implementation dependent, but shall be less than or equal to (255 * outlen ). no_of_bits_to_return is represented as a 32-bit integer. requested_bits : The result of performing the Hash_df. 52 Figure 8.9 N R B G Model Copyright © 2017 Pearson Education, Inc. All Rights Reserved Figure 8.9 provides a general model for a nondeterministic random bit generator. A hardware noise source produces a true random output. This is digitized to produce true, or nondeterministic, source of bits. This bit source then passes through a conditioning module to mitigate bias and maximize entropy. Figure 8.9 also shows a health-testing module, which is used on the outputs of both the digitizer and conditioner. In essence, health testing is used to validate that the noise source is working as expected and that the conditioning module is produced output with the desired characteristics. Both forms of health testing are recommended by SP 800-90B. 53 Health Tests on the Noise Source (1 of 3) The nature of the health testing of the noise source depends strongly on the technology used to produce noise In general, the assumption can be made that the digitized output of the noise source will exhibit some bias Thus, traditional statistical tests are not useful for monitoring the noise source, because the noise source is likely to always fail The tests on the noise source need to be tailored to the expected statistical behavior of the correctly operating noise source The goal is not to determine if the source is unbiased, but if it is operating as expected Copyright © 2017 Pearson Education, Inc. All Rights Reserved The nature of the health testing of the noise source depends strongly on the technology used to produce noise. In general, we can assume that the digitized output of the noise source will exhibit some bias. Thus, the traditional statistical tests, such as those defined in SP 800-22 and discussed in Section 8.1, are not useful for monitoring the noise source, because the noise source is likely to always fail. Rather, the tests on the noise source need to be tailored to the expected statistical behavior of the correctly operating noise source. The goal is not to determine if the source is unbiased, which it isn’t, but if it is operating as expected. SP 800-90B specifies that continuous tests be done on digitized samples obtained from the noise source (point A in Figure 8.9). The purpose is to test for variability. More specifically, the purpose is to determine if the noise source is producing at the expected entropy rate. SP 800-909B mandates the use of two tests: the Repetition Count Test and the Adaptive Proportion Test. The Repetition Count Test is designed to quickly detect a catastrophic failure that causes the noise source to become “stuck” on a single output value for a long time. For this test, it is assumed that a given noise source is assessed to have a given min-entropy value of H . The entropy is expressed as the amount of entropy per sample, where a sample could be a single bit or some block of bits of length n . With an assessed value of H , it is straightforward to calculate the probability that a sequence of C consecutive samples will yield identical sample values. The Repetition Count Test starts by recording a sample value and then counting the number of repetitions of the same value. If the counter reaches the cutoff value C, an error is reported. If a sample value is encountered that differs from the preceding sample, then the counter is reset to 1 and the algorithm starts over. The Adaptive Proportion Test is designed to detect a large loss of entropy, such as might occur as a result of some physical failure or environmental change affecting the noise source. The test continuously measures the local frequency of occurrence of some sample value in a sequence of noise source samples to determine if the sample occurs too frequently 54 Health Tests on the Noise Source (2 of 3) S P 800-90B specifies that continuous tests be done on digitized samples obtained from the noise source The purpose is to test for variability and to determine if the noise source is producing at the expected entropy rate S P 800-90B mandates the use of two tests Repetition Count Test Designed to quickly detect a catastrophic failure that causes the noise source to become “stuck” on a single output value for a long time Involves looking for consecutive identical samples Copyright © 2017 Pearson Education, Inc. All Rights Reserved The nature of the health testing of the noise source depends strongly on the technology used to produce noise. In general, we can assume that the digitized output of the noise source will exhibit some bias. Thus, the traditional statistical tests, such as those defined in SP 800-22 and discussed in Section 8.1, are not useful for monitoring the noise source, because the noise source is likely to always fail. Rather, the tests on the noise source need to be tailored to the expected statistical behavior of the correctly operating noise source. The goal is not to determine if the source is unbiased, which it isn’t, but if it is operating as expected. SP 800-90B specifies that continuous tests be done on digitized samples obtained from the noise source (point A in Figure 8.9). The purpose is to test for variability. More specifically, the purpose is to determine if the noise source is producing at the expected entropy rate. SP 800-909B mandates the use of two tests: the Repetition Count Test and the Adaptive Proportion Test. The Repetition Count Test is designed to quickly detect a catastrophic failure that causes the noise source to become “stuck” on a single output value for a long time. For this test, it is assumed that a given noise source is assessed to have a given min-entropy value of H . The entropy is expressed as the amount of entropy per sample, where a sample could be a single bit or some block of bits of length n . With an assessed value of H , it is straightforward to calculate the probability that a sequence of C consecutive samples will yield identical sample values. The Repetition Count Test starts by recording a sample value and then counting the number of repetitions of the same value. If the counter reaches the cutoff value C, an error is reported. If a sample value is encountered that differs from the preceding sample, then the counter is reset to 1 and the algorithm starts over. The Adaptive Proportion Test is designed to detect a large loss of entropy, such as might occur as a result of some physical failure or environmental change affecting the noise source. The test continuously measures the local frequency of occurrence of some sample value in a sequence of noise source samples to determine if the sample occurs too frequently 55 Health Tests on the Noise Source (3 of 3) Adaptive Proportion Test Designed to detect a large loss of entropy, such as might occur as a result of some physical failure or environmental change affecting the noise source The test continuously measures the local frequency of occurrence of some sample value in a sequence of noise source samples to determine if the sample occurs too frequently Copyright © 2017 Pearson Education, Inc. All Rights Reserved The nature of the health testing of the noise source depends strongly on the technology used to produce noise. In general, we can assume that the digitized output of the noise source will exhibit some bias. Thus, the traditional statistical tests, such as those defined in SP 800-22 and discussed in Section 8.1, are not useful for monitoring the noise source, because the noise source is likely to always fail. Rather, the tests on the noise source need to be tailored to the expected statistical behavior of the correctly operating noise source. The goal is not to determine if the source is unbiased, which it isn’t, but if it is operating as expected. SP 800-90B specifies that continuous tests be done on digitized samples obtained from the noise source (point A in Figure 8.9). The purpose is to test for variability. More specifically, the purpose is to determine if the noise source is producing at the expected entropy rate. SP 800-909B mandates the use of two tests: the Repetition Count Test and the Adaptive Proportion Test. The Repetition Count Test is designed to quickly detect a catastrophic failure that causes the noise source to become “stuck” on a single output value for a long time. For this test, it is assumed that a given noise source is assessed to have a given min-entropy value of H . The entropy is expressed as the amount of entropy per sample, where a sample could be a single bit or some block of bits of length n . With an assessed value of H , it is straightforward to calculate the probability that a sequence of C consecutive samples will yield identical sample values. The Repetition Count Test starts by recording a sample value and then counting the number of repetitions of the same value. If the counter reaches the cutoff value C, an error is reported. If a sample value is encountered that differs from the preceding sample, then the counter is reset to 1 and the algorithm starts over. The Adaptive Proportion Test is designed to detect a large loss of entropy, such as might occur as a result of some physical failure or environmental change affecting the noise source. The test continuously measures the local frequency of occurrence of some sample value in a sequence of noise source samples to determine if the sample occurs too frequently 56 Health Tests on the Conditioning Function S P 800-90B specifies that health tests should also be applied to the output of the conditioning component, but does not indicate which tests to use The purpose of the health tests on the conditioning component is to assure that the output behaves as a true random bit stream It is reasonable to use the tests for randomness defined in S P 800-22 Copyright © 2017 Pearson Education, Inc. All Rights Reserved SP 800-90B specifies that health tests should also be applied to the output of the conditioning component (point B in Figure 8.9), but does not indicate which tests to use. The purpose of the health tests on the conditioning component is to assure that the output behaves as a true random bit stream. Thus, it is reasonable to use the tests for randomness defined in SP 800-22, and described in Section 8.1. 57 Intel Digital Random Number Generator T R N Gs have traditionally been used only for key generation and other applications where only a small number of random bits were required This is because T R N G s have generally been inefficient with a low bit rate of random bit production The first commercially available T R N G that achieves bit production rates comparable with that of P R N G s is the Intel digital random number generator offered on new multicore chips since May 2012 It is implemented entirely in hardware The entire D R N G is on the same multicore chip as the processors Copyright © 2017 Pearson Education, Inc. All Rights Reserved As was mentioned, TRNGs have traditionally been used only for key generation and other applications where only a small number of random bits were required. This is because TRNGs have generally been inefficient, with a low bit rate of random bit production. The first commercially available TRNG that achieves bit production rates comparable with that of PRNGs is the Intel digital random number generator (DRNG) [TAYL11], offered on new multicore chips since May 2012. Two notable aspects of the DRNG: 1. It is implemented entirely in hardware. This provides greater security than a facility that includes a software component. A hardware-only implementation should also be able to achieve greater computation speed than a software module. 2. The entire DRNG is on the same multicore chip as the processors. This eliminates the I/O delays found in other hardware random number generators. 58 Figure 8.10 Intel Processor Chip with Random Number Generator Copyright © 2017 Pearson Education, Inc. All Rights Reserved Figure 8.10 shows the overall structure of the DRNG. The first stage of the DRNG generates random numbers from thermal noise. The heart of the stage consists of two inverters (NOT gates), with the output of each inverter connected to the input of the other. Such an arrangement has two stable states, with one inverter having an output of logical 1 and the other having an output of logical 0. The circuit is then configured so that both inverters are forced to have the same indeterminate state (both inputs and both outputs at logical 1) by clock pulses. Random thermal noise within the inverters soon jostles the two inverters into a mutually stable state. Additional circuitry is intended to compensate for any biases or correlations. This stage is capable, with current hardware, of generating random bits at a rate of 4 Gbps. The output of the first stage is generated 512 bits at a time. To assure that the bit stream does not have skew or bias, a second stage of processing randomizes its input using a cryptographic function. In this case, the function is referred to as CBC-MAC or CMAC, as specified in NIST SP 800-38B. In essence, CMAC encrypts its input using the cipher block chaining (CBC) mode (Figure 6.4) and outputs the final block. We examine CMAC in detail in Chapter 12. The output of this stage is generated 256 bits at a time and is intended to exhibit true randomness with no skew or bias. While the hardware’s circuitry generates random numbers from thermal noise much more quickly than its predecessors, it’s still not fast enough for some of today’s computing requirements. To enable the DRNG to generate random numbers as quickly as software PRNG, and also maintain the high quality of the random numbers, a third stage is added. This stage uses the 256-bit random numbers to seed a cryptographically secure PRNG that creates 128-bit numbers. From one 256-bit seed, the PRNG can output many pseudorandom numbers, exceeding the 3-Gbps rate of the entropy source. An upper bound of 511 128-bit samples can be generated per seed. The algorithm used for this stage is CTR_DRBG, described in Section 8.3. The output of the DRNG is available to each of the cores on the chip via the RDRAND instruction. RDRAND retrieves a 16-, 32-, or 64-bit random value and makes it available in a software-accessible register. Preliminary data from a pre-production sample on a system with a third generation Intel® Core™ family processor produced the following performance [INTE12]: up to 70 million RDRAND invocations per second, and a random data production rate of over 4 Gbps. 59 Figure 8.11 Intel D R N G Logical Structure Copyright © 2017 Pearson Education, Inc. All Rights Reserved Figure 8.11 provides a simplified view of the logical flow of the Intel DRNG. As was described, the heart of the hardware entropy source is a pair of inverters that feed each other. Two transistors, driven by the same clock, force the inputs and outputs of both inverters to the logical 1 state. Because this an unstable state, thermal noise will cause the configuration to settle randomly into a stable state with either Node A at logical 1 and Node B at logical 0, or the reverse. Thus the module generates random bits at the clock rate. The output of the entropy source is collected 512 bits at a time and used to feed to two CBC hardware implementations using AES encryption. Each implementation takes two blocks of 128 bits of “plaintext” and encrypts using the CBC mode. The output of the second encryption is retained. For both CBC modules, an all-zeros key is used initially. Subsequently, the output of the PRNG stage is fed back to become the key for the conditioner stage. The output of the conditioner stage consists of 256 bits. This block is provided as input to the update function of the PRNG stage. The update function is initialized with the all-zeros key and the counter value 0. The function is iterated twice to produce a 256-bit block, which is then XORed with the input from the conditioner stage. The results are used as the 128-bit key and the 128-bit seed for the generate function. The generate function produces pseudorandom bits in 128-bit blocks. 60 Summary Principles of pseudorandom number generation The use of random numbers T R N G s, P R N G s, and P R F s P R N G requirements Algorithm design Pseudorandom number generators Linear congruential generators Blum Blum Shub generator Pseudorandom number generation using a block cipher P R N G using block cipher modes of operation A N S I X9.17 P R N G N I S T C T R_D R B G Stream ciphers R C 4 Initialization of S Stream generation Strength of R C 4 True random number generators Entropy sources Comparison of P R N G s and T R N G s Conditioning Health Testing Intel digital random number generator Copyright © 2017 Pearson Education, Inc. All Rights Reserved Chapter 8 summary. 61 Copyright Copyright © 2017 Pearson Education, Inc. All Rights Reserved 62 2 1 0 m >
m
a

< < 0 m c < £ 0 0 X m X < £ 0 0 } { n X m c aX X n mod ) ( 1 n + = + m X n < £ 0 3DES AES-128 AES-192 AES-256 outlen 64 128 128 128 keylen 168 128 192 256 seedlen 232 256 320 384 reseed_interval ≤232 ≤248 ≤248 ≤248 , n m ³

Cryptography and Network Security: Principles and Practice

Seventh Edition

Chapter 9

Public Key Cryptography and RSA

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

If this PowerPoint presentation contains mathematical equations, you may need to check that your computer has the following installed:
1) MathType Plugin
2) Math Player (free versions available)
3) NVDA Reader (free versions available)
Lecture slides prepared for “Cryptography and Network Security”, 7/e, by William Stallings, Chapter 9 – “Public Key Cryptography and RSA”.
The development of public-key cryptography is the greatest and perhaps the
only true revolution in the entire history of cryptography. From its earliest beginnings
to modern times, virtually all cryptographic systems have been based on
the elementary tools of substitution and permutation. After millennia of working
with algorithms that could be calculated by hand, a major advance in symmetric
cryptography occurred with the development of the rotor encryption/decryption
Machine. The electromechanical rotor enabled the development of fiendishly complex
Cipher systems. With the availability of computers, even more complex systems
were devised, the most prominent of which was the Lucifer effort at IBM that culminated
in the Data Encryption Standard (DES). But both rotor machines and DES,
although representing significant advances, still relied on the bread-and-butter tools
of substitution and permutation.
Public-key cryptography provides a radical departure from all that has gone
before. For one thing, public-key algorithms are based on mathematical functions
rather than on substitution and permutation. More important, public-key cryptography
is asymmetric, involving the use of two separate keys, in contrast to symmetric
encryption, which uses only one key. The use of two keys has profound
consequences in the areas of confidentiality, key distribution, and authentication,
as we shall see.
This chapter and the next provide an overview of public-key cryptography.
First, we look at its conceptual framework. Interestingly, the concept for this
technique was developed and published before it was shown to be practical to
adopt it. Next, we examine the RSA algorithm, which is the most important encryption/
decryption algorithm that has been shown to be feasible for public-key
encryption. Other important public-key cryptographic algorithms are covered in
Chapter 10.
Much of the theory of public-key cryptosystems is based on number theory.
If one is prepared to accept the results given in this chapter, an understanding of
number theory is not strictly necessary. However, to gain a full appreciation of
public-key algorithms, some understanding of number theory is required. Chapter 2
provides the necessary background in number theory.
1

Table 9.1 Terminology Related to Asymmetric Encryption
Source: Glossary of Key Information Security Terms, NIST IR 7298 [KISS06]

Copyright © 2017 Pearson Education, Inc. All Rights Reserved
Copyright © 2017 Pearson Education, Inc. All Rights Reserved

Table 9.1 defines some key terms.
2

Misconceptions Concerning Public-Key Encryption
Public-key encryption is more secure from cryptanalysis than symmetric encryption
Public-key encryption is a general-purpose technique that has made symmetric encryption obsolete
There is a feeling that key distribution is trivial when using public-key encryption, compared to the cumbersome handshaking involved with key distribution centers for symmetric encryption

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

Before proceeding, we should mention several common misconceptions concerning
public-key encryption. One such misconception is that public-key encryption
is more secure from cryptanalysis than is symmetric encryption. In fact, the
security of any encryption scheme depends on the length of the key and the computational
work involved in breaking a cipher. There is nothing in principle about
either symmetric or public-key encryption that makes one superior to another from
the point of view of resisting cryptanalysis.
A second misconception is that public-key encryption is a general-purpose
technique that has made symmetric encryption obsolete. On the contrary, because
of the computational overhead of current public-key encryption schemes, there
seems no foreseeable likelihood that symmetric encryption will be abandoned. As
one of the inventors of public-key encryption has put it [DIFF88], “the restriction
of public-key cryptography to key management and signature applications is almost
universally accepted.”
Finally, there is a feeling that key distribution is trivial when using public-key
encryption, compared to the rather cumbersome handshaking involved with
key distribution centers for symmetric encryption. In fact, some form of protocol
is needed, generally involving a central agent, and the procedures involved are not
simpler nor any more efficient than those required for symmetric encryption (e.g.,
see analysis in [NEED78]).
3

Principles of Public-Key Cryptosystems
The concept of public-key cryptography evolved from an attempt to attack two of the most difficult problems associated with symmetric encryption:
Key distribution
How to have secure communications in general without having to trust a K D C with your key
Digital signatures
How to verify that a message comes intact from the claimed sender
Whitfield Diffie and Martin Hellman from Stanford University achieved a breakthrough in 1976 by coming up with a method that addressed both problems and was radically different from all previous approaches to cryptography

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

4
The concept of public-key cryptography evolved from an attempt to attack two of
the most difficult problems associated with symmetric encryption. The first problem
is that of key distribution, which is examined in some detail in Chapter 14.
As Chapter 14 discusses, key distribution under symmetric encryption requires
either (1) that two communicants already share a key, which somehow has been distributed
to them; or (2) the use of a key distribution center. Whitfield Diffie, one
of the discoverers of public-key encryption (along with Martin Hellman, both at
Stanford University at the time), reasoned that this second requirement negated
the very essence of cryptography: the ability to maintain total secrecy over your
own communication. As Diffie put it [DIFF88], “what good would it do after all to
develop impenetrable cryptosystems, if their users were forced to share their keys
with a KDC that could be compromised by either burglary or subpoena?”
The second problem that Diffie pondered, and one that was apparently
unrelated to the first, was that of digital signatures . If the use of cryptography
was to become widespread, not just in military situations but for commercial and
private purposes, then electronic messages and documents would need the equivalent
of signatures used in paper documents. That is, could a method be devised
that would stipulate, to the satisfaction of all parties, that a digital message had
been sent by a particular person? This is a somewhat broader requirement than
that of authentication, and its characteristics and ramifications are explored in
Chapter 13.
Diffie and Hellman achieved an astounding breakthrough in 1976
[DIFF76 a, b] by coming up with a method that addressed both problems and was
radically different from all previous approaches to cryptography, going back over
four millennia.

Public-Key Cryptosystems (1 of 2)
A public-key encryption scheme has six ingredients:
Plaintext
The readable message or data that is fed into the algorithm as input
Encryption algorithm
Performs various transforma-tions on the plaintext
Public key
Used for encryption or decryption

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

5
Asymmetric algorithms rely on one key for encryption and a different but related
key for decryption. These algorithms have the following important characteristic.
• It is computationally infeasible to determine the decryption key given only
knowledge of the cryptographic algorithm and the encryption key.
In addition, some algorithms, such as RSA, also exhibit the following characteristic.
• Either of the two related keys can be used for encryption, with the other used
for decryption.
A public-key encryption scheme has six ingredients (Figure 9.1a; compare
with Figure 3.1).
• Plaintext: This is the readable message or data that is fed into the algorithm as
input.
• Encryption algorithm: The encryption algorithm performs various transformations
on the plaintext.
• Public and private keys: This is a pair of keys that have been selected so that
if one is used for encryption, the other is used for decryption. The exact transformations
performed by the algorithm depend on the public or private key
that is provided as input.
•

Public-Key Cryptosystems (2 of 2)
Private key
Used for encryption or decryption
Ciphertext
The scrambled message produced as output
Decryption algorithm
Accepts the ciphertext and the matching key and produces the original plaintext

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

6
• Public and private keys: This is a pair of keys that have been selected so that
if one is used for encryption, the other is used for decryption. The exact transformations
performed by the algorithm depend on the public or private key
that is provided as input.
• Ciphertext: This is the scrambled message produced as output. It depends on
the plaintext and the key. For a given message, two different keys will produce
two different ciphertexts.
• Decryption algorithm: This algorithm accepts the ciphertext and the matching
key and produces the original plaintext.

Figure 9.1 Public-Key Cryptography

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

7
The essential steps are the following.
1. Each user generates a pair of keys to be used for the encryption and decryption
of messages.
2. Each user places one of the two keys in a public register or other accessible
file. This is the public key. The companion key is kept private. As Figure 9.1a
suggests, each user maintains a collection of public keys obtained from others.
3. If Bob wishes to send a confidential message to Alice, Bob encrypts the message
using Alice’s public key.
4. When Alice receives the message, she decrypts it using her private key. No
other recipient can decrypt the message because only Alice knows Alice’s private
key.
With this approach, all participants have access to public keys, and private
keys are generated locally by each participant and therefore need never be
distributed. As long as a user’s private key remains protected and secret, incoming
communication is secure. At any time, a system can change its private key and
publish the companion public key to replace its old public key.

Table 9.2
Conventional and Public-Key Encryption

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

8
Table 9.2 summarizes some of the important aspects of symmetric and public-key
encryption. To discriminate between the two, we refer to the key used in symmetric
encryption as a secret key . The two keys used for asymmetric encryption are
referred to as the public key and the private key . Invariably, the private key is kept
secret, but it is referred to as a private key rather than a secret key to avoid confusion
with symmetric encryption.

Figure 9.2 Public-Key Cryptosystem: Secrecy

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

9
Let us take a closer look at the essential elements of a public-key encryption
scheme, using Figure 9.2 (compare with Figure 3.2).
The scheme illustrated in Figure 9.2 provides confidentiality.

Figure 9.3 Public-Key Cryptosystem: Authentication

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

We mentioned earlier that either of the two related keys can be used for encryption,
with the other being used for decryption. This enables a rather different
cryptographic scheme to be implemented. Whereas the scheme illustrated in
Figure 9.2 provides confidentiality, Figures 9.1b and 9.3 show the use of public-key
encryption to provide authentication.
It is important to emphasize that the encryption process depicted in
Figures 9.1b and 9.3 does not provide confidentiality. That is, the message being
sent is safe from alteration but not from eavesdropping. This is obvious in the
case of a signature based on a portion of the message, because the rest of the
message is transmitted in the clear. Even in the case of complete encryption,
as shown in Figure 9.3, there is no protection of confidentiality because any
observer can decrypt the message by using the sender’s public key.
10

Figure 9.4 Public-Key Cryptosystem: Authentication and Secrecy

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

It is, however, possible to provide both the authentication function and confidentiality
by a double use of the public-key scheme (Figure 9.4).
In this case, we begin as before by encrypting a message, using the sender’s private
key. This provides the digital signature. Next, we encrypt again, using the receiver’s
public key. The final ciphertext can be decrypted only by the intended receiver, who
alone has the matching private key. Thus, confidentiality is provided. The disadvantage
of this approach is that the public-key algorithm, which is complex, must be
exercised four times rather than two in each communication.

Applications for Public-Key Cryptosystems
Public-key cryptosystems can be classified into three categories:
Encryption/decryption
The sender encrypts a message with the recipient’s public key
Digital signature
The sender “signs” a message with its private key
Key exchange
Two sides cooperate to exchange a session key
Some algorithms are suitable for all three applications, whereas others can be used only for one or two

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

Before proceeding, we need to clarify one aspect of public-key cryptosystems that is
otherwise likely to lead to confusion. Public-key systems are characterized by the use
of a cryptographic algorithm with two keys, one held private and one available publicly.
Depending on the application, the sender uses either the sender’s private key or
the receiver’s public key, or both, to perform some type of cryptographic function. In
broad terms, we can classify the use of public-key cryptosystems into three categories
• Encryption/decryption: The sender encrypts a message with the recipient’s
public key.
• Digital signature: The sender “signs” a message with its private key. Signing
is achieved by a cryptographic algorithm applied to the message or to a small
block of data that is a function of the message.
• Key exchange: Two sides cooperate to exchange a session key. Several different
approaches are possible, involving the private key(s) of one or both parties.
12

Table 9.3Applications for Public-Key Cryptosystems

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

Some algorithms are suitable for all three applications, whereas others can be
used only for one or two of these applications. Table 9.3 indicates the applications
supported by the algorithms discussed in this book.
13

Public-Key Requirements (1 of 2)
Conditions that these algorithms must fulfill:
It is computationally easy for a party B to generate a pair (public-key PUb, private key PRb)
It is computationally easy for a sender A, knowing the public key and the message to be encrypted, to generate the corresponding ciphertext
It is computationally easy for the receiver B to decrypt the resulting ciphertext using the private key to recover the original message
It is computationally infeasible for an adversary, knowing the public key, to determine the private key
It is computationally infeasible for an adversary, knowing the public key and a ciphertext, to recover the original message
The two keys can be applied in either order

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

14
The cryptosystem illustrated in Figures 9.2 through 9.4 depends on a cryptographic algorithm based on two related keys. Diffie and Hellman postulated this system without demonstrating that such algorithms exist. However, they did lay out the conditions that such algorithms must fulfill:
It is computationally easy for a party B to generate a pair (public key PUb, private key PRb).
It is computationally easy for a sender A, knowing the public key and the message to be encrypted, M, to generate the corresponding ciphertext:
C = E(PUb, M)
3. It is computationally easy for the receiver B to decrypt the resulting ciphertext using the private key to recover the original message: M = D(PRb, C) = D[PRb, E(PUb, M)
4. It is computationally infeasible for an adversary, knowing the public key, PUb, to determine the private key, PRb
5. It is computationally infeasible for an adversary, knowing the public key, PUb, and a ciphertext, C, to recover the original message, M.
6. (optional) The two keys can be applied in either order:
M = D[PUb , E(PRb, M)] = D[PRb, E(PUb, M)]
These are formidable requirements, as evidenced by the fact that only a few algorithms (RSA, elliptic curve cryptography, Diffie-Hellman, DSS) have received widespread acceptance in the several decades since the concept of public-key cryptography was proposed.

Public-Key Requirements (2 of 2)
Need a trap-door one-way function
A one-way function is one that maps a domain into a range such that every function value has a unique inverse, with the condition that the calculation of the function is easy, whereas the calculation of the inverse is infeasible
Y = f(X) easy
X = f–1(Y) infeasible
A trap-door one-way function is a family of invertible functions fk, such that
Y = fk(X) easy, if k and X are known
X = fk–1(Y) easy, if k and Y are known
X = fk–1(Y) infeasible, if Y known but k not known
A practical public-key scheme depends on a suitable trap-door one-way function

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

Before elaborating on why the requirements are so formidable, let us first recast
them. The requirements boil down to the need for a trap-door one-way function.
A one-way function is one that maps a domain into a range such that every
function value has a unique inverse, with the condition that the calculation of the
function is easy, whereas the calculation of the inverse is infeasible

Y = f(X) easy

X = f–1(Y) infeasible
Generally, easy is defined to mean a problem that can be solved in polynomial
time as a function of input length. Thus, if the length of the input is n bits, then the
time to compute the function is proportional to na , where a is a fixed constant. Such
algorithms are said to belong to the class P . The term infeasible is a much fuzzier
concept. In general, we can say a problem is infeasible if the effort to solve it grows
faster than polynomial time as a function of input size. For example, if the length
of the input is n bits and the time to compute the function is proportional to 2n ,
the problem is considered infeasible. Unfortunately, it is difficult to determine if a
particular algorithm exhibits this complexity. Furthermore, traditional notions of
computational complexity focus on the worst-case or average-case complexity of
an algorithm. These measures are inadequate for cryptography, which requires that
it be infeasible to invert a function for virtually all inputs, not for the worst case or
even average case. A brief introduction to some of these concepts is provided in
Appendix 9A.
We now turn to the definition of a trap-door one-way function , which is easy
to calculate in one direction and infeasible to calculate in the other direction unless
certain additional information is known. With the additional information the
inverse can be calculated in polynomial time. We can summarize as follows: A trapdoor
one-way function is a family of invertible functions fk , such that
Y = fk(X) easy, if k and X are known
X = fk–1(Y) easy, if k and Y are known
X = fk–1(Y) infeasible, if Y known but k not known
Thus, the development of a practical public-key scheme depends on discovery of a suitable trap-door one-way function.
15

Public-Key Cryptanalysis
A public-key encryption scheme is vulnerable to a brute-force attack
Countermeasure: use large keys
Key size must be small enough for practical encryption and decryption
Key sizes that have been proposed result in encryption/decryption speeds that are too slow for general-purpose use
Public-key encryption is currently confined to key management and signature applications
Another form of attack is to find some way to compute the private key given the public key
To date it has not been mathematically proven that this form of attack is infeasible for a particular public-key algorithm
Finally, there is a probable-message attack
This attack can be thwarted by appending some random bits to simple messages

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

16
As with symmetric encryption, a public-key encryption scheme is vulnerable to a
brute-force attack. The countermeasure is the same: Use large keys. However, there
is a tradeoff to be considered. Public-key systems depend on the use of some sort of
invertible mathematical function. The complexity of calculating these functions may
not scale linearly with the number of bits in the key but grow more rapidly than that.
Thus, the key size must be large enough to make brute-force attack impractical but
small enough for practical encryption and decryption. In practice, the key sizes that
have been proposed do make brute-force attack impractical but result in encryption/
decryption speeds that are too slow for general-purpose use. Instead, as was mentioned
earlier, public-key encryption is currently confined to key management and
signature applications.
Another form of attack is to find some way to compute the private key given
the public key. To date, it has not been mathematically proven that this form of attack
is infeasible for a particular public-key algorithm. Thus, any given algorithm,
including the widely used RSA algorithm, is suspect. The history of cryptanalysis
shows that a problem that seems insoluble from one perspective can be found to
have a solution if looked at in an entirely different way.
Finally, there is a form of attack that is peculiar to public-key systems. This is,
in essence, a probable-message attack. Suppose, for example, that a message were to
be sent that consisted solely of a 56-bit DES key. An adversary could encrypt all possible
56-bit DES keys using the public key and could discover the encrypted key by
matching the transmitted ciphertext. Thus, no matter how large the key size of the
public-key scheme, the attack is reduced to a brute-force attack on a 56-bit key. This
attack can be thwarted by appending some random bits to such simple messages.

Rivest-Shamir-Adleman (RSA) Algorithm
Developed in 1977 at MIT by Ron Rivest, Adi Shamir & Len Adleman
Most widely used general-purpose approach to public-key encryption
Is a cipher in which the plaintext and ciphertext are integers between 0 and n – 1 for some n
A typical size for n is 1024 bits, or 309 decimal digits

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

17
The pioneering paper by Diffie and Hellman [DIFF76b] introduced a new approach
to cryptography and, in effect, challenged cryptologists to come up with a cryptographic
algorithm that met the requirements for public-key systems. A number of
algorithms have been proposed for public-key cryptography. Some of these, though
initially promising, turned out to be breakable.
One of the first successful responses to the challenge was developed in 1977
by Ron Rivest, Adi Shamir, and Len Adleman at MIT and first published in 1978
[RIVE78]. The Rivest-Shamir-Adleman (RSA) scheme has since that time reigned
supreme as the most widely accepted and implemented general-purpose approach
to public-key encryption.
The RSA scheme is a cipher in which the plaintext and ciphertext are integers
between 0 and n – 1 for some n . A typical size for n is 1024 bits, or 309 decimal
digits. That is, n is less than 21024 . We examine RSA in this section in some detail,
beginning with an explanation of the algorithm. Then we examine some of the computational
and cryptanalytical implications of RSA.

RSA Algorithm
RSA makes use of an expression with exponentials
Plaintext is encrypted in blocks with each block having a binary value less than some number n
Encryption and decryption are of the following form, for some plaintext block M and ciphertext block C
C = Me mod n
M = Cd mod n = (Me)d mod n = Med mod n
Both sender and receiver must know the value of n
The sender knows the value of e, and only the receiver knows the value of d
This is a public-key encryption algorithm with a public key of PU={e,n} and a private key of PR={d,n}

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

18
RSA makes use of an expression with exponentials. Plaintext is encrypted in blocks,
with each block having a binary value less than some number n . That is, the block
size must be less than or equal to log2 (n ) + 1; in practice, the block size is i bits,
where 2i < n ≤ 2i+1 . Encryption and decryption are of the following form, for some plaintext block M and ciphertext block C. C = Me mod n M = Cd mod n = (Me )d mod n = Med mod n Both sender and receiver must know the value of n . The sender knows the value of e , and only the receiver knows the value of d . Thus, this is a public-key encryption algorithm with a public key of PU = {e , n } and a private key of PR = {d , n }. Algorithm Requirements For this algorithm to be satisfactory for public-key encryption, the following requirements must be met: It is possible to find values of e, d, n such that Med mod n = M for all M < n It is relatively easy to calculate Me mod n and Cd mod n for all values of M < n It is infeasible to determine d given e and n Copyright © 2017 Pearson Education, Inc. All Rights Reserved 19 For this algorithm to be satisfactory for public-key encryption, the following requirements must be met. 1. It is possible to find values of e , d , n such that Med mod n = M for all M < n . 2. It is relatively easy to calculate Me mod n and Cd mod n for all values of M < n . 3. It is infeasible to determine d given e and n . Figure 9.5 The RSA Algorithm Copyright © 2017 Pearson Education, Inc. All Rights Reserved 20 Figure 9.5 summarizes the RSA algorithm. It corresponds to Figure 9.1a: Alice generates a public/private key pair; Bob encrypts using Alice’s public key; and Alice decrypts using her private key. Figure 9.6 Example of RSA Algorithm Copyright © 2017 Pearson Education, Inc. All Rights Reserved An example from [SING99] is shown in Figure 9.6. 21 Figure 9.7 RSA Processing of Multiple Blocks Copyright © 2017 Pearson Education, Inc. All Rights Reserved Figure 9.7a illustrates the sequence of events for the encryption of multiple blocks, and Figure 9.7b gives a specific example. The circled numbers indicate the order in which operations are performed. 22 Exponentiation in Modular Arithmetic Both encryption and decryption in RSA involve raising an integer to an integer power, mod n Can make use of a property of modular arithmetic: [(a mod n) x (b mod n)] mod n =(a x b) mod n With RSA you are dealing with potentially large exponents so efficiency of exponentiation is a consideration Copyright © 2017 Pearson Education, Inc. All Rights Reserved 23 Both encryption and decryption in RSA involve raising an integer to an integer power, mod n . If the exponentiation is done over the integers and then reduced modulo n , the intermediate values would be gargantuan. Fortunately, as the preceding example shows, we can make use of a property of modular arithmetic: [(a mod n ) * (b mod n )] mod n = (a * b ) mod n Thus, we can reduce intermediate results modulo n . This makes the calculation practical. Another consideration is the efficiency of exponentiation, because with RSA, we are dealing with potentially large exponents. To see how efficiency might be increased, consider that we wish to compute x16 . A straightforward approach requires 15 multiplications: x16 = x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x However, we can achieve the same final result with only four multiplications if we repeatedly take the square of each partial result, successively forming (x2 , x4 , x8 , x16 ). Figure 9.8 Algorithm for Computing a to the power of b mod n Copyright © 2017 Pearson Education, Inc. All Rights Reserved 24 We can therefore develop the algorithm for computing ab mod n, shown in Figure 9.8. Table 9.4 Table 9.4 Result of the Fast Modular Exponentiation Algorithm for a to the power of b mod n ,where a = 7 b = 560 = 1000110000, and n = 561 Copyright © 2017 Pearson Education, Inc. All Rights Reserved Copyright © 2017 Pearson Education, Inc. All Rights Reserved Table 9.4 shows an example of the execution of this algorithm. Note that the variable c is not needed; it is included for explanatory purposes. The final value of c is the value of the exponent. 25 Efficient Operation Using the Public Key To speed up the operation of the RSA algorithm using the public key, a specific choice of e is usually made The most common choice is 65537 (216 + 1) Two other popular choices are e=3 and e=17 Each of these choices has only two 1 bits, so the number of multiplications required to perform exponentiation is minimized With a very small public key, such as e = 3, RSA becomes vulnerable to a simple attack Copyright © 2017 Pearson Education, Inc. All Rights Reserved 26 To speed up the operation of the RSA algorithm using the public key, can choose to use a small value of e. The most common choice is 65537 (216 + 1); two other popular choices are 3 and 17. Each of these choices has only two 1 bits and so the number of multiplications required to perform exponentiation is minimized. However, with a very small public key, such as e = 3, RSA becomes vulnerable to a simple attack. Efficient Operation Using the Private Key Decryption uses exponentiation to power d A small value of d is vulnerable to a brute-force attack and to other forms of cryptanalysis Can use the Chinese Remainder Theorem (CRT) to speed up computation The quantities d mod (p – 1) and d mod (q – 1) can be precalculated End result is that the calculation is approximately four times as fast as evaluating M = Cd mod n directly Copyright © 2017 Pearson Education, Inc. All Rights Reserved 27 We cannot similarly choose a small constant value of d for efficient operation. A small value of d is vulnerable to a brute-force attack and to other forms of cryptanalysis [WIEN90]. However, there is a way to speed up computation using the CRT. The quantities d mod (p - 1) and d mod (q - 1) can be precalculated. The end result is that the calculation is approximately four times as fast as evaluating M = Cd mod n directly [BONE02]. Key Generation Before the application of the public-key cryptosystem each participant must generate a pair of keys: Determine two prime numbers p and q Select either e or d and calculate the other Because the value of n = pq will be known to any potential adversary, primes must be chosen from a sufficiently large set The method used for finding large primes must be reasonably efficient Copyright © 2017 Pearson Education, Inc. All Rights Reserved 28 Before the application of the public-key cryptosystem, each participant must generate a pair of keys. This involves the following tasks. • Determining two prime numbers, p and q. • Selecting either e or d and calculating the other. First, consider the selection of p and q . Because the value of n = pq will be known to any potential adversary, in order to prevent the discovery of p and q by exhaustive methods, these primes must be chosen from a sufficiently large set (i.e., p and q must be large numbers). On the other hand, the method used for finding large primes must be reasonably efficient. At present, there are no useful techniques that yield arbitrarily large primes, so some other means of tackling the problem is needed. The procedure that is generally used is to pick at random an odd number of the desired order of magnitude and test whether that number is prime. If not, pick successive random numbers until one is found that tests prime. A variety of tests for primality have been developed (e.g., see [KNUT98] for a description of a number of such tests). Almost invariably, the tests are probabilistic. That is, the test will merely determine that a given integer is probably prime. Despite this lack of certainty, these tests can be run in such a way as to make the probability as close to 1.0 as desired. As an example, one of the more efficient and popular algorithms, the Miller-Rabin algorithm, is described in Chapter 2. With this algorithm and most such algorithms, the procedure for testing whether a given integer n is prime is to perform some calculation that involves n and a randomly chosen integer a . If n “fails” the test, then n is not prime. If n “passes” the test, then n may be prime or nonprime. If n passes many such tests with many different randomly chosen values for a , then we can have high confidence that n is, in fact, prime. Procedure for Picking a Prime Number Pick an odd integer n at random Pick an integer a < n at random Perform the probabilistic primality test with a as a parameter. If n fails the test, reject the value n and go to step 1 If n has passed a sufficient number of tests, accept n; otherwise, go to step 2 Copyright © 2017 Pearson Education, Inc. All Rights Reserved In summary, the procedure for picking a prime number is as follows. 1. Pick an odd integer n at random (e.g., using a pseudorandom number generator). 2. Pick an integer a < n at random. 3. Perform the probabilistic primality test, such as Miller-Rabin, with a as a parameter. If n fails the test, reject the value n and go to step 1. 4. If n has passed a sufficient number of tests, accept n ; otherwise, go to step 2. 29 The Security of R S A (1 of 2) Five possible approaches to attacking R S A are: Brute force Involves trying all possible private keys Mathematical attacks There are several approaches, all equivalent in effort to factoring the product of two primes Timing attacks These depend on the running time of the decryption algorithm Copyright © 2017 Pearson Education, Inc. All Rights Reserved 30 Five possible approaches to attacking the RSA algorithm are ■ Brute force: This involves trying all possible private keys. ■ Mathematical attacks: There are several approaches, all equivalent in effort to factoring the product of two primes. ■ Timing attacks: These depend on the running time of the decryption algorithm. ■ The defense against the brute-force approach is the same for RSA as for other cryptosystems, namely, use a large key space. Thus the larger the number of bits in d, the better. However because the calculations involved both in key generation and in encryption/decryption are complex, the larger the size of the key, the slower the system will run. The Security of R S A (2 of 2) Hardware fault-based attack This involves inducing hardware faults in the processor that is generating digital signatures Chosen ciphertext attacks This type of attack exploits properties of the R S A algorithm Copyright © 2017 Pearson Education, Inc. All Rights Reserved 31 ■ Hardware fault-based attack: This involves inducing hardware faults in the processor that is generating digital signatures. ■ Chosen ciphertext attacks: This type of attack exploits properties of the RSA algorithm. The defense against the brute-force approach is the same for RSA as for other cryptosystems, namely, use a large key space. Thus the larger the number of bits in d, the better. However because the calculations involved both in key generation and in encryption/decryption are complex, the larger the size of the key, the slower the system will run. Factoring Problem We can identify three approaches to attacking RSA mathematically: Factor n into its two prime factors. This enables calculation of ø(n) = (p – 1) x (q – 1), which in turn enables determination of d = e-1 (mod ø(n))
Determine ø(n) directly without first determining p and q. Again this enables determination of d = e-1 (mod ø(n))
Determine d directly without first determining ø(n)

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

32
We can identify three approaches to attacking RSA mathematically:
Factor n into its two prime factors. This enables calculation of ø(n) = (p – 1) x (q – 1), which in turn enables determination of d = e-1 (mod ø(n))
Determine ø(n) directly without first determining p and q. Again this enables determination of d = e-1 (mod ø(n))
Determine d directly without first determining ø(n)

Table 9.5 Progress in RSA Factorization

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

Table 9.5 Progress in RSA Factorization
A striking fact about the progress reflected in Table 9.5 concerns the method
used. Until the mid-1990s, factoring attacks were made using an approach known
as the quadratic sieve. The attack on RSA-130 used a newer algorithm, the generalized
number field sieve (GNFS), and was able to factor a larger number than RSA-
129 at only 20% of the computing effort.
33

Figure 9.9 MIPS-years Needed to Factor

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

The threat to larger key sizes is twofold: the continuing increase in computing
power and the continuing refinement of factoring algorithms. We have seen
that the move to a different algorithm resulted in a tremendous speedup. We
can expect further refinements in the GNFS, and the use of an even better algorithm
is also a possibility. In fact, a related algorithm, the special number field
sieve (SNFS), can factor numbers with a specialized form considerably faster
than the generalized number field sieve. Figure 9.9 compares the performance
of the two algorithms. It is reasonable to expect a breakthrough that would enable
a general factoring performance in about the same time as SNFS, or even
better [ODLY95]. Thus, we need to be careful in choosing a key size for RSA.
34

Timing Attacks
Paul Kocher, a cryptographic consultant, demonstrated that a snooper can determine a private key by keeping track of how long a computer takes to decipher messages
Are applicable not just to RSA but to other public-key cryptography systems
Are alarming for two reasons:
It comes from a completely unexpected direction
It is a ciphertext-only attack

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

35
If one needed yet another lesson about how difficult it is to
assess the security of a cryptographic algorithm, the appearance of timing attacks
provides a stunning one. Paul Kocher, a cryptographic consultant, demonstrated
that a snooper can determine a private key by keeping track of how long a computer
takes to decipher messages [KOCH96, KALI96b]. Timing attacks are applicable
not just to RSA, but to other public-key cryptography systems. This attack is alarming
for two reasons: It comes from a completely unexpected direction, and it is a
ciphertext-only attack.
A timing attack is somewhat analogous to a burglar guessing the combination
of a safe by observing how long it takes for someone to turn the dial from number
to number. We can explain the attack using the modular exponentiation algorithm
of Figure 9.8, but the attack can be adapted to work with any implementation that
does not run in fixed time. In this algorithm, modular exponentiation is accomplished
bit by bit, with one modular multiplication performed at each iteration and
an additional modular multiplication performed for each 1 bit.

Countermeasures
Constant exponentiation time
Ensure that all exponentiations take the same amount of time before returning a result; this is a simple fix but does degrade performance
Random delay
Better performance could be achieved by adding a random delay to the exponentiation algorithm to confuse the timing attack
Blinding
Multiply the ciphertext by a random number before performing exponentiation; this process prevents the attacker from knowing what ciphertext bits are being processed inside the computer and therefore prevents the bit-by-bit analysis essential to the timing attack

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

Although the timing attack is a serious threat, there are simple countermeasures
that can be used, including the following.
• Constant exponentiation time: Ensure that all exponentiations take the same
amount of time before returning a result. This is a simple fix but does degrade
performance.
• Random delay: Better performance could be achieved by adding a random
delay to the exponentiation algorithm to confuse the timing attack. Kocher
points out that if defenders don’t add enough noise, attackers could still succeed
by collecting additional measurements to compensate for the random delays.
• Blinding: Multiply the ciphertext by a random number before performing
exponentiation. This process prevents the attacker from knowing what ciphertext
bits are being processed inside the computer and therefore prevents the
bit-by-bit analysis essential to the timing attack.
36

Fault-Based Attack
An attack on a processor that is generating RSA digital signatures
Induces faults in the signature computation by reducing the power to the processor
The faults cause the software to produce invalid signatures which can then be analyzed by the attacker to recover the private key
The attack algorithm involves inducing single-bit errors and observing the results
While worthy of consideration, this attack does not appear to be a serious threat to RSA
It requires that the attacker have physical access to the target machine and is able to directly control the input power to the processor21

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

Still another unorthodox approach to attacking RSA is reported
in [PELL10]. The approach is an attack on a processor that is generating
RSA digital signatures. The attack induces faults in the signature computation by
reducing the power to the processor. The faults cause the software to produce invalid
signatures, which can then be analyzed by the attacker to recover the private
key. The authors show how such an analysis can be done and then demonstrate it
by extracting a 1024-bit private RSA key in approximately 100 hours, using a commercially
available microprocessor.
The attack algorithm involves inducing single-bit errors and observing the results.
The details are provided in [PELL10], which also references other proposed
hardware fault-based attacks against RSA.
This attack, while worthy of consideration, does not appear to be a serious
threat to RSA. It requires that the attacker have physical access to the target
machine and that the attacker is able to directly control the input power to the
processor. Controlling the input power would for most hardware require more than
simply controlling the AC power, but would also involve the power supply control
hardware on the chip.
37

Chosen Ciphertext Attack (CCA)
The adversary chooses a number of ciphertexts and is then given the corresponding plaintexts, decrypted with the target’s private key
Thus the adversary could select a plaintext, encrypt it with the target’s public key, and then be able to get the plaintext back by having it decrypted with the private key
The adversary exploits properties of RSA and selects blocks of data that, when processed using the target’s private key, yield information needed for cryptanalysis
To counter such attacks, RSA Security Inc. recommends modifying the plaintext using a procedure known as optimal asymmetric encryption padding (OAEP)

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

38
The basic RSA algorithm is vulnerable to a chosen ciphertext attack (CCA). CCA is
defined as an attack in which the adversary chooses a number of ciphertexts and
is then given the corresponding plaintexts, decrypted with the target’s private key.
Thus, the adversary could select a plaintext, encrypt it with the target’s public key,
and then be able to get the plaintext back by having it decrypted with the private
key. Clearly, this provides the adversary with no new information. Instead, the adversary
exploits properties of RSA and selects blocks of data that, when processed
using the target’s private key, yield information needed for cryptanalysis.
To counter such attacks, RSA Security Inc., a leading RSA vendor and former holder
of the RSA patent, recommends modifying the plaintext using a procedure known
as optimal asymmetric encryption padding (OAEP). A full discussion of the threats
and OAEP are beyond our scope; see [POIN02] for an introduction and [BELL94a]
for a thorough analysis. Here, we simply summarize the OAEP procedure.

Figure 9.10 Optimal Asymmetric Encryption Padding (OAEP)

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

Figure 9.10 depicts OAEP encryption. As a first step, the message M to be
encrypted is padded. A set of optional parameters, P , is passed through a hash
function, H. The output is then padded with zeros to get the desired length in the
overall data block (DB). Next, a random seed is generated and passed through
another hash function, called the mask generating function (MGF). The resulting
hash value is bit-by-bit XORed with DB to produce a maskedDB. The maskedDB
is in turn passed through the MGF to form a hash that is XORed with the seed
to produce the masked seed. The concatenation of the masked-seed and the
maskedDB forms the encoded message EM. Note that the EM includes the padded
message, masked by the seed, and the seed, masked by the maskedDB. The EM is
then encrypted using RSA.
39

Summary
Public-key cryptosystems
Applications for public-key cryptosystems
Requirements for public-key cryptography
Public-key cryptanalysis
The RSA algorithm
Description of the algorithm
Computational aspects
Security of RSA

Asymmetric Keys
Two related keys, a public key and a private key that are used to
perform complementary operations, such as encryption and decryption or
signature generation and signature verification.

Public Key Certificate
A digital document issued and digitally signed by the private key of a
Certification Authority that binds the name of a subscriber to a public key.
The certificate indicates that the subscriber identified in the certificate
has sole control and access to the corresponding private key.

Public Key (Asymmetric) Cryptographic Algorithm
A cryptographic algorithm that uses two related keys, a public key and
a private key. The two keys have the property that deriving the private key
from the public key is computationally infeasible.

Public Key Infrastructure (PKI)
A set of policies, processes, server platforms, software and
workstations used for the purpose of administering certificates and public-
private key pairs, including the ability to issue, maintain, and revoke
public key certificates.

Conventional Encryption Public-Key Encryption
Needed to Work:

1. The same algorithm with the same key is
used for encryption and decryption.

2. The sender and receiver must share the
algorithm and the key.

Needed for Security:

1. The key must be kept secret.

2. It must be impossible or at least
impractical to decipher a message if the
key is kept secret.

3. Knowledge of the algorithm plus
samples of ciphertext must be
insufficient to determine the key.

Needed to Work:

1. One algorithm is used for encryption and
a related algorithm for decryption with a
pair of keys, one for encryption and one
for decryption.

2. The sender and receiver must each have
one of the matched pair of keys (not the
same one).

Needed for Security:

1. One of the two keys must be kept secret.

2. It must be impossible or at least
impractical to decipher a message if one
of the keys is kept secret.

3. Knowledge of the algorithm plus one of
the keys plus samples of ciphertext must
be insufficient to determine the other
key.

Algorithm Encryption/Decryption Digital Signature Key Exchange
RSA Yes Yes Yes
Elliptic Curve Yes Yes Yes
Diffie-Hellman No No Yes
DSS No Yes No

Plaintext P
Decimal string
Sender
Figure 9.7 RSA Processing of Multiple Blocks
Receiver
(a) General approach (b) Example
Blocks of numbers
Transmit
P
1
, P
2
,
P
1
= C
1
d
mod n
P
2
= C
2
d
mod n
Ciphertext C
C
1
= P
1
e
mod n
C
2
= P
2
e
mod n
Recovered
decimal text
d = e–1 mod �(n)
�(n) = (p – 1)(q – 1)
n = pq
n = pq
Random number
generator
e, p, q
Private key
d, n
Public key
e, n
How_are_you?
33 14 22 62 00 17 04 62 24 14 20 66
Sender
Receiver
Transmit
P
1
= 3314 P
2
= 2262 P
3
= 0017
P
4
= 0462 P
5
= 2414 P
6
= 2066
C
1
= 3314
11
mod 11023 = 10260
C
2
= 2262
11
mod 11023 = 9489
C
3
= 17
11
mod 11023 = 1782
C
4
= 462
11
mod 11023 = 727
C
5
= 2414
11
mod 11023 = 10032
C
6
= 2066
11
mod 11023 = 2253
P
1
= 10260
5891
mod 11023 = 3314
P
2
= 9489
5891
mod 11023 = 2262
P
3
= 1782
5891
mod 11023 = 0017
P
4
= 727
5891
mod 11023 = 0462
P
5
= 10032
5891
mod 11023 = 2414
P
6
= 2253
5891
mod 11023 = 2066
11023 = 73 151
5891 = 11
–1
mod 10800
10800 = (73 – 1)(151 – 1)
11023 = 73 51
Random number
generator
e = 11
n = 11023
d = 5891
n = 11023
e = 11
p = 73, q = 151
1
2
6
3
4
5
7
1
2
6
3
4
5
7

i 9 8 7 6 5 4 3 2 1 0
bi 1 0 0 0 1 1 0 0 0 0
c 1 2 4 8 17 35 70 140 280 560
f 7 49 157 526 160 241 298 166 67 1

Number of
Decimal Digits
Number of Bits Date Achieved
100 332 April 1991
110 365 April 1992
120 398 June 1993
129 428 April 1994
130 431 April 1996
140 465 February 1999
155 512 August 1999
160 530 April 2003
174 576 December 2003
200 663 May 2005
193 640 November 2005
232 768 December 2009

Turn in your highest-quality paper
Get a qualified writer to help you with

“ Cryptography course assignment ”

Get high-quality paper

NEW! AI matching with writer

Hire a Writer

Client Reviews

4.9

Sitejabber

4.6

Trustpilot

4.8

Our Guarantees

100% Confidentiality

Information about customers is confidential and never disclosed to third parties.

Original Writing

We complete all papers from scratch. You can get a plagiarism report.

Timely Delivery

No missed deadlines – 97% of assignments are completed in time.

Money Back

If you're confident that a writer didn't follow your order details, ask for a refund.

New to Your Trusted Assignment Help Service? Sign up & Save

Calculate the price of your order

Type of paper needed:

Pages:

You will get a personal manager and a discount.

Academic level:

We'll send you the first draft for approval by at

Total price:

$0.00

Power up Your Academic Success with the
Team of Professionals. We’ve Got Your Back.

Power up Your Study Success with Experts We’ve Got Your Back.

Order Now Order Now