Cryptography Reference
In-Depth Information
On page 9, we looked at the concept of transposition/permutation ciphers.
We can now formalize this definition as well. First, as an introductory mecha-
nism, think of the following type of cipher as one in which the characters of the
plaintext are reordered according to some agreed-upon procedure by, say, Al-
ice and Bob, who are corresponding with one another (securely). For instance,
as we saw on page 9, the skytale is an historical example of such a cipher.
A modern-day example is in most local newspapers, namely, an
anagram puz-
zle
, which is a meaningful rearrangement of an already meaningful plaintext.
The clear conclusion, from the fact that these are solved on a regular basis by
ordinary readers, is that these kinds of ciphers are easily cryptanalyzed.
To informally introduce the notion of a “permutation”
f
on a set
S
=
{
to itself. A naive
question that arises is: How many such permutations are there? We see that
for the first element 1, of
1
,
2
,...,r
}
, we may think of
f
as a bijective function from
S
there are
r
choices to which it can be mapped, and
for the second choice, 2, there remain
r
S
1 choices to which it can be mapped
(since we cannot map the first element to
more
than one element given that
f
is a function), and similarly for the third element, 3, there are
r
−
2 elements to
which we can map it, and so on. Hence, the total number of such permutations
is
r
!. This explains the cardinality of the keyspace below.
−
Permutation/Transposition Ciphers
A
simple transposition cipher
or
simple permutation cipher
is a symmetric-
key block cryptosystem having blocklength
r
∈
N
, with keyspace
K
being the
set of permutations on
. The enciphering and deciphering transfor-
mations are given as follows, respectively:
{
1
,
2
,...,r
}
∈
M
∈
K
For each
m
=(
m
1
,m
2
,...,m
r
)
, and
e
,
E
e
(
m
)=(
m
e
(1)
,m
e
(2)
,...,m
e
(
r
)
)
,
and for each
c
=(
c
1
,c
2
,...,c
r
)
∈
C
,
D
d
(
c
)=
D
e
−
1
(
c
)=(
c
d
(1)
,c
d
(2)
,...,c
d
(
r
)
)
.
In the above, notice that
e
implicitly defines
r
since
e
is a permutation on
r
symbols. Moreover, in such cryptosystems, the cardinality
=
r
!. The
following is a simple, perhaps amusing, illustration of how such permutation
ciphers work in transposing the
places
where the plaintext letters sit.
|
K
|
Example 3.3
Suppose that
r
=13
and
. We apply the key
e
=
123456789 0 1 2 3
912613174102 3 11 5 8
M
=
C
=
Z
/
26
Z
to the plaintext,
m
=(
m
1
,m
2
,m
3
,m
4
,m
5
,m
6
,m
7
,m
8
,m
9
,m
10
,m
11
,m
12
,m
13
)=
(
b,r,i,t,n,e,y,s,p,e,a,r,s
)
,
Search WWH ::
Custom Search