Programming Projects - Spring 2008
last modified 02/17/08
project rules and guidelines
Fips guidelines for cryptographic programming
Unit 1 projects received
Unit 2 projects received
-------------------------------------------------------------------
Guidelines for grading cryptography projects...
Documentation (10 percent)
proper indentation, easy to read style
ample use of comments
program run (20 percent)
no errors at compile time
no warnings at compile time
no runtime errors, no logic errors
program style (12 percent)
easy to understand, good variable names
supporting README document, clear and precise
directions
program organization, file organization, no mystery code
program validity (58 percent)
produces correct results
produces ALL results it should
doesn't produce any spurious results
program meets project specifications
program appears distinct from others
program not found "as by web search"
elegant or clever solution
------------------------------------------------------------------------
------------------------------------------------------------------
Unit 1**********'on time' due date March 25...second date April 1
-----------------------------------------------------------------
Programming projects for CMSC 443 Spring 2008
This is Unit #1 -- there will be a Unit #2
due date for Unit #1 -- March 25......late date April 1
no projects accepted from Unit #1 after April 1
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
2. 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.
3.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.
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. 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
6. 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.
------------------------------------------------------------------
Unit 2**********'on time' due date . ..second date
-----------------------------------------------------------------
Note-----
genetic algorithms tutorial
genetic algorithms postscript tutorial
genetic algorithms
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
2. 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
3. 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
4. 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
5. 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 Points -------------------------------------
***For students who have maxed out or will come close to
maxing out in this category ****
. 1. Various programs exist on our website (and I ahve 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.
2. 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
----------------------------------------------------------------------