Solution of Exercise Sheet 1

saarland
Foundations of Cybersecurity (Winter 14/15)
Prof. Dr. Michael Backes
CISPA / Saarland University
university
computer science
Solution of Exercise Sheet 1
(6 points)
1 Cryptanalysis of the Vigen`
ere Cipher
The following ciphertext was encrypted using the Vigen`ere Cipher, where all spaces
and punctuation were removed. Decrypt it, using any tool you like. (The text is
available for download on the course web page.)
GIRR
MDOF
RYSJ
NEPO
ELNX
CBTJ
XSUZ
LCBI
PCIU
BMRI
MOEI
SSQL
PYAQ
CEQI
USSX
FEWR
KCGX
PCKW
QDSD
OAGV
XFKX
RDLY
OXFO
SSCI
CKFJ
YITO
KYBS
CPSP
DLGC
PDYG
AKRL
DCME
ACLJ
CCIT
OXMZ
REEI
SXHU
QIRK
GMEV
SCSL
YXZO
WFYY
MBWM
OVYV
IPPS
QCXF
SXFD
FMEX
QOML
WSPO
FPYO
JNER
WIIS
SDDL
PWED
OWCM
LCWG
RRMQ
DLCB
IJKF
CXFW
VIYC
RBOV
CWEP
BIOE
VCDO
YXFC
KRAS
IKKM
MBER
CYAR
XMXG
EKVR
OETK
ILMC
CISD
KPMD
ILDW
LNIP
OJMB
EQSQ
CSRW
ORAB
MJKF
YXEJ
DLGC
SDPY
REJD
YJRR
QQYJ
NVIR
YYPV
CNDS
JOEL
IWGC
GGZL
LLYR
PSPD
IAYY
QOGS
OGFX
Solution:
This exercise was meant to demonstrate how weak these historic ciphers are and
to show you how much crypto-related stuff can be found in the Internet. The
key that was used for encryption is “KEY”. Consequently, the encrypted message
is the following:
We thought that you should at least once in your life browse the web
for some kindergarten crypto tools. As you see, several of them are
available and are quite able to perform a frequency analysis and thus
to even guess the secret key of this cipher. Playing around with them
can be a lot of fun, but now please forget about this ancient stuff for
the rest of this course. In the remainder of the course we will focus
on more elaborate forms of security that cannot be broken by such a
simple technique.
Encryption, decryption and finding keys is possible here:
• http://smurfoncrack.com/pygenere/pygenere.php
• http://math.ucsd.edu/~crypto/java/EARLYCIPHERS/Vigenere.html
1/4
Foundations of Cybersecurity (Winter 14/15)
Solution for Exercise Sheet 1
The first step always consists in identifying the length of the key. This is usually
done as follows: for every key-length n, calculate letter frequencies. If these look
like the (shifted) letter frequencies of normal text, then we are likely to have
found the correct key size. The actual key is then computed by simple frequency
analysis.
Be aware that the key “A” might either represent a shift by zero or by one
position, depending on the exact definition/implementation. Here we typically
see “A” as a shift by zero (i.e., the identity). However, if we see “A” as a shift by
one, then the key would have been “JDX”, which is also an acceptable answer.
(6 points)
2 Identify encryption schemes
The task of this exercise is to find out which type of encryption was used for encrypting
messages. The possible types are: Shift cipher (e.g., Ceasar’s Cipher), Substitution
Cipher and Vigenere. For each pair of plaintext and ciphertext find out which method
of encryption was used and write down the key that was used for this method.
• Plaintext: THISISASECRETMESSAGE
Ciphertext: VJKUKUCUGETGVOGUUCIG
• Plaintext: NEVERTRUSTINSECURITYBYOBSCURITY
Ciphertext: MVEVIGIFHGRMHVXFIRGBYBLYHXFIRGB
• Plaintext: HELLO
Ciphertext: DSCWR
Solution:
• Plaintext: THISISASECRETMESSAGE
Ciphertext: VJKUKUCUGETGVOGUUCIG
We first realize, that all letters seem to be replaced independently of their
position in the ciphertext. Consequently, we assume that a shift cipher was
used. Indeed, the message was encrypted with a shift cipher with key=2.
Another technically correct answer would be “Vigen`ere Cipher” with key
“C”. As in the previous exercise, note that for the Vigen`ere cipher, the key
“A” might either represent a shift by zero or by one position. Therefore,
the answer “Vigen`ere Cipher” with key “B” is also acceptable.
• Plaintext: NEVERTRUSTINSECURITYBYOBSCURITY
Ciphertext: MVEVIGIFHGRMHVXFIRGBYBLYHXFIRGB
In contrast to the first example, this one cannot be a shift cipher, as “N” is
only shifted to “M”, whereas “E” is shifted to “V”. On the other hand, we
2/4
Foundations of Cybersecurity (Winter 14/15)
Solution for Exercise Sheet 1
again realize that the position does not seem to play a role, so probably
it’s not a Vigen`ere Cipher either. We find that the alphabet is reversed (A
becomes Z, B becomes Y, . . . , Z becomes A). This is a very simple variant
of the substitution cipher. Another technically correct answer would be
“Vigen`ere Cipher” with key “zrjrrnrlpnjzprvlrjndxdxxpvlrjnd” (if “A” is the
identity) or key “yqiqqmqkomiyoqukqimcwcwwoukqimc” (if “A” is a shift
by one).
• Plaintext: HELLO
Ciphertext: DSCWR
For this example, we realize that “L” is once replaced by “C” and immediately
thereafter by “W”. Consequently, it can be neither a shift cipher, nor
a substitution cipher. The correct answer in this case is: The message
“HELLO” is encrypted with a “Vigen`ere Cipher” with key=“WORLD” (when
“A” is defined as a shift by zero). This is, in a sense, the “Hello world!”
of cryptography, as it also constitutes the first secure encryption we have
seen (from the ciphertext alone one cannot learn the plaintext). You will
see a definition for what constitutes a secure cipher in the second lecture.
Another acceptable answer here is “Vigen`ere Cipher” with key=“VNQKC”,
if you define “A” as a shift by one.
(9 points)
3 Cryptanalysis of the Substitution Cipher
The following text was encrypted using the substitution cipher. Please decode it
using any method you find adequate. After you found a solution, please describe
how you analyzed the text. (Hint: You may use any program or simply count the
frequencies of all the pictures that appear within the text.) Happy Hacking!
3/4
Foundations of Cybersecurity (Winter 14/15)
Solution for Exercise Sheet 1
Solution:
The substitution looks as follows:
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:
Using this substitution, we get (as plaintext) the description of the exercise:
The following text was encrypted using the substitution cipher. Please
decode it using any method you find adequate. After you found a
solution, please describe how you analyzed the text. Hint: You may
use any program or simply count the frequencies of all the pictures
that appear within the text. Happy Hacking!
To decrypt the cipher, we have a look at the letter frequencies. Since each picture
corresponds to one letter, we (correctly) assume that the most common pictures
will also correspond to the most frequent letters (within the English language).
The most common pictures are (in decreasing order):
= 31,
=27,
=19,
=
= 17. If these look like the (shifted) letter frequencies of normal
text, then we are likely to have found the correct key size. The actual key is then
computed by simple frequency analysis.
4/4

Download Report