Cryptography and
Network Security
Eighth Edition
by William Stallings
© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
Chapter 9
Public Key Cryptography and RSA
© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
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, NIST IR 7298
© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
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
© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
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 KDC 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
© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
Public-Key Cryptosystems
• A public-key encryption scheme has six ingredients:
Encryption Decryption
Plaintext Public key Private key Ciphertext
algorithm algorithm
The Accepts the
readable ciphertext
Performs The
message Used for Used for and the
various scrambled
or data encryption encryption matching
transforma- message
that is fed or or key and
tions on the produced
into the decryption decryption produces the
plaintext as output
algorithm original
as input plaintext
© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
Bobs's
public key
ring
Joy
Ted
Mike Alice
PUa Alice's public PRa Alice 's private
key key
Transmitted X=
X ciphertext D[PRa, Y]
Y = E[PUa, X]
Plaintext Plaintext
Encryption algorithm Decryption algorithm
input output
(e.g., RSA)
Bob (a) Encryption with public key Alice
Figure 9.1 Public-Key Cryptography
© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
Alice's
public key
ring
Joy
Ted
Mike Bob
PRb Bob's private PUb Bob's public
key key
X=
X Transmitted D[PUb, Y]
ciphertext
Y = E[PRb, X]
Plaintext Plaintext
Encryption algorithm Decryption algorithm
input output
(e.g., RSA)
Bob (b) Encryption with private key Alice
Figure 9.1 Public-Key Cryptography
© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
Table 9.2 CONVENTIONAL AND PUBLIC-KEY ENCRYPTION
Conventional Encryption Public-Key Encryption
Needed to Work: Needed to Work:
1. The same algorithm with the same key is used for 1. One algorithm is used for encryption and a related
encryption and decryption. algorithm for decryption with a pair of keys, one for
encryption and one for decryption.
2. The sender and receiver must share the algorithm and
the key. 2. The sender and receiver must each have one of the
matched pair of keys (not the same one).
Needed for Security:
Needed for Security:
1. The key must be kept secret.
1. One of the two keys must be kept secret.
2. It must be impossible or at least impractical to decipher a
message if the key is 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 samples of ciphertext
must be insufficient to determine the key. 3. Knowledge of the algorithm plus one of the keys plus
samples of ciphertext must be insufficient to determine
the other key.
© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
Public-Key Cryptosystem: Confidentiality
^
X
Cryptanalyst
^
PRb
Source A Destination B
Message X Encryption Decryption
Destination
Source Algorithm Y = E[PUb, X] Algorithm
X=
D[PRb, Y]
PUb PRb
Key Pair
Source
© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
Public-Key Cryptosystem: Authentication
© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
Public-Key Cryptosystem:
Authentication and Secrecy
© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
Applications for Public-Key
Cryptosystems
• Public-key cryptosystems can be classified into
three categories:
•The sender encrypts a message
Encryption/decryption with the recipient’s public key
•The sender “signs” a message
Digital signature with its private key
•Two sides cooperate to
Key exchange exchange a session key
• Some algorithms are suitable for all three
applications, whereas others can be used only for
one or two
© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
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
Table 9.3 Applications for Public-Key Cryptosystems
© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
Public-Key Requirements
• 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
© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
Public-Key Requirements
• 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
© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
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
© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
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
© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
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}
© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
Algorithm Requirements
• 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
© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
Key Generation by Alice
Select p, q p and q both prime, p ≠ q
Calculate n = p ´ q
Calculate f(n) = (p – 1)(q – 1)
Select integer e gcd(f(n), e) = 1; 1 < e < f(n)
Calculate d d º e-1 (mod f(n))
Public key PU = {e, n}
Private key PR = {d, n}
Encryption by Bob with Alice's Public Key
Plaintext: M<n
Ciphertext: C = Me mod n
Decryption by Alice with Alice's Private Key
Ciphertext: C
Plaintext: M = Cd mod n
Figure 9.5 The RSA Algorithm
© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
Example of RSA Algorithm
Encryption Decryption
ciphertext
plaintext plaintext
7 11 23
88 88 mod 187 = 11 11 mod 187 = 88 88
PU = 7, 187 PR = 23, 187
Figure 9.6 Example of RSA Algorithm
© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
Sender
3
Plaintext P
Decimal string
4
Blocks of numbers
P1, P2,
Figure 9.7
5
Ciphertext C
2
RSA Processing Public key
e, n
C1 = P1e mod n
C2 = P2e mod n
of Multiple Blocks
n = pq
Transmit
6 7
Private key Recovered
d, n decimal text
P1 = C1d mod n
d= mod f(n)
e–1 P2 = C2d mod n
f(n) = (p – 1)(q – 1)
1 n = pq
e, p, q
Random number Receiver
generator
(a) General approach
© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
Sender
3
How_are_you?
33 14 22 62 00 17 04 62 24 14 20 66
Figure 9.7 4
P1 = 3314 P2 = 2262 P3 = 0017
P4 = 0462 P5 = 2414 P6 = 2066
RSA Processing 5
of Multiple 2
C1 = 3314 11 mod 11023 = 10260
C2 = 2262 11 mod 11023 = 9489
Blocks e = 11
n = 11023
C3 = 17 11 mod 11023 = 1782
C4 = 462 11 mod 11023 = 727
C5 = 2414 11 mod 11023 = 10032
C6 = 2066 11 mod 11023 = 2253
11023 = 73 151
Transmit
6 7
d = 5891
P1 = 10260 5891 mod 11023 = 3314
n = 11023
P2 = 9489 5891 mod 11023 = 2262
P3 = 1782 5891 mod 11023 = 0017
5891 = 11–1 mod 10800 P4 = 727 5891 mod 11023 = 0462
10800 = (73 – 1)(151 – 1) P5 = 10032 5891 mod 11023 = 2414
1 11023 = 73 51 P6 = 2253 5891 mod 11023 = 2066
e = 11
p = 73, q = 151
Random number
Receiver
generator
© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
(b) Example
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
© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
c ¬ 0; f ¬ 1
for i ¬ k downto 0
do c ¬ 2 ´ c
f ¬ (f ´ f) mod n
if bi = 1
then c ¬ c + 1
f ¬ (f ´ a) mod n
return f
Note: The integer b is expressed as a binary number bkbk–1...b0
Figure 9.8 Algorithm for Computing ab mod n
© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
Table 9.4
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
© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
Key Generation
• Before the application of • Because the value of n = pq
the public-key will be known to any
cryptosystem each potential adversary, primes
participant must must be chosen from a
generate a pair of keys: sufficiently large set
• Determine two prime • The method used for
numbers p and q finding large primes must
• Select either e or d and be reasonably efficient
calculate the other
© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
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
© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
The Security of RSA
Brute force
• Involves
Chosen ciphertext trying all Mathematical attacks
attacks possible • There are several
• This type of attack private keys approaches, all
exploits properties equivalent in effort to
of the RSA factoring the product
algorithm of two primes
Five
possible
approaches
to
Hardware fault-based attacking
attack RSA are: Timing attacks
• This involves inducing • These depend on the
hardware faults in the running time of the
processor that is decryption
generating digital algorithm
signatures
© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
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)
© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
Summary
• Present an overview
of the basic principles • Present an overview of
of public-key the RSA algorithm
cryptosystems
• Summarize the
• Explain the two relevant issues related
distinct uses of public- to the complexity of
key cryptosystems algorithms
• List and explain the
requirements for a
public-key
cryptosystem
© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
