The affine cipher is a substitution cipher, where a plaintext letter x is enciphered into a ciphertext letter y as follows: x y = x + (mod 26) The key for this encryption function is (, ), where 0 , 25. There are 12 possible choices for with gcd(, 26) = 1, where gcd stands for the greatest common divisor, and 26 choices for (i.e., 0, 1, 2, , 25). Thus, there are 12 26 = 312 choices for the key. The decryption is accomplished by an affine function as follows: y x = 1(y ) (mod 26), where 1 = 1 (mod 26). 1. Write an algorithm for an affine cipher. 2. Show that your proposed algorithm is correct using an informal proof (i.e., discussion). 3. Give a program corresponding to your proposed algorithm, using your java programming language. Your program should simulate this cipher and display the ciphertext along with the corresponding plaintext and key. The implementation of this affine cipher software should be as structured as possible. You should have a user-friendly interface showing all the steps of this cipher, including encryption and decryption

Problem 2 (Transposition Cipher): The rail fence cipher represents a form of transposition encryption, where a plaintext (i.e., secret message) is written in a zigzag pattern on more than one line, which is referred to as a rail. More specifically, the plaintext is written downwards and diagonally on successive "rails" of an imaginary fence. When the bottom rail is reached, the remainder of the plaintext is written in the same way as above, but upwards. When the top rail is reached the remainder of the plaintext is written downwards and diagonally again until the bottom rail is reached. Then, the remainder of the plaintext is written upwards and diagonally again until the bottom rail is reached. This pattern repeats until the whole plaintext is written out. To generate the ciphertext, the letters on the first rail are written. Then, those letters on the second rail are written, followed by those on the third rail, if any. This process repeats until those letters located at the last rail are written. Consider the following two ciphertexts, which are generated using nl-rail fence and n2-rail fence, respectively, where nl and n2 (i.e., keys) are unknown: Ciphertext associated with nl-rail fence: TTTEOOTAIUSBNOHSQTERBTTEINOEHO Ciphertext associated with n2-rail fence TEEOBTUS BOHQTETAEIOTTHOROITNNS 1. Recover the plaintext associated with each of the above ciphertexts. Hint: Find the keys nl and n2. 2. Conclude