CSC 281 Introduction to Cryptography: Assignments
The Rosetta Stone.
A historically important crib.
-
The assignments will be posted here after the day's class,
along with the due date.
Assignments are due at the beginning of class on the due date.
In general, no credit will be allowed for for late assignments.
Turn what you have in in for partial credit.
For cryptanalysis problems, there will generally be at least a week, so
if you start early, there should be no problem.
I plan to drop the lowest couple of assignments to cover occasional lapses.
-
Assignments will be of several sorts, including problem sets from the text,
and cryptanalysis projects that may or may not include a programming
component
For programming, you can use any platform/language you want,
but C/linux might be an advantage, because if I ever write and hand out
any source code, that is what it will be in.
(Not that you should have any trouble translating anything.)
-
Document every stage of your work, especially for cryptanalysis.
Hand in all scratch work, computer code, etc.
Little or no credit will be given just for getting the answer right.
Credit will be based on demonstrated understanding, creativity, effort,
results, and presentation.
If you find a program on the web that cracks ciphers of form "ABC"
and feed it the assignment "decrypt x", and hand in the answer, you
won't get (nearly) as much credit as if you wrote the cracker yourself, or
assembled it creatively out of other pieces.
-
For cryptanalysis and programming projects, I expect a well organized
report-style writeup that describes in detail what you did, why you did it,
and what the results were. This includes negative results.
Even if you fail to crack a particular ciphertext, you can still get
plenty of credit for an imaginative, well executed, and well documented
approach. Scratch work and computer code, if requested
should be appended to the main
writeup with appropriate pointers.
-
Attribute ANY work that is not your own, including software off the
web, text cribbed from other sources, etc.
You are encouraged to look for resources, but not to the extent that
it negates the point of the assignment.
This is sometimes a fine line, especially in programming assignments.
I will try to be specific as to what I expect you to write
as a minimum. If in doubt, ask.
In any case, use of UN-attributed material is plagiarism, and a violation
of the University's academic honesty policy.
-
You are encouraged to discuss general techniques and specific approaches
to general problems with your fellow students, or anyone else.
Unless specifically directed in an assignment, however, you are not to
share code you have written, or your written solutions to specific
problems.
Thursday August 31, 2017
- Topics: Introductory material, modulo arithmetic, simple ciphers.
- Reading assignment: Katz and Lindell, Chapter 1; Singh, Chapter1.
- Homework: Aristocrat cryptogram handed out in class. Hand in a writeup
describing what you tried, what worked, and what didn't.
Append all scratch work.
Due Tuesday, September 5, 2017
Tuesday, September 5, 2017
- Topics: Simple ciphers, breaking them,
probability, statistics of English.
- Reading Assignment: Singh, Chapter 2
- Homework, encryption:
Write a program (or adapt material found on the web)
to perform monoalphabetic encryption and decryption using a permutation
derived from a specified key phrase (Singh page 13).
For encryption, remove all non-alphabetic characters,
and print the output in groups of 5.
For decryption, just print one long string of lower case
letters, as that is easier to read than groups.
Encrypt two samples of English prose with at least 200 characters using
different keys.
Prose can be anything that is not offensive, or engineered to be
difficult to crack. For the next assignment, you will crack each other's
encryptions, so you might consider what you need to do this as you
are doing this program. Disallowed will be any tool that is fully
automated or that uses a dictionary, (unless you write it yourself).
Hand in short writeup, with encryption and decryption runs.
Also attach copies of the encryptions on separate sheets
of paper without keys or plaintext (provide these in the main writeup).
The program should not take long to write. If you adapt material you
find on the web, you must document your source.
Disallowed sources are other people associated with the class
(students, TA, prof).
Due Tuesday, September 12, 2017 (and be ready to crack a challenge by
Thursday Sept. 14).
Thursday, September 5, 2017
- No Class. Work on permutation encryption and decryption assignment.
Tuesday, September 12, 2017
- Topics: Probability and statistics.
Statistical attacks on affine and monalphabetic substitution
ciphers
- Cryptanalysis Assignment:
Decrypt the substitution cipher given to you today.
Provide a writeup detailing how you solved the problem (or not)
along with your solution (if any).
Hand in all scratch work, intermediate steps if you used a program,
and any programs you used. In other words, document your progress.
If you used tools you did not write yourself, document it.
Breaking into account of the student who generated the ciphertext
it is NOT an allowed method of attack.
As before, fully automated tools are disallowed.
Due Thursday, Sept. 14, 2017
- Due today: Aristocrat cryptogram; Problem set 1;
mono-alphabetic encryption assignment.
Sample solution to aristocrat cryptogram
A whole pile of aristocrat cryptograms (without solutions)
should you feel like doing puzzles.
Thursday, September 14, 2017
- Topics: Transposition ciphers and permutations.
- Reading assignment: Singh, chapter 2,
- Encryption assignment:
Write or find software to do block transposition encryption
with block of 16 characters using a key derived from a key phrase.
Document the source of any software you did not write yourself.
Since 16! is about 2 * 10^13, this should be reasonably secure
against brute-force attack.
Encrypt two segments of English prose at least 256 letters each,
(with spaces, punctuation, capitalization removed as usual)
and print the output in groups of 16.
Make sure the last group is filled by adding some random prose.
As before, hand in an additional two pages containing the
two encrypted messages with no other information.
Note that your main writeup should also contain the encrypted text.
Due Tuesday, Sept 19.
Schedule your time.)
Tuesday, September 19, 2017
- Topics: Polyalphabetic substitution and the Vigenere cipher
- Reading assignment: Singh, chapter 3.
- Decryption assignment:
Decrypt the transposition cipher given to you in class
You will probably need to write or get hold of some tools that allow
you to propose a trial (partial) transposition in one group,
and automatically see the result of that transposition in all the
other groups. As before, you can look for some help on the web,
with appropriate documentation, but remember that will receive little
credit if you use a fully or mostly automated cracker that you
did not write yourself.
Due Thursday, Sept 21 2017.
- Due today: Transposition Encryption.
Sample solution to a monoalphabetic substitution cipher
Thursday, September 21, 2017
- Topics: Polyalphabetic substitution and the Vigenere cipher (continued);
More probability and statistics, GCDs and LCMs.
-
Sample solution to a block transposition cipher
- Encryption assignment:
Write or locate software to perform Vigenere encryption with
a given key.
Encrypt two pieces of English prose of at least 1000 characters
using a Vigenere cipher with a key between 10 and 20 characters in
length. Output text in groups of 8, 8 groups to a line.
Hand in writeup along with plaintext, ciphertext, and keys used.
Hand in blind copies of the encrypted text as before, except put the
last 4 digits of your student id as a heading.
Also put copies of encrypted text in the directory crypto_vigenere
accessible with this
Google Drive link
under the file names xxxx_vigenere1.txt and xxx_vigenere2.txt
where xxxx is the four digits of your unique class number.
Due Tuesday, Sept 26, 2017.
DON'T ENCRYPT THE SAME TEXT AS A PREVIOUS ASSIGNMENT!!.
Thuesday, September 25, 2017.
- Topics: GCDs and LCMs, Euclidean algorithm, Hill Cipher.
Wikipedia on the Hill Cipher
- Decryption assignment:
Decrypt the Vigenere-encrypted cipher given to you in class.
You can use either the Kasiski or the Friedman approaches to
attack the keylength. As before, hand in full documentation of
your work.
Warning: there are several computer programs floating around the web
that (claim to) crack Vigenere ciphers completely, or nearly
completely, automatically.
If you use one of these, the available credit is substantially
less than if you performed the analysis yourself.
The vigenere-encryped texts should be available
here
Files are named xxxx_vigenere1.txt or xxxx_vigenere2.txt,
where xxxx is a four-digit number.
If you have a hardcopy ciphertext already, use the
corresponding electronic copy; if you don't find it there
(If you already typed in the hard copy, you can keep working on it.)
If you don't have a hardcopy ciphertext already, email me and I'll
assign you an electronic one (you can print out your own hardcopy).
Note: if you have a hardcopy ciphertext that you received on Thursday,
please hand it in with your writeup.
Note2: If, on any of the ciphertexts, you suspect that the rules
for encryption were not followed, ask the TA for another text.
You are expected to do the same if what you received is
obviously not well encrypted according to the assignment
(e.g. chunks of plaintext showing).
Due: Thursday, September 27.
Thursday, September 27, 2017
- Topics: Rotor machines, German Enigma.
- Reading assignment: Singh, Chapter 4.
- Encryption assignment: Write or find a program to find the
multiplicative inverse, mod 29 for
a square matrix if it exists, and report that it does not exist
if that is the case. This can be done using an adapation of the
Gauss-Jordan technique (see handout), using multiplicative inverses
instead of 1/x. You do not need to compute these
multiplicative inverses
on the fly - since you are only using mod 29, you can use a lookup
table - which is practical to initialize by hand or by exhaustive
search for the inverse.
Use this routine to write a program that encrypts and decrypts
messages using the Hill cipher.
Demonstrate that your decryption works.
Generate 2 (good) 4x4 keys, and use them to encrypt two
pieces of text at least 256 characters long.
To get 29 characters, use (space) = 26, (comma) = 27 and
(period or question mark) = 28.
Place the encryptions along with a 30 character crib
in the files xxxx_hill_4x4_1.txt and xxxx_hill_4x4_2.txt
in the directory crypto_hill accessible with this
Google Drive Link
Also generate 2 3x3 keys and use them to encrypt two pieces of text
at least 1800 characters. Place these without cribs in
xxxx_hill_3x3_1.txt and xxxx_hill_3x3_2.txt
DO NOT REUSE TEXT FROM A PREVIOUS ASSIGNMENT.
Due Tuesday, Oct 3,
- Due today: Vigenere decryption.
Tuesday, October 4, 2017
- Topics: More math. Equivalence relations, integers mod m,
primitive roots.
- Decryption assignment. Decrypt the two Hill ciphers you were given,
one 4x4 using supplied cribs, and one 3x3 without a crib, using
a probable trigram attack.
You should make use of the matrix inversion programs you wrote
for the last assignment to check the invertablility of
cribs and probable trigrams.
You may also want to develop some simple statistical checkers
to reduce your load in determining whether trial decryptions
are correct or not.
Due Thursday, October 10, 2002.
- Due today: Hill encryption.
Thursday, October 5, 2017
- Topics: Complexity.
- Topics: Steganography.
- Encryption assignment: Implement a simulator for a 3-rotor
Enigma type machine with symmetric reflector and plugboard
accomodating up to 13 cables (thus allowing all letters to be
swapped). Your progam should permit easy redefinition of rotors,
and should permit a plugboard setting and initial rotor position
to be specified as a key.
Use simple "odometer" gearing - rotor 1 counts up from 0 to 25
(or a to z), rotor 2 clicks one step, etc.
Make the fastest moving rotor the one closest to the plugboard
(and hence farthest from the reflector).
If you are imagining physical rotors, think of the index labels
being around the "input" side, and rotation is in a direction that
increases the index with respect to a point on the chassis.
Use the convention that
when a key is pressed, the system rotates BEFORE the encryption is
performed.
Wiring of rotors and reflectors of original German enigma
(from http://www.enigma-replica.com/wiring.html)
Rotors
Index..A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
1......E K M F L G D Q V Z N T O W Y H X U S P A I B R C J
2......A J D K S I R U X B L H W T M C Q G Z N P Y F V O E
3......B D F H J L C P R T X V Z N Y E I W G A K M U S Q O
4......E S O V P Z J A Y Q U I R H X L N F T G K D C M W B
5......V Z B R G I T Y U P S D N H L X A W M J Q O F E C K
6......J P G V O U M F Y Q B E N H Z R D K A S X L I C T W
7......N Z J H G R C X M Y S W B O U F A I V L P E K Q D T
8......F K Q H T L X O C B J S P D Z R A M E W N I U Y G V
Reflectors
B......Y R U H Q S L D P X N G O K M I E B F Z C W V J A T
C......F V P J I A O Y E D R Z X W G C T K U Q S B N M H L
Using rotors 1, 2, and 3, reflector B, and 6 plugs, encrypt two
messages in english, of (at least) 1000 characters, using different
keys and plug settings.
Place the messages the encryption keys and plug settings,
and a contact email in
last-name_enigma.txt (where last-name is your last name)
in the directory crypto_enigma accessible with this
Google Drive Link
These will serve as a test of whether the
rotor machine has been implemented correctly.
Due Thursday, October 12, 2017.
Thursday, October 12, 2017
- Topics: The Data Encryption Standard (DES).
- Reading Assignment: Cyrptography Engineering (Ferguson et al.)
Chapters 1-3. (Don't worry, they're short)
- Enigma check: Test your enigma machine by attempting to
decrypt several of the messages posted to Google drive (not your own).
If you can't decrypt any, chances are your implementation is wrong.
Fix it. If you find you can decrypt all but a few of the messages,
chances are those machines have a problem.
Consider sending an email to the owner.
DO THIS BY SUNDAY OCT. 15.
- Once you are sure your your machine is working consistent with
the other machines in the class, use a different key
(and plugboard setting), to encrypt a third message
of at least 1000 characters and (with the same settings) a short 50
character message.
The 50 character messages will serve as a crib for decrypting
the longer.
Place the 1000 character encryption and the 50 character message
along with its plaintext (no keys) in the file xxxx_enigma2.txt
where xxxx is your 4-digit number.
Put it in the Enigma Google Drive directory.
This will be test data for an Enigma cracking
assignment next week.
Tuesday, October 17, 2017
- Topics: Prime numbers, Fermat's little theorem.
- Reading Assignment:
Singh, chapter 6; Ferguson et al. Chapter 10
- Decryption Assignment: Decrypt the enigma encryption you were
given. Recover the plaintext of the 50 and 1000 character messages along
with the (common) plugboard and rotor settings.
The 50 character message with known plaintext can be used as a crib to
obtain the rotor settings and some, if not all, of the plugboard
settings.
The 1000 character message should then be decryptable,
serving as a check on the initial key determination, and as data to
recover any still unknown plugboard settings.
Note that this is somewhat easier than the problem where the
long message has different rotor settings but the same plugboard settings)
The character loop approach (Turing's method) described
in Singh might be helpful here, though the description is incomplete,
and the use of multiple loops seems to be necessary. More directly,
a partial trial decryption leveraging the fact that only 6 plugs are used
can be employed to find rotor and plugboard settings.
In any case you can use your encryption program
as a basis for a bombe simulator.
If you are feeling really ambitious, you could try a ciphertext only
attack on the 1000 character message using the index-of-coincidence
approach outlined in class. 1000 characters should be enough
to give you a good chance of cracking the six plug setup.
Due Thursday, October 17, 2002, reassigned version due Thursday, October 24.
Thursday, October 19, 2017
- Topics: Factoring special expressions, fast exponentiation, Sun Ze's
theorem.
- Topics: Probabilistic primality testing, Diffie_Hellman key exchange.
- Reading assignment: Singh, Chapter 6;
Ferguson et al. , Chapters 10, 11
- Decryption assignment: Enigma decryption reassigned. Due Tuesday,
October 24, 2017.
- Due today: Enigma encryption revision.
Tuesday, October 24, 2017
- Topics: Diffie_Hellman key exchange, RSA.
- Reading Assignment:
Singh, Chapter 6; Ferguson et al. Chapters 10, 11, 12.
- Decryption assignment: Enigma decryption reassigned. Again.
Due Thursday, October 26, 2017.
- Decryption assignment: Crypt/DES dictionary attack.
Get on a Unix/Linux system and read the man page on the crypt function.
Prepare to Use this function and web/other resources to mount an attack on
the encrypted passwords that will be made available Thursday.
Many of these passwords are poorly chosen, i.e. they are short, or
words, or names, or minor variations thereof, or potentially guessable
because they are TOOOO clever, or all of the above.
(No guarantees about only lowercase letters being present though).
See how many you can find out of the list of 190.
Stealing or sharing classmates results is disallowed in this assignment.
Use of fully canned password crackers is discouraged,
as are pre-encrypted dictionaries.
Use of text dictionary resources on the other hand, is encouraged, and
probably necessary to complete the assignment in a timely fashion.
As usual, document all of the resources you use.
Note that the crypt function does not run all that fast (deliberately),
so you may have to allow considerable time for your program to run.
You also have to put -lcrypt on the link line in Linux systems, which
is not mentioned in the documentation, at least on my Linux system.
Due, Tuesday Oct. 31, 2017.
Thursday, October 26, 2017
- Topics: RSA
- Topics: Introduction to group theory
- Reading Assignment: Ferguson et al. Chapters 4,5.
- Assignment: DES-based password cracking (see Oct. 24 assignment above).
The file of hashed passwords is
HERE.
Due Tuesday, Oct. 31, 2017.
- Due today: Enigma decryption (final).
Tuesday, October 31, 2017
- Topics: Block cipher modes, Hash functions.
- Reading Assignment: Singh, Chapter 7;
Ferguson et al., Chapters 4,5, if you have not already read them.
- Encryption Assignment: Use probabilistic primality testing methods
(Fermat's little theorem, or one of the more sophisticated
methods) to find 4 large (131 decimal digits) primes
(very probably) and 4 131 decimal digit non-primes without small
(less than 10^9) factors. One way to get these is to multiply a couple
of not-quite-so-large primes.
Also see how large a prime you can produce within the time
allowed for the assignment.
You can use pre-written large number routines (e.g in python)
or write your own.
However, do your own fast-modular exponentiation.
In your writeup, provide certificates of non-primality for the
non primes, and attempt to bound the probability that your
"primes" are actually not primes.
Also place a file named xxxx_primes.txt containing your 100 digit
primes and non-primes, in mixed order,
in the directory crypto_prime accessible with this
Google Drive Link.
Due Tuesday, November 7, 2017.
- Due today: Attack on password file
Thursday, November 2, 2017
- Topics: Introduction to Protocols.
- Reading Assignment: Ferguson et al. Chapter 6.
Tuesday, November 7, 2017
- Topics: Digital signatures.
- Reading Assignment: Ferguson et al. Chapter 7.
- Assignment: Prime Checking. Go to the Google Drive directory and
download the file with 4-digit extension that is 2 steps after yours in the
wrapped numerical sequence. Determine which of the 131 digit numbers
in the file are prime and which are composite.
Due Thursday, November 9, 2017.
Thursday, November 9, 2017
- Topics: Key exchange
- Reading Assignment: Ferguson et al. Chapters 8, 9.
Tuesday, November 14, 2017
- Topics: Authentication
- Reading Assignment: Ferguson et al. Chapters 13,14.
- Assignment. Find four news-making hacks in the last five years, and write
a description of each (a few paragraphs) including who was hacked, what
was lost or compromised, what the damage was, what vulnerabilities were
exploited (if known) and who was responsible (if known).
Come to class prepared to present (any of) the hacks you have researched.
Don't go only for the highest profile four, since if all yours have been
presented by the time your turn comes, that could be bad luck for you.
Thursday, November 16, 2017
- Topics: Hack presentations
Tuesday, November 21, 2017
- Topics: Hack Presentations
Thursday, November 30, 2017
- Topics: Bitcoin, Blockchain, & Crypto-currencies
Tuesday, Dec 5, 2017
- Topics: Secure Computation
Back to cryptography main page