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 | 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:

- replacing one letter in an alphabet by another
- Spelling a word backward
- Reversing alternative letters of words
- Giving numerical value to letters, and thus writing words in numbers
- Replacing a plaintext letter with two letters whose numerical value equaled the value of the plaintext letter
- Using a man's name or similar substitutions for letters
- Making special symbols, or lists of names of fruits, trees or countries as ciphertext substitutions

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 *c _{i}= p_{i}+ k_{i} (mod
26)*, where

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 p_{1}=19 and k_{1}=21,
and get c_{1}=21+19(mod 26), or c_{1}=40 (mod 26), so
c_{1}=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.

- Bauer, Friedrich L., Decrypted Secrets, Methods and Maxims of Cryptology, Springer: Germany, 1997.
- Beker, Henry and Fred Piper, Cipher Systems. Jonh Wiley and Sons: New York, 1976.
- Bosworth, C.E., "The Section on Codes and Their Decipherment in Qalqashandi's Subh al-a'sha. Journal of Semitic Studies, Vol. VIII: 1963.
- Kahn, David, The Annotated 'The American Black Chamber', from Cipher A, Deavours, David Kahn, Louis Knih, Greg Millen, and Brian Winkel. Cryptology; Yesterday , Today and Tomorrow. Artech House: Norwood, MA, 1987.
- Haldane, R.A., The Hidden World. St Martin's Press: New York, 1976.
- Padover, Saul K., and James Westfall Thompson. Secret Diplomacy: Espionage and Cryptography 1500-1815. Frederick Ungar Publishing Co: New York, 1963.
- Pratt, Fletcher. Secret and Urgent: The Story of Codes and Ciphers. The Bobbs-Merrill Company: New York, 1939.
- Reeds, Jim. The Code Book: The Evolution of Secrecy from Mary, Queen of Scots to Quantum Cryptography, Note of the AMS, Volume 47, Number 3: March 2000.
- Smith, David Eugene, History of Mathematics, Volume 1. Dover Publications, Inc., New York: 1958.
- Weber, Ralph E., United States: Diplomatic Codes and Ciphers, 1775-1938. Precedent Publishing Inc.: Chicago, 1979.