Programming Projects - Spring 2006
project rules and guidelines
Fips guidelines for cryptographic programming
Unit 1 projects received
Unit 2 projects received
Unit 1**********
March 28, April 4 (late date)
all projects in Unit 1 have due dates March 28, April 4. Note that
some of the projects allow teams of two.
1. a)The project here is to write a program which does simple substitution
on the last four bits of each byte of a binary file. There are 16!
possible permutations on the low order nibble. One is shown below
0000 replace with 0010 1010 replace with 1100
0001 0011 1011 1101
0010 0100 1100 1110
0011 0101 1101 1111
0100 0110 1110 0000
0101 0111 1111 0001
0110 1000
0111 1001
1000 1010
1001 1011
which could also be expressed in hex.
b) The above table can be written as 16 ordered pairs in either
decimal or hex and reside in a 'key file'. e.g. (0,2),(1,3),
(2,4)........or (00,01),(01,03).....(FF,01)
b) the binary file is scanned. the substitution, given by the key
file, is applied to various bytes in the plaintext binary file.
The encryption is
only applied to characters between ascii(32) (which is space) and
ascii(127) NOTE..this is a correction!!! previously had specified
ascii(122). Bytes which represent characters not
in this range are ignored and left alone.
c) the encryption should be written to a separate file named
by the user (either on the command line or via menu).
d) a separate program should be written which will print out the
encrypted file, printing a '.' for non-printable characters.
NOTE - several students have inquired about the newline
character. It's an exception and you can treat it as a printable
character.
e) decryption also uses the key file and is only applied to bytes
whose ascii ordinal is between 32 and 127.
I will give you a standard input file for incryption and a
key file.
test file for encryption
key file convert to your own format
estimated difficulty - medium. 50-70 points.
2. In this program you are to write a program which implements our
version of A5 (maybe we'll call it A443). We'll use this system
as a random bit engine. The specs are:
a) there are four right shift registers of lengths:
5,6,11 and 13 (referred to as A,B,C and D)
numbering the bits from the left as 0, the non-zero
taps are at:
A: 1,2 and 4
B: 0,3,5
C: 1,9,10
D: 1,7,12
(Note - these may or maynot be good choices!)
The key bit is determined by exclusive or from the
shifted out bits of the four registers. Whether or
not the clock (shift) or not will depend on bits
x,y,z and w. (x from bit 3 of A, y from bit 2 of B,
z from bit 7 of C and w from bit 3 of D).
In each case if distinguished bit exclusive ored with
x*y*z*w (NOTE correction from x+y+z+w) is 0 then shift
the register owning the distinguished bit.
b) these registers are seeded with a key which will be used
to start the prng process. (I will give you the key).
register seeds
c) Produce a key stream of 2000 bits. Rescalce the FIPS 140-1
tests to see if your system passes. Write out the results
in a report form.
estimated difficulty -- medium 50-80 points
3. The goal of this project is to enhance the automatic simple
substitution solver on our web site. You need to do this
in several steps:
a) Write a program which measures to what degree a file
contains meaningful English text. Perfect text would
correspond to the highest possible measure. Other text
near to English but not perfect might occur due to
noise of some type, of an incomplete break of ciphertext
or other possibilities. How you choose to create this
measure and implement it is up to you but you should
give the matter some thought to make sure the measure
captures what you are trying to capture.
c) You are to integrate your program described above with
the automatated substitution solver on the class web
site (written by Borodkin) so that it returns a proposed
solution with fewer errors than that which a single run
of the program would yield. There are different ways that
you could do this. Here are some ideas you might use:
i) you can run the program several times with the
same sampling text (e.g. moby.txt) and choose
the candidate that yields the highest measure of
English
ii) you can run the program several times with
different sampling text and choose the candidate
that yields the highest measure of English.
iii) you can take two programs which yield the highest
measures and try to use them to yield an improvement.
Whichever path you want to take the result should definitely
yield an improvement to that generated by a single run.
estimated difficulty medium to difficult points 50-85
(team of two is allowed)
4.Write a program which attacks and attempts to solve ciphertext
producted by the 2 by 2
Rubik's cube cipher described below assuming the existence
of known plaintext (without having to anagram.)
. If you need some guidance in formulating the
method of attack talk to me and I will give you a direction to
take. 50-70 points (team of two allowed)
estimated difficulty -- unknown
encryption method --
A block (24 characters)of text is written to the faces of a two by
two Rubik's (four positions to a face) cube (assume the cube is
colorless). Some Rubik twists are applied (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-100). due March 28. (second date April 4)
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.
Also...http://home.everestkc.net/ehess/cube2.html thanks to Aaron
Conran for this link
--------------------------------------------------------------------
--------------------------------------------------------------------
Unit 2********this unit is now complete
due dates...May 9 and May 16 (late date)
5. Recently secure hash methods have drawn attention because,
under computational pressure, they have yielded collisions
which is considered a weakness. The feeling is if collisions
can be discovered then collisions can be engineered. This project
requires you to read ahead and study hash methods. The project
here is to construct a hash method. You can either:
a) design a 'mini Tiger hash' (see p.89 of our text for
description of the Tiger hash. If you choose this option
then talk to me for the design of a suitable mini version.
points 70-100 teams of two allowed on part a--
estimated difficulty: medium
b) a) construct a textual hash method which maps a file of
text to a hash string of 8 hash characters. A text file
here will be considered 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
6. This is primarily not a programming project but a project of
analyzing a cipher. You are the to take the second Zodiac
cipher (unsolved) and translate it to alphabetic characters
then 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.
7. This project is to write a driving program which will break a
"mini-DES" method by key exhaustion . If you are interested in
this project I will give you the ciphertext and the "mini-DES"
code. You will need to write the key generator and efficient
solution checker. For 32 bit keys which are chosen from sequences
of 4 lower case letters there are about half a million keys to
check. This project will give you some appreciation of exhaustive
key attacks on DES.
estimated difficulty: medium 50-75 points.
8. How good of a PRNG is one of our mini-DES methods. It maps
32 bit blocks to 32 bit blocks. We could write
r_{i+1} = E(K,r_{i}) where K the 24 bit key is possibly
fixed. E represents encryption
We can interpret the 32 bit string as an unsigned integer. So
the above iteration is iteratively generating random integers
in the range 0 to 2^32 - 1. Do these integers satisfy
FIPS like criterion?
So this project involves a slight modification to the
mini-DES program (which is written in C) and constructing
some FIPS tests (or using some that you obtain from the
internet) and then writing a summary of your findings.
estimated difficulty - fairly easy 50-70 points
9. In our 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'll receive more points if you do it using a 'bignum'
type library (see the programming projects page).
team of two allowed. 50-100
10. This project is similar to project 6. You will need to
analyze the fourth 'kryptos' panel (the last remaining
unsolved portion) statistically. Your analysis should
include first, second, third order letter frequencies,
n gram entropy computations, IC calculation and whatever
new generalizations you can come up with. Describe the
results of your tests in a well written paper.
40-60 points
----------------------------------------------------------------------