Programming Projects - Spring 2009
last modified 02/17/09
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 ...second date
-----------------------------------------------------------------
Programming projects for CMSC 443 Spring 2009
This is Unit #1 -- there will be a Unit #2
due date for Unit #1 --
no projects accepted from Unit #1 after
1. 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.
2. 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
3. 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
4. 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.
Note-----
genetic algorithms tutorial
genetic algorithms postscript tutorial
genetic algorithms
5. 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
6. This is an automated 'break a random number generator' project.
In his paper ' "Cracking" a Random Number Generator' James Reeds
demonstrates via an example a method for cracking a congruential
random number generator (Cryptologia, 1977). Your program should
automate his approach. I will give a sequence of random numbers
which your method should be able to crack.
60 - 75 points
Unit 1 ends here
************************************************************************
------------------------------------------------------------------------
************************************************************************
Unit 2 begins here
Unit 2 is now complete
1. 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
-------------------------------------------------------------------
2. This project is in two parts.
. a) The purpose of this project is to map 'chains' for a two rotor
simplified version of the Enigma rotor machine. (I will give you the
code for this machine). Knowledge of these chains will help us break
the two rotor machine in a manner similar to the breaking of the
Enigma during World War II. (Since there are only two rotors it is
also possible to break this system by brute force). You should write
the chains that you compute to an output file.
first version of 2 rotor machine
b) The second part of this project is to use your work in part a to
attack the two rotor machine. I will give you some ciphertext to
try and break.
ciphertext
teams of two allowed 50-90 points
--------------------------------------------------------------------
3. Implement the method of Vigenere at either
a) character format or b) binary format. using a CBC mode.
For those doing character encryption you will need to figure out how you want to do
this and will need to figure out how to do decryption and make sure that decryption
works. If you choose this option I will give you a key and a file to encrypt as a
baseline. file and the key Vigenere key is XYTBMUYT If you use IV then set it to
AAAAAAAA.
baseline file
NOTE -- this project does not deal with the breaking of the Vigenere cipher.
If you do a) you only need encrypt alphabetic characters... punctuation spaces, and
numeric values need not be encrypted
If you do b) you should use exclusive or instead of character shift part a --
teams of two allowed 40-75 points
------------------------------------------------------------------------
4. Write a program which implements the probabilistic method of
finding a square root of a quadratic residue in the case of
p congruent to 1 mod 4 (see handout). (Use large integer
arithmetic).mi
40 - 60 points
---------------------------------------------------------------------
5. In a 1995 paper by Frank Rubin. He discusses a method for authenticating a message using quadratic residues.
http://www.mastersoftware.biz/crypt002.htm
You should implement this method (using large integer arithmetic).
40-60 teams of two allowed
6. In this project you are to create a version of CCM (authenticated encryption) which integrates with the mini AES created in Unit 1. If you didn't write a version of mini-AES I can provide you with one. Presently CCM is only defined for block ciphers with block size of 128. You will need to make some modifications. Here are some relevant links.
http://en.wikipedia.org/wiki/CCM_mode
csrc.nist.gov/groups/ST/toolkit/BCM/documents/comments/800-38_Series-Drafts/CCM/RW_CCM_comments.pdf
http://dic.academic.ru/dic.nsf/enwiki/1069186
50-85 points teams of two allowed
7. In this project you need to implement the Pollard rho algorithm for
solving the DLP (Discrete Log Problem). I have a handout that
you can read and there are many references available from Google.
You will need to use large integer arithmetic.
40 - 60 points
********** bonus points *******************
******************************************************
In a previous semester students wrote a 'mini' version of a hash function.
It produces 64 bit hashes. In this project you are to try and find
collisions in the mini hash. You may use any techniques that
you can think of and you might want to do a little research to see
how collisions have been produced with respect to other hashes..
You will need to produce strings that collide.
points 10-35 depending on success of program
link to python hash code
----------------------------------------------------------------------