CS480
Cryptography and Information Security
4. Traditional and Modern Symmetric
Key Ciphers
Huiping Guo
Department of Computer Science
California State University, Los Angeles
Outline
Symmetric key ciphers
Substitution and transposition ciphers
Stream ciphers and block ciphers
Modern block ciphers
4. Traditional ciphers
CS480_W16
4-2
Symmetric Cipher
4. Traditional ciphers
CS480_W16
4-3
Symmetric Cipher (cont.)
If P is the plaintext, C is the ciphertext, and K is the key
We assume that Bob creates P1; we prove that P1 = P:
4. Traditional ciphers
CS480_W16
4-4
Symmetric Cipher (cont.)
Figure 3.2 Locking and unlocking with the same key
4. Traditional ciphers
CS480_W16
4-5
Kerckhoffs Principle
Based on Kerckhoffs principle, one should
always assume that the adversary, Eve, knows
the encryption/decryption algorithm. The
resistance of the cipher to attack must be based
only on the secrecy of the key.
4. Traditional ciphers
CS480_W16
4-6
Categories of traditional ciphers
Substitution ciphers
Replace one symbol with another symbol
Transposition ciphers
Reorder the position of symbols in the plaintext
4. Traditional ciphers
CS480_W16
4-7
Substitution cipher
A substitution cipher replaces one symbol
with another
Monoalphabetic Ciphers
Polyalphabetic Ciphers
4. Traditional ciphers
CS480_W16
4-8
Monoalphabetic Ciphers
A character in the plaintext is always changed to
the same character in the ciphertext regardless of
its position in the text
the relationship between a symbol in the plaintext
to a symbol in the ciphertext is always one-to-one
categories
Additive cipher
Muliplicative cipher
Affine cipher
Mononalphabetic substitution cipher
4. Traditional ciphers
CS480_W16
4-9
Monoalphabetic Ciphers
Example:
The following shows a plaintext and its corresponding
ciphertext. The cipher is probably monoalphabetic
because both ls (els) are encrypted as Os.
4. Traditional ciphers
CS480_W16
4-10
Additive Cipher
The simplest monoalphabetic cipher is the additive
cipher. This cipher is sometimes called a shift cipher and
sometimes a Caesar cipher, but the term additive cipher
better reveals its mathematical nature.
4. Traditional ciphers
CS480_W16
4-11
Additive Cipher
When the cipher is additive, the plaintext,
ciphertext, and key are integers in Z26
4. Traditional ciphers
CS480_W16
4-12
Additive Cipher
Use the additive cipher with key = 15 to encrypt the message
hello.
Solution
We apply the encryption algorithm to the plaintext, character
by character:
4. Traditional ciphers
CS480_W16
4-13
Additive Cipher
Use the additive cipher with key = 15 to decrypt the
message WTAAD.
Solution
We apply the decryption algorithm to the plaintext
character by character:
4. Traditional ciphers
CS480_W16
4-14
Additive Cipher
Eve has intercepted the ciphertext UVACLYFZLJBYL. Show
how she can use a brute-force attack to break the cipher.
Solution
Eve tries keys from 1 to 7. With a key of 7, the plaintext is not very
secure, which makes sense.
4. Traditional ciphers
CS480_W16
4-15
Multiplicative Ciphers
The plaintext and ciphertext are integers in Z 26
The key is an integer in Z26*
4. Traditional ciphers
CS480_W16
4-16
Multiplicative Ciphers
What is the key domain for the multiplicative cipher?
The key needs to be in Z26*. This set has only 12 members: 1, 3, 5, 7,
9, 11, 15, 17, 19, 21, 23, 25.
We use a multiplicative cipher to encrypt the message hello with
a key of 7. The ciphertext is XCZZU.
4. Traditional ciphers
CS480_W16
4-17
Affine ciphers
4. Traditional ciphers
CS480_W16
4-18
Affine ciphers
The affine cipher uses a pair of keys in which the first key is
from Z26* and the second is from Z26. The size of the key
domain is 26 12 = 312.
Use an affine cipher to encrypt the message hello with the
key pair (7, 2).
4. Traditional ciphers
CS480_W16
4-19
Affine ciphers
Use the affine cipher to decrypt the message ZEBBW with
the key pair (7, 2) in modulus 26.
Solution
4. Traditional ciphers
CS480_W16
4-20
Monoalphabetic Substitution
Cipher
Because additive, multiplicative, and affine
ciphers have small key domains, they are very
vulnerable to brute-force attack
Brute-force attack: an attacker tries all possible keys
to find the correct one.
A better solution is to create a mapping between
each plaintext character and the corresponding
ciphertext character
Alice and Bob can agree on a table showing the mapping
for each character.
4. Traditional ciphers
CS480_W16
4-21
Monoalphabetic Substitution
Cipher
Figure 3.12 An example key for monoalphabetic substitution cipher
We can use the key in Figure 3.12 to encrypt the message
The ciphertext is
4. Traditional ciphers
CS480_W16
4-22
Monoalphabetic Substitution
Cipher Security
now have a total of 26! keys
with so many keys, might think is secure
but would be !!!WRONG!!!
problem is language characteristics
4. Traditional ciphers
CS480_W16
4-23
Statistics attacks
Human languages are redundant
Letters are not equally commonly used
In English E is by far the most common letter
followed by T,R,N,I,O,A,S
Other letters like Z,J,K,Q,X are fairly rare
Attackers can make use of the statistic
information to launch attacks
4. Traditional ciphers
CS480_W16
4-24
English Letter Frequencies
4. Traditional ciphers
CS480_W16
4-25
Statistics attacks
Eve has intercepted the following ciphertext. Using a statistical
attack, find the plaintext.
Solution
When Eve tabulates the frequency of letters in this ciphertext, she gets:
I =14, V =13, S =12, and so on. The most common character is I with 14
occurrences.
4. Traditional ciphers
CS480_W16
4-26
Polyalphabetic Ciphers
Each occurrence of a character may have a
different substitute
The relationship between a character in the
plaintext to a character in the ciphertext is oneto-many
4. Traditional ciphers
CS480_W16
4-27
Polyalphabetic Ciphers
AutoKey cipher
Playfair cipher
4. Traditional ciphers
CS480_W16
4-28
AutoKey cipher
Key is concatenated with the plaintext itself to
provide a running key
knowing keyword can recover the first few
letters
use these in turn on the rest of the message
4. Traditional ciphers
CS480_W16
4-29
AutoKey cipher
Assume that Alice and Bob agreed to use an
autokey cipher with initial key value k1 = 12.
Now Alice wants to send Bob the message Attack
is today
Enciphering is done character by character.
4. Traditional ciphers
CS480_W16
4-30
Playfair Key Matrix
a 5X5 matrix of letters based on a keyword
fill in letters of keyword (minus duplicates)
fill rest of matrix with other letters in
alphabetical order
eg. using the keyword MONARCHY
M
I/J
4. Traditional ciphers
CS480_W16
4-31
Encrypting and Decrypting
plaintext is encrypted two letters at a time
if a pair is a repeated letter, insert filler like 'X
e.g balloon is treated as ba lx lo on
if both letters fall in the same row, replace each with letter
to right
(wrapping back to start from end)
e.g ar is encrypted as RM
if both letters fall in the same column, replace each with the
letter below it (again wrapping to top from bottom)
e.g mu is encrypted as CM
otherwise each letter is replaced by the letter in the same
row and in the column of the other letter of the pair
e.g hs is encrytped as BP, ea is encrypted as IM(or JM)
4. Traditional ciphers
CS480_W16
4-32
In class exercise
Encrypt the plaintext hello using the key in the
above Figure
4. Traditional ciphers
CS480_W16
4-33
One-Time Pad
if a truly random key as long as the message is used, the
cipher will be secure
called a One-Time pad
is unbreakable since ciphertext bears no statistical
relationship to the plaintext
since for any plaintext & any ciphertext there exists a key
mapping one to other
can only use the key once though
problems in generation & safe distribution of key
4. Traditional ciphers
CS480_W16
4-34
Transposition cipher
A transposition cipher does not substitute one
symbol for another
Instead it changes the location of the symbols
Reorder the symbols
Category
Keyless Transposition Ciphers
Keyed Transposition Cipher
Combining Two Approaches
4. Traditional ciphers
CS480_W16
4-35
Keyless Transposition Ciphers
There are two methods:
1. The text is written into a table column by column
and then transmitted into the table row by row
2. The text is written into the table row by row and
then transmitted column by column
4. Traditional ciphers
CS480_W16
4-36
Rail fence cipher
The plaintext is arranged in two lines as a zigzag pattern
(column by column)
Then read off cipher row by row
For example, to send the message
Meet me at the park to Bob
Alice writes:
She then creates the ciphertext MEMATEAKETETHPR
4. Traditional ciphers
CS480_W16
4-37
Rail fence cipher
Alice and Bob can also agree on the number of
columns and. Alice writes the same plaintext, row
by row, in a table of four columns.
She then creates the ciphertext MMTAEEHREAEKTTP.
4. Traditional ciphers
CS480_W16
4-38
Keyed Transposition Ciphers
The keyless ciphers permute the characters by
writing plaintext in one way and reading it in
another way
The permutation is done on the whole plaintext to create
the whole ciphertext
Keyed transposition cipher
Divide the plaintext into groups of predetermined size,
called blocks
and then use a key to permute the characters in each
block separately
4. Traditional ciphers
CS480_W16
4-39
Keyed Transposition Ciphers
Alice needs to send the message Enemy attacks tonight to Bob..
The key used for encryption and decryption is a permutation key,
which shows how the character are permuted.
The permutation yields
4. Traditional ciphers
CS480_W16
4-40
Combining two approaches
4. Traditional ciphers
CS480_W16
4-41
Stream cipher
Call the plaintext stream P, the ciphertext stream C, and the
key stream K
4. Traditional ciphers
CS480_W16
4-42
Stream cipher
Additive ciphers can be categorized as stream
ciphers
The key stream is the repeated value of the key
In other words, the key stream is considered as a
predetermined stream of keys or
K = (k, k, , k)
In this cipher, however, each character in the
ciphertext depends only on the corresponding
character in the plaintext
because the key stream is generated independently.
4. Traditional ciphers
CS480_W16
4-43
Stream cipher
The monoalphabetic substitution ciphers are also
stream ciphers
However, each value of the key stream in this case
is the mapping of the current plaintext character
to the corresponding ciphertext character in the
mapping table.
4. Traditional ciphers
CS480_W16
4-44
Block cipher
In a block cipher, a group of plaintext symbols of
size m (m > 1) are encrypted together creating a
group of ciphertext of the same size.
A single key is used to encrypt the whole block
even if the key is made of multiple values.
4. Traditional ciphers
CS480_W16
4-45
Block cipher
Playfair ciphers are block ciphers. The size of the
block is m = 2. Two characters are encrypted
together
From the definition of the block cipher, it is clear
that every block cipher is a polyalphabetic cipher
because each character in a ciphertext block
depends on all characters in the plaintext block.
4. Traditional ciphers
CS480_W16
4-46
Modern block cipher
A symmetric-key modern block cipher encrypts an n-bit block of
plaintext or decrypts an n-bit block of ciphertext
The encryption or decryption algorithm uses a k-bit key
The decryption algorithm must be the inverse of the encryption
algorithm
4. Traditional ciphers
CS480_W16
4-47
Modern block cipher
If the message has fewer than n bits, padding
must be added to make it an n-bit block
If the message has more than n bits, it should be
divided into n bit blocks and the appropriate
padding must be added to the last block if
necessary
4. Traditional ciphers
CS480_W16
4-48
Example
How many padding bits must be added to a message of 100
characters if 8-bit ASCII is used for encoding and the block
cipher accepts blocks of 64 bits?
Solution
Encoding 100 characters using 8-bit ASCII results in an 800bit message. The plaintext must be divisible by 64. If | M | and
|Pad| are the length of the message and the length of the
padding,
4. Traditional ciphers
CS480_W16
4-49
