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

email_password
For Columbia email accounts your "email" is just your "University Network ID" and for other email accounts it is your full email address. Your password was assigned to you at the begining of the course.

Currently, there are two types of assignment:

The name of the assignment file gives you the relevant information about the kind of assignment, including the number of points. Currently, all the assignments are constructed by taking a subtext of Moby Dick with all punctuation and spacing stripped off and regular spacing re-introduced.

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

In case you missed a class, Liz has put together some excellent lecture notes which often add many details and links to the actual lecture presentations.

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:

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: 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.

    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):
  8. 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.
  9. 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 2n 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:

Last modified: Mon Aug 18 15:55:52 2003