Names                                                                             :
Math 390 Cryptography
Exam 2, Spring 2001
Central College
You may work in your groups for this exam and use your notes and text, however you may not "copy" answers from other groups. Good luck! Click here for a printable version.
  1. A Vigenere cipher with a key of length 12 was split into twelve columns (labeled column 0 to column 11). Below are columns 0,1, 4, and 10. Give your best analysis (including explanations) of the likely possibilities for characters 0, 1, 4, and 10 of the key.
  2. Each of the texts below came from either a Vigenere encryption, a block anagram encryption (where every block of k characters are shuffled with the same permutation f), or a mono-alphabetic substitution encryption (cryptogram). Decide which type of encryption was used for each cipher, and explain how you came to this conclusion. You should be able to decide which type of encryption was used by looking at the IC of each cipher and the letter-digram-trigram frequencies. You do NOT need to decrypt these messages.
  3. Use the Euclidean algorithm to verify that GCD(34,21) = 1, and then use your results to find integers x and y with 34x + 21y = 1. Be sure to show your work.
  4. Write a program that accepts two integers m and n as inputs, calculates GCD(m,n) using the Euclidean algorithm, and then reports the integers x and y so that mx + ny = GCD(m,n).
  5. It has been claimed that there is a "short cut" to finding the multiplicative inverse of x mod n (when x and n are relatively prime). Let j(n) denote the Euler phi function (which equals the number of positive integers less than n that are relatively prime to n), then the multiplicative inverse to x mod n is just x^(j(n) -1) mod n.
    1. Calculate j(26).
    2. What are the multiplicative inverses of 3, 7 and 19 mod 26 (just list them)?
    3. Show that the formula above, a-1 mod n = a^(j(n) - 1) mod n, works for a = 3, 7, and 19 when n = 26.
    4. Use the formula for j(n) (based on the prime factorization of n) to calculate j(100000).
    5. Working mod 100000, and using your result from part (d), find the multiplicative inverse of 7 mod 100000. Do this as efficiently as you can (by hand).
    6. Write a program that takes two integers n and a as inputs, and when a and n are relatively prime, your program returns the multiplicative inverse of a mod n. Your code should calculate j(n) by "counting" the integers less than n that are relatively prime to n. To calculate a-1, use the short cut method described in this problem.