Programming Projects - Past and Present
date last modified 08/30/06
The "BIG" list
***** Note This is NOT the list for Fall 2006 !! *****
1. Write a program which takes ciphertext as input and performs
Friedman's method of attack on a running key cipher(Assume the
ciphertext has been generated by a running key cipher). Try to
make your program as intelligent as possible. For instance, each
ciphertext character will likely have been generated by several high
frequency pairs. Based on these and neighboring pairs your program
may try and make guesses to determine portions of plaintext and
hence determine portions of the running key. Your program will be
judged to some extent by its effectiveness and the degree to which
the decrypting process is automated.
Points: 60-80
Only one former student has successfully completed this project.
This program must be demoed
2. Write a program which simulates a simple version of a rotor machine.
This machine will only have two rotors. Assume that plaintext input
is in the form of upper case and punctuation and spaces are not
encrypted.
Each input character is encrypted by the first rotor (the particular
ciphertext character corresponding to each plaintext character is
determined by the wheels orientation. It has 26 possible orientations)
The output of the first rotor is input to the second rotor which also
has 26 orientations. The encryption of the character from the first
rotor depends on the orientation of the second rotor. Every time a
character is encrypted the first rotor revolves one position clockwise.
When it makes one full revolution (every 26 encryptions) the second
rotor turns one position clockwise. There are 676 different possible
orientations. The starting orientations of the two rotors serve as the
key. The encryption must be set up so that if A encrypts to W with a
certain key then W encrypts to A with the same key. In that manner, it
is easy to decrypt a message. We just start with the rotors in the
key position and type in the ciphertext. You should allow the user to
specify a key and then encryption and decryption is done by reading
from files (rather than typing from the keyboard). We are using a
simple rotor machine because later we have a project on trying to
break this cipher. Note don't just have the rotors implement a shift
(where the length of the shift is given by the rotors orientation).
A affine substitution by each rotor is ok.
40-50 points
Many students have completed this project.
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.
One student has completed this project as specified above. Some
other students have made partial progress.
This program (3) must be demoed.
4. In this project the plan is to write a program which will aid in
the cryptanalysis of Vigenere type ciphers. A variety of
techniques
are at your disposal: techniques for the determination of key length,
verification of suspected key length by computing IC's for substrings,
etc., determination of key characters by best fit shifts on substrings,
and so on. Whether a definite key length is found or not, possibly
strategies exist for exhausing ngrams of consecutive key characters
to yield meaningful plaintext. All of these techniques should be as
automated as possible. The user should not have to offer very much
interaction. The points will range somewhere in the interval 60-100
depending on how well your program performs on sample Vigenere ciphers.
To some extent the awarding of points for this project and for number
3 above is competitive. The best (most effective) submitted program will
most likely receive the most points (assuming it is accompanied by
adequate documentation).
Five or six students have done a very good job with this project.
(See available software on this site)
This program (4) must be demoed.
5. Write your own version of a Lucifer-like cipher system. The key
length (it should be at least 16) and other specifications are up to you.
You might want to talk to me for some advice and suggestions before
you start this designing and coding this system. The points for this
project are in the range 40-70. three or four students have
successfully completed this cipher.
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.
b) Design and write the code for a "maxi" version of DES. This will
be your attempt to design and implement your version of a "more
secure" DES. The key length should be at least 70 bits and your
program should go through at least 20 rounds. You must plan the
stages of this algorithm very carefully. As in part (a) you must
make sure that decryption is essentially the same as encryption
with the key schedule run backwards. Parts (a) and (b) are somewhat
ambitious. Points can only be awarded to a student for either one or
the other. Don't undertake project 5 unless you have adequate time.
The comment in part a) also applies here. Very few points are
given for a slight modification to DES.
The number of points for this option are between 70-110.
7. Write a program which will break the "two rotor" cipher machine.
You may use any techniques that you like -statistical, exhaustion,
etc. 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.
This program (7) must be demoed.
8. In this small project you need to change, or embellish, or modify
several programs already written in C++. For this project you need
to be a good C++ programmer. The points for this option are between
30 and 60.
9. Write a program using C++ with BigNum or C with LIP (large integer
package) which implements the RSA method. Your program should be
able to implement secrecy, authentication or both. A feature of your
program should be the generation of probabilistic primes.
This program is worth 60-80. For some additional points, send and
receive messages from someone else in class who also done this
project (don't work together on the project though) --use primes of
at least 12 digits.
10. For students who only need between 10 and 40 points in this category
you can acquire points by furnishing me with Internet addresses
(URLs) of cryptographic sites. The number of points that you achieve
will be directly proportional to the number of NEW references. In
other words, its in your interests to get new URLs to me as soon as
possible. Each address should be accompanied by a description of the
material there.
11. This project is a simplified version of project 3 (since past students
have had difficulty implementing project 3).
Write a program (possibly interactive) which attempts to
automate the breaking of a simple affine substitution cipher.
Your program should use techniques other than exhaustive search.
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).
There should be little or no human intervention.
If you are successful at this you might want to consider turning this
project into project 3. 40-70 points.
12. Implement your version of the homophonic cipher described in class.
If you need some additional details see me; but you can also refer
to the handout on the history of the Beale Ciphers.
Your program should be able to encrypt and decrypt. Additional points
are given for programs written in Java. 40-50 points.
13. 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. 30-70 points.
14. Make improvements to the present version of the columnar transposition
tool. Add options to 1) read data into a specified rectangle by
columns 2) permute rows of data 3) 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 points.
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.
16. 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. Minimal credit will be
given to programs that make elementary transformations to reduce to
the regular DES situation. 50-75 points.
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.
50-70 points
18. a)Implement El-Gamal's method using either Bignum (C++) or LIP (C).
To undertake this project now will mean reading ahead. Material
in Stinson can be found starting on page 162. Your program should
be able to correctly encrypt and decrypt using large integers.
Develop your code for this method. Don't use public domain
code. 40-60 points
b) Implement Shanks algorithm (space-time tradeoff) to attack the
Discrete Log problem using Bignum or LIP. Show with computational
examples how this program can break cases of encryption formed
in part a). 30-50 points
19. Write a program using Bignum or LIP (or possibly Java) which
implements RSA using computations in the Galois field GF(2^n)
where n is fairly large. This project is well suited for those
who did project 15. Your program should successfully encrypt and
decrypt text files of any length. 40-60 points.
20. 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.
To start this project now you will need to read ahead in Stinson.
The appropriate material begins on page 191. 40-60 points.
21. Need just a few points. Use Bignum, LIP or Java to implement a
version of the Chinese Remainder Theorem where the program can
either read input from a file or the user can enter it at the terminal.
15-25 points.
22. 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
23. Implement with another class mate the secret key exchange method
of Diffie Hellman. Write the code using some extended integer
package.
The number exchanged should be at least 30 digits.
15-25 points.
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.
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.
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.
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.
26. Write a program which performs anagramming of a given phrase.
That is given a phrase is 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. You will receive bonus points if do
the integration with one of our existing 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.
27. 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
28. In the past students have simulated the workings of a simplified
Enigma rotor machine.(See project 2 on the big list of programming
projects). This simplified machine only had two rotors and didn't
have a plugboard or reflector. Consequently it was easy to break
the ciphers from this machine. This project is more ambitious.
Here you are to simulate the full working enigma as described in
Singh's book (see pages 127-165). If you need to you may make some
simplifying assumptions ---1. There are only three rotors to
choose from - not five. 2. These three rotors are fixed in position
(as opposed to the actual situtation). If you intend to choose this
project then you should read the material mentioned above very
carefully. 70-100 points Several students have done a very good job
on this project.
29. This project is a chance to implement your own cipher system --that
is, some system of your own design. You will need to carefully design
your own original method that is capable of encrypting and decrypting
files. If you choose this option you should submit some plans to me
concerning your design. The number of points here is negotiable,
depending on how ambitious you are. Some possibilities for you to
think about are: nonlinear feedback shift cipher, columnar
transposition of bit blocks, some Java encryption, decryption system
with nice GUI
30. Implement the Rabin cryptosystem that was discussed in class. Use a
a language that permits the use of large integers (Big Integer, LIP,
bignum, etc.) due May 7 60-80
31. On the class website under 'Historical ciphers' there is a
description of Thomas Jefferson's cipher wheel. Implement
a simulation of the cipher wheel so that you can perform encryption
and decryption. Allow for a 'space' as one of the characters
listed across each edge of a wheel (26 letters and a space permuted
along the edge of each ring.)
points (40-60) due April 2
32. Implement a cipher system which first does simple substitution and
then follows the first round of encryption with columnar transposition.
You may use parts of preexisting software on website. Your program
should also be able to decrypt by first doing columnar transposition
applying the proper column permutation writing out the text and then
applying the reverse substitution. (60-80). due April 30.(date
revised from April 2)
This program should be demoed.
33. Write programs which do three dimensional transposition. A block (54
characters)of text is written to the faces of a three by three
Rubik's (nine positions to a face) cube. 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 April 30. (second date May 5) 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.
34. 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).
35. 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.
36. 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
37. 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
38. 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
39. 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
40. 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
41. To get an advance start on this project you will need to do
some advance reading on DES (the Data Encryption Standard).
We already have a mini DES program that has been written in
the past. For reference to past projects see projects 6a, 16
and 37 in the 'Big List'. These references and programs posted
on our site may give you some implementational ideas.
This new project is to write an
even 'smaller' version of the DES. Something we might call
Mini DES. If you are interested in this project you will need
to obtain some xerox material from me.
points 60-80
**NOTE** added later. This program should be able to encrypt and
decipher files.
42. A previous project dealt with constructing a permutation cipher
based on the 3 by 3 Rubik's cube. See project 33 in the 'Big List'.
This project is simpler; it is to construct a cipher on the 2 by
2 Rubik's cube. You system should encipher and decipher.
You will want to see some references on the
Internet concerning Rubik's cube.
points 60-80 see note at top
43 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 methods. You can either:
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). points 50-70
b) a binary hash function which a hash function maps maps a
file to a binary string of 32 bits. points 60-80
see note at top
You will need to design your own hash function or I can furnish some
possibilities for you to implement. You should pay some regard to
a 'secure hash' (see Stinson p. 118)
44 Project 1 in the 'Big List'. If you are interested in this
project I will give you a handout that describes the method.
(team of 2 allowed)
**note** file input expected here. This program can be written
as interactive helper. If so, user can guide progress by
interactive input.
45 Implement the version of the homophonic cipher as it was implemented
in creating the second Beale cipher and as it was described in class.
Recall that integers are determined by the position of words in a
chosen document. If you need some additional details see me; but
you can also
refer to our text on the history of the Beale Ciphers. Your program
should be able to encrypt and decrypt. 40-70 points.
*see note at top*
46 Write a program which attacks and attempts to solve ciphertext
produced by the 2 by 2
Rubik's cube cipher described in project 2 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)
*see note at top*
47 . Can we associate 'signatures' with types of ciphers? Often the
difficulty in solving a cipher results from our not knowing
the encryption technique used. This makes it difficult to mount
an effective attack. The purpose of this project is to do a
thorough statistical study of different types of ciphers - both
at the character and at the bit level - to attempt to develop
signatures for different categories of ciphers e.g. Vigenere,
Hills Cipher, Playfair, columnar transposition, mini DES, DES,
etc. Such a signature would entail possibly: IC, entropy, and
other statistical parameters. Even just a partial success would
prove to be a useful tool. This project could well prove to be
more time consuming that some of the others. Statistics will
needed to be gathered from different types of ciphertext.
50-110 (teams of two allowed)
48 . GSM phone systems (Global Systems for Mobile communications)
use the stream cipher A5 for the generation of keys. A GSM
message is based on 228 bit frames each frame gets encrypted
with a 228 bit key generated by stream. A5 is based on
an irregularly clocked trio of three register LFSR systems where
the registers are pairwise relatively prime (19,22 and 23
respectively). See handout. This project is to create a system
which generates keys in this manner. You are helped out by the
fact that I have LFSR code for registers of user supplied length.
I will supply you with the source of the LFSR code.
So all that needs to be done is modify this code properly and
set up the clocking and resulting key stream.
after you have set up the key stream you need to then check
it using the tests that will be discussed soon in class.
50 - 90 points
49 . If you've made a nice improvement to any of the class 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
50 This project is to convert a text string to a decimal integer
in preparation for the RSA crypto scheme. In the past students
have used an easy but not so efficient method. For example
for the string 'cab' the ASCII translation would be
999798 which was treated as the integer to be processed.
However, the conventional treatment is to convert 99, 97, 98 to
their hex values - then cab becomes a hex string of 6 hex digits-
this is then converted to a decimal integer
so cat becomes 636162 a hex string which becomes the
integer 6*(16)^5 + 2*(16)^4 + 6*(16)^3 + 1*(16)^2 +6*(16)+ 2
this integer would then be encrypted.
Write a function which given a file of text and a user input
block size converts it to a series of decimal integers as
described above.
50-70 points
51 (06s)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.
52 (06s) 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
53 (06s). 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)
54 (06s).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
55 (06s)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
56 (06s). 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.
57 (06s) 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.
58 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
59 (06s) 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
60 (06s) 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
Bonus
1. i)Write a program which input a large prime, tests to see whether
a residue x (mod p) 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.
2. 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
3. In our text there is described a method for solving the 'Discrete
Log Problem' in the case of a prime p for which the prime divisors of
p - 1 are small. Write a program using some form of 'big integer'
class or library which implements this method and give some examples.
20 points
4. Implement, using large integers, the Las Vegas algorithm for finding
the square root of quadratic residues (the case p =1 mod 4) in Z/p.
include the easy case (p = 3 mod 4).
20 points
3. Kennedy's (with Hannebahn's improvement) RSA tools program could use
some improvements. The separate program which does fast encryption
and decryption could be integrated as an option. The whole tool could
be rewritten in Java.
30-50 points
------------------------------------------------------------------------
1. Friedman's running key attack
2. simulate two rotor machine
3. automate the breaking of simple substitution ciphers
4. automate the breaking of Vigenere ciphers
5. implement your own Lucifer like system
6. a) mini DES method
b) maxi DES method
7. break a two rotor machine cipher
8 improvement to existing programs
9. implement the RSA method
10 ........
11. automated breaking of an affine cipher
12. implement a homophonic cipher
13. tool for attacking a homophonic cipher
14. improvements to the columnar transposition tool
15. GF(q^n) calculator.
16. break miniDES by key exhaustion
17. a) probabilistic prime generator
; b) calculate density of primes
18. a) ElGamal's method
b) Shank's space-time tradeoff
19. RSA in GF(2^{n})
20. implement the knapsack cipher
21. Chinese Remainder Theorem
22. Pollard's p-1 method
23. Diffie Hellman key exchange
24. linear algebra in mod system
25. fractionated morse code
cryptanalysis of morse code cipher
morse code redivision
26. anagramming
27. LFSR at bit level
28. modifications to simple substitution and homophonic cipher tools
29. integrate anagramming with columnar transposition tool
30. Rabin's method
31. Jefferson's cipher wheel
32. substitution followed by columnar transposition
33. three dimensional transposition - Rubik's cube
34. one time pad
bit level
character level
35. Playfair
in another language
at the bit level
36. non-linear FSR stream
bit level
character version
37. miniDes to do CBC
38. Steganography
39. Shamir's secret sharing
40. Blum-Blum Shub random number generator
41 Mini DES (not same as miniDES).
42. construct cipher system for 2 x 2 Rubik's cube
43. hash construction methods
44. repeat of project 1
45. document based homophonic cipher
46. see 53
47. signatures of cipher types
48. generate A5 keys
49. improvement of existing tools
50. conversion of text to deciaml for RSA
51 Simple Nibble substitution.
52. revised A5 stream cipher
53. improve automatic simple substitution solver
54. break Rubik's 2 x 2 cipher
55 mini Tiger hash
56. tools for Zodiac cipher
57, break miniDES by exhaustion (same as 16)
58. miniDES as PRNG
59. break Knapsack cipher
60. tools for Kryptos
bonus
1. quadratic residue tester
LVroot2
2. zero knowledge login improvement
3. Discrete log problem solver , small factors of p-1
4. square root of quadratic residue
5. RSA tools
----------------------------------------------------------------