VIGENERE CIPHER WITH THE TI-83, THE
Hamilton, Michael
1. INTRODUCTION
Cryptology, the science of secret writing, is a great way to introduce students to different areas of mathematics such as number theory, linear algebra, probability and statistics. Cryptology consists of two branches: cryptography and cryptanalysis. Cryptography is the science of designing techniques for encrypting and decrypting a message. Cryptanalysis is the science of recovering plaintext (the original unencrypted form of a message) from ciphertext (the secret form of the message after encryption) without knowledge of the process used for encryption and decryption.
Cryptography is separated into two main categories: private-key and public-key. For a discussion of these different categories see [1], [2], or [5]. Until 1978, when the paper “A Method for Obtaining Digital Signatures and Public Key Cryptosystems” by Rivest, Shamir and Adelman was published in the journal Communications of the Association for Computing Machinery, all cryptography fell into the category of private-key. Since that time, private-key cryptography has largely given way to its public key counterpart [5]. However, some cryptosystems that employ both techniques have been developed. These cryptosy stems are typically called hybrids. In many hybrid cryptosystems the message is enciphered using a private-key algorithm, but the key for the private-key cryptosystem is transmitted using some type of public-key cryptography [2]. Hence it is still worthwhile to investigate private-key cryptosystems.
One of the most famous, private-key cryptosystems is the Vigenere Cipher. Encryption and decryption using the Vigenere Cipher was originally described in terms of a table known as the Vigenere Square and a secret keyword. Like many other cryptosystems, it is quite easy to describe this cryptosystem mathematically using basic properties of modular arithmetic.
A variety of techniques can be used to perform a cryptanalysis on a message that has been encrypted using the Vigenere Cipher. Most techniques require that a frequency analysis be done on either the entire message or on various parts of the message. After the frequency analysis is complete, there are ways to estimate the keyword length and use that information to determine the keyword. Once the keyword is determined a cryptanalyst can easily recover a message that was intended to be secret.
More realistic applications of Vigenere Cipher encryption and decryption involve long messages, hence it is not practical to perform these processes by hand. Although it is common to use computers to do the work, the algorithms necessary to perform the computations required to encipher, decipher and cryptanalyze messages can easily be programmed into a TI-83 graphing calculator.
The general concepts discussed above are available elsewhere, but it is our purpose here to show how they can be made available to students with lower level mathematics skills. We will also show how the TI-83 graphing calculator can perform the computations needed to implement the Vigenere Cipher, and a message encoded via the Vigenere Cipher will be cryptanalyzed using the TI-83.
3. THE VIGENERE CIPHER
The Vigenere Cipher is named after the Frenchman Blaise de Vigenere and uses a table known as the Vigenere Square. An English form of the table is shown below.
In the Vigenere Square, plaintext letters label the columns and keyword letters label the rows. The main entries of the table correspond to ciphertext letters. To use the Vigenere Cipher two correspondents must first agree upon a secret keyword or key phrase. We will briefly illustrate how one can encrypt and decrypt messages using the Vigenere Square. For a detailed explanation as well as some interesting historical background about the Vigenere Cipher, see [1], [2] or [5].
Suppose Michael wants to send Bill the message “MATH IS COOL” using the Vigenere Cipher with keyword “DOG”. Michael first writes down the plaintext and then writes the keyword repeatedly above the plaintext, character for character. To encrypt this message using the Vigenere Cipher, Michael replaces each plaintext letter with the letter that lies in the Vigenere Square at the intersection of the column headed by the plaintext letter and the row headed by the corresponding keyword letter. For example, to encrypt the first plain-key pair D-M, Michael finds the letter at the intersection of the M column and D row. This letter is P and it becomes the first letter of the ciphertext. he continues this process until the entire message has been encrypted.
5. ENCRYPTION AND DECRYPTION OF THE VIGENERE CIPHER ON THE TI-83
A program for performing modular arithmetic on TI-82 graphing calculators was presented in [4]. It was used as a model for the program VIGENERE (the code appears in the appendix). The mathematical formulas given in the last section have been programmed into the code. VIGENERE allows an individual to encrypt and decrypt messages using the Vigenere Cipher on a TI-83. The string capability of the TI-83 provides an efficient way for individuals to enter a large amount of text directly into the TI-83 and let the calculator perform the extensive computations.
We now demonstrate how messages can be encrypted and decrypted using the TI-83. As an example, suppose Michael wants to encrypt the message “NORTHCAROLINAWESLEYANCOLLEGE” using the keyword “BISHOP”. He first accesses the VIGENERE program and then enters the keyword and plaintext message as text. The program is designed so that Michael has the option of either encrypting or decrypting the message. After execution, the first 14 characters of the ciphertext appear on the calculator display while the rest can be viewed by pressing the right arrow key. Here the ciphertext is
“OWJAVRBZGSWCBEWZZTZIFJCAMMYL”.
Bill can now use VIGENERE to decrypt the message. If he wants to recover the plaintext from the ciphertext
“OWJAVRBZGSWCBEWZZTZIFJCAMMYL”,
Bill accesses VIGENERE and enters the keyword and ciphertext message as text. As before, the first fourteen characters of the original plaintext appear on the display and the remainder of the message “NORTHCAROLINAWESLEYANCOLLEGE” can be viewed by pressing the right arrow keys.
Our program VIGENERE uses the string capability of the TI-83 to compute the numerical representation of a letter without using IF-THEN statements. As a result it only requires 380 bytes of RAM. This is substantially less than a Vigenere Cipher program on the TICALC.org website that uses 4,329 bytes of RAM [6]. Essentially, the program goes through a text one letter at a time and finds the location of that letter in another string that contains the alphabet
“ABCDEFGHIJKLMNOPQRSTUVWXYZ”.
For example if the first letter in a piece of text is “D”, VIGENERE looks for the location of “D” in the alphabet string. It determines that D is in the 4th place and returns a value of 4. The program then subtracts 1 in order to get the numerical representation for the letter “D” which is 3.
6. CRYPTANALYSIS OF THE VIGENERE CIPHER
We first note a few more basic definitions and facts. A monoalphabetic cipher is a cipher that has a one-to-one correspondence between plaintext and ciphertext letters. A polyalphabetic cipher is a cipher in which plaintext letters are replaced by ciphertext letters from more than one cipher alphabet. The probability that two randomly selected letters from a text are identical is called the index of coincidence. If the index of coincidence for a ciphertext is close to 0.065, then the cipher is likely to be monoalphabetic. However, if the index of coincidence is close to 0.0385, the cipher is likely to be polyalphabetic [1]. Since the Vigenere Cipher is a polyalphabetic cipher that performs different shifts (depending on the key letter) on different parts of the plaintext, both of these numbers are useful when conducting a cryptanalysis.
Obtaining an estimate about the keyword length is an important step in conducting a cryptanalysis of a message encrypted via the Vigenere Cipher. Suppose we use the Friedman Test and estimate the secret keyword length to be 3. This essentially means that the plaintext was broken up into three parts before encryption. We can now organize the ciphertext into three columns. The first, fourth, seventh, etc., … ciphertext letters are placed in the first column. The second, fifth, eighth, etc., … ciphertext letters are placed in the second. The third, sixth, ninth, etc., … ciphertext letters are placed in the third column. This means the first, fourth, seventh, etc… ciphertext letters were encrypted with the same shift, the second, fifth, eighth, etc., … ciphertext letters were encrypted with the same shift, and the third, sixth, ninth, etc., … ciphertext letters were encrypted with the same shift. We refer to each of these three columns of letters as cosets. Since the entire message was encrypted with a poly alphabetic cipher, we would expect the index of coincidence for the entire message to be close to 0.0385. However, if we calculate the index of coincidence for each ciphertext coset, then we should get values close to 0.065 since each letter in the coset was encrypted using the same monoalphabetic shift. These expectations are based on the assumption that we have a relatively long message and the length of the keyword is considerably shorter than the length of the message [1]. This information will further help us determine if we have estimated the correct keyword length.
7. CRYPTANALYSIS OF THE VIGENERE CIPHER USING THE TI-83
As one may suspect, the process described in the previous section involves a tremendous amount of computations in addition to finding a good way to organize the data. The TI-83 can perform all the computations needed to determine the possible keyword and store the data in an organized manner.
We illustrate the process with the following example. Suppose we obtain the ciphertext shown below and want to perform a cryptanalysis on it. “UOTIPRFSUTGFFTZEUIKXIEIYFSLMPNOLFTZISTAWOOTPFRAR UHWQJNVXPSMJGEJXIEKPJNYWBNVESRGATOXSVTJEHEGYTF GVUUFIPRLSUACIBREWBGSMOSLETESSGTJSVBDITAFHCYGTQ OKMOGWRETZIN”.
Our first step is to compute the index of coincidence for the ciphertext. To assist in this process, program A (the code is given in the Appendix) is provided. We begin by accessing program A and typing the ciphertext.
Program A first conducts a frequency count on the ciphertext. Once the count is complete, the program computes the Index of Coincidence for the ciphertext (assuming a keyword of length 1) and determines the possible keyword length under the assumption the ciphertext was encrypted using the Vigenere Cipher. Figure 5 shows the results.
Since the Index of Coincidence is closer to 0.0385 than 0.065 it is reasonable to assume the message was encrypted using a polyalphabetic cipher. The keyword estimate of 4.42 is performed via the Friedman Test described in section 6. The program now gives the user the option of trying a different keyword length. Since we suspect the message was encrypted using a polyalphabetic cipher, we can take a guess at the keyword length. Based on the estimate of 4.42, it is reasonable to guess the keyword length is 4. Program A now runs again; however, this time it breaks up the ciphertext into 4 cosets and determines the Index of Coincidence for each coset.
We can view all values by using the right arrow key. These values are approximately 0.0594, 0.0825, 0.0427 and 0.0612. Since overall the values are closer to 0.065 than 0.0385, it is likely we have determined the correct keyword length.
Within program A, a matrix that contains the actual frequencies for the letters in the coset is constructed. The result is stored in the TI-83 as matrix A and a partial display of the matrix A appears in Figure 7. The first column of A is the frequency vector for coset 1, the second column is the frequency vector for coset 2, the third column is the frequency vector for coset 3 and the fourth column is the frequency vector for coset 4. Additionally, the ciphertext is stored as Str3. This allows an individual to access the ciphertext later without having to retype it. At this point we are prompted again and asked if we want to try a different keyword length. Since we think we have correctly determined the keyword length we can proceed to the next step of the cryptanalysis process.
We can now use the program DOTSHIFT (the code is given in the appendix) to determine the possible keyword. We begin by accessing DOTSHIFT. The program DOTSHIFT computes the dot product of the shifted copies of the relative frequency vector, a, for each coset with the relative frequency vector, b, for standard English. The program keeps track of the largest dot product obtained for each coset, determines the shift used to obtain that dot product, and finally reconstructs the possible keyword. DOTSHIFT first asks for the frequency matrix. At this point we just need to access the matrix A constructed in program A. The program runs and DOTSHIFT outputs the possible keyword “BASE”.
We can now use this possible keyword “BASE” and VIGENERE to attempt to decrypt the ciphertext. If our keyword guess is correct, the message should be sensible English. We access VIGENERE and are prompted to enter the keyword and text. We can avoid having to re-enter the ciphertext since it was stored as Str3 in program A. To recall the ciphertext we press the following sequence of keys: RCL (2nd then STO), VARS, 7 (to choose the String option from the VARS menu), 3 (to choose Str3 from the STRING menu), and finally ENTER. At this point the ciphertext reappears after the TEXT prompt. The end of the ciphertext appears on the display.
After the text appears we are asked if we want to encrypt or decrypt. We choose the decrypting option and VIGENERE now decrypts the text using the keyword “BASE”. The first 14 characters of the possible plaintext appear on the display and we can view the entire text by using the right arrow keys. The text reads as:
TOBEORNOTTOBETHATISTHEQUESTIONWHETHERTISNOBLERINTHEMINDT OSUFFERTHESLINGSANDARROWSOFOUTRAGEOUSFORTUNEORTOTAKEAR MSAGAINSTASEAOFTROUBLESANDBYOPPOSINGENDTHEM.”
This, of course, is a sensible English message. It is the beginning of a famous soliloquy from Shakespeare’s Hamlet [3]. Using the TI-83 we have effectively performed a cryptanalysis of the original message and recovered the plaintext!
8. CONCLUSION
This paper demonstrates how the TI-83 can be used to encrypt and decrypt a message using the Vigenere Cipher. It also shows how one can use the TI-83 to perform a cryptanalysis on a message encrypted by the Vigenere Cipher. The technology allows individuals to see how the concepts are implemented with messages longer than those that can be feasibly computed by hand.
The Vigenere Cipher is one of the most famous, classical cryptosystems. For more details on how and why the cryptosystem works, as well as some historical notes about it, see [1], [2] or [5].
REFERENCES
1. Thomas Barr, Invitation to Cryptology, Prentice Hall Inc., Upper Saddle River, NJ (2002).
2. Robert Lewand, Cryptological Mathematics, MAA, Washington D.C. (2000).
3. William Shakespeare, Hamlet, W.W. Norton and Company, Inc., New York, NY (1963).
4. Neil Sigmon and Bill Yankosky, “RSA Encryption with the TI-82”, Mathematics and Computer Education, Vol. 36, No. 1, pp. 13-23, 2002.
5. Simon Singh, The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography, Anchor Books, New York, NY (1999).
6. Ticalc.org. http://www.ticalc.org/pub/83/basic/programs/(20 August 2000).
Michael Hamilton* and Bill Yankosky
Mathematics Department
North Carolina Wesleyan College
Rocky Mount, North Carolina 27804
mh165807@mailncwc.edu; byankosky@ncwc.edu
* This author was a first year student at North Carolina Wesleyan College when the programs in this paper were developed.
Copyright Mathematics and Computer Education Winter 2004
Provided by ProQuest Information and Learning Company. All rights Reserved
