You can code in any language. C or Java preferable.

Introduction For this assignment you will write a utility for encrypting, decrypting, and deciphering ASCII text documents using an affine cipher. An affine cipher is a slight generalization of the shift ciphers we discussed in chapter 6. For an affine cipher we select two integers a and b as our key. Since we will deal with ASCII characters only, each character of our input text is represented by a number between 0 and 127. For example the lower case letter 'a' is represented by the number 97. As with the Caesar and general shift ciphers, we encrypt our message character by character. Given a character of our plaintext message m, the encryption function E(m, a, b) - (am + b) mod 128. Here a is the multiplier and b is the increment. Using what you have learned about modular arithmetic, you ought to be able to come up with a decryption function D(c, a, b) = m where c = E(m, a, b). You should consider the following questions. . Are all choices of integers (a, b) valid keys? In other words, does D(c, a, b) exist for all possible choices of (a, b)? If not, what restrictions must be placed on a and b to ensure that the decryption function exists? (Hint: You are going to need multiplicative inverses for the multiplier modulo 128-so what consequences does that have for the multiplier?) What is a reasonable upper bound on the number of different key pairs (a, b) that can be used to encrypt ASCII text? (Hint: remember that when you are doing modular arithmetic with modulus 128, you are really working with the residue classes [0]128, [1]128, ...[127]128.) Given such an upper bound, what do we need to process in breaking an affine cypher? The Extended Euclidean Algorithm As noted in class, this is a tough little program to write. Here is an implementation in Ruby that you can use in your program if you like (suitably modified for your language) # Find integers s and t such that gcd (a,b) -s*a + t*b # pre : a,b >= 0 # post: return gcd(a,b), s, t def egcd (a, b) # let A, B = a, b s,t,u, v=1, 0, 0, 1 while 0