Once the encoder is working, build a decoder by duplicating the code and changin

Question

Once the encoder is working, build a decoder by duplicating the code and changing the addition to a subtraction.

If you use printf() to output the array, remember that a null termination is required on a string.

Goal: Vigenere cipher program

Instructions:
Step 1. Creating the assembly language file

Step 2. The application area

In the previous programming assignment we looked at ROT13 encoding, which is an example of a simple substitution cipher called a Caesar cipher (because it was supposedly used by Julius Caesar 2000 years ago).

ROT13 is simply a Caesar cipher with a rotation of 13. Caesar ciphers are relatively easy to break because the code does not change the frequency distribution of letters. For example, in English the most common letter is E--around 12% of all text. By counting up the number of different letters in a ciphertext, you can make a good guess which one is E. That gives you the rotation factor and then the cipher is broken. Or you could just try all possible rotations until you find the one that works (an elementary example of "brute-force attack".)

The Vigenere cipher, invented in 1553, uses multiple Caesar ciphers so that the frequency distribution of encoded letters is spread over several different encodings. Some versions were based on something like sliding tables or concentric letter wheels. However for military use in the field it is better not to need special equipment and to have the cipher be based on something easy to remember such as a keyword.

For better frequency characteristics the keyword should not have any repeated letters. Also, if it contains the letter A the encrypted letter will be the same as the plaintext, although this is not necessarily a bad thing.

To implement this algorithm with a pencil and paper, many descriptions ask you to build a Vigenere Square. However this is not really necessary when you are using a computer to do the encoding and decoding.

Essentially the keyword is written repeatedly over and over above the plaintext. Suppose the keyword is CRYPTOGRAM.

Pg. 1

CmpE102 Fall 2016 Programming Assignment 4

Consider that the letters are numbered 0 to 25. The letter on the top determines which Caesar-cypher to use for the letter below. Thus C means shift the alphabet by 2, A means shift by 0, and so on. In mathematical terms, we are adding the two letters together modulo 26. (The square was used because the concept of modular arithmetic was not generally understood by soldiers in 1553.)

To decrypt the message, the same operation is performed in reverse. That is, the value of the keyword letter is subtracted rather than added.

Another example (Andrew Pennycook, Codes and Ciphers, MacKay, New York, 1980):

Key: SUFFERINGCATSSUFFERINGCA Plaintext: BETHEREATMIDNIGHTTONIGHT Ciphertext: TYYMIIMNZOIWFAAMYXFVVMST

Notice that the word "night" appears twice in the message. The first time it is encoded as FAAMY and the second time as VVMJT. There is nothing to show that they came from the same word in the original.

The Vigenere cipher was long considered to be unbreakable as long as the secrecy of the keyword could be preserved. However by the middle 19th century techniques for breaking the cipher had been developed, although they were not widely known until later. In the American Civil War, Confederate forces routinely made use of Vigenere ciphers, not realizing that Union intelligence had little difficulty deciphering the messages.

Step 3. What your code should do

1. Your code should use STDIN and STDOUT for input and output. (This is the default.) Use redirection on the command line to read from a file and write to a file.

2. Your code should open a file, read it character by character and save it into an array.

When you get to the end of the file you should encode the contents of the array with a Vigenere cipher using the keyword CRYPTOGRAM, then print it out.

Maintain the distinction between upper-case and lower-case letters, and do not modify non-alphabetic characters. This is not very good for the security of your message, but the result will look neater.

This program should use glibc functions. In addition to printf(), you may need getchar() and putchar().

Assume that the input file contains just ASCII text Don't worry about what happens with non-text files.

Explanation / Answer

PLAINTEXTMESSAGE
KEYKEYKEYKEYKEYK

Then, each character has a Caesar shift applied, with the amount of shift determined by the key character. The table below shows exactly what happens. To encrypt a character, find the column with the plaintext at the top, and the row with the key on the left side. The ciphertext is the character that this row and column intersect on. To decrypt, locate the row with the key on the left side, and look along this until you find the ciphertext.

Decrypting a ciphertext without a key is usually possible, provided that the message is substantially longer than the key (the program only works with keys of less than 255 characters), and the plaintext's language is known (the program only works with English). Of course, the program can't be sure of what the key is - it can only find the most likely possibility. Because of this, information about each decision is presented to the user, who then has a chance to override the automatic suggestion.

The first step is to determine the length of the key, using the method of coincidence indices. To calculate a coincidence index, shift the ciphertext and compare against itself, counting character matches:

CIPHERTEXT
   CIPHERTEXT
   ----*-*

In this example, for a shift of three, there are two matches out of a possible seven, so the coincidence index is 28.57%. For random text the expected value is 3.85%, but this number tends to be higher for non-random text in any language, because some letters are more frequent than others. For Vigenere ciphertexts, the coincidence index is higher for shifts that are a multiple of the key length than otherwise (can you see why?). The program calculates the first 256 shifts, and finds the shortest length for which all shifts that are a multiple of this length have a coincidence index greater than 6%, which it suggests as the key length.

Knowing the key length, you can break the ciphertext up into chunks, each of which have been encrypted by the same character in the key. For each chunk, try decrypting it with each possible key letter (A...Z). Compare the letter frequencies in each possible plaintext with a table of English letter frequencies. The key letter which results in the least squared deviation is the most likely candidate, which the program suggests.

To test the cracking code, I used words.txt, a list of many English words, found in the Word Patterns download. With this much ciphertext, keys as long as 200 characters can be uncovered without the user overriding any automatic suggestions.

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.