CSSE/MA479: Cryptography

Homework 4, due on the date listed on the schedule page

• Implement the DES algorithm given in the textbook. You need to encrypt a 64-bit string for a given number of rounds. You do not need to implement decryption.
• The program must read from a file called desinput.txt the number of iterations, the number of rounds in each iteration (which can vary from 1 to 16), the 64 bit string input message, and the key. For debugging simplicity, the message and the key will each be stored as a single 64-character string without spaces, all on one line (e.g., 10011101101010... ). Here is a sample input file (the key is last).

  You may assume that the input is always 64 bits long: no need to worry about breaking apart long messages.

  When the number of iterations is greater than one, you will use using the cipher-block chaining (CBC) method described in class and the text. Use C₀ = 0. Since our message m is only 64 bits long, we will use it in each round. That is, use m for P₁, P₂, etc. in Figure 4.6 in the text.

  You might be wondering why I am requiring you to encrypt for other than 16 rounds and other than 1 iteration. I will use the ability to change the number of rounds to test correctness. For example, if your answer is incorrect for 16 rounds, but correct for 1, it's probably a bug in how you are generating round keys. (If your code consistently works for 16 rounds, I won't bother checking fewer rounds.)

  I will use the ability to change the number of iterations to test speed and correctness. Speed: I can run it enough times to isolate the runtime of the algorithm from the runtime of I/O. Correctness: I want to make sure that you aren't hard-coding anything specific to a given message or key.

• Output: please only display the message output from the last iteration to the console. Printing output for each of a million iterations will make your program slow and severely I/O-bound.

  If you want to display debugging output, please put a DEBUG flag of some type in your code that defaults to off. This is optional, and I won't use it unless your encryption is incorrect and you would like me to consider you for partial credit.

• In 2011, I tested for speed using a junior HP laptop with Windows 7, 32 bit.
• Submit your project including anything need to compile it (like a Makefile for anyone using C) in the dropbox on Angel.
• If you wish to use a language other than C, C++, Java, Python, or MATLAB, that's fine if you don't mind working with me to install it on my machine.
• Grading:
  • (70%) Correctness of encryption. I will test it by varying the number of rounds (up to 16) for 1 iteration of DES, then for n rounds for a small value of n, to test the CBC.
  • (20%) Efficiency. I will run your program to encrypt a block of text repeatedly (usually between 10^5 and 10^8 times) on my machine (for numIterations), using 16 rounds each, to determine runtimes. In addition, the fastest program will receive 20 bonus points. (Note that due to the CBC requirement, you will not be able to multithread or otherwise parallelize iterations to gain efficiency, but you are welcome to try to parallelize within a round if you like.
  • (10%) Elegance of code, documentation, and style. Can I open it and understand what you are doing? (Some documentation goes a long way... I expect some doc per method, and longer methods should have internal documentation as well. What's obvious to you as the programmer isn't necessarily obvious to another person reading your code - explain why you did what you did.)
• Here is a spreadsheet containing the constants from the book and the key (also used for the example below): DESConstants.xls or DESConstants.csv.

1 iteration (from above): dc67f1c4f0d9a8da 1 1 0 1 1 1 0 0 0 1 1 0 0 1 1 1 1 1 1 1 0 0 0 1 1 1 0 0 0 1 0 0 1 1 1 1 0 0 0 0 1 1 0 1 1 0 0 1 1 0 1 0 1 0 0 0 1 1 0 1 1 0 1 0

2 iterations: c97cde8c10d89bef 1 1 0 0 1 0 0 1 0 1 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 1 1 0 1 1 0 0 0 1 0 0 1 1 0 1 1 1 1 1 0 1 1 1 1

20 iterations: 082b5e9b15a51b95 0 0 0 0 1 0 0 0 0 0 1 0 1 0 1 1 0 1 0 1 1 1 1 0 1 0 0 1 1 0 1 1 0 0 0 1 0 1 0 1 1 0 1 0 0 1 0 1 0 0 0 1 1 0 1 1 1 0 0 1 0 1 0 1

100,000 iterations: bdf34116e8564bae 1 0 1 1 1 1 0 1 1 1 1 1 0 0 1 1 0 1 0 0 0 0 0 1 0 0 0 1 0 1 1 0 1 1 1 0 1 0 0 0 0 1 0 1 0 1 1 0 0 1 0 0 1 0 1 1 1 0 1 0 1 1 1 0