Cryptography

Chapter9Powerpoint.pptx

Home >Information Systems homework help >Cryptography

Cryptography and Network Security: Principles and Practice

Eighth Edition

Chapter 9

Public Key Cryptography and R S A

Lecture slides prepared for “Cryptography and Network Security”, 8/e, by William Stallings, Chapter 9 – “Public Key Cryptography and RSA”.

The development of public-key, or asymmetric 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.

Learning Objectives

Present an overview of the basic principles of public-key cryptosystems.

Explain the two distinct uses of public-key cryptosystems.

List and explain the requirements for a public-key cryptosystem.

Present an overview of the RSA algorithm.

Understand the timing attack.

Summarize the relevant issues related to the complexity of algorithms.

Table 9.1 Terminology Related to Asymmetric Encryption

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.

Source: Glossary of Key Information Security Terms, NISTIR 7298.

Table 9.1 defines some key terms.

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

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]).

9.1 Principles of Public-Key Cryptosystems

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

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

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

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

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.

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

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.

Figure 9.1 Public-Key Cryptography (2 of 2)

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

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 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. 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 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.

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.

Public-Key Cryptosystem: Confidentiality

Figure 9.2 Public-Key Cryptosystem: Confidentiality

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.

Public-Key Cryptosystem: Authentication

Figure 9.3 Public-Key Cryptosystem: Authentication

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.

Public-Key Cryptosystem: Authentication and Secrecy

Figure 9.4 Public-Key Cryptosystem: Authentication and Secrecy

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

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, which is a secret key for

symmetric encryption generated for use for a particular transaction (or session) and valid for

a short period of time. Several different approaches are possible, involving the private key(s)

of one or both parties.

Table 9.3 Applications for Public-Key Cryptosystems

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

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.

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 P Ub, private key P Rb)

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

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: [DIFF76b].

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. 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

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. [LAI18] provides an excellent introduction to complexity.

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.

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

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.

9.2 The RSA Algorithm

Rivest-Shamir-Adleman (R S A) Algorithm

Developed in 1977 at M I T 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

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. 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.

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.

R S A 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}

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

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, and 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 R S A Algorithm

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.

Example of R S A Algorithm

Figure 9.6 Example of R S A Algorithm

An example is shown in Figure 9.6.

Figure 9.7 R S A Processing of Multiple Blocks (1 of 2)

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.

Figure 9.7 R S A Processing of Multiple Blocks (2 of 2)

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.

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

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 ab mod n

Note: The integer b is expressed as a binary number bkbk − 1...b0

We can therefore develop the algorithm for computing ab mod n, shown in

Figure 9.8.

Table 9.4 Result of the Fast Modular Exponentiation Algorithm for ab mod n, where a = 7, b = 560 = 1000110000, and n = 561

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

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.

Efficient Operation Using the Public Key

To speed up the operation of the R S A 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, R S A becomes vulnerable to a simple attack

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 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 (C R T) 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

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

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

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.

The Security of R S A

Five possible approaches to attacking RSA 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

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

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.

■ 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)

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)

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

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

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.

Fault-Based Attack

An attack on a processor that is generating R S A 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 R S A

It requires that the attacker have physical access to the target machine and is able to directly control the input power to the processor

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.

Chosen Ciphertext Attack (C C A)

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 R S A and selects blocks of data that, when processed using the target’s private key, yield information needed for cryptanalysis

To counter such attacks, R S A Security Inc. recommends modifying the plaintext using a procedure known as optimal asymmetric encryption padding (O A E P)

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.9 Encryption Using Optimal Asymmetric Encryption Padding (O A E P)

Figure 9.9 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.

Summary

Present an overview of the basic principles of public-key cryptosystems

Explain the two distinct uses of public-key cryptosystems

List and explain the requirements for a public-key cryptosystem

Present an overview of the R S A algorithm

Understand the timing attack

Summarize the relevant issues related to the complexity of algorithms

Chapter 9 summary.

This work is protected by United States copyright laws and is provided solely for the use of instructors in teaching their courses and assessing student learning. Dissemination or sale of any part of this work (including on the World Wide Web) will destroy the integrity of the work and is not permitted. The work and materials from it should never be made available to students except by instructors using the accompanying text in their classes. All recipients of this work are expected to abide by these restrictions and to honor the intended pedagogical purposes and the needs of other instructors who rely on these materials.

.MsftOfcThm_Text1_Fill { fill:#000000; } .MsftOfcThm_MainDark1_Stroke { stroke:#000000; }

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

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

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