Cryptography Reference
In-Depth Information
We notice important particular cases:
when the key is of length 1, we obtain a simple substitution;
when the key is as long as the message and the alphabet is binary, we obtained
the Vernam cipher (one-time pad). (see Section 1.1.4.)
x
n
of characters
x
i
in an alphabet
Z
, we define the
number
n
c
of indices
i
for which
x
i
=
Given a sequence
x
=
x
1
x
2
···
c
, and the index of coincidence by
n
c
(
n
c
−
1)
Index
=
Pr
I
J
[
x
I
=
x
J
|
I
<
J
]
=
n
(
n
−
1)
,
c
∈
Z
where
I
and
J
are two independent uniformly distributed elements of
. The
index of coincidence is invariant under substitution: if we encrypt
x
into another se-
quence by simple substitution, this will not change the index of coincidence. When
n
tends toward infinity, the index of coincidence only depends on the sequence distribu-
tion. For a sequence randomly taken from an English text, the index of coincidence is
approximately 0
{
1
,...,
n
}
.
065. For sequences generated from a truly random distribution, this is
approximately 0
.
038.
This index of coincidence can thus be used in order to break the Vigenere Cipher.
1:
for
all guesses for the length
m
of the secret key
do
2: put the ciphertext in an array with
m
columns
3: check that the index of coincidence of each column is high
4:
end for
5: check the key shifts between columns with mutual indices of coincidence
(Note that the guess for the length of the key can be speeded up by using the Kasiski
Test.) The mutual index of coincidence between two sequences
x
=
x
1
x
2
···
x
n
and
y
=
y
1
y
2
···
y
n
is Pr
I
,
J
[
x
I
=
y
J
]. It should be high when the two sequences come
from the same substitution.
With the example
TIKSJUAEWMNAMFUSBIE
, if we guess that
m
=
3 we can
write
T
I
K
S
J
U
A
E
W
M
N
A
M
F
U
S
B
I
E
and so we can compute the index of coincidence of
TSAMMSE
,
IJENFB
, and
KUWAUI
.
(Note that this example is not so relevant because the ciphertext is too short.)
Search WWH ::
Custom Search