1

CSIT 561 – COMPUTER SECURITY

MODULE 4 : CRYPTOGRAPHY

Bharath K. Samanthula
Department of Computer Science
Montclair State University

Slides are adopted from Chapter 12, Security in Computing, Fifth Edition, by Charles P. Pfleeger, et al. (ISBN: 9780134085043)..
 2

Objectives
• Learn basic terms and primitives of cryptography
• Deep dive into how symmetric encryption algorithms work
• Study the RSA asymmetric encryption algorithm
• Compare message digest algorithms
• Explain the math behind digital signature

From Security in Computing, Fifth Edition, by Charles P. Pfleeger, et al. (ISBN: 9780134085043). Copyright 2015 by Pearson Education, Inc. All rights reserved.
 3

Methods of Cryptanalysis
• Break (decrypt) a single message
• Recognize patterns in encrypted messages
• Infer some meaning without even breaking the encryption,
such as from the length or frequency of messages
• Easily deduce the key to break one message and perhaps
subsequent ones
• Find weaknesses in the implementation or environment of
use of encryption by the sender
• Find general weaknesses in an encryption algorithm

From Security in Computing, Fifth Edition, by Charles P. Pfleeger, et al. (ISBN: 9780134085043). Copyright 2015 by Pearson Education, Inc. All rights reserved.
 4

Cryptographic Primitives

• Confusion
• An algorithm providing good confusion has a complex functional
relationship between the plaintext/key pair and the ciphertext, so
that changing one character in the plaintext causes unpredictable
changes to the resulting ciphertext
• Achieved by Substitution - One set of bits is exchanged for another

• Diffusion
• Distributes the information from single plaintext characters over the
entire ciphertext output, so that even small changes to the plaintext
result in broad changes to the ciphertext
• Achieved by Transposition - Rearranging the order of the ciphertext
to break any repeating patterns in the underlying plaintext

From Security in Computing, Fifth Edition, by Charles P. Pfleeger, et al. (ISBN: 9780134085043). Copyright 2015 by Pearson Education, Inc. All rights reserved.
 5

One-Time Pads
• A one-time pad is often used as an example of the perfect
cipher, but it is only useful as a concept, as it is
completely impractical.
• A one-time pad is a substitution cipher that uses an
arbitrarily large, nonrepeating set of keys for substitution
(in the diagram of the Vernam cipher, XOR is used
instead of pure substitution), and requires both an
unlimited set of completely random keys and absolute
synchronization between sender and receiver, both of
which are impractical.
• In terms of resistance to cryptanalysis, the one-time pad is
the gold standard against which other encryption
algorithms are measured, as it offers no patterns for
attackers to analyze.
From Security in Computing, Fifth Edition, by Charles P. Pfleeger, et al. (ISBN: 9780134085043). Copyright 2015 by Pearson Education, Inc. All rights reserved.
 6

One-Time Pads

Long
nonrepeating
series of
numbers

Exclusive Exclusive
OR or other OR or other Original
Plaintext Ciphertext
combining combining Plaintext
function function

This is a diagram of the Vernam cipher, a type of one-time pad

From Security in Computing, Fifth Edition, by Charles P. Pfleeger, et al. (ISBN: 9780134085043). Copyright 2015 by Pearson Education, Inc. All rights reserved.
 7

Shannon’s Characteristics of Good

Ciphers
1. The amount of secrecy needed should determine the
amount of labor appropriate for the encryption and
decryption
2. The set of keys and the enciphering algorithm should be
free from complexity
3. The implementation of the process should be as simple
as possible
4. Errors in ciphering should not propagate and cause
corruption of further information in the message
5. The size of the enciphered text should be no larger than
the text of the original message

From Security in Computing, Fifth Edition, by Charles P. Pfleeger, et al. (ISBN: 9780134085043). Copyright 2015 by Pearson Education, Inc. All rights reserved.
 8

Properties of a Trustworthy Cryptosystem

• It is based on sound mathematics
• It has been analyzed by competent experts and
found to be sound
• It has stood the test of time

Because cryptographic algorithms are complex, it

can take years of analysis before serious flaws are
identified.

From Security in Computing, Fifth Edition, by Charles P. Pfleeger, et al. (ISBN: 9780134085043). Copyright 2015 by Pearson Education, Inc. All rights reserved.
 9

DES Algorithm
• DES is no longer practical for use against modern
technology, the algorithm has a combination of strong
fundamentals and relative simplicity
• The data bits are permuted by an “initial permutation” (not shown)
• The key is reduced from 64 bits to 56 bits (parity bits are removed) (not shown)
• The 64 permuted data bits are broken into a left half and right half
• The 32-bit right half is expanded to 48 bits by repeating certain bits
• The key is reduced to 48 bits by choosing only certain bits according to tables called S-
boxes (S-boxes are not shown for simplicity)
• The key is shifted left by a number of bits and also permuted
• The key is combined with the right half, which is then combined with the left half
• The result of these combinations becomes the new right half, while the old right half
becomes the new left half

From Security in Computing, Fifth Edition, by Charles P. Pfleeger, et al. (ISBN: 9780134085043). Copyright 2015 by Pearson Education, Inc. All rights reserved.
 10

DES Algorithm
Left Data Half Right Data Half
Key Shifted
32 bits 32 bits 56 bits

Expansion
Permutation
48 bits
Key
Permuted
48 bits

Substitution,
Permuted Choice
32 bits

Permutation

New Left Data Half

New Right Data Half
(Old Right Half)

From Security in Computing, Fifth Edition, by Charles P. Pfleeger, et al. (ISBN: 9780134085043). Copyright 2015 by Pearson Education, Inc. All rights reserved.
 11

DES Algorithm (cont.)

Input

Initial Permutation

L0 R0
Key Shifted

Substitution Key Permuted

Permutation

Cycle 1

L1 = R 0 R1
Key Shifted

Substitution Key Permuted

Permutation
Cycle 2

L2 = R 1 R2
... ...
L15 = R 14 R 15
Key Shifted

Substitution Key Permuted

Permutation
Cycle 16

L16 = R 15 R 16

Inverse Initial Permutation

Output

From Security in Computing, Fifth Edition, by Charles P. Pfleeger, et al. (ISBN: 9780134085043). Copyright 2015 by Pearson Education, Inc. All rights reserved.
 12

DES Algorithm (cont.)

Input

Initial Permutation

L0 R0
Key Shifted

Substitution Key Permuted

Permutation

Cycle 1

L1 = R 0 R1
Key Shifted

From Security in Computing, Fifth Edition, by Charles P. Pfleeger, et al. (ISBN: 9780134085043). Copyright 2015 by Pearson Education, Inc. All rights reserved.
 13

Chaining
• DES uses the same process for each 64-bit block, so two
identical blocks encrypted with the same key will have
identical output
• This provides too much information to an attacker, as
messages that have common beginnings or endings, for
example, are very common in real life, as is reuse of a
single key over a series of transactions
• The solution to this problem is chaining, which makes the
encryption of each block dependent on the content of the
previous block as well as its own content

From Security in Computing, Fifth Edition, by Charles P. Pfleeger, et al. (ISBN: 9780134085043). Copyright 2015 by Pearson Education, Inc. All rights reserved.
 14

AES
• AES is much more complex than DES, and we will not explain it in detail
here. The goal of this chapter is to provide a high-level understanding of
how and why these algorithms work. For a detailed understanding, a full
course dedicated to cryptography is appropriate.
• The algorithm consists of 10, 12, or 14 cycles, for a 128-, 192-, or 256-bit
key, respectively. Each cycle consists of four steps:
1. Byte substitution. This step substitutes each byte of a 128-bit block
according to a substitution table. This is a straight diffusion operation.
2. Shift row. Certain bits are shifted to other positions. This is a straight
confusion operation.
3. Mix column. This step involves shifting left and XORing bits with
themselves. These operations deliver both confusion and diffusion.
4. Add subkey. Here, a portion of the key unique to this cycle is XORed with
the cycle result. This operation delivers confusion and incorporates the
key.

Each cycle performs both confusion and diffusion as well as blends the key
into the result.

From Security in Computing, Fifth Edition, by Charles P. Pfleeger, et al. (ISBN: 9780134085043). Copyright 2015 by Pearson Education, Inc. All rights reserved.
 15

Structure of AES
1. Byte Sub 2. Shift Row 3. Mix Columns

S
input
S

k k k k 4. Add Round Key

next cycle output

From Security in Computing, Fifth Edition, by Charles P. Pfleeger, et al. (ISBN: 9780134085043). Copyright 2015 by Pearson Education, Inc. All rights reserved.
 16

Longevity of AES
• Since its initial publication in 1997, AES has been
extensively analyzed, and the only serious challenges to
its security have been highly specialized and theoretical
• Because there is an evident underlying structure to AES,
it will be possible to use the same general approach on a
slightly different underlying problem to accommodate keys
larger than 256 bits when necessary
• No attack to date has raised serious question as to the
overall strength of AES

From Security in Computing, Fifth Edition, by Charles P. Pfleeger, et al. (ISBN: 9780134085043). Copyright 2015 by Pearson Education, Inc. All rights reserved.
 17

Asymmetric Encryption with RSA

• Since its introduction in 1978, RSA has been the subject
of extensive cryptanalysis, and no serious flaws have yet
been found
• The encryption algorithm is based on the underlying
problem of factoring large prime numbers, a problem for
which the fastest known algorithm is exponential in time
• Two keys, d and e, are used for decryption and encryption
(they are interchangeable)
• The plaintext block P is encrypted as Pe mod n
• The decrypting key d is chosen so that (Pe)d mod n = P

From Security in Computing, Fifth Edition, by Charles P. Pfleeger, et al. (ISBN: 9780134085043). Copyright 2015 by Pearson Education, Inc. All rights reserved.
 18

Detailed Description of RSA

From Security in Computing, Fifth Edition, by Charles P. Pfleeger, et al. (ISBN: 9780134085043). Copyright 2015 by Pearson Education, Inc. All rights reserved.
 19

Deriving an RSA Key Pair

• The encryption key consists of the pair of integers (e, n), and the
decryption key is (d, n)
• The value of n should be quite large, a product of two primes, p and q
• Typically, p and q are nearly 100 digits each, so n is approximately 200
decimal digits (about 512 bits) long
• A large value of n effectively inhibits factoring n to infer p and q (but time
to encrypt increases as the value of n grows larger)
• A relatively large integer e is chosen so that e is relatively prime to (p − 1)
* (q − 1). An easy way to guarantee that e is relatively prime to (p − 1) *
(q − 1) is to choose e as a prime that is larger than both (p − 1) and (q −
1)
• Finally, select d such that e * d = 1 mod (p − 1) * (q − 1)

Observation: These days, 2048-bit keys are increasingly becoming a

standard requirement (thanks to increased computing power). The user of
RSA distributes the value of e and n and keeps d secret.

From Security in Computing, Fifth Edition, by Charles P. Pfleeger, et al. (ISBN: 9780134085043). Copyright 2015 by Pearson Education, Inc. All rights reserved.
 20

Message Digests
• Previously introduced in Chapter 2, message digests are
ways to detect changes to a block of data
• One-way hash functions are cryptographic functions with
multiple uses:
• They are used in conjunction with public-key algorithms for both
encryption and digital signatures
• They are used in integrity checking
• They are used in authentication
• They are used in communications protocols
• Modern hash functions meet two criteria:
• They are one-way, meaning they convert input to a digest, but it is
infeasible to start with a digest value and infer the input
• They do not have obvious collisions, meaning that it is infeasible to
find a pair of inputs that produce the same digest

From Security in Computing, Fifth Edition, by Charles P. Pfleeger, et al. (ISBN: 9780134085043). Copyright 2015 by Pearson Education, Inc. All rights reserved.
 21

Properties of Current Hash Standards

In practice, for security purposes, MD5 and SHA-1 are too weak for modern use.
SHA-3 has much better processing performance than its predecessors, but it is
relatively new and has not yet stood the test of time (nor have its implementations).
From Security in Computing, Fifth Edition, by Charles P. Pfleeger, et al. (ISBN: 9780134085043). Copyright 2015 by Pearson Education, Inc. All rights reserved.
 22

Digital Signatures
• As we initially saw in Chapter 2, digital signatures must
meet two requirements and, ideally, satisfy two more:
• Unforgeable (mandatory): No one other than the signer can
produce the signature without the signer’s private key
• Authentic (mandatory): The receiver can determine that the
signature really came from the signer
• Not alterable (desirable): No signer, receiver, or any interceptor can
modify the signature without the tampering being evident
• Not reusable (desirable): Any attempt to reuse a previous signature
will be detected by receiver
• The general way of computing digital signatures is with
public key encryption:
• The signer computes a signature value by using a private key
• Others can use the public key to verify that the signature came
from the corresponding private key
From Security in Computing, Fifth Edition, by Charles P. Pfleeger, et al. (ISBN: 9780134085043). Copyright 2015 by Pearson Education, Inc. All rights reserved.
 23

Summary
• Substitution, transposition, confusion, and diffusion are the
basic primitives of cryptography
• DES is a relatively simple symmetric algorithm that, although
no longer practical, is useful for studying technique
• Chaining and random initialization vectors are important
techniques for preventing ciphertext repetition
• AES remains the modern standard for symmetric encryption
almost 20 years after its introduction
• RSA is a popular and deceptively simple algorithm for
asymmetric cryptography
• Message digests use one-way cryptographic hash functions to
detect message modification
• Digital signatures use asymmetric encryption to detect forged
messages
From Security in Computing, Fifth Edition, by Charles P. Pfleeger, et al. (ISBN: 9780134085043). Copyright 2015 by Pearson Education, Inc. All rights reserved.