Stallings_8e_Accessible_fullppt_10.pdf

Cryptography and Network Security:
Principles and PracticeEighth Edition
Chapter 10
Other Public-Key Cryptosystems
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
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

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Figure 10.1 The Diffie–Hellman Key
Exchange

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Figure 10.2 Man-in-the-Middle Attack

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
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

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Figure 10.3 The ElGamal
Cryptosystem

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
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

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
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

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Figure 10.4 Example of Elliptic
Curves

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
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

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
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)

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Figure 10.5 The Elliptic Curve
E23(1, 1)

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
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)

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
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)

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Figure 10.6 The Elliptic Curve
E24(g4, 1)

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
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

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Figure 10.7 ECC Diffie–Hellman Key
Exchange

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
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

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
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.

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
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

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Copyright
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.