Programming Projects - Spring 2001
1. a) Write a program which attempts to break a fractionated Morse
code type of cipher. A handout will be given out with
suggestions.At least one program exists on our web site which
encrypts and decrypts in this manner. (60-70) 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. (due March 28)
b) 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. (due March 28)
2.
a) 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 q 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, 10 pts
subtraction, 10 pts
multiplication, 20 pts
exponentiation, 20 pts
multiplicative inverses. 20 pts
(due March 28)
b) Use the results of a) to implement one of the methods of encryption
that we have studied this semester (or will study).Use GF(2^n) instead
of the integers mod n. See me for a discussion of points.
(due March 28)
3. a)Several programs exist on our website which are tools for helping solve
simple substitution ciphers. In this project you are to either alter
one of these programs (recommended) or start fresh and augment the
output. Presently these programs list the frequency (count and %) of
the ciphertext. You are make changes so that it also prints out the
'social index' of each cipher text character. To see what I mean by
this term it's best to refer to Singh's book page 22. For a given
character Ch a table should be given (as on page 22) which lists
the number of times Ch is adjacent to the other alphabetic characters.
Such an index might be useful for the breaking of these ciphers and
might be of use, for instance, in project 4. (50 points).
(due March 28)
b)The same modification and improvement needs to be made to the
homophonic cipher tool. The following modifications need to be
made.
i) revise program so that single digit numbers can be counted
ii) print out social index for each number, or at least those
with highest index
iii) highest freq. trigrams should be indexed.
(due March 28) (50 points)
4.
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. Warning- don't select this
project lightly.
This program (3) must be demoed. due May 7
5. There are several program tools on our web site which help break
columnar transposition ciphers. In this project you are too
strengthen this tool by building in an anagramming ability. This
option should allow the user to anagram rows or columns of the
ciphertext which has been written into rectangular form. You may
use anagram tools which have already been written but they must be
integrated into one of the existing columnar transposition tools.
The number of points awarded will depend on how successful your
program is. The number should vary between 50 and 100.
(due May 7)
6. 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 (due March 28)
7. 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(due May 7)
8. Implement the attack on running key ciphers as discussed in the recent
class handout. This project is more fully described as #1 in the
list of all projects ("the complete list").
9. 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
this is all the projects that will be assigned this semester
more bonus projects may be assigned
bonus projects
1. 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
2. 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