Advances in Cryptography
Dara Kirschenbaum
History of Mathematics
Research Paper
Rutgers, Spring 2000
Cryptography, a method of keeping one's privacy and secrets intact, has existed since the time of Caesar (100-44 B.C.) (Smith 122). Many techniques of encryption have been developed over the last 2000 years, developing over time from the most simple to the most complex. Among the "[s]implest is the backslang or crab...(Bauer 90)" which reverses the letters of a word, phrase, or sentence. For instance, "backslang" would be "gnalskcab". Most encryptions are far more complicated and intricate than backslang, as will be discussed further below.
Before going into further detail we will need to introduce some specialized terminology and give a brief explanation of the number theoretic concept of a congruence. In cryptography the term plaintext refers to the actual text, encrypted into ciphertext. A cipher is a method for changing the plaintext into ciphertext. Encryption is the implementation of the cipher. Decryption is the more difficult process of reversing the cipher method, i.e., transforming the ciphertext back into the original text, the plaintext. The entire study of cryptography is known as Cryptology. These terms are useful in describing the many methods of encryption and decryption.
The theory of congruences was developed by Karl Friedrich Gauss,
(1777-1855), (Rosen 119). We "let m be a positive integer. If
a and b are integers, we say that a is congruent to b
modulo m
if m|(a-b) [Note: "|" means divides evenly, i.e. the remainder is 0]
(Rose n 120)." The notation for "a is congruent to b modulo m" is
a=b(mod m).
For example, 13=1(mod 12), since 12=(13-1). Inverses of
congruences are necessary to decipher codes. If ax=1(mod m), then
x
is an inverse of a modulo m. For instance, 9*2=1(mod 17), so 2 is an
inverse of 9 modulo 17. With this terminology, we can continue our
discussion on the development of cryptography. In the second century
before Christ, the Greek historian Polybius devised a simple system for
signaling messages (Weber). This method utilized the following table:
| 1 | 2 | 3 | 4 | 5 | |
| 1 | a | b | c | d | e |
| 2 | f | g | h | ij | k |
| 3 | l | m | n | o | p |
| 4 | q | r | s | t | u |
| 5 | v | w | x | y | z |
The letter "d" would correspond to the number 14 since it is in the row 1 and column 4. "Polybius conceived the idea of transmitting messages in this way by means of torches, the left hand carrying the appropriate number of torches for the numerals down the side and the right hand for numerals across the top (Haldane 39)." Other advancemen ts were made in the Greek civilization.
The first known use
of ciphers is often accredited to Julius Caesar. It is claimed,
Caesar set up a system of codes to send military messages to his army
in order to keep the message secure and private during battles. He
used what is commonly known as a monoalphabetic cipher where a letter
is replaced by another single letter in the alphabet. In a
monoalphabetic cipher, a letter can only be represented by one other
letter, as opposed to a polyalphabetic cipher, where one letter can be
represented by d ifferent letters of the alphabet. Caesar's method
was to shift each plaintext letter three places down to the ciphertext
letter:
| Plaintext: | a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z | Ciphertext: | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | Z | Y | Z | A | B | C |
In the above, the alphabet is shifted 3 places. So "A" is replaced
by "D", "B" by
"E" and so forth. Suppose Caesar wished to encipher the following message:
ettubrute
He would substitute the plaintext with the ciphertext and it would
look like this:
HWWZEUZWH
Congruences can be used for encipherment by Caesar's shift. "To
describe this cipher using modular arithmetic, let P be the numerical
equivalent of a letter in plaintext and C the numerical equivalent of
the corresponding ciphertext letter. Then C=P + 3
(mod 26), 0 < C < 25 (Rosen 235)."
The numerical equivalents are as follows:
| Plaintext: | a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | Ciphertext: | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | Z | Y | Z | A | B | C |
| 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 0 | 1 | 2 |
Using the previous example, ettubrute becomes:
4 19 19 20 1 17 20 19 4
These numbers are substituted for P.
So for the first ciphertext letter,
C=4 + 3 (mod 26)=7(mod 26), so C=7,
which corresponds to H in the ciphertext.
This is continued for the rest of the numbers until
the following is obtained:
7 22 22 25 4 20 25 22 7
Translating back into letters, we have HWWZEUZWH.
At one point the leaders in the realm of cryptoanalysis were the Arabs. "[T]he Arabs became heirs to the cultures, sciences and administartive practices of the ancient civilizations of Egypt, Greece and Persia (Bosworth 17)." The Egyptians used hieroglyphics, which we re symbols used to decorate tombs. According to Weber, in David Kahn's The Codebreakers, he explained hieroglyphics as one of the oldest texts that incorporates an important element in cryptography, which is "transforming a method of writing" (Weber 5).
While Egyptian writing was pictorial, the Greeks "...devised more scientific, numerical ciphers based on the substitution principle (Bosworth 17)." The Arabs focused on the use of letters and numerals in secret writings and wrote books on them.
A notable piece of literature from the Arab civilization was written by Qalqashandi, an Egyptian scholar, entitled Sub al-a'sha fi sina'at al-insa', and was completed in 1412 (Bosworth 20). This 14-volume "encyclopedia" went into detail both in cryptogr aphy and cryptoanalysis. In the translation of this piece by C. E. Bosworth, Qalqashandi takes much information from Ibn ad-Duraihim, (1312-61) (Haldane 147) and references him. Without knowledge of the Arabic language it is rather difficult to underst and even the translation of the encyclopedia, but one can say Qalaqashandi summarized seven ways to manufacture ciphers of Ibn ad-Duraihim:
Additionally, Qalqashandi cites Ibn ad-Duraihim's method for finding solutions to messages by using frequencies, and subsequently the first words that should be worked out are the smaller ones and then working to the larger words (Weber 7). Frequency ana lysis is frequently used to decipher. In the English alphabet, analysis makes use of percentages for the occurrence of the 26 letters alphabet (Rosen 238). Interestingly, Qalqashandi also has recipes for making disappearing ink. It is no doubt Qalqasha ndi's Sub al-a'sha fi sina'at al-insa' was a turning point for future crypographers and cryptoanalysts.
It has been alleged by many scholars, such as Haldane, and Weber, who agrees with Thomson and Padover, that essential features of the foundations of cryptography developed first in Italy. The architect Leon Battista Alberti is frequently called "the Father of Western Cryptography", according to Weber, and "the father of modern cryptography" according to Bauer, although he is best remembered for his architecture, and was skilled in many other arts. Alberti's cryptographic title was bestowed mainly for his construction of his polyalphabetic substitution in 1468 (Weber 9). This made use of a device composed of "two circular copper plates, one larger than the other, secured on an axis, one bearing the ... [plaintext] alphabet and the other the cipher alphabet, changing the relative positions after every few words (Haldane 47)." This system is illustrated below. The brilliance of theidea of changing the position of the device after every few words is that this interferes with the use of frequency analysis to uncover the code.
In 1508, fifty years after the development of Alberti's polyalphabetic cipher, the first printed book on cryptography was published by Johannes Trithemius (1462-1516), entitled Polygraphaif (Bauer 14). Trithemius' publication included a square tableau, which included lines of the alphabet, where each line has a different starting letter. The letters "j" and "v" are excluded from the tableau.:
"Trithemius employed the first line of the alphabet to encipher the first le tter of the message, second line for the second letter and so on through 24 lines before beginning with line 1 again." (Weber 11) For instance, the word home would be encoded as hpoh.
This tableau probably inspired Blaise de Vigénère (1523-96) of France (Haldane 56). His tableau, which is shown below, is very similar to Trithemius except for a few minor differences. Vignhre's tableau includes the letters "i" and "v" and also includes an extra row and column of the alphabet. Weber has claimed, that according to David Kahn's The Codebreakers, the system "contains an initial single secret letter known only to the encipherer and the decipherer. Using the latter to decipher the next cryptogram [or ciphertext] letter and continues alternating this process for unlocking the complete cryptogram (Weber 12)." If the letter was "t" and the code was "Friday", to encipher, one would find "f" in the top row, and "t" along the first colu mn, and match it to obtain "y". Next "y" becomes the code letter, so we do the same with "r" and "y", and we obtain "p". If this method is exhausted with the rest of the letters, we obtain the following: ypxaay The decipherer can solve this if the key letter is known. However, the more popular method, which bears the name Vignhre, employs a key. The key simply consists of a word or a phrase, and if needed it is repeated several times to fill the plaintext. For instance: Key Word: vige ne re Plaintext: this is it
In order to find the ciphertext, we would find "t" across the top of the tableau, and "v" along the side, and obtain "o". This is done for the remaining letters, and we get: Ciphertext: opow vx zx One would be able to dismiss the tableau, and use congruences.
The equation used to represent the Vigénère
cipher is ci= pi+ ki (mod
26), where 0 < c i < 25. Each ki
represents the numerical equivalent of a
letter in the key word, while each pi represents the numerical
equivalent of a letter in the paintext, and the ci
is the numerical
equivalent of the ciphertext (Rosen 243). The numerical equivalents
of the letters are as follows:
| a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |
Using the previous example with key word vigenere, the numerical equivalent of the key is:
21 8 6 4 13 4 17 4
The numerical equivalent of the code this is it is as folows:
19 7 8 18 8 18 8 19
Next we find the ciphertext by using p1=19 and k1=21,
and get c1=21+19(mod 26), or c1=40 (mod 26), so
c1=14.
Doing this for the rest of the k's and p's, we obtain:
14 15 14 22 21 22 25 23
Thus we obtain the exact cipherext as before, but without requiring the tableau.
The United States Constitution was drafted in 1787, and ratified in 1789. In that same year, Thomas Jefferson was the Secretary of State. There were many new developments in cryptography during the 1800's, which stemmed from the newly found competition of the United States and other countries (Weber 119). As a result, Jefferson along with John Quincy Adams, Alexander Hamilton and others, communicated using coded messages. Jefferson took an especially strong interest in the security of messages since he was working overseas.
This overpowering desire to find security and an insurance of secrecy led Thomas Jefferson to develop the "wheel cipher" in the 1790's (Beker 60). It was made of a cylinder of wood with an axis through the center. The cylinder is then divided into 26 e qual parts, one for each letter of the alphabet. This is accomplished by taking the circumference of the base and dividing it into 26 equal arcs. Next, the cylinder is sliced 36 times, creating 36 equal cylinders. These cylinders can be rotated about t he axis, or even taken off and switched with a different cylinder. Both the dispatcher and receiver of the coded message must have the same order.
Suppose one wanted to encipher Let's beat those Brits. The first cylinder is turned so the letter "l" is showing. Then, the second cylinder is rotated, so "e" is next to "l", and then the dispatcher follows through with the rest of the phrase. The dis patcher can choose the ciphertext from any of the other sets of letters, and writes them down. (The sets of letters are achieved from the 26 arcs, since one arc is taken by the plaintext, there are 25 other possible choices of text.) The ciphertext is s ent, and the receiver fixes his or her wheel so they are presented in the same order, and then searches about the wheel at the other 25 possibilities to see which makes sense. David Kahn claims Jefferson filed the method of his cipher in papers, which we re not uncovered until 1922 in the Library of Congress (Haldane 87). Concurrently, the United States Army used an almost identical device.
Charles Wheatstone, in 1854 (Bauer 61), invented a cipher which does not bear his name, but the name of Lord Palyfair. The Playfair cipher was commonly used due to its simplicity. There was no tableau or device needed. "The system may have been used f or the first time in the Crimean War and was reportedly used in the Boer War...(Bauer 61)." To implement the cipher a key word is chosen. For example, let's pick the keyword Playfair. The keyword is then written in a 5x5 square followed by the remainin g letters of the alphabet, excluding "J" as shown:
| P | L | A | Y | F |
| X | I | R | B | C |
| D | E | G | H | K |
| M | N | O | Q | R |
| S | T | U | V | Z |
Usually, if a letter occurs twice in a keyword the double of the repeated letter is replaced by an "X". Suppose we wished to encipher The Front Door. The letters of the plaintext are written in pairs: TH EF RO NT DO OR The letters T and H in the square form a rectangle, so the ciphertext would be the opposing corners of the rectangle, VE. The letters EF would be KL. Since R and O are in the same row so the letter to the right is taken as the ciphertext; MQ. Next, N a nd T are in the same column so the ciphertext is the letter directly below: TL. Then DO would be GM. Lastly, OR becomes QM. The ciphertext is written out as follows: VEKLM QTDOL Q Another advantage of the Playfair cipher is since "the letters are paired, single letter frequencies such as the letter E are protected (Haldane 92)."
The early 1900's yielded the development of the radio, which impacted encryptions during World War I. During this time much information was kept secret, especially that of United States Military Intelligence. Herbert Osborne Yardley organized MI-8, in 1918 (Bauer 134). MI-8 was used during World War I with great success. According to Bauer, they deciphered a Japanese telegram that included information of the Japanese desire for expansion in the Far East (Bauer 134). With the election of Herbert Hoov er in 1929, the organization was shut down, and the newly unemployed director of MI-8, Yardley, wrote a book entitled The American Black Chamber. "Herbert O. Yardley's The American Black Chamber is by far the best picture of the activities and personalit ies of a cryptanalytic bureau ever written. It provides more detail, more color, more specifics than any other book (Kahn 55)." Kahn continues saying that not everything in the book is true, some is fictional and exaggerated. Furthermore, the publisher s withheld some information.
A bill presented by the Roosevelt administration in 1933, made it "punishable to publish or furnish without authorization matter which was obtained while in process of transmission between any foreign government and its diplomatic mission in the United S tates (Bauer 134)". Since this bill, it was difficult to obtain literature on cryptography.
An innovative cipher system was introduced publicly in 1976 (Bauer 5), by Witfield Diffie and Martin Helman, known as public-key cryptography. "In this type of cipher system, enciphering keys can be made public, since an unrealistically amount of comput er time is required to find a deciphering transformation form an enciphering transformation (Rosen 259)." The only part that is not made public is the deciphering key. Since it takes too long to decipher, only those that are authorized are able to decip her the message. Public-key cryptography was a huge breakthrough in the field.
Cryptography has developed much since the time of Caesar, and one can see the vast changes and advances that have been made. It is often considered an art due to the many intricacies and complexities held within itself. For some ciphers, one does not need to be knowledgeable of congruences since inventors of ciphers such as Caesar and Vigenére were not alive at the time Guass invented them. Congruences are necessary, however, for the decipherment of codes. It is not always easy to obtain accurate information or a reliable source about cryptography since its whole purpose is to keep things secret and private. "Healthy suspicion about the competency of sources is of course appropriate in all branches of hist orical research, but in the history of cryptography the proportion of misinformed or deceptive sources is probably greater than generally found in the history of a science or technology (Reeds 369)." One such source, I found not to be reliable is written by Fletcher Pratt and is entitled Secret and Urgent. This book has been widely read, but Pratt supplies no sources for the information. The most reliable source seems to be The Codebreakers by David Kahn, which unfortunately I was unable to consult.