Programming Projects - Past and Present   
                                               date last modified 02/17/09
      
projects for Spring 2010
project due dates for this semester
short description of 'big list'
Info on Big Number Packages
tarred and zipped version of lip

The 'Rules' for programming projects

The "BIG" list ***** Note This is NOT the list for Spring 2009 ! *****
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. One student has completed this project as specified above. Some other 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 28. In the past students have simulated the workings of a simplified Enigma rotor machine.(See project 2 on the big list of programming projects). This simplified machine only had two rotors and didn't have a plugboard or reflector. Consequently it was easy to break the ciphers from this machine. This project is more ambitious. Here you are to simulate the full working enigma as described in Singh's book (see pages 127-165). If you need to you may make some simplifying assumptions ---1. There are only three rotors to choose from - not five. 2. These three rotors are fixed in position (as opposed to the actual situtation). If you intend to choose this project then you should read the material mentioned above very carefully. 70-100 points Several students have done a very good job on this project. 29. This project is a chance to implement your own cipher system --that is, some system of your own design. You will need to carefully design your own original method that is capable of encrypting and decrypting files. If you choose this option you should submit some plans to me concerning your design. The number of points here is negotiable, depending on how ambitious you are. Some possibilities for you to think about are: nonlinear feedback shift cipher, columnar transposition of bit blocks, some Java encryption, decryption system with nice GUI 30. Implement the Rabin cryptosystem that was discussed in class. Use a a language that permits the use of large integers (Big Integer, LIP, bignum, etc.) due May 7 60-80 31. On the class website under 'Historical ciphers' there is a description of Thomas Jefferson's cipher wheel. Implement a simulation of the cipher wheel so that you can perform encryption and decryption. Allow for a 'space' as one of the characters listed across each edge of a wheel (26 letters and a space permuted along the edge of each ring.) points (40-60) due April 2 32. Implement a cipher system which first does simple substitution and then follows the first round of encryption with columnar transposition. You may use parts of preexisting software on website. Your program should also be able to decrypt by first doing columnar transposition applying the proper column permutation writing out the text and then applying the reverse substitution. (60-80). due April 30.(date revised from April 2) This program should be demoed. 33. Write programs which do three dimensional transposition. A block (54 characters)of text is written to the faces of a three by three Rubik's (nine positions to a face) cube. Some Rubik twists are applied (their type and order is the key). The data is written out is some order. Next block is read in, etc. Your program should be able to encrypt and decrypt. (80-100). due April 30. (second date May 5) This program should be demoed. A set of notes on the mathematics of Rubik's cube can be found at : http://web.usna.navy.mil/~wdj/rubik_nts.htm thanks to Jeff Walton for this link. 34. Write a program which implements the one time pad at either (1) the character level or (2) the bit level. With respect to the character implementation you will need to figure out how you are going to (randomly) randomly shift the printing (keyboard) characters (don't assume that you only dealing with lower or uppercase letters). You can assume the input file consists of entirely of printable ASCII characters -- the output file should be of the same type. Whichever alternative you choose you should pay particular attention to your (pseudo) random number generator. It should be relatively secure (not a linear congruential generator for instance). This will probably require you to do a little outside reading to look into secure random number generators (try google for example). The random key (of character or bit type) should be written to a keyfile along with some identifier for the file that has just been encrypted. (number of points ....50-80). 35. 2. a) Do you know another language? This project is to implement the Playfair cipher in the font of another (alphabet based) language. Some options are: Russian, Hebrew, Arabic, Thai. If you've never done it, you will obviously need to get acquainted with dealing with fonts of other languages. You may assume the input file contains only letters which you may assume are of the same type (e.g. lower case) and that there are no other punctuation signs or if there are they may be ignored. b).Implement the Playfair cipher at the bit level as was discussed in class. Your table should be (square) and at least 256 by 256 and hold (in some order) all 2 to the sixteenth possible bit strings of length 16. Creating and filling this table will be the main challenge of part b. 36. In class we discussed the LFSR stream cipher. We also discussed a generalized, possibly non-linear version. Here you are to design and program your own version of a non-linear version. You will need to design a functin E_B which defines new registers from the contents of the old one. Your method should both encrypt and decrypt. You can do this project at one of two possible levels. a) the bit level -- here the register should hold at least sixteen bits. The key stream bit will fall from the least significant bit position. All bits in the register are redefined using the function E_B. Shifting in the register is also allowed. The key stream is exclusive 'ored' with the plaintext bit. b) a character version. You may imagine each position (cell) in the register holding an ASCII character. New characters are defined from old ones in a way that you must design. The rightmost character is used in each step to shift the plaintext character. points 50-80 37. Modify the miniDES on our website ('student software development') to give the option of encrypting by CBC (cipher block chaining). You will need to become familiar enough with the code to make (hopefully) some relatively minor changes. points - negotiable 38. This project will require you to do some reading and learning on your own outside of class. It involves creating a steganography application. Steganography refers to the technique of hiding information (possibly encrypted) inside of some informational medium such as, for instance, graphics or sound files. There are several good places to start reading. Two of them are: Disappearing Cryptography, second ed. by Peter Wayner (paperback) Morgan Freeman Hiding in Plain Site by Eric Cole (paperback) John Wiley and Sons In addition, there is steganographic software on the internet including source code. Your development should be independent of this code although you can use some existing procedures as tools. 50 - 90 points 39. Implement Shamir's secret sharing scheme using a large number number package such as LIP, MIRACL, or using java. Input would be the master key, w the number of users and t the threshold value. Output should be the w shadows. You should then demonstate that t shadows are sufficient to reconstruct the master key. 30-60 points 40. Implement the Blum-Blum Shub Generator (pseudo random bit generator) using a large integer library. It is given as follows: let n = p*q the product of two large primes. Given a seed s_0 which is a quadratic residue in Z/n. compute the sequence s_i by successive squaring mod n. s_(i+1) = (s_i * s_i) mod n then z_i = s_i mod 2 your program should generate at least 1000 bits andwrite the bits z_i to a file. points 30-50 41. To get an advance start on this project you will need to do some advance reading on DES (the Data Encryption Standard). We already have a mini DES program that has been written in the past. For reference to past projects see projects 6a, 16 and 37 in the 'Big List'. These references and programs posted on our site may give you some implementational ideas. This new project is to write an even 'smaller' version of the DES. Something we might call Mini DES. If you are interested in this project you will need to obtain some xerox material from me. points 60-80 **NOTE** added later. This program should be able to encrypt and decipher files. 42. A previous project dealt with constructing a permutation cipher based on the 3 by 3 Rubik's cube. See project 33 in the 'Big List'. This project is simpler; it is to construct a cipher on the 2 by 2 Rubik's cube. You system should encipher and decipher. You will want to see some references on the Internet concerning Rubik's cube. points 60-80 see note at top 43 Recently secure hash methods have drawn attention because, under computational pressure, they have yielded collisions which is considered a weakness. The feeling is if collisions can be discovered then collisions can be engineered. This project requires you to read ahead and study hash methods. The project here is to construct a hash methods. You can either: a) construct a textual hash method which maps a file of text to a hash string of 8 hash characters. A text file here will be considered a file of upper/lower alphabetic characters, digits, and the characters + and / ( a base 64 format). points 50-70 b) a binary hash function which a hash function maps maps a file to a binary string of 32 bits. points 60-80 see note at top You will need to design your own hash function or I can furnish some possibilities for you to implement. You should pay some regard to a 'secure hash' (see Stinson p. 118) 44 Project 1 in the 'Big List'. If you are interested in this project I will give you a handout that describes the method. (team of 2 allowed) **note** file input expected here. This program can be written as interactive helper. If so, user can guide progress by interactive input. 45 Implement the version of the homophonic cipher as it was implemented in creating the second Beale cipher and as it was described in class. Recall that integers are determined by the position of words in a chosen document. If you need some additional details see me; but you can also refer to our text on the history of the Beale Ciphers. Your program should be able to encrypt and decrypt. 40-70 points. *see note at top* 46 Write a program which attacks and attempts to solve ciphertext produced by the 2 by 2 Rubik's cube cipher described in project 2 assuming the existence of known plaintext (without having to anagram.) . If you need some guidance in formulating the method of attack talk to me and I will give you a direction to take. 50-70 points (team of two allowed) *see note at top* 47 . Can we associate 'signatures' with types of ciphers? Often the difficulty in solving a cipher results from our not knowing the encryption technique used. This makes it difficult to mount an effective attack. The purpose of this project is to do a thorough statistical study of different types of ciphers - both at the character and at the bit level - to attempt to develop signatures for different categories of ciphers e.g. Vigenere, Hills Cipher, Playfair, columnar transposition, mini DES, DES, etc. Such a signature would entail possibly: IC, entropy, and other statistical parameters. Even just a partial success would prove to be a useful tool. This project could well prove to be more time consuming that some of the others. Statistics will needed to be gathered from different types of ciphertext. 50-110 (teams of two allowed) 48 . GSM phone systems (Global Systems for Mobile communications) use the stream cipher A5 for the generation of keys. A GSM message is based on 228 bit frames each frame gets encrypted with a 228 bit key generated by stream. A5 is based on an irregularly clocked trio of three register LFSR systems where the registers are pairwise relatively prime (19,22 and 23 respectively). See handout. This project is to create a system which generates keys in this manner. You are helped out by the fact that I have LFSR code for registers of user supplied length. I will supply you with the source of the LFSR code. So all that needs to be done is modify this code properly and set up the clocking and resulting key stream. after you have set up the key stream you need to then check it using the tests that will be discussed soon in class. 50 - 90 points 49 . If you've made a nice improvement to any of the class tools you've used this semester or believe that you can make an interesting improvement --then that will be worth some points. 30-60 points 50 This project is to convert a text string to a decimal integer in preparation for the RSA crypto scheme. In the past students have used an easy but not so efficient method. For example for the string 'cab' the ASCII translation would be 999798 which was treated as the integer to be processed. However, the conventional treatment is to convert 99, 97, 98 to their hex values - then cab becomes a hex string of 6 hex digits- this is then converted to a decimal integer so cat becomes 636162 a hex string which becomes the integer 6*(16)^5 + 2*(16)^4 + 6*(16)^3 + 1*(16)^2 +6*(16)+ 2 this integer would then be encrypted. Write a function which given a file of text and a user input block size converts it to a series of decimal integers as described above. 50-70 points 51 (06s)a)The project here is to write a program which does simple substitution on the last four bits of each byte of a binary file. There are 16! possible permutations on the low order nibble. One is shown below 0000 replace with 0010 1010 replace with 1100 0001 0011 1011 1101 0010 0100 1100 1110 0011 0101 1101 1111 0100 0110 1110 0000 0101 0111 1111 0001 0110 1000 0111 1001 1000 1010 1001 1011 which could also be expressed in hex. b) The above table can be written as 16 ordered pairs in either decimal or hex and reside in a 'key file'. e.g. (0,2),(1,3), (2,4)........or (00,01),(01,03).....(FF,01) b) the binary file is scanned. the substitution, given by the key file, is applied to various bytes in the plaintext binary file. The encryption is only applied to characters between ascii(32) (which is space) and ascii(127) NOTE..this is a correction!!! previously had specified ascii(122). Bytes which represent characters not in this range are ignored and left alone. c) the encryption should be written to a separate file named by the user (either on the command line or via menu). d) a separate program should be written which will print out the encrypted file, printing a '.' for non-printable characters. NOTE - several students have inquired about the newline character. It's an exception and you can treat it as a printable character. e) decryption also uses the key file and is only applied to bytes whose ascii ordinal is between 32 and 127. I will give you a standard input file for incryption and a key file. test file for encryption key file convert to your own format estimated difficulty - medium. 50-70 points. 52 (06s) In this program you are to write a program which implements our version of A5 (maybe we'll call it A443). We'll use this system as a random bit engine. The specs are: a) there are four right shift registers of lengths: 5,6,11 and 13 (referred to as A,B,C and D) numbering the bits from the left as 0, the non-zero taps are at: A: 1,2 and 4 B: 0,3,5 C: 1,9,10 D: 1,7,12 (Note - these may or maynot be good choices!) The key bit is determined by exclusive or from the shifted out bits of the four registers. Whether or not the clock (shift) or not will depend on bits x,y,z and w. (x from bit 3 of A, y from bit 2 of B, z from bit 7 of C and w from bit 3 of D). In each case if distinguished bit exclusive ored with x*y*z*w (NOTE correction from x+y+z+w) is 0 then shift the register owning the distinguished bit. b) these registers are seeded with a key which will be used to start the prng process. (I will give you the key). register seeds c) Produce a key stream of 2000 bits. Rescalce the FIPS 140-1 tests to see if your system passes. Write out the results in a report form. estimated difficulty -- medium 50-80 points 53 (06s). The goal of this project is to enhance the automatic simple substitution solver on our web site. You need to do this in several steps: a) Write a program which measures to what degree a file contains meaningful English text. Perfect text would correspond to the highest possible measure. Other text near to English but not perfect might occur due to noise of some type, of an incomplete break of ciphertext or other possibilities. How you choose to create this measure and implement it is up to you but you should give the matter some thought to make sure the measure captures what you are trying to capture. c) You are to integrate your program described above with the automatated substitution solver on the class web site (written by Borodkin) so that it returns a proposed solution with fewer errors than that which a single run of the program would yield. There are different ways that you could do this. Here are some ideas you might use: i) you can run the program several times with the same sampling text (e.g. moby.txt) and choose the candidate that yields the highest measure of English ii) you can run the program several times with different sampling text and choose the candidate that yields the highest measure of English. iii) you can take two programs which yield the highest measures and try to use them to yield an improvement. Whichever path you want to take the result should definitely yield an improvement to that generated by a single run. estimated difficulty medium to difficult points 50-85 (team of two is allowed) 54 (06s).Write a program which attacks and attempts to solve ciphertext producted by the 2 by 2 Rubik's cube cipher described below assuming the existence of known plaintext (without having to anagram.) . If you need some guidance in formulating the method of attack talk to me and I will give you a direction to take. 50-70 points (team of two allowed) estimated difficulty -- unknown encryption method -- A block (24 characters)of text is written to the faces of a two by two Rubik's (four positions to a face) cube (assume the cube is colorless). Some Rubik twists are applied (their type and order is the key). The data is written out is some order. Next block is read in, etc. Your program should be able to encrypt and decrypt. (80-100). due March 28. (second date April 4) This program should be demoed. A set of notes on the mathematics of Rubik's cube can be found at : http://web.usna.navy.mil/~wdj/rubik_nts.htm thanks to Jeff Walton for this link. Also...http://home.everestkc.net/ehess/cube2.html thanks to Aaron Conran for this link 55 (06s)Recently secure hash methods have drawn attention because, under computational pressure, they have yielded collisions which is considered a weakness. The feeling is if collisions can be discovered then collisions can be engineered. This project requires you to read ahead and study hash methods. The project here is to construct a hash method. You can either: a) design a 'mini Tiger hash' (see p.89 of our text for description of the Tiger hash. If you choose this option then talk to me for the design of a suitable mini version. points 70-100 teams of two allowed on part a-- estimated difficulty: medium b) a) construct a textual hash method which maps a file of text to a hash string of 8 hash characters. A text file here will be considered a file of upper/lower alphabetic characters, digits, and the characters + and / ( a base 64 format) You should try to make your hash as secure as possible. It shouldn't be immediately obvious how to create collisions, etc. points 50-70 estimated difficulty: easy to medium 56 (06s). This is primarily not a programming project but a project of analyzing a cipher. You are the to take the second Zodiac cipher (unsolved) and translate it to alphabetic characters then analyze it using some of the tools on our web site and any other tools that you might want to use. This analysis should include at the least: frequency analysis, IC, entropy, and attempts at solution by various tools. You will need to give a short 15 minute talk to the class detailing your efforts and to write the results up in a report form. 57 (06s) 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. estimated difficulty: medium 50-75 points. 58 How good of a PRNG is one of our mini-DES methods. It maps 32 bit blocks to 32 bit blocks. We could write r_{i+1} = E(K,r_{i}) where K the 24 bit key is possibly fixed. E represents encryption We can interpret the 32 bit string as an unsigned integer. So the above iteration is iteratively generating random integers in the range 0 to 2^32 - 1. Do these integers satisfy FIPS like criterion? So this project involves a slight modification to the mini-DES program (which is written in C) and constructing some FIPS tests (or using some that you obtain from the internet) and then writing a summary of your findings. estimated difficulty - fairly easy 50-70 points 59 (06s) In our text book there is a section on a method for breaking the knapsack cipher. You will need to read that section carefully and most likely some other sources in order to write a program which attempts to break the knapsack cipher. You'll receive more points if you do it using a 'bignum' type library (see the programming projects page). team of two allowed. 50-100 60 (06s) This project is similar to project 6. You will need to analyze the fourth 'kryptos' panel (the last remaining unsolved portion) statistically. Your analysis should include first, second, third order letter frequencies, n gram entropy computations, IC calculation and whatever new generalizations you can come up with. Describe the results of your tests in a well written paper. 40-60 points 61.(06f)The goal of this project is to enhance the automatic simple substitution solver on our web site. You need to do this in several steps: a) Write a program which measures to what degree a file contains meaningful English text. Perfect text would correspond to the highest possible measure. Other text near to English but not perfect might occur due to noise of some type, of an incomplete break of ciphertext or other possibilities. How you choose to create this measure and implement it is up to you but you should give the matter some thought to make sure the measure captures what you are trying to capture. c) You are to integrate your program described above with the automatated substitution solver on the class web site (written by Borodkin) so that it returns a proposed solution with fewer errors than that which a single run of the program would yield. There are different ways that you could do this. Here are some ideas you might use: i) you can run the program several times with the same sampling text (e.g. moby.txt) and choose the candidate that yields the highest measure of English ii) you can run the program several times with different sampling text and choose the candidate that yields the highest measure of English. iii) you can take two programs which yield the highest measures and try to use them to yield an improvement. Whichever path you want to take the result should definitely yield an improvement to that generated by a single run. estimated difficulty medium to difficult points 50-85 (team of two is allowed) 62. Write a program which attacks and attempts to solve ciphertext producted by the 2 by 2 Rubik's cube cipher described below assuming the existence of known plaintext . You may use an anagramming approach if you wish or if you need some guidance in formulating an alternative method of attack talk to me and I will give you a direction to take, 50-70 points (team of two allowed) estimated difficulty -- unknown encryption method -- A block (24 characters)of text is written to the faces of a two by two Rubik's (four positions to a face) cube (assume the cube is colorless). Some Rubik twists are applied (their type and order is the key). The data is written out is some order. Next block is read in, etc. A set of notes on the mathematics of Rubik's cube can be found at : http://web.usna.navy.mil/~wdj/rubik_nts.htm thanks to Jeff Walton for this link. Also...http://home.everestkc.net/ehess/cube2.html thanks to Aaron Conran for this link 63, Write a program which performs anagramming of a given phrase. That is, given a phrase it 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. 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. (This project relates to project 2 but you do not need to also work on 2) points 40-70 64. Our text discusses the 'Autokey cipher' (see p.46-50). In this project you are to write a program which attacks and solves an autokey cipher. One of the factors taken into consideration in evaluating your program will be how well it performs on a particular autokey cipher. points 50-70 5. This project is in two parts. You can do 'a' without going on to 'b'. a) The purpose of this project is to map put 'chains' for a two rotor simplified version of the Enigma rotor machine. (I will give you the code for this machine). Knowledge of these chains will help us break the two rotor machine in a manner similar to the breaking of the Enigma during World War II. (Since there are only two rotors it is also possible to break this system by brute force). You should write the chains that you compute to an output file. points 40-80 links first version of 2 rotor machine second version of 2 rotor machine b) The second part of this project is to use your work in part a to attack the two rotor machine. I will give you some ciphertext to try and break. points 40-60 65. Implement the method of Vigenere at either a) character format or b) binary format. NOTE -- this project does not deal with the breaking of the Vigenere cipher. If you do a) you only need encrypt alphabetic characters... punctuation spaces, and numeric values need not be encrypted If you do b) you should use exclusive or instead of character shift part a -- 40-55 points part b -- 50-65 points . In a previous semester students wrote a 'mini' version of the Tiger 66. hash (see Wikipedia for a description http://en.wikipedia.org/wiki/Tiger_(hash) ) It produces 80 bit hashes. In this project you are to try and find collisions in the mini Tiger hash. You may use any techniques that you can think of and you might want to do a little research to see how collisions have been produced with respect to other hashes.. 50-75 points 67 . For those students who finished project 65 above, here is an opportunity to earn 30 additional points by modifying their programs. The idea is to modify their Vigenere ciphering systems by putting them in a CBC mode. For those doing character encryption you will need to figure out how you want to do this and will need to figure out how to do decryption and make sure that decryption works. If you choose this option I will give you a key and a file to encrypt as a baseline. file and the key Vigenere key is XYTBMUYT If you use IV then set it to AAAAAAAA. 30 points 68 Construct a textual hash method which maps a file of text to a hash string of 8 hash characters. A text file here will be considered a file of upper/lower alphabetic characters, digits, and the characters + and / ( a base 64 format) You should try to make your hash as secure as possible. It shouldn't be immediately obvious how to create collisions, etc. points 50-70 estimated difficulty: easy to medium 69 Implement the ADFGVX cipher (see page 374 of Singh's text for a description). Your program should be able to encrypt and decrypt. If you are interested in this project I will give a file for encryption and decryption (you should include a script. You can neglect any conversion to Morse code and just produce plaintext output. points 50-70 estimated difficulty : easy to medium check here for key and file details 70 . Implement ONE of the following four ciphers ----- You can only get credit for one of the options below. You may find these methods defined and discussed at www.quadibloc.com/crypto/pp1322.htm Of course, you are also encouraged to read about at other sites also -- a) The 'Bifid' cipher of Delastelle (somewhat related to the Playfair cipher) 50 points b) The Trifid Cipher (enhanced version of the above) 50 points c) The Straddling Checkerboard another variation 50 points d) The 'Vic' cipher. more complicated and probably the most secure of the class of hand ciphers 80 points 71. 1. Write a program which will break the "two rotor" cipher machine. You may use statistical techniques similar to those described in one our texts and in a handout that I will give you. (don't use brute force methods -- that's already been done) 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. estimated difficulty is medium. This program must be demoed. for code of brute force attack www.cs.umbc.edu/~stephens/crypto/SOFTWARE/ebombe.c for two rotor code www.cs.umbc.edu/~stephens/crypto/SOFTWARE/mgurskirotor.perl 72. 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. Additional points may be given to programs written in Matlab which display some statistical results visually. 30-70 points. 73.Make improvements to one of the present versions of the columnar transposition tools (or write your own from scratch). Add options to 1) read data into a specified rectangle by rows then: (a) permute columns by some designated permutation key and then (b) permute rows of data by some second designated permutation key and then c) 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 - 50 points. 74. In class we discussed the LFSR stream cipher. We also discussed a generalized, possibly non-linear version. Here you are to design and program your own version of a non-linear version. You will need to design a functin E_B which defines new registers from the contents of the old one. Your method should both encrypt and decrypt. You can do this project at one of two possible levels. a) the bit level -- here the register should hold at least sixteen bits. The key stream bit will fall from the least significant bit position. All bits in the register are redefined using the function E_B. Shifting in the register is also allowed. The key stream is exclusive 'ored' with the plaintext bit. b) a character version. You may imagine each position (cell) in the register holding an ASCII character. New characters are defined from old ones in a way that you must design. The rightmost character is used in each step to shift the plaintext character. points 50-80 75. If you've made a nice improvement to any of the class cipher breaking tools you've used this semester or believe that you can make an interesting improvement --then that will be worth some points. 30-60 points 76. This is primarily not a programming project but a project of analyzing one of two ciphers. You are to choose either the second Zodiac or the fourth Kyptos cipher both of which are unsolved. If you choose the Zodiac cipher you must first translate it to alphabetic characters. Whichever cipher you choose you need to analyze it using some of the tools on our web site and any other tools that you might want to use. This analysis should include at the least: frequency analysis, IC, entropy, and attempts at solution by various tools. You will need to give a short 15 minute talk to the class detailing your efforts and to write the results up in a report form. The emphasis here is on analysis -- with some description of background. The emphasis is not on background. 77. 1. A design mini-version of AES exists and can be found on the web. See http://findarticles.com/p/articles/mi_qa3926/is_200210/ai_n9129484 Also see .. .http://findarticles.com/p/articles/mi_qa3926/is_200210/ai_n9129484/print For information on the full article check BlackBoard. The purpose of this project is to write the code for this design. It is important that it be your own program and not a down-loaded version. It should be complete with documentation and include sample runs. It should both encrypt and decrypt and be easy to use. Teams of two are allowed. 80 - 110 points 78. a) In one text book there is a section on a method for breaking the knapsack cipher . You will need to read that section carefully and most likely some other sources in order to write a program which attempts to break the knapsack cipher. You can take the original method using lattices (see Stamp) or using a genetic algorithm (Stillman). If you are interested in the later then I will give you a copy of Stillman's paper. You'll receive more points if you do it using a 'bignum' type library (see the programming projects page). team of two allowed. 50-100 points b) Another alternative is to try to improve an existing version of the lattice method so that it is more efficient. This existing version is written in C++. 40-80 points depending on degree of improvement 79. In the past two students wrote an automated simple substitution solver using a genetic algorithm. It works fairly well but is quite slow. It needs a good 'tuning up'. This project involves taking their program and making changes that decrease it's overall running time. This project contains two programs written in python. Part of the challenge will be finding the correct 'population size' to work with. 50-75 points 80. The first part of this project is to convert any file to one of base 64 format. You may use any programs that you can find on the web for this portion of the project or you can obtain some code from me. The second part of the project is to construct a textual hash method which maps a file of text to a hash string of 8 hash characters (base 64 chars). A text file here will be (as a result of part 1) a file of upper/lower alphabetic characters, digits, and the characters + and / ( a base 64 format) You should try to make your hash as secure as possible. It shouldn't be immediately obvious how to create collisions, etc. points 50-70 estimated difficulty: easy to medium 81. Write programs which do three dimensional transposition. A block (6n*n characters) of text is written to the faces of an n by n Rubik's (n*n positions to a face) cube. Some Rubik twists are applied. You will need to define them since this is not the standard 3 by 3 Rubik's cube. (their type and order is the key). The data is written out is some order. Next block is read in, etc. Your program should be able to encrypt and decrypt. (80-120). This program should be demoed. A set of notes on the mathematics of Rubik's cube can be found at : http://web.usna.navy.mil/~wdj/rubik_nts.htm thanks to Jeff Walton for this link. *************************************************************************************** *************************************************************************************** Bonus 1. i)Write a program which input a large prime, tests to see whether a residue x (mod p) is or is not a quadratic residue ii) Write a program which implements LVroot2 using a large integer package. Given input x it should use i) to test if it is a quadratic residue ; if so it should find the square roots. do both 30-40 points. 2. The zero-knowledge login simulation needs to be improved with i) large integer package ii) new square root required after each successful (right hand side) test. iii) choose initially whether logon is legitimate or not -- if so, choose quadratic residue from stored table of large integers - if not, user must enter values.. 30-40 points 3. In our text there is described a method for solving the 'Discrete Log Problem' in the case of a prime p for which the prime divisors of p - 1 are small. Write a program using some form of 'big integer' class or library which implements this method and give some examples. 20 points 4. Implement, using large integers, the Las Vegas algorithm for finding the square root of quadratic residues (the case p =1 mod 4) in Z/p. include the easy case (p = 3 mod 4). 20 points 3. Kennedy's (with Hannebahn's improvement) RSA tools program could use some improvements. The separate program which does fast encryption and decryption could be integrated as an option. The whole tool could be rewritten in Java. 30-50 points 4. Various programs exist on our website (and I have others) which are written in C++ and use the BigNum library. That library is not accessible to us. Some of these programs with minor rewriting can be compiled and run with C using gmp. This project allows you to accumulate bonus points by converting these programs. The number of points will depend on how many you convert that successfully are able to execuate. 5. . 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 ------------------------------------------------------------------------ 1. Friedman's running key attack 2. simulate two rotor machine 3. automate the breaking of simple substitution ciphers 4. automate the breaking of Vigenere ciphers 5. implement your own Lucifer like system 6. a) mini DES method b) maxi DES method 7. break a two rotor machine cipher 8 improvement to existing programs 9. implement the RSA method 10 ........ 11. automated breaking of an affine cipher 12. implement a homophonic cipher 13. tool for attacking a homophonic cipher 14. improvements to the columnar transposition tool 15. GF(q^n) calculator. 16. break miniDES by key exhaustion 17. a) probabilistic prime generator ; b) calculate density of primes 18. a) ElGamal's method b) Shank's space-time tradeoff 19. RSA in GF(2^{n}) 20. implement the knapsack cipher 21. Chinese Remainder Theorem 22. Pollard's p-1 method 23. Diffie Hellman key exchange 24. linear algebra in mod system 25. fractionated morse code cryptanalysis of morse code cipher morse code redivision 26. anagramming 27. LFSR at bit level 28. modifications to simple substitution and homophonic cipher tools 29. integrate anagramming with columnar transposition tool 30. Rabin's method 31. Jefferson's cipher wheel 32. substitution followed by columnar transposition 33. three dimensional transposition - Rubik's cube 34. one time pad bit level character level 35. Playfair in another language at the bit level 36. non-linear FSR stream bit level character version 37. miniDes to do CBC 38. Steganography 39. Shamir's secret sharing 40. Blum-Blum Shub random number generator 41 Mini DES (not same as miniDES). 42. construct cipher system for 2 x 2 Rubik's cube 43. hash construction methods 44. repeat of project 1 45. document based homophonic cipher 46. see 53 47. signatures of cipher types 48. generate A5 keys 49. improvement of existing tools 50. conversion of text to deciaml for RSA 51 Simple Nibble substitution. 52. revised A5 stream cipher 53. improve automatic simple substitution solver 54. break Rubik's 2 x 2 cipher 55 mini Tiger hash 56. tools for Zodiac cipher 57, break miniDES by exhaustion (same as 16) 58. miniDES as PRNG 59. break Knapsack cipher 60. tools for Kryptos bonus 1. quadratic residue tester LVroot2 2. zero knowledge login improvement 3. Discrete log problem solver , small factors of p-1 4. square root of quadratic residue 5. RSA tools ----------------------------------------------------------------