What's Your Secret?

Due Tuesday, November 25, 11:59 PM

There has always been a need for private communications. Governments want to send sensitive messages to their diplomatic staff in foreign countries. Spies need to send secure messages to their headquarters. Credit card transactions need to be secure.

Before computers existed, there was still a need to encipher messages so that they could not be read except by the intended receipient. There is some evidence that Julius Ceasar used a simple alphabetic substitution cipher to protect some of his messages - we'll talk about this in class.

In the history of cryptography, there has been a constant battle between the cryptographers who invent new cryptographic techniques and the cryptananalysts who try to break them. Simple cryptographic techniques have to be replaced by more complex ones as the simple techniques lose their effectiveness.

I would like you to write a program to encrypt messages using the Playfair cipher. This cipher was used by the British government from the mid 1800s until World War I. Although it has some significant weaknesses, it was a very good cipher for its time. Messages could be encrypted and decrypted using only pen and paper, the rules for encrypting and decrypting messages were easy to learn, and encrypted messages were very difficult to decrypt for someone who did not know the keyword.

Objective

To learn to use two dimensional arrays and the String and/or StringBuffer classes.

Some Terminology

Cleartext - the original message that you want to send.

Ciphertext - the encrypted version of the message.

Keyword - A secret word known only to the sender and receiver. The keyword is used to generate the key table.

Key Table - A table that is used by the encryption algorithm to convert characters in the cleartext to characters in the ciphertext. It is also used by the decryption algorithm to convert the ciphertext back to the plaintext.

Encrypt or encipher - to convert the cleartext to ciphertext

Decrypt or decipher - to convert the ciphertext to cleartext.

The Playfair Cipher

The Ceasar cipher noted above is a type of monoalphabetic cipher - each character in the cleartext is replaced by a single character in the ciphertext. For example, every 'A' is replaced with a 'D', every 'B' with and 'E', and so on.

The Playfair cipher is more complex. It bases its substitution on pairs of characters (or digraphs) from the cleartext, using a key table. This means that a particular character in the cleartext can be replaced by different characters in the ciphertext, depending upon what character it is next to.It also means that each letter in the ciphertext replaces more than one letter in the cleartext. For example, one instance of the letter C might be a replacement for A, while another instance of C replaced H. This makes encrypted messages much harder to decrypt if you don't know the keyword.

The encryption algorithm is probably best shown with an example. We'll use the following keytable:

B I O C H 
E M S T R 
Y F L Q W 
A G N U X 
D K P V Z 

This key table contains every letter of the alphabet except 'J'. Since the table has only 25 elements, the letter I is used to represent both I and J.

The encryption algorithm has the following process

1. Remove all non-alphabetic characters from your cleartext. Replace all of the J's in the cleartext with I's. Convert lower case letters to upper case.
2. Break the cleartext up into pairs of letters (or digraphs). For each digraph:
• If both letters are in the same row, replace each letter with the one to its right. For example S and E are in the same row, so SE is replaced with TM. If one of the letters is at the end of the row, replace it with the one at the beginning of the row. For example, replace OH with CB.
• If both letters are in the same column, replace each letter with the one below it. If one of the letters at the bottom of the column, replace it with the one at the top. Thus, GI is replaced with KM, and ED is replaced with YB.
• Otherwise, the letters are in different rows and columns. Imagine that the two letters are at two corners of a rectangle. Replace each letter with the one in the same row that forms the other corner of the rectangle. For example, ND is replaced with AP (not PA), and BU is replaced with CA.
3. What if both letters in the cleartext pair are the same? In this case, you need to add a letter to the cleartext to separate the doubled letter. We'll use the letter 'X'. For example, if our cleartext is "message", then the first pair is ME and the second pair is SS. You need to insert an X between the two S's. Thus, the digraphs become ME, SX, SA, GE, and the resulting ciphertext is SMRNENAM.
   Don't add an X between every doubled letter. You only do this when the letters are part of the same digraph. For example, if your message is "Attack at dawn", you don't need to separate the two T's in 'attack' because they are in different digraphs.
   
4. If there is an unpaired letter at the end of the cleartext, add an extra 'X' to form a digraph, and then use the above algorithm to encrypt it. For example, if your cleartext message is "Send money", then you will need to add an X to the last digraph: SE, ND, MO, NE, YX.

The decryption algorithm reverses these steps, using the same Key Table.

Generating the Key Table

This algorithm requires the sender and receiver to use the same key table. Since it is not a good idea to write down the key table (what if it gets captured?), how can someone remember what it is? This is where the keyword comes in. The keyword is some word that the sender and receiver can both remember. It is used to generate the key table.

Take the keyword, and remove all duplicate letters from it. For example, if the original keyword is 'everyday', then the resulting keyword is EVRYDA. Starting at the upper left corner of the keytable and progressing by rows, put one character of this keyword into the key table, like this

E V R Y D
A * * * *
* * * * *
* * * * *
* * * * *

Now, use the remaining letters of the alphabet (except J) to fill in the rest of the table, by columns:

E V R Y D
A G L P U
B H M Q W
C I N S X
F K O T Z

The keyword used to generate the table shown earlier was 'biochemistry'.

Important:You need to replace any J's in the keyword with I's before removing duplicate characters.

The Program

Your program must do the following:

1. Ask the user to enter a keyword.
2. Use the keyword to generate and print the key table.
3. Ask the user for their cleartext. The cleartext will be on a single input line (that is, you can use Console.in.readLine() ).
4. Encrypt the cleartext and print the resulting ciphertext..

Methods and Arrays

You must write methods in this program. Remember to think about top-level design when deciding what to put in each method. A method should do one task or subtask. Also, remember that a method can call other methods.

Your program must use a two dimensional array for the key table.

Make sure that you understand the Coding Standard rules for methods and arrays.

String and StringBuffer

You will probably find the String and StringBuffer classes useful for this assignment. Character arrays may also be needed.

String and StringBuffer documentation is available from Sun Microsystems. Select String and StringBuffer from the list of classes in the lower left frame.

Some methods from the String class that might be useful include indexOf(), charAt(), replace(), and toUpperCase().

Some methods from the StringBuffer class that might be useful include append(), charAt(), delete(), insert(), and toString().

Grading Criteria

You can earn up to 25 points on this assignment. The points are allocated as follows

• Follows the coding standard for this assignment. You should refer to this, because there are some specific rules that apply to arrays.(9 points)
• Your Java source file is named Encrypt.java and the class is named Encrypt. (1 point)
• Works correctly (14 points). This includes, but is not limited to:
  • Generates the key table correctly (7 of the 14 points)
    • With keywords where all characters are unique
    • With keywords that contain duplicate characters
  • Encrypts corrrectly (7 of the 14 points)
    • With cleartext that doesn't contain any paired characters
    • With cleartext that requires you to add X's to separate pairs
    • With cleartext that requires an X to be added at the end
    • With cleartext that includes the letter J.
  • Produces the same ciphertext as my program when given the same keyword and cleartext.
• You submit your time log when you are done. (1 point)

Approach

Remember, a good approach to follow when developing software is to do a little bit at a time. Pick a task, get it working, and then save your work. It is important to save your working versions so that when you add something to it that doesn't work, you can easily get back to a known good point.

For this program I strongly suggest writing your psuedocode before trying to write any Java.

I suggest the following course of action:

1. Try to generate the keytable:
   1. First using keywords that do not have any repeated letters (such as "computer" or "chemistry")
   2. Then with keywords that have duplicated characters that need to be removed.
2. Use the keytable to encrypt messages:
   1. First, with simple messages that don't need any X's added or J's replaced.
   2. Then with more complex messages that need these features.

You can verify your program using my sample programs. Use SampleEncrypt to make sure that your ciphertext is the same as mine. Use SampleDecrypt to check that your ciphertext can be decrypted.

Testing

There are a number of things to think about when testing this program:

• Does your keyword have repeated characters?
• Does your cleartext need to have repeated characters separated?
• Does your cleartext need to have an extra character added at the end?
• Does your cleartext include the letter J?

Sample Program

You can run my version of the program by entering the command 'java SampleEncrypt'. Here is example run

Please enter your keyword: pinecone
P I N E C 
O F L S W 
A G M T X 
B H Q U Y 
D K R V Z 
Please enter your clear text: Saddam is in Tikrit
The ciphertext is: OTZAPBGNFEEMFIKNXA

Submitting Your Program

When you are ready to turn your assignment in, use the following command

submit cmps012a-bh.f03 hw6 Encrypt.java

You can submit your program more than once. Later submissions replace earlier ones. Only the last one is saved, and is the one that will be graded.

If you want to see what you have submitted, use the command

peek cmps012a-bh.f03 hw6

Please follow these rules:

1. Only submit your Java source file. Do not submit the Java class file.
2. Do not submit solutions from both partners' accounts. If you do, I won't know which one to grade.

Extra Credit

(10 points)

Write a second program that decrypts your ciphertext and produces the original cleartext. Of course, you won't be able to put back the original whitespace and punctuation, but you should be able to generate the correct text. You also won't be able to tell which I's should be J's - we'll just have to live with that.

The decryption algorithm reverses the steps in the encryption algorithm. For example, if both characters in the digraph are in the same column of the keytable, replace each character with the one above it.

After completing the substitution, you will need to remove the X's that were added because the original cleartext digraph contained duplicate characters.

It is OK to leave an extra X at the end of your cleartext. (Why? Well, what if your original message was "Use the ax"?)

This program should be called Decrypt.java, and can be submitted using the command

submit cmps012a-bh.f03 hw6 Decrypt.java

Here is an example run from my sample program (java SampleDecrypt):

Please enter your keyword: pinecone
P I N E C 
O F L S W 
A G M T X 
B H Q U Y 
D K R V Z 
Please enter your cipher text: otzapbgnfeemfiknxa
The cleartext is: SADDAMISINTIKRITX