Programming Projects - Spring 2000
1.(=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.
50-65 points (due March 29)
2.(=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. (due March 29)
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. (due May 8)
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. (due May 8)
due March 29
3.(=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. due March 29
4.(=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. Warning- don't select this
project lightly.
This program (3) must be demoed. due May 8
5. 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.
6. 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
7.(=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. See links to the prime number
theorem on this web site.
50-70 points
due May 8
8. (=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.
due May 8
9. 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. This program should both encrypt and
decrypt files. In its best form the program should ask the user
for the desired block size (in characters or bits). Also in its
best form it should ask the user whether they want to enter the
required data (superincreasing vector, modulus, multiplier or
have it generated).
To start this project now you will need to read ahead in Stinson.
The appropriate material begins on page 191. 40-60 points.
These are all the projects that will be assigned this semester.