Programming Projects - Spring 2004
instructions for submitting projects
project rules and guidelines
1. 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).
you may do either part a or b (or both) of problem 2 below.
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.
3. 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) points 50-80
and/or
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).
For this project you can either start from scratch or continue the
development of another students work. There exist programs in Perl
and C if you want to enhance them. If you choose this option talk
to me first. The points depend on how well your program
works -- somewhere between 40 and 60. Extra points for Java
applets. (due March 28) points 40-70
4. 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
5. Project 16 in the "Big List" . Break miniDES by brute force.
This project has been completed by one student in the past.
6. This particular project is not a programming project but
certainly may involve some programming. The project is to
do an in depth study of one of the presently regarded 'famous
unsolved ciphers' e.g. Beale ciphers, Zodiac ciphers, Elgar's
cipher. This study should be quite exhaustive and as complete
as you can make it. You should indicate whether there has been
any progress such as partial solutions, or dead ends and/or false
leads that have discovered. The internet will likely be a very good
source of information. Other sources would be books, journal
papers, accounts from the media, etc. Even though the study
you do is mainly expository you should perform some statistical
tests on the cipher you choose - and indicate your own findings
and opinions. You will need to write up your findings in the
form of a polished paper, double spaced, complete with diagrams,
etc. and at least 12 pages in length.
The number of points assigned will depend on how good a
job you do, but the number assigned will probably be between
50 and 100.
7. Modify the program bitprint.c available on our website (see
cipher breaking tools, general tools) or start from scratch
to compute the n-gram entropy of a file (regarded as a binary
stream). n and the file are
the user's input. You will need to decide how to handle
less than complete ngrams at the end of the file. You will
also need to test your program will some files that I will
supply you.
see a matlab related group of codes for similar type problems
points - between 40 and 70.
8. 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
9. 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
10. 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
11. 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
Bonus
A. i)Write a program which input a large p tests to see whether
a residue x 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.
B. 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