Programming Projects - Past and Present
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