Learning Outcomes. This assessment addresses the following learning outcomes of COMP122:
Describe the concept of object polymorphism in theory and demonstrate this concept in practice.
Design and code iterators for collection-based data management.
Identify and describe the task and issues involved in the process of developing interactive products for
people, and the techniques used to perform. these tasks.
Part I (50% of assessment mark)
Introduction
Note: Students who took COMP105 will recognize this problem to some extent. We are going to solve it
here without the use of Haskell’s fancy functional programming methods. However, all the background you
need about this problem is given here, so don’t worry if you haven’t seen this before.
TheCaesarcipher. The Caesar cipher is an ancient method of encrypting text, i.e. attempting to transform
text into a format that is unreadable by others. The Caesar cipher is defined by a “shift”, i.e. a number that
is used to shift letters elsewhere in the alphabet. (Caesar would have been operating in Latin, we will be
working in English.)
To encrypt your text using a given (positive) shift, you translate letters by that many places later in the
alphabet.
For example, if your text to encrypt is ”Meet me at midnight under the bridge” and your shift is 5, the
encrypted text is “Rjjy rj fy rnisnlmy zsijw ymj gwnilj”. In this case, the letter “m” gets translated to five
places later in the alphabet, to the letter “r”, the “e” to a “j” (five places later in the alphabet), etc. As said,
we “wrap around”, so a “z” gets changed to a “e” given a shift of 5.
We can interpret a negative value for the shift as translating letters backwards (e.g. an “f” gets encrypted
as the letter “b” if the shift is 4).
Figure 1: A Caesar cipher with a shift of 3
It is believed that Caesar actually used such a “shift cipher”, but this was likely also aided by the fact that
many people at that time would have been illiterate, or barely literate, so they might think messages were
written in a foreign language.
Unfortunately for Caesar, this type of cipher is easily broken by the use of “frequency analysis”. In other
words, we know the general frequency of the occurrence of letters in the English alphabet, e.g. “e” is the
most common letter, then “t”, etc. Caesar would have working in Latin, whereas we are working in English,
but the ideas are the same. I suppose we would want to know, or guess, the language that the person is using,
since letter frequencies can vary significantly across different languages.
Cracking the Caesar cipher. How could we go about cracking this cipher? Suppose we are given a
“cipher text”, i.e. text that has already been encrypted with some (unknown) shift, and we want to determine
the original unencrypted text (typically referred to as the “plaintext”). For example, given the cipher text
“Hxotm euax ycuxj yotik ck gzzgiq gz jgct”, how can we reconstruct the original text?
1. Try decoding the text with a particular shift.
2. Compute the letter frequencies for that decoded text.
3. Check to see if the frequencies are close to the English frequencies.
4. Examine all 26 possible shifts, and take the one that is “closest” to English frequencies.
How do we measure “closeness” of the letter frequencies in the given text to those of regular English? If
freq denotes the frequency of a letter in our text, and English is the corresponding English letter frequency,
we use the 2 score (that is the Greek letter “chi”, so it’s the “chi-squared score”). This score is defined as
follows:
2 =
zX
=a
(freq English )2
English :
In other words, we sum the fraction over all 26 possible letters to determine this score. The 2 score will
be lower when the frequencies are closer to English. Note that when we do this, we are ignoring the case of
letters (we want to treat upper and lower case equally for our purposes).
Note that we don’t have to actually perform. the shift and then compute the frequencies, we can compute
the frequencies of the cipher text and then shift those frequencies.
We will be using the following known frequencies for the letters in English, conveniently given here in
a Java-style. array (arranged in the usual alphabetic order):
double[] knownFreq = {0.0855, 0.0160, 0.0316, 0.0387, 0.1210,
0.0218, 0.0209, 0.0496, 0.0733, 0.0022,
0.0081, 0.0421, 0.0253, 0.0717, 0.0747,
0.0207, 0.0010, 0.0633, 0.0673, 0.0894,
0.0268, 0.0106, 0.0183, 0.0019, 0.0172,
0.0011};
Requirements
For this problem, you want to develop a program that will crack a given Caesar cipher text, and to display
the original plain text on the screen. You may assume that the cipher text has been produced using a Caesar
cipher by some (unknown) shift. This shift has only been applied to letters, not anything else that may appear
in the text, so spaces are spaces, any punctuation is left untouched, etc. Lower case letters are transformed
to lower case letters, etc.
I don’t want to tell you exactly how to go about doing this, but you will need to develop a method to
encrypt (or decrypt) a string given a shift. (After all, you need to give the original unencrypted plaintext.)
We note the following things that can help you in Java:
2
In Java, char and int variables are (more or less) interchangeable. A Java statement like
int diff = ’e’ - ’b’;
is perfectly legal, i.e. Java can interpret the “difference of two letters” with no problem, and this will
give an integer value. If the two letters are of the same case, then this will give a value between 25
and 25. In particular, if ch is a lower case (char) letter, then
int diff = ch - ’a’;
tells you how many places after ‘a’ that letter is in the alphabet. (The value of diff will be between
0 and 25 inclusive.)
We can use this idea in encrypting/decrypting letters. Assuming that shift is a nonnegative integer,
we can encrypt the (lower case) letter ch by doing the following:
char newChar = (char) ((ch - ’a’ + shift) % 26 + ’a’);
What is this doing? First we find out the number of characters after ‘a’ for the letter ch, and add the
shift. The % operator is “mod”, so we get the remainder left over after dividing by 26. That is doing
the “wrap around”. Then we turn this back into a char by “adding” the letter ‘a’ and typecasting to a
char variable.
Using the above procedure, we can then encrypt any lower case letter. To encrypt an upper case letter,
we can do the same except replace ‘a’ by ‘A’.
How do we encrypt both lower and upper case letters? Let ch be any character (which could also be
a space or non-alphabetic letter). If ch-’a’ is between 0 and 25 (inclusive), then ch is a lower case
letter, and we encrypt as above.
Alternatively, if ch-’A’ is between 0 and 25 (inclusive), we encypt ch similarly to get a new upper
case letter.
Otherwise, ch is not a letter we want to change, so we leave it alone.
How do we put the ideas together to encrypt (or decrypt) a whole string? Recall a precious prac-
tical where we talked about some Java String methods. In particular, if str is a String, then
str.charAt(i) gives you the char at index i in str. (Also remember that Java strings use 0-based
indices.)
Can you write a Java method to encrypt (or decrypt) a String given a shift? Note that if the shift
is a negative number, add 26 to it until you get a positive number. (This is because the Java “mod”
operator doesn’t deal with negative numbers in the right way.) Note that shifting by 5, say, is the
same as shifting by 21 i.e. shifting back 5 places is the same as shifting forward by 21 places.
Once you have a method to encrypt/decrypt with a shift, you’re half way done. You need to count
letter frequencies. Remember that frequencies are fractional values. In the string ”Mississippi moon”, the
frequency of the letter “m” is 2=15, while the frequency of the letter “s” is 4=15. As stated before, we
consider upper and lower case to be the same in this case, and we also only count the letters (that’s why
the denominator is 15, not 16). To compare to English frequencies, we need to find the frequency for all 26
letters to compute the 2 score. (Many will be 0, but we still need all of them.)
Contrary to what I said earlier, you don’t need to “shift and then count letter frequencies”. You can
actually count letter frequencies of the cipher text, and then shift those frequencies when searching for the
right shift. (Shift frequencies, and then compute the 2 score for that shift.)
Finally, write your application to take input from the command line. Your string will be in the variable
args[0]. If your input has spaces in it, put that input inside of (single or double) quotation marks. You
should print out an error message if you invoke your program with no string specified on the command line.
Call your application “BreakCaesar.java”.