Assignment Instructions

Each of you has your own assignment directory. You access your directory by typing in the directory URL directly. The name of the directory is of the form

Currently, there are two types of assignment:

• programming and encryption assignments
• ciphertext cracking assignments

All work is supposed to be your own, and we will be checking for plagiarism using a strong software tool. Working with friends on cryptanalysis assignments is very much encouraged BUT you should not look at each other's ciphertext. Instead, you should practice together on practice files available at the following directories

• Practice directory no. 1
• Practice directory no. 2
• Practice directory no. 3
• Practice directory no. 4
• Practice directory no. 5

Programming Assignments:

You should implement the algorithm assigned in class. Usually this will mean extending the classes Kernel and Key, but sometimes other classes will be written. You will be given the name of the algorithm in class. For example, if you are to implement the "Linear" algorithm, your file names will be "Linear.java" and "LinearKey.java" and these should be inside a directory named by your email and part of the package "webcrypt.crypto.email" (email varies from student to student). To help us identify your code during testing, you should over-ride the toString() method of your Kernel including your email as part of the output. For further programming details checkout README.txt in your webcrypt\crypto directory. After finishing your Java program, you will need to demonstrate its efficacy by encrypting the file using the keytext in the last part of the filename. For example, if the plaintext filename is "2_encryptLinear_10pts_7_13.txt" you will need to encrypt the file using linear monoalphabetic substitution with a = 7 and b = 13.

Physical hand-in. In the beginning of the class during which the assignment is due, bring printouts of the following:

• The classes that you implemented (don't worry about files such as WebBrowser.java that you only made slight changes to)
• The original plaintext file
• The resulting ciphertext file

Electronic hand-in. In addition, we would like to test your code. You should email the classes that you implemented to zeph@cs.columbia.edu and to sbe2001@columbia.edu. Please don't send us the plaintext and ciphertext files. Instead, you should post these files somewhere on your homepage, and let us know in the email the URL of the files. We will then test your code against your posted files.

Finally:

1. The email should be sent by the due-time of the assignment.
2. Don't forget to make sure your algorithm works by decrypting your ciphertext to ensure you get the original plaintext.

Ciphertext Cracking Assignments:

The instructions are similar to the above. You print and also post the ciphertext and plaintext and email us your URL's for the posts. You should also find the key used (or at least an equivalent key) and email this to us, as well as writing it on your hand-in. You should explain in your hand in, how you figured out the answer. You're only guaranteed to get 100% credit if you use the method discussed in class but if you get the right answer with other means, you are still guaranteed to get a very high score. The are "tricks" you can do by using the fact that the plaintext is known to be part of Moby Dick to your advantage. In certain cases, you may be able to deduce small parts of the text by pure analysis and be able to figure out the rest of the text by placing those parts in the context of Moby Dick. The stripped down version of Moby Dick could be helpful here. Again, if you use a trick to solve the answer you may not get full credit, but you will get almost all credit. If your trick is especially ingenious, you may get even more than 100%!!! Again, you must explain how you cracked the ciphertext to receive full credit.

Hints for specific assignments

1. For Caesar there is no key!
2. Remember, you're supposed to implement the reverseKey() method inside of your LinearKey so that decryption becomes encryption using the reverse key. Don't forget to throw a KeyCreationException when an attempt is made to creat a non-invertible LinearKey.
3. Moby Dick's frequency tables should help crack your problem:
   • monograph frequencies
   • top 100 bigraph frequencies
   • top 100 trigraph frequencies
   Also, don't forget that you can try out partial decrypts with MonoAlphabetic by pre-appending your inverse keyword with '!' and encrypting.
4. Remember to insert an X between repeated letters in the plaintext that would form a bigram, except when you have XX in which case the second X becomes KS. For example EE XX X becomes EX EX XX becomes EX EX XK S
5. First off, don't forget to delete the first two lines of the file before trying to decrypt.

   Matlab is very useful for working with matrices and can help you with this assignment. You can access it from any cunix prompt. Here are some Matlab constructs to try out.

   • m = [ [1 2] ; [3 4] ] ---defines the square matrix containing 1, 2, 3, 4
   • det(m) ---compute the determinant
   • m = mod(m,2) ---applies (mod 2) to all the entries
   • m*n ---multiplies matrices m and n (assuming you defined n before)
   Unfortunately, matlab doesn't invert modular matrices. However, in the webcrypt package the following command will attempt to invert the matrix m defined above, modulo 26:

   java webcrypt.math.ModSquareMatrix 2 26 1 2 3 4

   The first argument is the matrix dimension 2, the second argument is the modulus 26, and the last four arguments are the matrix elements.
6. The following text contains a lot of ideas for cryptographic algorithms: Handbook of Applied Cryptography by Menezes, Oorschot and Vanstone. You are allowed to download the text and print one copy out for personal use.
   If you're not sure that your crypto method is "original enough" just email me a description of your algorithm and I'll let you know.
7. Remember to delete the first three lines of the Enigma ciphertext.
   Cracking Enigma using Turing's method involves the following steps:
   1. Create a labeled correspondence graph using the given crib.
   2. Write down the cycle information of the non-trivial 2-connected components.
   3. Use the cycle information inside of the Bombe simulator to find the possible rotor settings.
   4. Use the plug analyzor to deduce the cable settings sequentially.
   Some nice Enigma sights (but you don't have to worry about the turnovers or different wheel choices and ordering for your cracking assignment):
   • Good essay explaining everything
   • Another thorough explanation
8. • The following cunix command should help you figure when the file was created to within about a second: ls --full-time -l
   • wget can download the file without changing its timestamp
   • the Timestamp Analyzor (just added to webcrypt) can convert dates to long integers in the same manner as Java's System.currentTimeMillis()
   • In all likelihood the timestamp is within 10 seconds of the key creation time.
   • There is a little program that you can MODIFY to search through the relevant keyspace for your ciphertext example.
   • WARNING: You cannot use a brute force attack (e.g. CrackMyElGamal) on CUNIX or NEWCUNIX as it is too CPU intensive!!! I got the warning:

     Compilation cpu Limit Exceeded at Tue Aug  5 11:35:04

     when I ran it on newcunix after only 10 minutes. So you'll have to do this on your personal computer.
   • Jeff Lin's fix: The 251 ET lab (251 MUDD) is open Monday through Friday from 10am to 5pm. Last I remember, an extended account is needed to log in to those machines. I quickly looked at the students enrolled in the class and everyone seems to have an extended account, including the Summer Session students, so logins shouldn't be a problem for people. It runs Java 1.4 on each machine locally, but you have to come in during normal business hours!!!
   • If using a variant of my program, you'll want to make sure and capture all the output. The easy way to do it is with the redirect command e.g.:

     java CrackMyElGamal >> output.txt

     But this may cause you problems if you don't want to wait till the program finishes to see if you've found the key. The following procedure is one solution to this problem. If you run the command java CrackMyElGamal at the command line, you are risking using up your entire terminal buffer. So you should run it in an application that captures all the output. For example EMACS:
     1. In emacs run the program with the following command sequence:
        1. go into the same direcotory where CrackMyElGamal.class resides (use CTRL-x f to open the file CrackMyElGamal.java)
        2. ESC-x, then type the word: compile (ENTER)
        3. type: java CrackMyElGamal (ENTER)
     2. To switch to the compiling buffer do the following:
        1. CTRL-x, then type: 4b
        2. type the name of the buffer: *compilation* (ENTER)
        3. You can search for plain text (e.g. the bigraph TH) with the command
           CTRL-s, then type: TH
        When the compilation finishes, be sure to save!!!!!!!!!!!
9. Extra Credit Cracking: There are about 10 available extra-credit ciphertext cracking assignments. They were created using your "Create Your Own" projects applied to Moby Dick. Each filename explains how many points it is worth and which program was used to create the ciphertext. When you succeed in cracking an example, you should email us immediately as only the first cracker gets to keep the extra credit points. There are two types of cracking proglems:
   1. Standard cracking problems in the extraCreditCracks directory. These are worth 10 points each.
   2. Known plaintext attack problems in the extraCreditCracks/withcrib directory. The crib was created by putting the following string:

      String crib = "AHAB IS WAY OUT OF CONTROL AND NEEDS TO RELAX\n"

      at the very beginning of the file.
   3. Points: you get 10 pts. for cracking the standard ciphertext and 5 pts. for cribbed ciphertext. 10 pts. max per algorithm that you break. To get your points you must be able to deduce the keyword (in certain cases you may be able to get partial credit without the keyword).
   CURRENT CRACKING STATUS: Anything listed is out of play.
   • As of Tue, 5 Aug 2003 03:29:49 Walid and Jeff's regular ciphertext and cribbed ciphertext have been cracked by Alan.
   • As of Sat, 9 Aug 2003 16:21:18 Shohei's regular ciphertext and cribbed ciphertext have been cracked by Chun.
   • As of Sat, 9 Aug 2003 16:41:26 Chun's regular ciphertext and cribbed ciphertext have been cracked by Alan.
10. Final projects: Unless you tell me otherwise, you're supposed to implement RSA.java in a way that closely resembles the ElGamal.java code that I've handed out. Additionally, there are three choices for the second part of the project:
    1. Modes project
    2. JCE2webcrypt project
    3. a third choice that you should have contacted me about by now...
    Let's give some hints for each of the two 2nd parts:
    1. Modes hints:
       • The following reference may be useful: Explanation of different cipher modes used in DES (thanks Liz for link)
       • Found that this project was a breeze? For 5 EC points, you can implement the new OCB mode. It uses arithmetic in the field of size 2ⁿ which you may find baffling. If you're interested, I'll gladly talk it over with you.
       • I sent an email out explaining how Modes is supposed to interact with your RSA code, and giving some details about converting between BigIntegers and hexadecimals and ASCII.
    2. JCE2webcrypt hints:
       • An email that I sent out about it.
       • Java Cryptography Extension guide
       • List of supported Cihphers with standard names
       • Example of password based encryption. NOTE: you don't have to use any salt for this assignment, so use the method I detailed in class and ignore the salty code.