Applied Cryptography

CY363IA
 Unit -1
Introduction to Number Theory
Traditional Symmetric-Key Ciphers
 Unit 1 CONTENTS

• Divisibility and the Division Algorithm

• The Euclidean Algorithm
• Modular Arithmetic, Prime Numbers, Fermat’s and Euler’s Theorems,
Testing for Primality, The Chinese Remainder Theorem
• Traditional Symmetric-Key Ciphers: Substitution ciphers:
Monoalphabetic ciphers, Polyalphabetic ciphers, Transposition ciphers.
Stream Ciphers and Block Ciphers: Stream Ciphers, Block Ciphers.
 Divisors

● A non-zero Number b divides a if for some m have a=mb (a,b,m all integers)
i.e b divides into a with no remainder and is denoted as b | a and is said b is a
divisor of a.

● Ex: 1,2,3,4,6,8,12,24 divide 24

● 13 | 182, -5 | 30, 17 | 289, -3|33, 17 | 0

 Properties of Divisibility
● If a | 1, then a= ± 1
● If a | b and b | a, then a= ±b
● Any b≠0 divides 0
● If a | b and b | c then a | c. Ex: 11 | 66 and 66 |198 = 11 | 198
● If b | g and b | h then b | (mg+nh) For arbitrary integers m and n, note that
• If b | g, then g is of the form g = b * g1 for some integer g1
• If b | h, then h is of the form h = b * h1 for some integer h1
So mg + nh = mbg1 + nbh1 = b * (mg1 + nh1)
● and therefore b divides mg + nh.
○ Ex: b=7; g=14; h=63; m=3; n=2
■ Hence 7|14 and 7| 63
 The Division Algorithm
● Given any positive integer n and any nonnegative integer a, if we divide a by n,
we get an integer quotient q and an integer remainder r that obey the following
relationship:
a = qn + r 0<=r<n; q= floor(a/n) (4.1)
● Equation (4.1) is referred to as the division algorithm.
● Figure 4.1a demonstrates that, given a and positive n, it is always possible to
find q and r that satisfy the preceding relationship.
● Represent the integers on the number line; a will fall somewhere on that line
Starting at 0, proceed to n, 2n, up to qn, such that qn <= a and (q + 1)n > a.
● The distance from qn to a is r, and we have found the unique values of q and r.
The remainder r is often referred to as a residue.
The Division Algorithm
 The Euclidean Algorithm

● One of the basic techniques of number theory is the Euclidean algorithm, which is a simple
procedure for determining the GCD of two positive integers. 2 integers are relatively prime if
their only common positive integer factor is 1.
● Greatest Common Divisor
● Non zero b is defined to be a divisor of a if a = mb for some m, where a, b, and m are integers.
● The greatest common divisor of a and b is the largest integer that divides both a and b. Also
gcd(0, 0) = 0.
● More formally, the positive integer c is said to be the greatest common divisor of a and b if
1. c is a divisor of a and of b.
2. Any divisor of a and b is a divisor of c.
● An equivalent definition is the following:
● gcd(a, b) = max[k, such that k | a and k | b]
● Because we require that the greatest common divisor be positive, gcd(a, b) = gcd(a, -b) =
gcd(-a, b) = gcd(-a,-b). In general, gcd(a, b) = gcd( a , b ).
● Also, because all nonzero integers divide 0, we have gcd(a, 0) = a .
● It is stated that two integers a and b are relatively prime if their only common
positive integer factor is 1. This is equivalent to saying that a and b are relatively
prime if gcd(a, b) = 1.
● 8 and 15 are relatively prime because the positive divisors of 8 are 1, 2, 4, and
8, and the positive divisors of 15 are 1, 3, 5, and 15. So 1 is the only integer on
both lists.
 Finding the Greatest Common Divisor
● Euclid for easily finding the greatest common divisor of two integers.
● Suppose we have integers a, b such that d = gcd(a, b).
● Because gcd( | a | , | b | ) = gcd(a, b), there is no harm in assuming a >= b > 0. Now
dividing a by b and applying the division algorithm, we can state:
a = q1b + r1 0 <=r1 < b (4.2)
● If it happens that r1 = 0, then b | a and d = gcd(a, b) = b. But if r1 != 0, we can state
that d | r1. This is due to the basic properties of divisibility: the relations d | a and d | b
together imply that d (a - q1b), which is the same as d | r1.
● Consider 4.2 and assume that r1!= 0. Because b > r1,
● we can divide b by r1and apply the division algorithm to obtain:
b = q2r1 + r2 0 <=r2 < r1
● As before, if r2 = 0, then d = r1 and if r2!=0, then d = gcd(r1, r2). The division
● process continues until some zero remainder appears, say, at the (n + 1)th stage
where rn-1 is divided by rn. The result is the following system of equations:
 Finding the Greatest Common Divisor

● At each iteration, we have d = gcd(ri, ri+1) until finally d = gcd(rn, 0) = rn.

● Thus, GCD of two integers can be found by repetitive application of the
division algorithm. This scheme is known as the Euclidean algorithm.
 Modular Arithmetic
● The Modulus : If a is an integer and n is a positive integer, a mod n is he
remainder. when a is divided by n. The integer n is called the modulus. Thus, for
any integer a, we can rewrite Equation (4.1) as a = qn + r 0<=r<n; q = floor (a/n );
● a = floor (a/n ) * n + (a mod n)
Ex: 11 mod 7 = 4; - 11 mod 7 = 3
● Two integers a and b are said to be congruent modulo n, if (a mod n) = (b mod n).
This is written as a ≡ b (mod n)
● 73 ≡ 4 (mod 23) 21 ≡ -9 (mod 10)
● Note that if a ≡ 0 (mod n), then n | a.
 Properties of Congruences
● Congruences have the following properties:
1. a ≡ b (mod n) if n (a - b).
2. a ≡ b (mod n) implies b ≡ a (mod n).
3. a ≡ b (mod n) and b ≡ c (mod n) imply a ≡ c (mod n).
● To demonstrate the first point, if n (a - b), then (a - b) = kn for some k.
● So we can write a = b + kn. Therefore, (a mod n) = (remainder when b + kn is
divided by n) = (remainder when b is divided by n) = (b mod n).
● 23 ≡ 8 (mod 5) because 23 - 8 = 15 = 5 * 3
● -11 ≡ 5 (mod 8) because -11 - 5 = -16 = 8 * (-2)
● 81 ≡ 0 (mod 27) because 81 - 0 = 81 = 27 * 3
 Modular Arithmetic Operations
● By definition, the (mod n) operator maps all integers into the set of integers {0, 1, c, (n - 1)}.
arithmetic operations within the confines of this set? Yes ; this technique is known as
modular arithmetic.
● Modular arithmetic exhibits the following properties:
1. [(a mod n) + (b mod n)] mod n = (a + b) mod n
2. [(a mod n) - (b mod n)] mod n = (a - b) mod n
3. [(a mod n) * (b mod n)] mod n = (a * b) mod n
1. Define (a mod n) = ra and (b mod n) = rb.
● Then we can write a = ra + jn for some integer j and b = rb + kn for some integer k. Then (a
+ b) mod n = (ra + jn + rb + kn) mod n = (ra + rb + (k + j)n) mod n = (ra + rb) mod n
● = [(a mod n) + (b mod n)] mod n
● The remaining properties are proven as easily.
 Examples of the three properties:
● 11 mod 8 = 3; 15 mod 8 = 7
[(11 mod 8) + (15 mod 8)] mod 8 = 10 mod 8 = 2
(11 + 15) mod 8 = 26 mod 8 = 2
● [(11 mod 8) - (15 mod 8)] mod 8 = -4 mod 8 = 4
(11 - 15) mod 8 = -4 mod 8 = 4
● [(11 mod 8) * (15 mod 8)] mod 8 = 21 mod 8 = 5
(11 * 15) mod 8 = 165 mod 8 = 5
● Exponentiation is performed by repeated multiplication, as in ordinary
arithmetic.
● To find 117 mod 13,
○ 112 = 121 ≡ 4 (mod 13)
○ 114 = (112)2 ≡ 42 ≡ 3 (mod 13)
○ 117 ≡ 11 * 4 * 3 ≡ 132 ≡ 2 (mod 13)
 Modular addition and multiplication modulo 8
● Looking at addition, results are straightforward & there is a
regular pattern to the matrix. Both matrices are symmetric
about the main diagonal in conformance to the commutative
property of addition and multiplication. As in ordinary addition,
there is an additive inverse, or negative, to each integer in
modular arithmetic. In this case, the negative of an integer x is
the integer y such that (x + y) mod 8 = 0. To find the additive
inverse of an integer in the left-hand column, scan across the
corresponding row of the matrix to find the value 0; the integer
at the top of that column is the additive inverse; thus, (2 + 6)
mod 8 = 0.
● Similarly, there is a multiplicative inverse, or reciprocal, to each
integer. In modular arithmetic mod 8, the multiplicative inverse
of x is the integer y such that (x * y) mod 8 = 1 mod 8. Now, to
find the multiplicative inverse of an integer from the
multiplication table, scan across the matrix in the row for that
integer to find the value 1; the integer at the top of that column
is the multiplicative inverse; thus, (3 * 3) mod 8 = 1. Note that
not all integers mod 8 have a multiplicative inverse;
 Properties of Modular Arithmetic
● Define the set Zn as the set of nonnegative integers less than n: Zn = {0, 1, c, (n - 1)}
● This is referred to as the set of residues, or residue classes (mod n).
● To be more precise, each integer in Zn represents a residue class. We can label the residue
classes (mod n) as [0], [1], [2],....., [n - 1], where [r] = {a: a is an integer, a ≡ r (mod n)}
● The residue classes (mod 4) are
[0] = {……, -16, -12, -8, -4, 0, 4, 8, 12, 16, ……}
[1] = {……, -15, -11, -7, -3, 1, 5, 9, 13, 17, ……}
[2] = {……, -14, -10, -6, -2, 2, 6, 10, 14, 18, ……}
[3] = {……, -13, -9, -5, -1, 3, 7, 11, 15, 19, ……}
● Of all the integers in a residue class, the smallest nonnegative integer is the one used to
represent the residue class. Finding the smallest nonnegative integer to which k is
congruent modulo n is called reducing k modulo n.
● If modular arithmetic is performed within Zn, the properties shown in Table 4.3 hold for
integers in Zn.
There is one peculiarity of modular arithmetic that sets it apart from ordinary arithmetic
First, (as in ordinary arithmetic) we can write, if (a + b) K (a + c) (mod n) then b K c (mod n) (4.4)
(5 + 23) ≡ (5 + 7) (mod 8); ≡ 7(mod 8)
Equation (4.4) is consistent with the existence of an additive inverse. Adding the additive inverse of a to both sides
of Equation (4.4),
((-a) + a + b) ≡ ((-a) + a + c) (mod n)
b ≡ c (mod n)
However, the following statement is true only with the attached condition:
if (a * b) ≡ (a * c)(mod n) then b ≡ c (mod n) if a is relatively prime to n (4.5)

Two integers are relatively prime if their only common positive integer factor is 1. Similar to the case of Equation
(4.4), it can be said that Equation (4.5) is consistent with the existence of a multiplicative inverse.
Applying the multiplicative inverse of a to both sides of Equation (4.5),
((a )ab) ≡((a-1)ac) (mod n)
-1

b ≡ c (mod n)
Modular Arithmetic Properties
 Euclidean Algorithm
an efficient way to find the GCD(a,b)
uses theorem that:
● GCD(a,b) = GCD(b, a mod b)
Euclidean Algorithm to compute GCD(a,b) is:
Euclid(a,b)
if (b=0) then return a;
else return Euclid(b, a mod b);
Extended Euclidean Algorithm
calculates not only GCD but x & y:
ax + by = d = gcd(a, b)
useful for later crypto computations
follow sequence of divisions for GCD but
assume at each step i, can find x &y:
r = ax + by
at end find GCD value and also x & y
if GCD(a,b)=1 these values are inverses
 Finding Inverses
EXTENDED EUCLID(m, b)
1. (A1, A2, A3)=(1, 0, m);
(B1, B2, B3)=(0, 1, b)
2. if B3 = 0
return A3 = gcd(m, b); no inverse
3. if B3 = 1
return B3 = gcd(m, b); B2 = b–1 mod m
4. Q = A3 div B3
5. (T1, T2, T3)=(A1 – Q B1, A2 – Q B2, A3 – Q
B3)
6. (A1, A2, A3)=(B1, B2, B3)
7. (B1, B2, B3)=(T1, T2, T3)
8. goto 2
find the multiplicative inverse of 3 mod 5
using Extended Euclid’s Algorithm

Q a b r T1 T2 T

1 5 3 2 0 1 -1

1 3 2 1 1 -1 2

2 2 1 0 -1 2 -5

1 0 2 -5
T=T1-T2*Q
 Prime Numbers
prime numbers only have divisors of 1 and self
● they cannot be written as a product of other numbers
● note: 1 is prime, but is generally not of interest
eg. 2,3,5,7 are prime, 4,6,8,9,10 are not
prime numbers are central to number theory
list of prime number less than 200 is:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101
103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191
193 197 199
 Prime Factorization
to factor a number n is to write it as a product
of other numbers: n=a x b x c
note that factoring a number is relatively hard
compared to multiplying the factors together to
generate the number
Fundamental theorem of arithmetic
the prime factorization of a number n is when
its written as a product of primes
● eg. 91=7x13 ; 3600=24x32x52
 Relatively Prime Numbers &
GCD
two numbers a, b are relatively prime if have no
common divisors apart from 1
● eg. 8 & 15 are relatively prime since factors of 8 are 1,2,4,8
and of 15 are 1,3,5,15 and 1 is the only common factor
conversely can determine the greatest common divisor by
comparing their prime factorizations and using least
powers
● eg. 300=21x31x52 18=21x32 hence
GCD(18,300)=21x31x50=6
 Fermat's Theorem
ap-1 = 1 (mod p)
● where p is prime and gcd(a,p)=1
also known as Fermat’s Little Theorem
also have: ap = a (mod p)
useful in public key and primality testing
Euler Totient Function ø(n)
when doing arithmetic modulo n
complete set of residues is: 0..n-1
reduced set of residues is those numbers
(residues) which are relatively prime to n
● eg for n=10,
● complete set of residues is {0,1,2,3,4,5,6,7,8,9}
● reduced set of residues is {1,3,7,9}
number of elements in reduced set of residues
is called the Euler Totient Function ø(n)
Euler Totient Function ø(n)
to compute ø(n) need to count number of
residues to be excluded
in general need prime factorization, but
● for p (p prime) ø(p)=p-1
● for p.q (p,q prime) ø(p.q)=(p-1)x(q-1)
eg.
ø(37) = 36
ø(21) = (3–1)x(7–1) = 2x6 = 12
 Euler's Theorem
a generalisation of Fermat's Theorem
aø(n) = 1 (mod n)
● for any a,n where gcd(a,n)=1
eg.
a=3;n=10; ø(10)=4;
hence 34 = 81 = 1 mod 10
a=2;n=11; ø(11)=10;
hence 210 = 1024 = 1 mod 11
also have: aø(n)+1 = a (mod n)
 Primality Testing
often need to find large prime numbers
traditionally sieve using trial division
● ie. divide by all numbers (primes) in turn less than
the square root of the number
● only works for small numbers
alternatively can use statistical primality tests
based on properties of primes
● for which all primes numbers satisfy property
● but some composite numbers, called
pseudo-primes, also satisfy the property
can use a slower deterministic primality test
Chinese Remainder Theorem
used to speed up modulo computations
if working modulo a product of numbers
● e.g., mod M, where M = m1m2..mk
Chinese Remainder theorem lets us work
in each modulus mi separately
since computational cost is proportional
to size, this is faster than working in the
full modulus M
Chinese Remainder Theorem
can implement CRT in several ways
to compute A(mod M)
● first compute all ai = A mod mi separately
● determine constants ci below, where Mi = M/mi
● then combine results to get answer using:
 Primitive Roots
from Euler’s theorem have aø(n)mod n=1
consider am=1 (mod n), GCD(a,n)=1
● must exist for m = ø(n) but may be smaller
● once powers reach m, cycle will repeat
if smallest is m = ø(n) then a is called a
primitive root
if p is prime, then successive powers of a
"generate" the group mod p
these are useful but relatively hard to find
Powers mod 19
 3-1 INTRODUCTION

Figure 3.1 shows the general idea behind a symmetric-key cipher.

The original message from Alice to Bob is called plaintext; the
message that is sent through the channel is called the ciphertext.
To create the ciphertext from the plaintext, Alice uses an encryption
algorithm and a shared secret key. To create the plaintext from
ciphertext, Bob uses a decryption algorithm and the same secret
key.
Topics discussed in this section:

3.1.1 Kerckhoff’s Principle

3.1.2 Cryptanalysis
3.1.3 Categories of Traditional Ciphers
Figure 3.1 General idea of symmetric-key cipher
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:

Figure 3.2 Locking and unlocking with the same key
 3.1.1 Kerckhoff’s Principle

Based on Kerckhoff’s 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.
 Cryptanalysis
As cryptography is the science and art of creating secret
codes, cryptanalysis is the science and art of breaking
those codes.

Figure 3.3 Cryptanalysis attacks

 Ciphertext-Only Attack

Figure 3.4 Ciphertext-only attack

 Known-Plaintext Attack

Figure 3.5 Known-plaintext attack

 Chosen-Plaintext Attack

Figure 3.6 Chosen-plaintext attack

 Chosen-Ciphertext Attack

Figure 3.7 Chosen-ciphertext attack

 3-2 SUBSTITUTION CIPHERS

A substitution cipher replaces one symbol with another. Substitution ciphers can be categorized as either
monoalphabetic ciphers or polyalphabetic ciphers.

Note

A substitution cipher replaces one

symbol with another.
Topics discussed in this section:

3.2.1 Monoalphabetic Ciphres

3.2.2 Polyalphabetic Ciphers
 Monoalphabetic Ciphers

Note

In monoalphabetic substitution, the

relationship between a symbol in the
plaintext to a symbol in the ciphertext is
always one-to-one.
Example 3.1
The following shows a plaintext and its corresponding ciphertext.
The cipher is probably monoalphabetic because both l’s (els) are
encrypted as O’s.

Example 3.2
The following shows a plaintext and its corresponding ciphertext.
The cipher is not monoalphabetic because each l (el) is encrypted
by a different character.
 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.

Figure 3.8 Plaintext and ciphertext in Z26

 Figure 3.9 Additive cipher

Note

When the cipher is additive, the

plaintext, ciphertext, and key are
integers in Z26.
Use the additive cipher with key = 15 to encrypt the message
“hello”.

Solution
We apply the encryption algorithm to the plaintext, character by
character:
 Example 3.4

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

“WTAAD”.
Solution
We apply the decryption algorithm to the plaintext character by
character:
 Shift Cipher and Caesar Cipher

Historically, additive ciphers are called shift ciphers. Julius

Caesar used an additive cipher to communicate with his officers.
For this reason, additive ciphers are sometimes referred to as the
Caesar cipher. Caesar used a key of 3 for his communications.

Note

Additive ciphers are sometimes referred

to as shift ciphers or Caesar cipher.
 Example 3.5
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.
 Table 3.1 Frequency of characters in English

Table 3.2 Frequency of diagrams and trigrams

 Example 3.6

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. This means key = 4.
 Multiplicative Ciphers

Figure 3.10 Multiplicative cipher

Note

In a multiplicative cipher, the plaintext

and ciphertext are integers in Z26; the
key is an integer in Z26*.
Example 3.7
What is the key domain for any multiplicative cipher?
Solution
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.
Example 3.8
We use a multiplicative cipher to encrypt the message “hello”
with a key of 7. The ciphertext is “XCZZU”.
 Affine Ciphers

Figure 3.11 Affine cipher

 Example 3.09
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.

Example 3.10
Use an affine cipher to encrypt the message “hello” with the key
pair (7, 2).
Example 3.11
Use the affine cipher to decrypt the message “ZEBBW” with the
key pair (7, 2) in modulus 26.
Solution

Example 3.12
The additive cipher is a special case of an affine cipher in which
k1 = 1. The multiplicative cipher is a special case of affine cipher
in which k2 = 0.
 Monoalphabetic Substitution Cipher

Because additive, multiplicative, and affine ciphers have small key

domains, they are very vulnerable to brute-force attack.

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.

Figure 3.12 An example key for monoalphabetic substitution cipher

 Example 3.13
We can use the key in Figure 3.12 to encrypt the message

The ciphertext is
 3.2.2 Polyalphabetic Ciphers

In polyalphabetic substitution, 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 one-to-many.

Autokey Cipher
 Example 3.14
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.
 Playfair Cipher
Figure 3.13 An example of a secret key in the Playfair cipher

Example 3.15
Let us encrypt the plaintext “hello” using the key in Figure 3.13.
 Vigenere Cipher

Example 3.16
We can encrypt the message “She is listening” using the
6-character keyword “PASCAL”.
 Example 3.16
Let us see how we can encrypt the message “She is listening”
using the 6-character keyword “PASCAL”. The initial key stream
is (15, 0, 18, 2, 0, 11). The key stream is the repetition of this initial
key stream (as many times as needed).
 Example 3.17
Vigenere cipher can be seen as combinations of m additive
ciphers.

Figure 3.14 A Vigenere cipher as a combination of m additive ciphers

 Example 3.18
Using Example 3.18, we can say that the additive cipher is a
special case of Vigenere cipher in which m = 1.

Table 3.3
A Vigenere Tableau
 Vigenere Cipher (Crypanalysis)

Example 3.19
Let us assume we have intercepted the following ciphertext:

The Kasiski test for repetition of three-character segments yields

the results shown in Table 3.4.
 Example 3.19

Let us assume we have intercepted the following ciphertext:

The Kasiski test for repetition of three-character segments yields

the results shown in Table 3.4.
 Example 3.19 (Continued)
The greatest common divisor of differences is 4, which means that
the key length is multiple of 4. First try m = 4.

In this case, the plaintext makes sense.

 Hill Cipher

Figure 3.15 Key in the Hill cipher

Note

The key matrix in the Hill cipher needs

to have a multiplicative inverse.
 Example 3.20
For example, the plaintext “code is ready” can make a 3 × 4
matrix when adding extra bogus character “z” to the last block
and removing the spaces. The ciphertext is “OHKNIHGKLISS”.

Figure 3.16 Example 3.20

 Example 3.21
Assume that Eve knows that m = 3. She has intercepted three
plaintext/ciphertext pair blocks (not necessarily from the same
message) as shown in Figure 3.17.

Figure 3.17 Example 3.21

 Example 3.21 (Continued)

She makes matrices P and C from these pairs. Because P is

invertible, she inverts the P matrix and multiplies it by C to get
the K matrix as shown in Figure 3.18.

Figure 3.18 Example 3.21

Now she has the key and can break any ciphertext encrypted with
that key.
 One-Time Pad

One of the goals of cryptography is perfect secrecy. A

study by Shannon has shown that perfect secrecy can be
achieved if each plaintext symbol is encrypted with a key
randomly chosen from a key domain. This idea is used
in a cipher called one-time pad, invented by Vernam.
Rotor Cipher

Figure 3.19 A rotor cipher

3.2.2 Continued
Enigma Machine

Figure 3.20 A schematic of the Enigma machine

 3-3 TRANSPOSITION CIPHERS

A transposition cipher does not substitute one symbol for another, instead it changes the location of the
symbols.

Note

A transposition cipher reorders symbols.

Topics discussed in this section:

3.3.1 Keyless Transposition Ciphers

3.3.2 Keyed Transposition Ciphers
3.3.3 Combining Two Approaches
 Keyless Transposition Ciphers
Simple transposition ciphers, which were used in the
past, are keyless.
Example 3.22
A good example of a keyless cipher using the first method is the
rail fence cipher. The ciphertext is created reading the pattern
row by row. For example, to send the message “Meet me at the
park” to Bob, Alice writes

She then creates the ciphertext “MEMATEAKETETHPR”.

 Example 3.23

Alice and Bob can agree on the number of columns and use the
second method. Alice writes the same plaintext, row by row, in a
table of four columns.

She then creates the ciphertext “MMTAEEHREAEKTTP”.

 Example 3.24

The cipher in Example 3.23 is actually a transposition cipher. The

following shows the permutation of each character in the plaintext
into the ciphertext based on the positions.

The second character in the plaintext has moved to the fifth

position in the ciphertext; the third character has moved to the
ninth position; and so on. Although the characters are permuted,
there is a pattern in the permutation: (01, 05, 09, 13), (02, 06, 10,
13), (03, 07, 11, 15), and (08, 12). In each section, the difference
between the two adjacent numbers is 4.
 3.3.2 Keyed Transposition Ciphers

The keyless ciphers permute the characters by using

writing plaintext in one way and reading it in another
way The permutation is done on the whole plaintext to
create the whole ciphertext. Another method is to divide
the plaintext into groups of predetermined size, called
blocks, and then use a key to permute the characters in
each block separately.
 Example 3.25

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

 3.3.3 Combining Two Approaches
Example 3.26
Figure 3.21
 Keys
In Example 3.27, a single key was used in two directions for the
column exchange: downward for encryption, upward for
decryption. It is customary to create two keys.

Figure 3.22 Encryption/decryption keys in transpositional ciphers

Figure 3.23 Key inversion in a transposition cipher
 Using Matrices
We can use matrices to show the encryption/decryption process
for a transposition cipher.

Example 3.27

Figure 3.24 Representation of the key as a matrix in the transposition cipher

 Example 3.27
Figure 3.24 shows the encryption process. Multiplying the 4 × 5
plaintext matrix by the 5 × 5 encryption key gives the 4 × 5
ciphertext matrix.

Figure 3.24 Representation of the key as a matrix in the transposition cipher

Double Transposition Ciphers
Figure 3.25 Double transposition cipher
 STREAM AND BLOCK CIPHERS

The literature divides the symmetric ciphers into two broad categories: stream ciphers and block ciphers.
Although the definitions are normally applied to modern ciphers, this categorization also applies to
traditional ciphers.

Topics discussed in this section:

3.4.1 Stream Ciphers

3.4.2 Block Ciphers
3.4.3 Combination
 Stream Ciphers

Call the plaintext stream P, the ciphertext stream C, and

the key stream K.

Figure 3.26 Stream cipher

 3.4.1 Continued
Example 3.30
Additive ciphers can be categorized as stream ciphers in which
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.

Example 3.31
The monoalphabetic substitution ciphers discussed in this chapter
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.
Example 3.32
Vigenere ciphers are also stream ciphers according to the
definition. In this case, the key stream is a repetition of m values,
where m is the size of the keyword. In other words,

Example 3.33
We can establish a criterion to divide stream ciphers based on
their key streams. We can say that a stream cipher is a
monoalphabetic cipher if the value of ki does not depend on the
position of the plaintext character in the plaintext stream;
otherwise, the cipher is polyalphabetic.
 Combination
In practice, blocks of plaintext are encrypted
individually, but they use a stream of keys to encrypt the
whole message block by block. In other words, the
cipher is a block cipher when looking at the individual
blocks, but it is a stream cipher when looking at the
whole message considering each block as a single unit.