Math 390 Cryptography
Final Exam Review

Topics to know

Chapter 1: Be able to work with mod 26 arithmetic (things like 3*'e', 'a' + 17, inverses etc.), understand key spaces and attacks for shift, affine and one time pad ciphers.
Chapter 2: The binomial coefficients (n choose k), simple counting problems, frequencies of English letters-words-di and tri-grams. Solving two equations, like 5a + b = 17 and 3*a + b = 9 mod 26.
Chapter 3: Cryptograms: keyword and offset letter creation, key space, attacking one. Permutations: cycle decomposition, order, composing them counting the number of permutattions with a given pattern (say a 5 cycle times a 2-cycle in S9), the good shuffle, block interleavers.
Chapter 4: Vigenere ciphers: Its construction-design, cipher text only attacks, Kasiski-what it is and why it works, IC-what it is and why it works and how you use it to reconstruct the key, plus the key space for a Vigenere cipher.
Chapter 6: Given an S-box and an input, calculate the output.
Chapter 7: GCD, Euclidean algorithm, finding x and y so that ax + by = GCD(a,b), factoring into primes, Euler's phi function, finding inverses mod n, large powers mod n.
 

Sample questions

  1. For the affine cipher, explain what a key is, how you use it to encrypt a short message, how you decrypt an affine encrypted cipher, and how you carry out a cipher text only attack on an affine cipher.
  2. If a language has three characters, 'a', 'b', and 'c', which occur with probabilities 0.15, 0.35, 0.5 respectively:
    1. How likely is it that a string of 20 characters in this language has exactly 4 a's?
    2. How many b's would you expect in a 10 character message?
    3. What would the IC of a typical message in this language be?
    4. What would the IC of a random string of a, b, and c's be (each occurs with equal probability)?
  3. Find all primes from 1 to 169.
  4. What is f(3564)? What is 5-1 mod 3564?
  5. In S14, how many permutations are there that have the form of two four cycles times a 3 cycle? Write one such permutation down, then find its inverse and its square. Apply the permutation to the word monoalphabetic.
  6. What character of cipher text corresponds to the plaintext letter 'g' if I create a cryptogram using keyphrase underdogandpenelope with key letter n?
  7. Given the key length of a Vigenere cipher, how do you utilize IC's to find the actual key?
  8. Find x and y integers so that 246x + 33y = 3.