Cryptoanalysis of the Vigenere Cipher:
The vulnerability of the cipher is due to the periodicity of the
keyword. I.e. using the keyword "cat" produces shifts of length 2 (=c) for the 1st , 4th , 7th, 10th
, ... plain letter,
shifts of length 0 (=a) for the 2nd , 5th , 8th , 11th , ... plain
letter and shifts of length 19 (=t) for the 3rd , 6th , 9th , 12th , ...
plain letter.
Consequently, if an eavesdropper only knows the keyword length (here 3), he
groups the above cipher letters into 3 categories. He then applies letter frequency analysis on each group of letters. Certainly, he will have
to intercept a large piece of cipher text in order to successfully perform
the frequency analysis. The remaining challenge to successfully
break the Vigenere Cipher remains to determine the keyword length.
The German soldier Friedrich Wilhelm Kasiski
(1805-1881) introduced a method to determine the keyword length - the so
called "Kasiski-Test". I am going to show
you an easy example of this method. Say, we vigenere-encode as follows:
theappleisinthecornerandthepearistheretoo
(plain)
catcatcatcatcatcatcatcatcatcatcatcatcatca
(key)
vhxcpinebuigvhxeokpekcnwvhxrettilvhxtemqo
(cipher)
The eavesdropper has to search for repeating cipher
letter combinations (i.e. "vhx"). He then counts the distances between
such letter combinations (i.e. 12, 9, 21, 33). Such distances are multiples of the
keyword length if same plain words happened to be encoded with the same
keyword. Therefore, their greatest common divisor is the desired
keyword length (i.e. 3). Assuming the keyword length is 3, letter frequency analysis
is applied to the 3 groups of cipher letters. Cipher letters in same
groups stem from plain letters that were shifted by the same same number of
positions, they are Caesar shifts. Thus, the most frequent cipher letter in
each group is very likely the Cipher "e". Consequently, the
Vigenere Cipher is broken.
Exercise 5:
Determine the
keyword length of the vigenere-encoded cipher text below. Once found, try to
break the encoded message. Attention: To easily find repeating letter
combinations I maintained the word spacing. Therefore, blanks are encrypted
(but remain blanks) and distances between repeating letter combinations are
determined by incorporating the blanks in the summation process as well.
I.e. The distance between the first two "wvk"
is 33 and not 28. Count the spaces just like regular letters. A great help
to count letters with and without spaces is "Word Count" under
Tools in MS WinWord.
|
wvk
kuur ffeshujfgsve qupsy txra wvk
uxhsq kuury yxbdzrg psgqwtj nlrjhb dbj
uxddnhwt akdboqu zfowwtj iumvwcmuovkm lg wvk
gzxre cl
vogrkq cuwzlbm cx hnh yfwkqqk cl
stffeshoqu dbj
rkffeshoqu wsdw tlbkwskqhn qkqhaum vqnrzgug gsiumvwsj
otfwkqh hueshodb kwkucmomvkwiv ckst bgscrhctv yrzjlsxv lritg
zks ucyhhzd ywcth thox fuvszwo huesh lhy wtvqxldzlct
dxdwylbm yoqu shuossb b kgv oq zkfkh gqqohbz zgquadukv
jhauwwi vohfujzesvofg dbj
uxhsq hnh
yfvuooxv ckc fcaor usgg gqqohbz uxhsq rkffeshkg zks rhnhf
ootjigjsy pe hxdbyoozlbm hnh
muskn gqr fcssoxlbm hnh
zkfkh oqgiuwvwwuqg lb wvk
hchbzlszk ihbzxfe kuuzj cl
qupdawsx bkwkuuyy akvggjsy oxh jluoworom hbiumvwsj ct hnh
yhbjlbm gogs dbj
rkffeshkg uq zks usihwblbm gogs xgoqu ffeshujfgsvof yhfblqkv
gqr dzmrfowvsv gouuuwzkay oxh sdhnhagwwidz
wsikbotikv uu xxzkv zkoz ovsze o ffeshujfgsvof yhfblqk hu o
psyvomh
|
|
Please complete: Letter combinations such as
"dbj", "wvk",
"cl" and
"hnh" appear often. (Can you find any others? How about
"ffesh"?) The
distances between consecutive ...
"dbj" are
102, __ , __ .
"wvk" are 33,
__ , __ .
"hnh" are __ , __ , __, __ , __ .
"cl" are
__ , __ .
Their greatest common divisor is __ .
To then figure out the keyword, we find the ...
first letter to be a Caesar shift of __ positions.
second letter to be a Caesar shift of __ positions.
third letter to be a Caesar shift of __ positions.
Thus, the keyword is ____ (numbers) = ____ (word)
Therefore, the plain text is ???
|
the
word cryptography comes from the greek words kryptos
meaning hidden and graphein meaning writing
cryptography is the study of hidden writing or
the science of encrypting and decrypting text
nineteenth century scholars decrypted ancient egyptian
hieroglyphics when napoleons soldiers found the rosetta
stone near rosetta egypt its inscription praising king
ptolemy v was in three ancient languages demotic
hieroglyphics and greek the scholars who could
read ancient greek decrypted the other languages by
translating the greek and comparing the three
inscriptions in the twentieth century world of
computer networks messages are digitally encrypted on the
sending side and decrypted on the receiving side
using cryptographic services and algorithms algorithms are
mathematical techniques or rules that apply a
cryptographic service to a message
|
|
Exercise 6:
Break the
following Vigenere Cipher.
Mvc gnxqgywa aglgghb ht Tbrbzjxg Lqfhcj wq hm dphjgws Lh Mvmfoq olw Qm Hhvl kgmv ifgoorx nkwktfw olw qxqmgrykm xrsvorbcl cd hfx fbufxgr estzgmm Mvc tsgqrbcl cd hfx Jhkck Qvvmhz bg mc ifciopx qmibxbrl dhf t pbumkcsl ahzjxuc dpxdykorhfw dphupta bb mvc Agwrjx ygr Ndnxf Lqfhcjl Ras Tbrbzjxg Lqfhcj dphupta bg wsqbulxr mc xbqnfc oq asvv tg bh bg icqlwzes mvym ekobnorxg tfc dpxdyksb hm acxh mvc obfwqlwmgg ksonwpxacghq cd hfx khgr qmfdcmwrbjc qmezczsq olw sgwtxfqbhgxg mc xlaxz bb liaa gggrbhsmwmgg tbb hm ormogg rasgk nxfqhbye ygr vopxsp umtzq Oje qvvmhz ifmzfyfg tfc rclwegsb hm rcosjhd lhswslmg tqywskbq tbb zctrckgfbd tpgewrbsq olw rasgk nxfqhbye qhqgtz tbb qgowa outfcgsql
Keyword:
TOY
Plain text: The specific
mission of Antilles School is to provide St Thomas and St John with private
primary and secondary education of the highest quality The function of the
Lower School is to prepare students for a rigorous college preparatory
program in the Middle and Upper Schools The Antilles School program is
designed to ensure as much as it is possible that graduates are prepared to
meet the admissions requirements of the most competitive colleges and
universities to excel in such institutions and to attain their personal and
career goals All school programs are designed to develop students academic
and leadership abilities and their personal social and civic awareness
The Vigenere Plateau
Before the computer age messages were vigenere-encoded and decoded by using
the famous Vigenere Plateau below. The cipher letter is determined by the
keyword column and the plaintext row. I.e. let's encode the plain letter
"T" using the keyword letter "C". The intersection of
the T-row with the C-column happens at letter "V", the cipher
letter. Correspondingly, the plain letter can be derived from the cipher
letter and the keyword. How?
Keyword
A
B C D E F G H I J K L M N O P Q R S T U
V W X Y Z
B C D E F G H I
J K L M N O P Q R S T U V W X Y Z A
C D E F G H I J
K L M N O P Q R S T U V W X Y Z A B
P
D E F
G H I J K L M N O P Q R S T U V W X Y Z A B C
l E F
G
H I J K L M N O P Q R S T U V W X Y Z A B C D
a F G
H
I J K L M N O P Q R S T U V W X Y Z A B C D E
i G H I
J K L M N O P Q R S T U V W X Y Z A B C D E F
n H I J
K L M N O P Q R S T U V W X Y Z A B C D E F G
t I J K
L M N O P Q R S T U V W X Y Z A B C D E F G H
e J K L
M N O P Q R S T U V W X Y Z A B C D E F G H I
x K L M
N O P Q R S T U V W X Y Z A B C D E F G H I J
t
L M N
O P Q R S T U V W X Y Z A B C D E F G H I J K
M N O P Q R S T
U V W X Y Z A B C D E F G H I J K L
N O P Q R S T U
V W X Y Z A B C D E F G H I J K L M
O P Q R S T U V
W X Y Z A B C D E F G H I J K L M N
P Q R S T U V W
X Y Z A B C D E F G H I J K L M N O
Q R S T U V W X
Y Z A B C D E F G H I J K L M N O P
R S T U V W X Y
Z A B C D E F G H I J K L M N O P Q
S T U V W X Y Z
A B C D E F G H I J K L M N O P Q R
T U V W X
Y Z A B C D E F G H I J K L M N O P Q R S
U V W X Y Z A B
C D E F G H I J K L M N O P Q R S T
V W X Y Z A B C
D E F G H I J K L M N O P Q R S T U
W X Y Z A B C D
E F G H I J K L M N O P Q R S T U V
X Y Z A B C D E
F G H I J K L M N O P Q R S T U V W
Y Z A B C D E F
G H I J K L M N O P Q R S T U V W X
Z A B C D E F G
H I J K L M N O P Q R S T U V W X Y
|