Description
2 Cipher / Decipher
You have probably already tried to whisper things to your neighbour so
that people around you would not hear you. Well, other people have been
doing that for a pretty long time and they came up with a clever solution :
cryptography. The idea is that people may hear you or find the piece of paper
where you wrote your message, so it is not enough to hide it, you should in
fact change its form (cipher or encrypt the message) and the person who
the message is for should be the only one able to get the original form back
(decipher or decrypt).
Some people found some very ingenious ways of hiding messages though :
during the antiquity, Histiaeus shaved the head of his most-trusted slave,
tattooed a message (asking to revolt against the Persians) on his bald head,
waited for the hair to grow back again and then sent the slave to Aristagoras.
This may work when there is plenty of time, but it is very inconvenient in
many ways.
In this assignment you will implement several classical ciphers. They all
rely on the fact that the people trying to communicate share a key (hence
it is also called symmetric ciphers). You will only need to modify the file
Message.java. It implements the class Message that has two fields : a String
message corresponding to the message and an int field corresponding to the
length of the message.
2.1 First function
Question 1. (10 pts) First, you will need to implement the method makeValid :
it will remove all characters that are not letters from ’a’ to ’z’ and change
upper case letters to their corresponding lower case letters.
This is important because leaving spaces, punctuation or upper case letters in a message will give information to the people who want to understand
your message but should not have access to it (this is called cryptanalysis).
2.2 Caesar Cipher
The Caesar cipher is one of the easiest and oldest ciphers. In this case the
key is a number n. To encrypt a message, you shift all letters by n, so for
instance if the key is 2,
3
a becomes c
b becomes d
.
.
.
y becomes a
z becomes b
As you can see, the encrypted message still contains only letters as once we
reach z, we start over again from a. With that key, the message goodluck
becomes iqqfnwem and the message zebra becomes bgdtc.
Question 2. (15 pts) Fill in the code for caesarCipher. Be careful, the key
could be any signed integer and in java, 36%26 = 10 but (−36)%26 = −10 !
To decipher a message, you only have to shift back the letters, we have
implemented that method for you. You can see that this cipher is not very
robust : if you want to read a message that is not addressed to you, you
only have 25 keys to test. But there is a cleverer way to do this. In many
languages like English, there are letters that appear more often than others
(e in English). If the message is long enough, it becomes very simple to find
the key : first look at which letter appears more often. This letter is the most
likely to correspond to letter e in the original message, so you can decide on
what is the most likely key and decipher with the key you have just found.
Question 3. (15 pts) Fill in the code for caesarAnalysis.
2.3 Vigenere Cipher
There is a variant of the Caesar cipher that was much more complicated to
crack and it took three centuries to break it. Instead of being a single integer,
the key is an array of integers. Let’s show you how it works on an example.
You want to encrypt “I love Computer Science”. The corresponding Message
has message ilovecomputerscience. You want to encrypt it using the key
\{ 4, 11, 4, 15, 7, 0, 13, 18\}. First you write down the key under
the message as such
i l o v e c o m p u t e r s c i e n c e
4 11 4 15 7 0 13 18 4 11 4 15 7 0 13 18 4 11 4 15
The number under the letter tells you by how much you should shift each
letter. i with 4 gives the letter m, then l with 11 gives w, etc. In the end you
get the message mwsklcbetfxtyspaiygt.
Question 4. (15 pts each) Fill in the code for vigenereCipher and vigenereDecipher.
If you look on the wikipedia page, you will see that the key is usually a
word, but this works essentially in the same way and in our example, our key
would be elephant.
4
You can see that the analysis of which letter is more frequent cannot be
performed here. But if the message was long enough and if you knew the
length of the key, you could break it into smaller messages and perform the
Caesar analysis on them. And get back the key. The difficulty is now finding
the length of the key.
Question 5. Optional (0 pt) You can code the Analysis of Vigenere (either
knowing the length of the key or not depending on how much you want to
challenge yourself)
2.4 Transposition Cipher
Both the Caesar and Vigenere ciphers are what we call substitution ciphers :
you substitute a letter for an other one. There are other ciphers that change
the position of the letter and not the letter itself. They are called transposition ciphers.
You are going to code an easy one and its corresponding decipher method.
The key is a single integer. Let’s show you how it works on an example. Consider the sentence “This course is amazing” and the key 6. First, write down
the sentence in an array with 6 columns and fill in the empty boxes by a *
t h i s c o
u r s e i s
a m a z i n
g * * * * *
Now, instead of reading it row by row, read it column by column and you
get “tuaghrm*isa*sez*cii*osn*”. Note that the length of the message has
changed as you have added * to it.
In order to decipher, you basically have to construct that same array
and then read it row by row again. For instance, if you received a message
yadoloumnaoers*et* that was constructed with the same key (6), first, compute the size of the array : there are 6 columns and 3 rows that you can fill
one column after the other. For instance, after reading 7 letters and at the
end of the sentence :
y o u
a l .
.
.
d o
y o u a r e
a l m o s t
d o n e * *
And you can now read the original message : youarealmostdone.
Question 6. (15 pts each) Fill in the code for transpositionCipher and
transpositionDecipher.
5
Question 7. Optional (0 pt) You can also code the Analysis of this transposition cipher or other transposition ciphers (many more are explained on
the wikipedia page).
6
