MA 479 / CSSE 479: Cryptography
Homework 1 problems inspired by Computer Science

Rose-Hulman Institute of Technology
A joint effort of the
Department of Mathematics
and the Department of Computer Science & Software Engineering
Spring term, 2003-2004

• Use any language and environment you wish. Please check with me if you have any questions about what features of the language or environment you may use. In particular, please do not use pre-packaged matrix calculation routines.
• The user interface is up to you.
• Turn in the source and object code of the program, and any supporting materials, to these drop boxes.
• Make sure you include clear instructions on how the code is to be run! Most of the points will be determined based on whether the program performs correctly on test cases.

The non-programming problems you may turn in to the drop boxes or on paper.

Drop box submissions are due at midnight on the due date. Paper submissions are due in class or in the box outside my office by 5:00 p.m.

1. [2 points.] Create software that can encrypt and decrypt using an additive cipher.

2. [2 points.] There are at least two ways in practice to decrypt a "3x+2" affine cipher: table lookup and subtract 2 and divide by 3 (mod 26). Give advantages and disadvantages of each from an implementation point of view. Extend your answer to a general "ax+b" affine cipher.

3. [4 points.] Create software that can encrypt and decrypt using an affine cipher.

4. [4 points.] Write a program that can perform a letter frequency attack on an additive cipher without human intervention. Your software should produce possible plaintexts in rough order of likelihood. It would be good if your user interface allowed the user to specify "give me the top 10 possible plaintexts".

5. [2 points, after doing the previous problem.] Modify your program to work on an affine cipher.

6. [12 points.] Write a program that can perform a letter frequency attack on any monoalphabetic subsitution cipher without human intervention. Your software should produce possible plaintexts in rough order of likelihood. It would be good if your user interface allowed the user to specify "give me the top 10 possible plaintexts".

7. [3 points. (Originally 2 points.)] Using the big-Oh notation, how fast is encrypting in a Hill cipher, as a function of the length n of the ciphertext and the dimension m of the key? How about decrypting?

8. [4 points.] Create software that can encrypt and decrypt using a 2 by 2 Hill cipher.

9. [4 points, after doing the previous problem.] Modify your program to work on an m by m Hill cipher.

10. [6 points.] Create software that can perform a fast known plaintext attack on a Hill cipher, given the dimension m. How fast are your algorithms, as a function of m?

11. [2 points, after doing the previous problem.] Same as previous, but without knowing m.