Stallings_8e_Accessible_fullppt_10.pdf

Cryptography and Network Security:

Principles and PracticeEighth Edition

Chapter 10

Other Public-Key Cryptosystems

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

Figure 10.1 The Diffie–Hellman Key

Exchange

Figure 10.2 Man-in-the-Middle Attack

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

Figure 10.3 The ElGamal

Cryptosystem

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

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

Figure 10.4 Example of Elliptic

Curves

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

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)

Figure 10.5 The Elliptic Curve

E23(1, 1)

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

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

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)

Figure 10.6 The Elliptic Curve

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

Figure 10.7 ECC Diffie–Hellman Key

Exchange

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

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 = 1601024 160–223

112 L = 2048

N = 2242048 224–255

128 L = 3072

N = 2563072 256–383

192 L = 7680

N = 3847680 384–511

256 L = 15,360

N = 51215,360 512 +

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

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

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.

Stallings_8e_Accessible_fullppt_10.pdf

Stallings_8e_Accessible_fullppt_10.pdf

Related posts

HW