Cryptography Reference
In-Depth Information
A0ne ciphers are just special cases of the following, which we informally
encountered on page 8. This can now be put into a well-defined mathematical
notion. The reader unfamiliar with, or in need of a reminder of at least the no-
tation for, the notion of permutations should review page 9 where we introduced
the informal notion therein.
Substitution Ciphers
A substitution cipher is defined as follows. Let
A
be an alphabet of definition
consisting of
n
symbols, and
M
be the set of all blocks of length
r
∈
N
over
A
. The keyspace,
K
, consists of all ordered
r
-tuples
e
=(
σ
1
,σ
2
,...,σ
r
)of
permutations
σ
j
on
. The enciphering and deciphering transformations are
defined by the actions below, respectively. If
e
A
∈
K
and
m
=(
m
1
m
2
...m
r
)
∈
M
, then
E
e
(
m
)=(
σ
1
(
m
1
)
,σ
2
(
m
2
)
,...,σ
r
(
m
r
)) = (
c
1
,c
2
,...,c
r
)=
c
∈
C
,
and for
d
=(
d
1
,d
2
,...,d
r
)=(
σ
−
1
,σ
−
2
,...,σ
−
r
)=
σ
−
1
,
D
d
(
c
)=(
d
1
(
c
1
)
,d
2
(
c
2
)
,...,d
r
(
c
r
)) = (
σ
−
1
(
c
1
)
,σ
−
2
(
c
2
)
,...,σ
−
r
(
c
r
)) =
m.
=
σ
r
, then this cryp-
tosystem is called a
simple substitution cipher
or
monoalphabetic substitution
cipher
. If the keys differ, we call this cryptosystem a
polyalphabetic substitution
cipher
.
Thus, we know that the Caesar cipher is an example of a block cipher that
is a monoalphabetic substitution, whereas the Vigenere cipher, studied earlier
(see page 56), is an example of a polyalphabetic substitution.
As we have seen in Chapters 1 and 2, simple substitution ciphers suffer from
the inherent weakness that a frequency analysis can be done on the ciphertext,
whereas polyalphabetic substitution ciphers are more secure than the monoal-
phabetic ones.
When a substitution block cipher replaces one or more symbols by groups of
ciphertext symbols, we call this a
polygramsubstitutioncipher
. We encountered
one of these already on page 68, namely, the Playfair cipher, which is an exam-
ple of a digraphic cipher. In fact, as we saw therein, this was the
first
literal
digraphic cipher. Another polygram substitution cipher we have already men-
tioned in our historical travels is the Hill cipher. We now describe this cipher
in detail.
The reader will need a tiny bit of elementary matrix theory, all of which is
supplied in Appendix A (see pages 491-494).
The Hill Cipher
If all the keys are the same, namely,
σ
1
=
σ
2
=
···
Choose fixed
r,n
∈
N
and let the keyspace
K
=
{
e
∈
M
r
(
Z
/n
Z
):
e
is invertible
}
,
r
×
)
r
. This
and let the message space,
M
and ciphertext space
C
, both be (
Z
/n
Z
stands for
r
copies of the integers
Z
/n
Z
, meaning ordered
r
-tuples of integers
Search WWH ::
Custom Search