Chapter 30

Cryptography

30.1 Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
 30--1 INTRODUCTION
30

Let us introduce the issues involved in cryptography.

cryptography.
First, we need to define some terms
terms;; then we give some
taxonomies..
taxonomies

Topics discussed in this section:

Definitions
Two Categories

30.2
 Figure 30.1 Cryptography components

30.3
 Figure 30.2 Categories of cryptography

30.4
 Figure 30.3 Symmetric-key cryptography

30.5
 Note

In symmetric-key cryptography, the

same key
k iis used d by
b the
th sender
d
(for encryption)
and the receiver (for decryption).
The key is shared.

30.6
 Figure 30.4 Asymmetric-key cryptography

30.7
 Figure 30.5 Keys used in cryptography

30.8
 Figure 30.6 Comparison between two categories of cryptography

30.9
 30--2 SYMMETRIC
30 SYMMETRIC--KEY CRYPTOGRAPHY

Symmetric-key cryptography started thousands of years

Symmetric-
ago when people needed to exchange secrets (for
example in a war)
example, war).. We still mainly use symmetric
symmetric--key
cryptography in our network security
security..

Topics discussed in this section:

Traditional Ciphers
Simple Modern Ciphers
Modern Round Ciphers
Mode of Operation

30.10
 Figure 30.7 Traditional ciphers

30.11
 Note

A substitution cipher replaces one

symbol
b l with
ith another.
th

30.12
 Example 30.1

The following shows a plaintext and its corresponding

ciphertext. Is the cipher monoalphabetic?

Solution
The cipher is probably monoalphabetic because both
occurrences of L’s are encrypted as O’s.

30.13
 Example 30.2

The following shows a plaintext and its corresponding

ciphertext. Is the cipher monoalphabetic?

Solution
The cipher is not monoalphabetic because each
occurrence of L is encrypted by a different character.
character
The first L is encrypted as N; the second as Z.

30.14
 Note

The shift cipher is sometimes referred to

as the
th Caesar
C cipher.
i h

30.15
 Example 30.3

Use the shift cipher with key = 15 to encrypt the message

“HELLO.”

Solution
We encrypt one character at a time. Each character is
shifted 15 characters down.
down Letter H is encrypted to W. W
Letter E is encrypted to T. The first L is encrypted to A.
The second L is also encrypted to A.
A And O is encrypted to
D. The cipher text is WTAAD.

30.16
 Example 30.4

Use the shift cipher with key = 15 to decrypt the message

“WTAAD.”

Solution
We decrypt one character at a time. Each character is
shifted 15 characters up.
up Letter W is decrypted to H. H
Letter T is decrypted to E. The first A is decrypted to L.
The second A is decrypted to L. L And,
And finally,
finally D is
decrypted to O. The plaintext is HELLO.

30.17
 Note

A transposition cipher reorders

(
(permutes)
t ) symbols
b l in
i a block
bl k off
symbols.

30.18
 Figure 30.8 Transposition cipher

30.19
 Example 30.5

Encrypt the message “HELLO MY DEAR,” using the key

shown in Figure 30.8.

Solution
We first remove the spaces in the message. We then divide
the text into blocks of four characters.
characters We add a bogus
character Z at the end of the third block. The result is
HELL OMYD EARZ. EARZ We create a three
three-block
block ciphertext
ELHLMDOYAZER.

30.20
 Example 30.6

Using Example 30.5, decrypt the message

“ELHLMDOYAZER”.

Solution
The result is HELL OMYD EARZ. After removing the
bogus character and combining the characters
characters, we get the
original message “HELLO MY DEAR.”

30.21
 Figure 30.9 XOR cipher

30.22
 Figure 30.10 Rotation cipher

30.23
 Figure 30.11 S-box

30.24
 Figure 30.12 P-boxes: straight, expansion, and compression

30.25
 Figure 30.13 DES

30.26
 Figure 30.14 One round in DES ciphers

30.27
 Figure 30.15 DES function

30.28
 Figure 30.16 Triple DES

30.29
 Table 30.1 AES configuration

30.30
 Note

AES has three different configurations

with
ith respectt to
t the
th number
b off rounds
d
and key size.

30.31
 Figure 30.17 AES

30.32
 Figure 30.18 Structure of each round

30.33
 Figure 30.19 Modes of operation for block ciphers

30.34
 Figure 30.20 ECB mode

30.35
 Figure 30.21 CBC mode

30.36
 Figure 30.22 CFB mode

30.37
 Figure 30.23 OFB mode

30.38
 30--3 ASYMMETRIC
30 ASYMMETRIC--KEY CRYPTOGRAPHY

An asymmetric
asymmetric--key (or public
public--key) cipher uses two
keys:: one private and one public
keys public.. We discuss two
algorithms:: RSA and Diffie
algorithms Diffie--Hellman
Hellman..

Topics discussed in this section:

RSA
Diffie-Hellman

30.39
 Figure 30.24 RSA

30.40
 Note

In RSA, e and n are announced to the

public;
bli d and d Φ are kept
k t secret.
t

30.41
 Example 30.7

Bob chooses 7 and 11 as p and q and calculates

n = 7 · 11 = 77. The value of Φ = (7 − 1) (11 − 1) or 60.
Now he chooses two keys, e and d. If he chooses e to be
13, then
h d isi 37. Now imagine
i i Alice
Ali sendsd the
h plaintext
l i 5
to Bob. She uses the public key 13 to encrypt 5.

30.42
 Example 30.7 (continued)

Bob receives the ciphertext 26 and uses the private key 37

to decipher the ciphertext:

The plaintext 5 sent by Alice is received as plaintext 5 by

B b
Bob.

30.43
 Example 30.8

Jennifer creates a pair of keys for herself. She chooses

p = 397 and q = 401. She calculates n = 159,197 and
Φ = 396 · 400 = 158,400. She then chooses e = 343 and
d = 12,007. Show
Sh howh Tedd can sendd a message to Jennifer
if
if he knows e and n.

30.44
 Example 30.8 (continuted)

Solution
Suppose Ted wants to send the message “NO” to Jennifer.
He changes each character to a number (from 00 to 25)
with
i h eachh character
h coded
d d as two digits.
di i He then
h
concatenates the two coded characters and gets a four-
di i number.
digit b The h plaintext
l i i 1314.
is 1314 Tedd then
h uses e andd n
to encrypt the message. The ciphertext is 1314343 = 33,677
mod d 159,197.
159 197 Jennifer
J if receives
i the
h message 33,677
33 677 andd
uses the decryption key d to decipher it as 33,67712,007 =
1314 modd 159,197.
159 197 Jennifer
J if then
h decodes
d d 1314 as the h
message “NO”. Figure 30.25 shows the process.

30.45
 Figure 30.25 Example 30.8

30.46
 Example 30.9

Let us give a realistic example. We randomly chose an

integer of 512 bits.
bits The integer p is a 159-digit number.
number

The integer
g q is a 160-digit
g number.

30.47
 Example 30.9 (continued)

We calculate n. It has 309 digits:

We calculate Φ. It has 309 digits:

30.48
 Example 30.9 (continued)

We choose e = 35,535. We then find d.

Alice wants to send the message “THIS IS A TEST”

which
hi h can be
b changed
h d to
t a numeric i value
l by
b using
i the
th
00–26 encoding scheme (26 is the space character).

30.49
 Example 30.9 (continued)

The ciphertext calculated by Alice is C = Pe, which is.

Bob can recover the plaintext from the ciphertext by

i P = Cd, which
using hi h is
i

The recovered plaintext is THIS IS A TEST after

d di
decoding.
30.50
 Note

The symmetric (shared) key in the

Diffi H ll
Diffie-Hellman protocol
t l is
i
K = gxy mod p.

30.51
 Example 30.10

Let us give a trivial example to make the procedure clear.

Our example uses small numbers, but note that in a real
situation, the numbers are very large. Assume g = 7 and
p = 23. The
h steps are as ffollows:
ll
1. Alice chooses x = 3 and calculates R1 = 73 mod 23 = 21.
2 Bobb chooses
2. h y = 6 andd calculates
l l R2 = 76 modd 23 = 4.
4
3. Alice sends the number 21 to Bob.
4 Bob
4. B b sendsd the
h number b 4 to Alice.
Ali
5. Alice calculates the symmetric key K = 43 mod 23 = 18.
6 Bob
6. B b calculates
l l the
h symmetric k K = 216 modd 23 = 18.
i key 18
The value of K is the same for both Alice and Bob;
gxy modd p = 718 modd 23 = 18.
18
30.52
 Figure 30.27 Diffie-Hellman idea

30.53
 Figure 30.28 Man-in-the-middle attack

30.54