Programming Projects - Past and Present   

The 'Rules' for programming projects

projects assigned Spring 2000 projects for 2001 Instructions for turning in your projects download lip.c lip.h tarred and zipped version of lip Documentation for LIP (large integer package) Documentation on Bignum - compiling with the Integer Class bignum.h C and assember source code for bignum example of Bignum program one line summary of projects site devoted to prime numbers

The complete list (this is not the list for spring 2001) 1. Write a program which takes ciphertext as input and performs Friedman's method of attack on a running key cipher(Assume the ciphertext has been generated by a running key cipher). Try to make your program as intelligent as possible. For instance, each ciphertext character will likely have been generated by several high frequency pairs. Based on these and neighboring pairs your program may try and make guesses to determine portions of plaintext and hence determine portions of the running key. Your program will be judged to some extent by its effectiveness and the degree to which the decrypting process is automated. Points: 60-80 Only one former student has successfully completed this project. This program must be demoed 2. Write a program which simulates a simple version of a rotor machine. This machine will only have two rotors. Assume that plaintext input is in the form of upper case and punctuation and spaces are not encrypted. Each input character is encrypted by the first rotor (the particular ciphertext character corresponding to each plaintext character is determined by the wheels orientation. It has 26 possible orientations) The output of the first rotor is input to the second rotor which also has 26 orientations. The encryption of the character from the first rotor depends on the orientation of the second rotor. Every time a character is encrypted the first rotor revolves one position clockwise. When it makes one full revolution (every 26 encryptions) the second rotor turns one position clockwise. There are 676 different possible orientations. The starting orientations of the two rotors serve as the key. The encryption must be set up so that if A encrypts to W with a certain key then W encrypts to A with the same key. In that manner, it is easy to decrypt a message. We just start with the rotors in the key position and type in the ciphertext. You should allow the user to specify a key and then encryption and decryption is done by reading from files (rather than typing from the keyboard). We are using a simple rotor machine because later we have a project on trying to break this cipher. Note don't just have the rotors implement a shift (where the length of the shift is given by the rotors orientation). A affine substitution by each rotor is ok. 40-50 points Many students have completed this project. 3. Write a program (possibly interactive) which attempts to automate the breaking of a simple substitution cipher. The user may have occasion to steer the decryption process but for the most part the program should make intelligent choices for a sequence of single or multiple character substitutions and in some manner measure its progress toward the final solution (possibly by looking for key words of plaintext or by statistical indicators). Human intervention is allowed but should be minimal. Your program should, for example, be able to solve shift substitutions. Can it solve cipher one? Your program will be tested on several simple substitution ciphers. This project is somewhat challenging and previous attempts by students have been disappointing with a couple of exceptions. Several years ago a student was able to write a program which worked quite well. The number of points possible for this project is in the range 75-100 depending on how well your program works. Warning: no points given for a program which simply acts like a tool for substitution ciphers similar to the one already given out. No student has completed this project as specified above. Some students have made partial progress. This program (3) must be demoed. 4. In this project the plan is to write a program which will aid in the cryptanalysis of Vigenere type ciphers. A variety of techniques are at your disposal: techniques for the determination of key length, verification of suspected key length by computing IC's for substrings, etc., determination of key characters by best fit shifts on substrings, and so on. Whether a definite key length is found or not, possibly strategies exist for exhausing ngrams of consecutive key characters to yield meaningful plaintext. All of these techniques should be as automated as possible. The user should not have to offer very much interaction. The points will range somewhere in the interval 60-100 depending on how well your program performs on sample Vigenere ciphers. To some extent the awarding of points for this project and for number 3 above is competitive. The best (most effective) submitted program will most likely receive the most points (assuming it is accompanied by adequate documentation). Five or six students have done a very good job with this project. (See available software on this site) This program (4) must be demoed. 5. Write your own version of a Lucifer-like cipher system. The key length (it should be at least 16) and other specifications are up to you. You might want to talk to me for some advice and suggestions before you start this designing and coding this system. The points for this project are in the range 40-70. three or four students have successfully completed this cipher. 6. a) Design and write the code for a "mini" version of DES. The key length should be in the neighborhood of 32 bits. You will need to design : permutations, expansions , S boxes, construction of subkeys, etc. It will be a version of DES on a smaller scale. Remember that decryption should be essentially the same algorithm with the key schedule run backwards. You should work the design out carefully before you start any programming. Minimal points are given for a slight modification to DES or a program which is easily transformable to DES -for instance, starting with a 32 bit key, expanding it to 56 bits and then using DES. Points for this option are between 60-90. b) Design and write the code for a "maxi" version of DES. This will be your attempt to design and implement your version of a "more secure" DES. The key length should be at least 70 bits and your program should go through at least 20 rounds. You must plan the stages of this algorithm very carefully. As in part (a) you must make sure that decryption is essentially the same as encryption with the key schedule run backwards. Parts (a) and (b) are somewhat ambitious. Points can only be awarded to a student for either one or the other. Don't undertake project 5 unless you have adequate time. The comment in part a) also applies here. Very few points are given for a slight modification to DES. The number of points for this option are between 70-110. 7. Write a program which will break the "two rotor" cipher machine. You may use any techniques that you like -statistical, exhaustion, etc. In order to demonstrate the effectiveness of your program, I will provide you with some cipher text from a two rotor machine. I will provide some insight into the "wiring" of the machine--but you must find the key. If you are interested in pursuing this option you should talk to me first. This program is worth 40-70. This program (7) must be demoed. 8. In this small project you need to change, or embellish, or modify several programs already written in C++. For this project you need to be a good C++ programmer. The points for this option are between 30 and 60. 9. Write a program using C++ with BigNum or C with LIP (large integer package) which implements the RSA method. Your program should be able to implement secrecy, authentication or both. A feature of your program should be the generation of probabilistic primes. This program is worth 60-80. For some additional points, send and receive messages from someone else in class who also done this project (don't work together on the project though) --use primes of at least 12 digits. 10. For students who only need between 10 and 40 points in this category you can acquire points by furnishing me with Internet addresses (URLs) of cryptographic sites. The number of points that you achieve will be directly proportional to the number of NEW references. In other words, its in your interests to get new URLs to me as soon as possible. Each address should be accompanied by a description of the material there. 11. This project is a simplified version of project 3 (since past students have had difficulty implementing project 3). Write a program (possibly interactive) which attempts to automate the breaking of a simple affine substitution cipher. Your program should use techniques other than exhaustive search. For the most part, the program should make intelligent choices for a sequence of single or multiple character substitutions and in some manner measure its progress toward the final solution (possibly by looking for key words of plaintext or by statistical indicators). There should be little or no human intervention. If you are successful at this you might want to consider turning this project into project 3. 40-70 points. 12. Implement your version of the homophonic cipher described in class. If you need some additional details see me; but you can also refer to the handout on the history of the Beale Ciphers. Your program should be able to encrypt and decrypt. Additional points are given for programs written in Java. 40-50 points. 13. Write a program tool which will aid in making a serious attack on a homophonic cipher. Your tool can implement any number of ideas, but should certainly include important ngram statistics. This project is quite open ended. 30-70 points. 14. Make improvements to the present version of the columnar transposition tool. Add options to 1) read data into a specified rectangle by columns 2) permute rows of data 3) read data out of a rectangle to a file by columns.--Make any other improvements to give this program more flexibility in the future. Make sure that all of your modifications work correctly. 40 points. 15. Write a program which is a GF(q^n) calculator. This should be an interactive program which allows the user to perform basic calculations in the finite fields GF(q^n). For the purposes of this project n can be taken to be two. The project then reduces to a certain kind of arithmetic on bit strings. You should be able to do addition, subtraction, multiplication, exponentiation, and find multiplicative inverses. 40-55 points. 16. This project is to write a driving program which will break a "mini-DES" method by key exhaustion . If you are interested in this project I will give you the ciphertext and the "mini-DES" code. You will need to write the key generator and efficient solution checker. For 32 bit keys which are chosen from sequences of 4 lower case letters there are about half a million keys to check. This project will give you some appreciation of exhaustive key attacks on DES. Minimal credit will be given to programs that make elementary transformations to reduce to the regular DES situation. 50-75 points. 17. The purpose of this project is to compute the approximate density of primes. It is an attempt to answer the questions 'how many primes are there between 1 and n?' or 'asymptotically how many primes are there between m and n, where m and n are very large integers?' The project consists of two parts: a) write a probabilistic prime generator in C++ (using BIGNUM). Use the Miller-Rabin algorithm discussed in Stinson to determine probabilistic primes. b) and use the program of part a) to calculate the density of primes between 1 and 10e12 and test against the prediction of the famous prime number theorem. 50-70 points 18. a)Implement El-Gamal's method using either Bignum (C++) or LIP (C). To undertake this project now will mean reading ahead. Material in Stinson can be found starting on page 162. Your program should be able to correctly encrypt and decrypt using large integers. Develop your code for this method. Don't use public domain code. 40-60 points b) Implement Shanks algorithm (space-time tradeoff) to attack the Discrete Log problem using Bignum or LIP. Show with computational examples how this program can break cases of encryption formed in part a). 30-50 points 19. Write a program using Bignum or LIP (or possibly Java) which implements RSA using computations in the Galois field GF(2^n) where n is fairly large. This project is well suited for those who did project 15. Your program should successfully encrypt and decrypt text files of any length. 40-60 points. 20. Write a program using Bignum or LIP (or possibly Java) which implements the Knapsack Cipher (Merkle-Hellman). Your block size should be at least 64 bits. To start this project now you will need to read ahead in Stinson. The appropriate material begins on page 191. 40-60 points. 21. Need just a few points. Use Bignum, LIP or Java to implement a version of the Chinese Remainder Theorem where the program can either read input from a file or the user can enter it at the terminal. 15-25 points. 22. I have a version of Pollard's p-1 method written in C using LIP which is not working correctly. This program needs to be debugged and overhauled. If you are interested in this project you should talk to me first. 15-25 points 23. Implement with another class mate the secret key exchange method of Diffie Hellman. Write the code using some extended integer package. The number exchanged should be at least 30 digits. 15-25 points. 24. Several students in the past have written applications which perform linear algebra in a mod system. However these efforts can definitely be improved on. Write a program which allows the user to read in a matrix, matrices, or linear system and specify a modulus. The user should be able to specify that he/she wants: matrix multiplication or solution of a linear system or or the inverse (if it exists) of a given matrix with respect to a mod system that is he/she specifies. If the matrix is singular an appropriate message should be given. Results should be able to be written out to a file. 25. For this project you may do any of a,b, or c independently. However if you are going to do b) you should probably do a) first. a) Write a program which implements the method of 'fractionated Morse code'. Use a 0 for . (dot), 1 for (dash), and 2 for | (separator). Your program should be able to encrypt and decrypt files or plaintext from the keyboard. 40 points. b) Write a program which attempts to break a cipher of the type in part a. See the handout for suggestions.(40-50 points) The number of points will depend in large part how successful your program is. Your program should expect input from a ascii or binary file. c) Morse code redivision- plaintext in morse code can be manipulated to possible yield latent messages. As an example....take the word THREE. In morse code this is 1 0000 010 0 0 which can be rewritten (redivisioned) 1000 001 000 which is the morse for BUS. Write a program which will convert a document to morse then look for 'meaningful' submessages. You might consider this project in conjunction with project 5.(You might want to see the book 'Times 17' by Gareth Penn, and his theories about the infamous Zodiac killer). points depend on how well your program works -- somewhere between 40 and 60. Extra points for Java applets. 26. Write a program which performs anagramming of a given phrase. That is given a phrase is should construct all (most) meaningfull anagrams of that phrase. Some programs of this type can be found on the internet. In order to get a good idea of what is required for this project you should investigate some of these anagramming demonstations. The length of the phrase should be up to at least 20 characters. A successful program could be integrated with our columnar transposition tools. You will receive bonus points if do the integration with one of our existing columnar transposition tools. The number of points awarded will depend on how successful your program is. The number should vary between 40 and 80. Extra bonus points for Java applets. 27. Implement LFSR encryption and decryption at the bit level. Your implemention should closely follow the details of the method as it was discussed in class and is discussed in the text. Your program should read from a file and produce an encrypted binary file (not a text file of 0's and 1's - that's too inefficient with space.) 40 - 50 points