Cryptography Reference
In-Depth Information
Yet, as with most of his discoveries, he did not publish this fantastic break-
through. There is speculation that since the breaking of the chiffre indechiffrable
occurred after the start of the Crimean War, British intelligence may have
wanted Babbage to keep it a secret. (The Crimean War, October 1853 to Febru-
ary 1856, was fought primarily on the Crimean peninsula between the Russians
and the British, French, and Ottoman Turks.) The British felt that this secrecy
would give them an advantage over the Russians for several years. Thus it is
that Babbage died on October 18, 1871 in London, without it being revealed
that he broke the Vigenere cipher. That credit would go to another.
Frederich W. Kasiski (1805-1881) was born on November 29, 1805, in West-
ern Prussia. He enlisted in East Prussia's thirty-third infantry at the age of 17,
and retired in 1852 as a major. Although interested in cryptography during his
military career, he did not publish any of his ideas until after his retirement. In
1863, he published
Die GeheimschRiften und die Dechiffrir - Kunst
, a general
solution to cryptanalyzing polyalphabetic cryptosystems with repeating key-
words, including the famed Vigenere cipher, a long-sought-after breakthrough.
The central idea behind Kasiski's attack is the keen observation that re-
peated portions of plaintext enciphered with the same part of a key must result
in identical ciphertext patterns. Hence, barring coincidence, one would expect
that the same plaintext portions corresponding to repeated ciphertext were en-
ciphered with the same position in the key. Therefore, the number of symbols
between the start of repeated ciphertext patterns should be a multiple of the
keylength
(the number of characters in the key). For example, if the repeated
ciphertext is
ABC
, called a
trigram
, and if the number of letters between the
C
and the occurrence of
A
in the next trigram
ABC
is, say, 15, and this is
not an accident, then 18 is a multiple of the keylength. Since it is possible
that some of the repeated ciphertext segments are coincidental, a method of
analyzing them, called a
Kasiski examination
, is to compute the greatest com-
mon divisor (gcd)
2.5
of the collection of all the distances between the repeated
sections. Then choosing the largest factor occurring most often among these
gcd
s is (probably) the keylength. Once a probable keylength
, say, is obtained,
a frequency analysis can be performed on a breakdown of the ciphertext into
classes (with an individual class containing every
-th character) to determine
the suspected key. The following is an illustration of the Kasiski method for
finding the keylength.
Example 2.2
Suppose that
“keys”
is the keyphrase and
“these are the safest
aims”
is the plaintext. Then consider the following Vigenere enciphering.
k e y s k e y s k e y s
t h e s e a r e t h e s
D L C K
O E P W
D L C K
2.5
For the reader unfamiliar with this concept and related notions, see Definition A.11 in
Appendix A on page 470.
Search WWH ::
Custom Search