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 30, 2018

• 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 4, 2018

Tuesday, September 4, 2018

• Topics: Simple ciphers, breaking them, probability, statistics of English.
• Due today: Aristocrat cryptogram.
  Sample solution to aristocrat cryptogram
  A whole pile of aristocrat cryptograms (without solutions) should you feel like doing puzzles.
• 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 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 11, 2018 (and be ready to crack a challenge by Thursday Sept. 13).

Thursday, September 6, 2018

• Reading Assignment: Katz and Lindell, Chapter 2
• Topics: Probability and statistics. Statistical attacks on affine and monalphabetic substitution ciphers.
• Assignment: Continue Work on mono-alphabetic substitution encryption and decryption.
• Grads: Katz and Lindell: Problems 1.2 and 1.6. Due Tuesday, Sept 11.

Tuesday, September 11, 2018

• Topics: Transposition ciphers and permutations.
• Decryption 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. 13, 2018
• 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 18. Schedule your time.)
• Due today: Mono-alphabetic encryption assignment; Grad problem set 1
  

Thursday, September 13, 2018

• Topics: Polyalphabetic substitution and the Vigenere cipher
• Reading assignment: Singh, chapter 2,
• Grads: Katz and Lindell: Problems 2.6, 2.7, 2.9. Due Tuesday, Sept 18.

Tuesday, September 18, 2018

• Topics: Polyalphabetic substitution and the Vigenere cipher (continued); More probability and statistics.
• 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 20 2018.
• Due today: Transposition Encryption.
  Sample solution to a monoalphabetic substitution cipher

Thursday, September 20, 2018

• Topics: GCDs and LCMs, Euclidean algorithm.
  
• 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 25, 2018. DON'T ENCRYPT THE SAME TEXT AS A PREVIOUS ASSIGNMENT!!.

• Topics: Hill Cipher.
  Wikipedia on the Hill Cipher
• Reading Assignment: Singh, Chapter 3.
• Decryption assignment: Decrypt the Vigenere-encrypted ciphers with the associated xxxx_* number immediately following your own in circular numeric order. (i.e. if you are last, loop around and take the first) 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.

  Note: 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.

• 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 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, question mark, exclamation point) = 28. Place the encryptions along with your email address AND THE ENCRYPTION KEYS in the files xxxx_hill_test_1.txt and xxx_hill_test_2.txt in the directory crypto_hill accessible with this Google Drive Link
  
  The purpose of this is to test the class encryption and decryption algorithms to make sure they all are consistent with each other. Tuesday, October 2, 2018
  • Class Canceled. Professor sick.
  • Assignment: Test your Hill decryption on the encrypted files with the associated xxxx_* number immediately following your own in circular numeric order. (i.e. if you are last, loop around and take the first). This will involve inverting the supplied encryption key to produce the appropriate decryption matrix. If you suspect that the encryption was done incorrectly, contact the person who encrypted it via the provided email and sort things out so the two of you are consistent. The forward chain should get all the systems consistent with each other. Hand in (on Thursday) a writeup showing you correctly decrypted the test.
  Thursday, October 4, 2018
  • Topics: More math. Equivalence relations, integers mod m, primitive roots.
  • Decryption assignment.
    Using your (checked) Hill encrypter, encrypt two NEW pieces of text at least 256 characters long. This will be test data for the cracking homework. Place the encryptions along with a 30 character crib in the files xxxx_hill_4x4_1.txt and xxxx_hill_4x4_2.txt 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.
    DO THIS BY THIS EVENING (Oct 4)
    
    Now decrypt the two Hill ciphers in the file names advanced TWO steps from your number, 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 Tuesday, October 9, 2018.
  • 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.
    Also Due Tuesday, October 9, 2018.
  • Due today: Hill encryption.
  Thursday, October 11, 2018
  • Topics: Complexity.
  • Decryption assignment: Using your (now perfectly debugged) enigma machine emulator, rotors 1, 2, and 3, reflector B, and 6 plugs, encrypt a brand new message in english, of (at least) 1000 characters, using different keys and plug settings than any you have used before. Also encrypt, using the same settings, a short 50 character message that will serve as a crib (supply the plaintext as well as the encrypted text. 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. in the directory crypto_enigma accessible with this Google Drive Link This will be test data for the cracking assignment.
    

    Crack the enigma encryption in the file 3 steps beyond your own number. Specifically, recover the plaintext of 1000 character message along with the 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) One approach is to search partial trial decryptions over the rotor space leveraging the fact that only 6 plugs are used. In any case you can use your encryption program as a basis for a bombe simulator for any approach you wish to try.
    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 18, 2018.

  Thursday, October 18, 2018
  • Topics: Steganography.
  • Reading Assignment: Cyrptography Engineering (Ferguson et al.) Chapters 1-3. (Don't worry, they're short)
  Tuesday, October 23, 2018
  • Topics: The Data Encryption Standard (DES).
  • Reading Assignment: Ferguson et al. Chapters 4, 5.
  Thursday, October 25, 2018
  • Topics: DES continued, Block Cipher Modes, Hash functions.
  • 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 Tuesday. 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.
    List of encrypted passwords HERE
    Due, Thursday Nov 1, 2018.
  • Reading: Feguson et al. Chapters 5, 6.
  Tuesday, October 30, 2018
  • Topics: Prime numbers, Fermat's little theorem.
  • Topics: Probabilistic primality testing.
  • Reading Assignment: Singh, Chapter 6; Ferguson et al. Chapters 10, 11, 12.
  Thursday, November 1, 2018
  • Topics: Fast Exponentiation, Factoring special expressions, Sun Ze's theorem.
  Tuesday, November 6, 2018
  • Topics: Diffie_Hellman key exchange.
  • Reading: Ferguson et al. Chapter 11.
  Thursday, November 8, 2018
  • Topics: RSA
  • Reading: Ferguson et al. Chapter 12.
  Tuesday, November 13, 2018
  • Topics: Introduction to group theory
  • Reading Assignment: Ferguson et al. Chapters 8,9.
  • Encryption Assignment: Use probabilistic primality testing methods (Fermat's little theorem, or one of the more sophisticated methods) to find 4 large (137 decimal digits) primes (very probably) and 4 137 decimal digit non-primes obtained by multiplying two smaller primes of at least 50 digits each. 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, write your own fast-modular exponentiation. In your writeup, provide the factors for the non primes, and attempt to bound the probability that your "primes" are actually not primes. Place a file named xxxx_primes.txt containing your 137 digit primes and non-primes (but not their factors), in mixed order, in the directory crypto_prime accessible with this Google Drive Link.

    In cryptographic prime generation, it is important to have unique primes, or at least ones that is it extremely unlikely some other person will generate. Thus you should take some care in producing the "random" numbers that you test for primality. Don't use an online source for either your random numbers or your large primes. Such sources have been known to generate duplicates. If the numbers you generate match anyone else's, credit will be lost.
    Due Tuesday, November 7, 2017.

  Thursday, November 15, 2018
  • Topics: Introduction to Protocols.
  • Reading Assignment: Ferguson et al. Chapters 8, 9, 13.

• 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 3 steps after yours in the wrapped numerical sequence. Determine which of the 137 digit numbers in the file are prime and which are composite.
  Due Tuesday, November 27, 2018.

Back to cryptography main page