3 - Discussions

Sinners0043

Chapter10_Cryptography.pptx

Home >Computer Science homework help >3 - Discussions

Cryptography and Network Security: Principles and Practice

Eighth Edition

Chapter 10

Other Public-Key Cryptosystems

Lecture slides prepared for “Cryptography and Network Security”, 8/e, by William Stallings, Chapter 10 – “Other Public-Key Cryptosystems”.

This chapter begins with a description of one of the earliest and simplest PKCS: Diffie-Hellman key exchange. The chapter then looks at another important scheme, the Elgamal PKCS. Next, we look at the increasingly important PKCS known as elliptic curve cryptography.

Learning Objectives

Define Diffie–Hellman key exchange.

Understand the man-in-the-middle attack.

Present an overview of the ElGamal cryptographic system.

Understand elliptic curve arithmetic.

Present an overview of elliptic curve cryptography.

Present two techniques for generating pseudorandom numbers using an asymmetric cipher.

10.1 Diffie–Hellman Key Exchange

Diffie-Hellman Key Exchange

First published public-key algorithm

A number of commercial products employ this key exchange technique

Purpose is to enable two users to securely exchange a key that can then be used for subsequent symmetric encryption of messages

The algorithm itself is limited to the exchange of secret values

Its effectiveness depends on the difficulty of computing discrete logarithms

The first published public-key algorithm appeared in the seminal paper by Diffie and Hellman that defined public-key cryptography [DIFF76b] and is generally referred to as Diffie-Hellman key exchange. A number of commercial products employ this key exchange technique.

The purpose of the algorithm is to enable two users to securely exchange a key that can then be used for subsequent symmetric encryption of messages. The algorithm itself is limited to the exchange of secret values.

The Diffie-Hellman algorithm depends for its effectiveness on the difficulty of computing discrete logarithms. Briefly, we can define the discrete logarithm in the following way. Recall from Chapter 2 that a primitive root of a prime number p is one whose powers modulo p generate all the integers from 1 to p - 1. That is, if a

is a primitive root of the prime number p, then the numbers

a mod p , a2 mod p , . . . , ap-1 mod p

are distinct and consist of the integers from 1 through p - 1 in some permutation.

For any integer b and a primitive root a of prime number p , we can find a unique exponent i such that

b = ai (mod p ) where 0 ≤ i ≤ (p - 1)

The exponent i is referred to as the discrete logarithm of b for the base a , mod p . We express this value as dloga,p (b ). See Chapter 2 for an extended discussion of discrete logarithms.

Figure 10.1 The Diffie–Hellman Key Exchange

Figure 10.1 summarizes the Diffie-Hellman key exchange algorithm. For this scheme, there are two publicly known numbers: a prime number q and an integer a that is a primitive root of q .

Figure 10.1 shows a simple protocol that makes use of the Diffie–Hellman calculation. Suppose that user A wishes to set up a connection with user B and use a secret key to encrypt messages on that connection. User A can generate a one-time private key XA, calculate YA, and send that to user B. User B responds by generating a private value XB, calculating YB, and sending YB to user A. Both users can now calculate the key. The necessary public values q and a would need to be known ahead of time. Alternatively, user A could pick values for q and a and include those in the first message.

Figure 10.2 Man-in-the-Middle Attack

The protocol depicted in Figure 10.1 is insecure against a man-in-the-middle attack. Suppose Alice and Bob wish to exchange keys, and Darth is the adversary. The attack proceeds as follows (Figure 10.2).

Darth prepares for the attack by generating two random private keys XD1 and XD2 and then computing the corresponding public keys YD1 and YD2

Alice transmits YA to Bob.

Darth intercepts YA and transmits YD1 to Bob. Darth also calculates K2 = (YA )^ XD2 mod q

Bob receives YD1 and calculates K1=(YD1 )^ XB mod q

Bob transmits YB to Alice.

Darth intercepts YB and transmits YD2 to Alice. Darth calculates K1=(YB )^ XD1 mod q

Alice receives YD2 and calculates K2=(YD2 )^ XA mod q .

At this point, Bob and Alice think that they share a secret key, but instead Bob and Darth share secret key K1 and Alice and Darth share secret key K2. All future communication between Bob and Alice is compromised in the following way:

Alice sends an encrypted message M: E(K2, M).

Darth intercepts the encrypted message and decrypts it, to recover M.

Darth sends Bob E(K1, M) or E(K1, M'), where M' is any message. In the first case, Darth simply wants to eavesdrop on the communication without altering it. In the second case, Darth wants to modify the message going to Bob.

The key exchange protocol is vulnerable to such an attack because it does not authenticate the participants. This vulnerability can be overcome with the use of digital signatures and public-key certificates.

10.2 Elgamal Cryptographic System

ElGamal Cryptography

Announced in 1984 by T. Elgamal

Public-key scheme based on discrete logarithms closely related to the Diffie-Hellman technique

Used in the digital signature standard (DSS) and the S/MIME e-mail standard

Global elements are a prime number q and a which is a primitive root of q

Security is based on the difficulty of computing discrete logarithms

In 1984, T. Elgamal announced a public-key scheme based on discrete logarithms, closely related to the Diffie-Hellman technique [ELGA84, ELGA85]. The ElGamal cryptosystem is used in some form in a number of standards including the digital signature standard (DSS) and the S/MIME email standard.

As with Diffie-Hellman, the global elements of ElGamal are a prime number q and a, which is a primitive root of q. User A generates a private/public key pair. The security of ElGamal is based on the difficulty of computing discrete logarithms.

Figure 10.3 The ElGamal Cryptosystem

Figure 10.3 summarizes the ElGamal Cryptosystem. 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.

Process

Bob generates a random integer k.

Bob generates a one-time key K using Alice’s public-key components YA, q, and k.

Bob encrypts k using the public-key component α, yielding C1. C1 provides sufficient information for Alice to recover K.

Bob encrypts the plaintext message M using K.

Alice recovers K from C1 using her private key.

Alice uses K−1 to recover the plaintext message from C2.

10.3 Elliptic Curve Arithmetic

Elliptic Curve Arithmetic

Most of the products and standards that use public-key cryptography for encryption and digital signatures use RSA

The key length for secure RSA use has increased over recent years and this has put a heavier processing load on applications using RSA

Elliptic curve cryptography (ECC) is showing up in standardization efforts including the IEEE P1363 Standard for Public-Key Cryptography

Principal attraction of ECC is that it appears to offer equal security for a far smaller key size

Most of the products and standards that use public-key cryptography for encryption and digital signatures use RSA. As we have seen, the key length for secure RSA use has increased over recent years, and this has put a heavier processing load on applications using RSA. This burden has ramifications, especially for electronic commerce

sites that conduct large numbers of secure transactions. A competing system challenges RSA: elliptic curve cryptography (ECC). ECC is showing up in standardization efforts, including the IEEE P1363 Standard for Public-Key Cryptography.

The principal attraction of ECC, compared to RSA, is that it appears to offer equal security for a far smaller key size, thereby reducing processing overhead.

ECC is fundamentally more difficult to explain than either RSA or Diffie-Hellman, and a full mathematical description is beyond the scope of this book. This section and the next give some background on elliptic curves and ECC. We begin with a brief review of the concept of abelian group. Next, we examine the concept of elliptic curves defined over the real numbers. This is followed by a look

at elliptic curves defined over finite fields. Finally, we are able to examine elliptic curve ciphers.

Abelian Group

A set of elements with a binary operation, denoted by •, that associates to each ordered pair (a, b) of elements in G an element (a • b) in G, such that the following axioms are obeyed:

(A1) Closure: If a and b belong to G, then a • b is also in G

(A2) Associative: a • (b • c) = (a • b) • c for all a, b, c in G

(A3) Identity element: There is an element e in G such that a • e = e • a = a for all a in G

(A4) Inverse element: For each a in G there is an element a′ in G such that a • a′ = a′ • a = e

(A5) Commutative: a • b = b • a for all a, b in G

Recall from Chapter 5 that an abelian group G, sometimes denoted by {G , . }, is a set of elements with a binary operation, denoted by . , that associates to each ordered pair (a,b) of elements in G an element (a . b ) in G , such that the following axioms are obeyed:

(A1) Closure: If a and b belong to G , then a . b is also in G .

(A2) Associative: a . (b . c ) = (a . b ) . c for all a , b , c in G .

(A3) Identity element: There is an element e in G such that a . e = e . a = a for all a in G .

(A4) Inverse element: For each a in G there is an element a′ in G such that a . a′ = a′ . a = e.

(A5) Commutative: a . b = b . a for all a , b in G .

Figure 10.4 Example of Elliptic Curves

Elliptic curves are not ellipses. They are so named because they are described by cubic equations, similar to those used for calculating the circumference of an ellipse. In general, cubic equations for elliptic curves take the following form, known as a Weierstrass equation:

y2 + axy + by = x3 + cx2 + dx + e

where a , b , c , d , e are real numbers and x and y take on values in the real numbers.

For our purpose, it is sufficient to limit ourselves to equations of the form

y2 = x3 + ax + b

Such equations are said to be cubic, or of degree 3, because the highest exponent they contain is a 3. Also included in the definition of an elliptic curve is a single element denoted O and called the point at infinity or the zero point, which we discuss subsequently. To plot such a curve, we need to compute

y = √x3 + ax + b

For given values of a and b, the plot consists of positive and negative values of y for each value of x. Thus, each curve is symmetric about y = 0. Figure 10.4 shows two examples of elliptic curves. As you can see, the formula sometimes produces weird looking curves.

Now, consider the set of points E(a,b ) consisting of all of the points (x,y ) that satisfy Equation (10.1) together with the element O. Using a different value of the pair (a,b ) results in a different set E(a,b ). Using this terminology, the two curves in Figure 10.4 depict the sets E(- 1, 0) and E(1,1), respectively.

Elliptic Curves Over Zp

Elliptic curve cryptography uses curves whose variables and coefficients are finite

Two families of elliptic curves are used in cryptographic applications:

Prime curves over Zp

Use a cubic equation in which the variables and coefficients all take on values in the set of integers from 0 through p-1 and in which calculations are performed modulo p

Best for software applications

Binary curves over GF(2m)

Variables and coefficients all take on values in GF(2m) and in calculations are performed over GF(2m)

Best for hardware applications

Elliptic curve cryptography makes use of elliptic curves in which the variables and coefficients are all restricted to elements of a finite field. Two families of elliptic curves are used in cryptographic applications: prime curves over Zp (best for software use), and binary curves over GF(2m). For a prime curve over Zp, we use a cubic equation in which the variables and coefficients all take on values in the set of integers from 0 through p - 1 and in which calculations are performed modulo p. For a binary curve defined over GF(2m), the variables and coefficients all take on values in GF(2m) and in calculations are performed over GF(2m). [FERN99] points out that prime curves are best for software applications, because the extended bit-fiddling operations needed by binary curves are not required; and that binary curves are best for hardware applications, where it takes remarkably few logic gates to create a powerful, fast cryptosystem.

There is no obvious geometric interpretation of elliptic curve arithmetic over finite fields. The algebraic interpretation used for elliptic curve arithmetic over real numbers does readily carry over, and this is the approach we take.

Table 10.1 Points (other than O) on the Elliptic Curve E23(1, 1)

(0, 1)	(6, 4)	(12, 19)
(0, 22)	(6, 19)	(13, 7)
(1, 7)	(7, 11)	(13, 16)
(1, 16)	(7, 12)	(17, 3)
(3, 10)	(9, 7)	(17, 20)
(3, 13)	(9, 16)	(18, 3)
(4, 0)	(11, 3)	(18, 20)
(5, 4)	(11, 20)	(19, 5)
(5, 19)	(12, 4)	(19, 18)

Table 10.1 Points (other than O) on the Elliptic Curve E23(1, 1)

Figure 10.5 The Elliptic Curve E23(1, 1)

Figure 10.5 plots the points of E23 (1,1); note that the points, with one exception, are symmetric about y = 11.5.

Elliptic Curves Over GF(2m)

Use a cubic equation in which the variables and coefficients all take on values in GF(2m) for some number m

Calculations are performed using the rules of arithmetic in GF(2m)

The form of cubic equation appropriate for cryptographic applications for elliptic curves is somewhat different for GF(2m) than for Zp

It is understood that the variables x and y and the coefficients a and b are elements of GF(2m) and that calculations are performed in GF(2m)

Recall from Chapter 5 that a finite field GF(2m ) consists of 2m elements, together with addition and multiplication operations that can be defined over polynomials. For elliptic curves over GF(2m ), we use a cubic equation in which the variables and coefficients all take on values in GF(2m ) for some number m and in which calculations are performed using the rules of arithmetic in GF(2m ).

It turns out that the form of cubic equation appropriate for cryptographic applications for elliptic curves is somewhat different for GF(2m ) than for Zp . The form is y2 + xy = x3 + ax2 + b

Table 10.2 Points (other than O) on the Elliptic Curve E24(g4, 1)

(0, 1)	(g5, g3)	(g9, g13)
(1, g6)	(g5, g11)	(g10, g)
(1, g13)	(g6, g8)	(g10, g8)
(g3, g8)	(g6, g14)	(g12, 0)
(g3, g13)	(g9, g10)	(g12, g12)

Table 10.2 lists the points (other than O ) that are part of E24 (g4 , 1).

Figure 10.6 The Elliptic Curve E24(g4, 1)

Figure 10.6 plots the points of E24 (g4 , 1).

Elliptic Curve Cryptography (ECC)

Addition operation in ECC is the counterpart of modular multiplication in RSA

Multiple addition is the counterpart of modular exponentiation

To form a cryptographic system using elliptic curves, we need to find a “hard problem” corresponding to factoring the product of two primes or taking the discrete logarithm

Q=kP, where Q, P belong to a prime curve

Is “easy” to compute Q given k and P

But “hard” to find k given Q, and P

Known as the elliptic curve logarithm problem

The addition operation in ECC is the counterpart of modular multiplication in RSA, and multiple addition is the counterpart of modular exponentiation. To form a cryptographic system using elliptic curves, we need to find a “hard problem” corresponding

to factoring the product of two primes or taking the discrete logarithm.

We give an example taken from the Certicom Web site (www.certicom.com). Consider the group E23(9, 17). This is the group defined by the equation y2 mod 23 = (x3 + 9x + 17) mod 23. What is the discrete logarithm k of Q = (4, 5) to the base P = (16, 5)? The brute-force method is to compute multiples of P until Q is found. Thus P = (16, 5); 2P = (20, 20); 3P = (14, 14); 4P = (19, 20); 5P = (13, 10); 6P = (7, 3); 7P = (8, 7); 8P = (12, 17) ; 9P = (4, 5). Because 9P = (4, 5) = Q, the discrete logarithm Q = (4, 5) to the base P = (16, 5) is k = 9. In a real application, k would be so large as to make the brute-force approach infeasible.

Figure 10.7 ECC Diffie–Hellman Key Exchange

Figure 10.7 ECC Diffie-Hellman Key Exchange.

A key exchange between users A and B can be accomplished as follows (Figure 10.7).

10.4 Elliptic Curve Cryptography

Security of Elliptic Curve Cryptography

Depends on the difficulty of the elliptic curve logarithm problem

Fastest known technique is “Pollard rho method”

Compared to factoring, can use much smaller key sizes than with RSA

For equivalent key lengths computations are roughly equivalent

Hence, for similar security ECC offers significant computational advantages

The security of ECC depends on how difficult it is to determine k given kP and P . This is referred to as the elliptic curve logarithm problem. The fastest known technique for taking the elliptic curve logarithm is known as the Pollard rho method.

Table 10.3 Comparable Key Sizes in Terms of Computational Effort for Cryptanalysis (NIST SP-800-57)

Symmetric Key Algorithms	Diffie–Hellman, Digital Signature Algorithm	RSA (size of n in bits)	ECC (modulus size in bits)
80	L = 1024 N = 160	1024	160–223
112	L = 2048 N = 224	2048	224–255
128	L = 3072 N = 256	3072	256–383
192	L = 7680 N = 384	7680	384–511
256	L = 15,360 N = 512	15,360	512 +

Note: L = size of public key, N = size of private key.

Table 10.3, from NIST SP800-57 (Recommendation for Key Management—Part 1: General, September 2015), compares various algorithms by showing comparable key sizes in terms of computational effort for cryptanalysis. As can be seen, a considerably

smaller key size can be used for ECC compared to RSA.

Based on this analysis, SP 800-57 recommends that at least through 2030, acceptable key lengths are from 3072 to 14,360 bits for RSA and 256 to 512 bits for ECC. Similarly, the European Union Agency for Network and Information Security (ENISA) recommends in their 2014 report (Algorithms, Key Size and Parameters report—2014 , November 2014) minimum key lengths for future system of 3072 bits

and 256 bits for RSA and ECC, respectively.

Analysis indicates that for equal key lengths, the computational effort required for ECC and RSA is comparable [JURI97]. Thus, there is a computational advantage to using ECC with a shorter key length than a comparably secure RSA.

Summary

Define Diffie-Hellman Key Exchange

Understand the Man-in-the-middle attack

Present an overview of the Elgamal cryptographic system

Understand Elliptic curve arithmetic

Present an overview of elliptic curve cryptography

Present two techniques for generating pseudorandom numbers using an asymmetric cipher

Chapter 10 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; }