(Last Mod: 27 November 2010 21:38:01 )
As the page title indicates, this page provides mostly interesting historical tidbits intended to spice up the discussion of cryptography in the Cryptography Module of the Summer Seminar at the U.S. Air Force Academy.
Please keep in mind that this is not intended to be comprehensive in any way nor is any claim being made that the information presented here is the most important information related to a given topic. Each of these topics could easily (and in many cases have been) expanded into entire books, so a lot of information is completely ignored.
Also keep in mind that the historical accuracy of some of these claims is disputed, particularly those relating to ancient times.
The students attending Summer Seminar come from a highly diverse background, though most have fairly well established math skills. None-the-less, the concepts needed for this module, while simple, are taught in some schools and ignored in others. This exercise is intended to help people get up to speed on the basic concepts needed as well as introduce some of the terminology that will be used.
Consider the following ciphertext:
IWJOBHECDPPDNKQCDHEBAEOOQOPWEJAZXUPDALKSANKBDEOGJKSHAZCA
You will decipher this message using a method similar to that which cost Mary Queen of Scots her head, namely frequency analysis.
Before we get to that, however, let's generate a number that will prove useful later. Perform the following steps on a piece of paper:
The five steps above form what is referred to as an "algorithm" - which is simply as set of steps that are performed to accomplish a given task.
Keep the number that the algorithm produced handy as we will come back to it later in the module.
Step 4 and Step 5 may or may not be familiar to you, so let's look at them in a bit more detail. Recall from grade school (at a time when you only knew about "whole numbers" -- you hadn't learned about fractions or decimals yet) that when you divided, say, 17 by 5 you wrote the result as 3r2, meaning 3 with a remainder of 2. The '3' is known as the quotient and the '2' is known as the remainder. This is all that is being used in these two steps.
For example, let's say that the result of Step 3 was 189. Dividing this by 5 would yield 37r4 and since our algorithm tells us to only keep the integer quotient, the result of Step 4 would be 37. Moving to Step 5, 37 divided by 26 (also written as 37/26) would yield 1r11. Since we are told to only keep the integer remainder, the final result of our algorithm would be 11.
In general, if we always divide our results by N and keep only the remainder, we are said to be "reducing the result modulo N". A common shorthand for this is to simply say that we are "working in a mod-N world" or something similar. We will make a lot of use of this concept throughout this module.
Simply put, cryptography is the art and science of secret communications. Until relatively recently -- say the last fifty years or so -- this was restricted to the goal of "confidentiality" in which one aimed to keep unauthorized readers from comprehending the contents of the message.
In the classic jargon of the cryptoworld, "Alice" and "Bob" are our two "good-guys" that want to communicate with each other while "Eve" is the evil eavesdropper that has figured out a way to make a copy of anything Alice and Bob send each other without them knowing about it. Since Alice knows that Eve might intercept her messages to Bob, she wants to take the actual message, known as the "plaintext" and modify it to create the "ciphertext." The means by which she does this is generically referred to as her "encryption algorithm." She will then transmit the ciphertext to Bob anticipating that Eve will likely get a copy of it. Bob will then apply his "decryption algorithm" in order to transform the ciphertext back into the plaintext. Of course, the whole exercise is pointless unless something prevents Eve from doing the exact same thing; therefore the bottom-line goal is to develop algorithms that make it hard for Eve to do the exact same thing.
As cryptography evolved, particularly in the first half of the 20th century, and as electronic communication systems became widespread in the post-WWII era, two other aspects of "information security" began getting more and more attention, namely "integrity" and "authenticity". In essence, we have added a new player to our game, "Malory," who not only has the ability to read messages sent between Alice and Bob, but to maliciously change them as well. The usual example is that Alice sends the message, "Attack at dawn" to Bob but Malory intercepts it and modifies it to read "Attack at noon" before sending it on to Bob. The result is that Alice commences her attack at dawn but Bob is not there to support her and hence her army is defeated. Likewise, when Bob attacks at noon he can't get the support he needs from Alice's already defeated forces and hence he, too, is vanquished. So there is a need to develop a means of ensuring that the message received has not been altered, or at least a means of detecting the fact that it has. This is known as ensuring message integrity. A variation on this occurs when Malory, instead of changing the contents of a legitimate message, fabricates his own message and sends it to Bob while pretending to be Alice. In this case, Bob needs a way of verifying that a message that claims to be from Alice could, in fact, only have been created by Alice. This is referred to as message authentication.
Modern cryptographic algorithms are capable of attaining all three of these security goals when properly used: That is, when Bob receives a message from Alice, he can be confident that no one else in the world could have read it, that the plaintext he recovers from it is a perfect copy of the plaintext that was sent, and that the message did, in fact, come from Alice. This is an extremely powerful capability -- in fact, things that we take for granted every day, such as on-line shopping and banking (and e-commerce in general) would not be possible without it. These cryptographic algorithms for the basis of the protocols used whenever someone accesses a "secure web site", which is one whose url starts with "https://".
Since Eve has the ability to get complete copies of everything that Bob receives from Alice, the only way to keep Alice from decrypting the ciphertext just as easily as Bob is to ensure that Bob has access to information that Eve does not. The minimum amount of information that Bob has to have but that has to be kept secret from Eve is known as the message "key", in that anyone that has it can "unlock" the ciphertext to get the underlying plaintext.
Somewhat surprisingly, the amount of material that constitutes the key has historically gotten smaller over time. Originally everything about the algorithm had to be kept secret and thus the entire algorithm was also the key. But as cryptography grew we devised algorithms in which only a relatively small, critical piece had to be kept secret. One of the first strong ciphers, DES (Data Encryption Standard), was approved in 1976 and used by much of the financial world to safeguard financial transactions (including multi-billion dollar international transactions) for nearly a quarter of a century afterword. It had a 56-bit key. To put this in context, we could represent the key using 64 printable characters by restricting ourselves to the upper and lower case letters, the digits, and just two punctuation marks (say the plus sign and the forward slash - '+' and '/'). Each character would therefore represent six bits of the key requiring only ten characters to represent the key.
DES probably represents a historical minimum in which growing sophistication in algorithm development could no longer offer shorter key sizes in light of increasing processing power available for performing brute force attacks. For instance, at the time that DES was developed it probably would have taken a high-end computer costing millions of dollars well over a thousand years to break the key using brute force techniques. Today, specially designed hardware can do it in less than a day and relatively low cost, easy to build hardware can do it in less than a week. So for the last twenty years key sizes have been increasing and the present main-line encryption algorithm, AES (Advanced Encryption Standard) has a 256-bit key. Even so, this key can still be represented by 43 characters (as described above), equivalent to a sentence containing only about eight words.
As with most human endeavors, cryptography began from very simple origins using very crude methods. In fact, it evolved for several thousands of years before it ever had a name or was studied in any systematic way. To fully appreciate it's beginnings, it's necessary to appreciate the context in which it was first used. First off, languages tended to be very local and people separated by even comparatively short distances, perhaps only a few tens of miles, could not communicate with each other. As a result, it was usually adequate to send even important messages by simply telling the message to a messenger and then having the messenger travel to the recipient and recite the message. If the messenger was captured the message was safe as long as none of the captors spoke the same language as the messenger.
For the cryptosystem described above, what is the algorithm? The algorithm was explicitly given:
What is the key? Remember that the "key" is the information that Bob (the recipient) must have but that Eve (the captors) must not. Hint: consider the last sentence carefully. The key is the language spoken by the messenger!
It might seem unbelievable that such a system could possibly provide any security, but in fact the United States used this same system very effectively beginning in WWI and ending shortly after the start of the Vietnam War when it used Native American radio operators to transmit messages in their native language. The best known examples were the Navajo "code talkers" used in the Pacific Theater. The Navajo language is extremely complex, difficult to learn, unwritten (i.e., has no alphabet or symbols associated with it), and, at the time, it was estimated that fewer then 30 non-Navajo people in the world spoke it (and none of them were Japanese).
Going back to the ancient times, relying on potential captors not being able to speak the language of the messenger was a pretty risky approach, so a second approach, almost as simple, evolved: Write the message down and have the messenger deliver it. What is the key in this case? The written language! This was effective for a long time because literacy rates, even among the leaders of a society, were near zero for most of human history. If a message was captured by an opposing army it was very unlikely that anyone in that army, even the commander, could read or write. Of course, as societies evolved and grew this changed until most "educated" people (still a small fraction of the population) could read and write as well as speak many of the languages used by nearby societies. At this point more thought had to be put into how to safeguard secret messages.
One account from about 500 B.C. tells of Histiaeus shaving the head of the messenger and essentially tattooing the message on the person's head. After the hair had grown in enough to hide the message, the messenger then made his way to Aristagoras of Miletus and told him to shave his head to see the message. Today this seems humorously absurd, but we live in a world in which people routinely travel to even the furthest points of the globe in less than a day and exchange information with people in even the most remote locations in real time, so it can be hard for us to appreciate that this was at a time when few people ever traveled more than twenty miles from where they were born and that a courier generally could only make 25 to 100 miles a day over the best ground and over broken terrain might be lucky to manage ten miles a day. Despite this, diplomacy and wars were still carried out over distances of thousands of miles requiring weeks of travel each way.
Eventually, of course, people began putting more thought into how they could systematically relay secret messages. One such method dates back twenty-five hundred years to ancient Sparta. They would wrap a piece of cloth around a scytale (rhymes with Italy), which was basically a shaft of wood or other material, and write the message lengthwise along the shaft such that each successive letter was written on the adjacent wrap of cloth. The cloth was then removed from the scytale and given to a messenger, who frequently disguised the cloth as a belt or the straps on an animal pack. When delivered to the recipient, who had a matching scytale, the cloth would be wrapped around the shaft and the message read.
This is an example of a transposition cipher, which is a cipher in which the letters that make up the plaintext message are only rearranged -- i.e., they are simply shuffled. In this case, the ciphertext is generated by splitting the plaintext into N strings where N is the number of characters that can be written around the circumference of the scytale and then interleaving the N strings. The plaintext is recovered by simply taking every Nth letter of the ciphertext
What is the key? It might be easy say that N is the key and, in most respects, this is correct. But since we are, somewhat informally, using the "key" to mean all of the information that must be kept secret to prevent Eve from deciphering the message, we have to ask how hard it would be for Eve to decipher our message if she knows the algorithm but doesn't know N? Certainly knowing both algorithm and N would make it trivial for Eve to decipher the message, but even if she didn't know N, her knowledge of the algorithm would permit her to decipher the message in pretty short order. She can use a brute force attack and simply try all values of N knowing that, for practical reasons, N can't be very large (perhaps 100 or so). So the only way for this method to provide any reasonable level of security is if the entire algorithm remains a secret from Eve and, hence, from one perspective, the key consists of the entire algorithm as well as the particular value of N. Keeping all of this secret is a very difficult task, especially over any significant period of time. Consequently, the scytale's lifespan as a useful cryptographic tool was probably very short. Today relying on the algorithm itself remaining secret is known as "security through obscurity" and is considered the hallmark of a very poor algorithm.
Several hundred years after the scytale faded away, Julius Caesar invented a number of algorithms for relaying secret messages. Unfortunately, while it is known that these were chronicled in the a treatise written by Valerius Probus roughly a century later, the book itself was destroyed and so the details of most of his algorithms are unknown. However, it is almost certainly the case that they all relied on security through obscurity and where therefore only good for a fairly short period of time, which perhaps explains why he invented so many. One algorithm -- argued to be the first use of a substitution cipher in a military situation -- simply involved replacing the Latin letters of the plaintext message with their corresponding Greek letters. Caesar himself wrote of this cipher, known today simply as the Caesar Cipher, in his work The Gaelic Wars. Another one involved replacing each letter with the letter three places further down in the alphabet - hence 'A' became 'D', 'M' became 'P', and 'Y' became 'B' (notice the "wraparound" involved in this last example). This is known as the "Caesar Shift Cipher".
These types of ciphers are known as substitution ciphers because each character of the plaintext, while retaining its corresponding position within the ciphertext, is substituted by a different character.
The Caesar Shift Cipher was very easy to use, as illustrated below:
| PLAIN | 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 |
| CIPHER | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | A | B | C |
Stones with this table inscribed on them (written in two concentric circles) have been found.
To encrypt the word "CRYPTO" simply look up each letter on the "PLAIN" line and replace with the corresponding letter on the "CIPHER" line. The result in this case is "FUCSWR". To decrypt it, simply reverse the process looking up each cipher character on the "CIPHER" line and replacing it with the corresponging letter on the "PLAIN" line.
Today we usually generalize the Caesar Shift Cipher by removing the requirement that the offset be 3 and, instead, allow the offset to be any of the 26 possible shifts. There is no evidence that Caesar ever used any shift other than 3. The quick conclusion might be that he didn't realize that he could use different shifts to obtain different ciphers. However, it is unlikely that this escaped him. More likely, it implies that Caesar was aware that using different shifts would offer no additional security - specifically, he was aware that the security lay in keeping the entire algorithm secret and that once the algorithm itself became known to the enemy, changing the shift amount would accomplish nothing.
While a political prisoner, Mary Queen of Scots became involved in a conspiracy to assassinate Queen Elizabeth I of England and claim the English crown as her own. She communicated with her conspirators using a substitution cipher in which each letter was replaced by a different symbol (as opposed to another letter). In addition, five symbols represented "nulls" (junk that was added to confuse the adversary) as well as a handful of symbols that represented whole words. The conspiracy was discovered and all of the other participants executed, but due to political reasons Queen Elizabeth could not afford to have Mary executed without proof that she was both aware of and active in the conspiracy. This proof was provided by Thomas Phelippes, England's first true cryptanalyst.
Philippes had learned of the work of Arabs, the first cryptanalysts, that dated from the 8th century. At that time nearly all ciphers were essentially mono-alphabetic meaning that each character in the plaintext was converted to a character in the ciphertext using the same substitution rule. For example, an 'A' in the plaintext was always replaced by a 'J' in the ciphertext and, even more importantly, a 'J' in the ciphertext always represented an 'A' in the plaintext. Since certain letters are used more frequently in a given language than others, it is possible to make good guesses about the mapping between plaintext characters and ciphertext characters. For instance, in English, the letter or symbol that appears most frequently in the ciphertext most likely represents the letter 'E' in the plaintext. Using frequency analysis on the many intercepted messages, Phellippes was able to decipher the messages and show that Mary was an active plotter in the conspiracy. As a result, she was beheaded in 1587.
In actuality, Mary made a mistake that has been made by many others, both before and after her. She believed that by encrypting her messages that it was impossible for others to read them. As a result, she and her conspirators wrote their messages in clear and unmistakable terms. For instance, had she written "should events evolve along such lines as to require it, rest assured that I will do whatever I can to help our nation recover, though it is unlikely that I would have the opportunity to even try since, as a prisoner, it is most likely that I would be killed as part of any such events" she might have had a chance of convincing the court that she was not advocating the overthrow of the Queen but rather simply stating that she could always be counted upon to do what her nation called upon her and had merely been observing that it was probably a moot point. Instead, she wrote something very much along the lines of, "I must be freed from prison before you kill Queen is killed lest my jailer murder me before you can free me."
Recall the encrypted message from the Breaking the Ice section. The plaintext was enciphered using a generalized Caesar Shift Cipher. Using frequency analysis, see if you can crack the cipher and recover the plaintext. Once you have done so, see if you can determine the relevance of the number that the algorithm in that same section produced at the end of Step 5.
At about the same time that Mary Queen of Scots was losing her head because she used a cipher that cryptanalysts had learned how to crack, Blaise de Vigenere devise a polyalphabet cipher, known now as the Vigenere Cipher, in which a given plaintext character might be represented by different ciphertext characters and, more importantly, a given ciphertext character could represent several different plaintext characters. This cipher was believed to be unbreakable for roughly the next 300 years. It was not until about the time of the American Civil War that Charles Babbage and Friedrich Kasiski, working independently, devised a means of defeating it.
Today a common early homework assignment in a cryptography course is to break a Vigenere cipher. While it's somewhat ironic that breaking a cipher that defeated the best minds of nearly three centuries has almost literally become child's play, we must always remember that it became so only after some truly superb minds finally figured out how to crack it.
The Enigma machine was a very sophisticated machine used by the Germans in WWII, although it originated as a commercial cipher machine used by businesses in the years between WWI and WWII. In essence, an Enigma machine can be thought of as a polyalphabetic cipher on steroids. At any given moment the machine is in a state that will map a plaintext character to a ciphertext character and vise-versa. However, that mapping changes for each character. The order in which the mappings occur is controlled by the configuration of the machine and its initial settings. These configurations changed regularly -- at first monthly or weekly but soon daily and, by war's end, several times a day. Furthermore, the initial settings were changed for every message (ideally).
A common misconception is that the Germans believed Enigma to be unbreakable and were unaware of several of its weaknesses. For instance, the presence of a "reflector" wheel meant that no plaintext character could ever encrypt to itself. In fact, the Germans were aware of most of these weaknesses but determined that, despite those weaknesses, the amount of effort needed to break Enigma was simply too great for any adversary to commit to the effort. What they failed to realize was that their view of the war and England's view of the war were very different. Germany, as the aggressor, always had the option (at least subconsciously) of ending the war with a negotiated settlement. Furthermore, they controlled the pace of the war and, in the early stages, were clearly winning. England, on the other hand, was fighting a war for survival and was a hair's breadth from defeat very quickly; therefore no price was too great to pay.
England had become dependent on merchant traffic from the United States and a handful of other countries for the material it needed to survive. This material had to sail across the Atlantic and was ruthlessly targeted by the German Navy, particularly the U-boats (submarines). Losses were averaging nearly twenty ships (plus their invaluable cargos) a week, an unsustainable rate. Even convoys that were heavily escorted suffered withering losses. England realized that it had to find a way to know where the U-boats were, in advance, so that they could route the convoys around the German Wolfpacks. This convinced them of the critical importance of cracking the codes used by the U-Boats, known as the Naval Enigma, frequently and quickly enough to do some good. England therefore brought hundreds of the best minds together at Bletchley Park (officially called the Government Code and Cipher School) and gave them the task of breaking this, and other, intercepted codes. At the height of activity there, Bletchley employed over nine thousand people. The electromechanical "bombes", designed by Alan Turing and others, worked through all possible settings, eliminating large segments of the potential workspace by exploiting weaknesses in how the Enigma worked and was used in practice. By the end of the war, 211 bombes were working -- requiring a dedicated staff of over two thousand people -- and could search the entire space in six hours (on average, they found the settings in half that time). Since settings changed each day at midnight, this meant that by midmorning the British were usually deciphering that day's traffic in real time. In rising to this challenge, the field of cryptanalysis made great strides as did the field of computer technology - in fact the Colussus, designed and built at Bletchley to break a different high-level German cipher system, was the first fully programmable digital computer.
Recall that the Germans felt that Enigma was too difficult to break in practice because of the extreme effort that would be required even in spite of its handful of weaknesses. It might seem like this was a false belief, given the British success at cracking the Enigma codes. However, one key component that allowed the British to attain success were poorly designed operating practices or, in other instances, poorly disciplined operators that ignored proper practices. Since all it took on any given day was one poorly disciplined operator to compromise that day's settings, the odds were stacked against the Germans. None-the-less this was not always the case and there exist to this day several Enigma messages that have yet to be deciphered despite ongoing efforts to do so (for historical reasons as well as to earn bragging rights). Thus the Germans were arguably correct in their belief, but were simply overconfident about their ability to ensure that the technology would consistently be used properly. This was not the first, or last, time that this mistake would be made.
The only existing practical cipher system that, used properly, is provably secure -- meaning that no amount of time or processing power can recover the plaintext from the ciphertext -- is the one-time pad. A one-time pad is extremely simple to create and use, but very difficult to manage in practice. To create a one-time pad, you simply generate a very long string of random characters which will serve as the key. To use a one-time pad, you simply combine the plaintext with the key, character by character, to produce the ciphertext. The recipient does the same thing with their copy of the key, only in reverse, to recover the plaintext.
The security of the algorithm stems from the fact that the key is completely random such that any character in the key could literally be any character and no amount of knowledge about the algorithm, or even the other characters in the key, will help the attacker determine it. As a result, without the key, any potential ciphertext could represent any potential plaintext with the only difference being the key. For example, the cipher text KWYXP could represent the plaintext words WOMAN, KITES, DODGE, YEMEN, FIFTH, A BIRD, TO ROT, FLY IN, or any other five letter sequence, with equal probability.
The problem with a one-time pad is that, as the name implies, it can only be used once. Let's say that you are in charge of running a large group of spies and that each spy could send back a report each day that was up to five pages long. Since maintaining secrecy is of the utmost importance, you choose to use a one-time pad and since you know that one-time pads must never be used more than once, you give each spy two distinct sets of key material (one to encrypt outgoing material and one to decrypt incoming material). If you are running one thousand spies, that means that you must generate and print twenty thousand pages of key material every day. And that only let's you talk to the spies and them with you - they can't talk to anyone else. If they work in groups of, say, ten and must be able to exchange messages amongst themselves then this would increase the amount of key material by a factor of 450 to nine million pages of key material each day.
Both the United States and the Soviet Union have made extensive use of one-time pads. In fact, it is commonly understood that the NSA (the National Security Agency) maintained the largest printing presses in the world for the sole purpose of printing key material for U.S. agents. The Soviets used one-time pads during WWII and the U.S. had a strong interest in determining if the Soviets, ostensibly our allies, had intentions of entering into a pact with Germany and changing sides. A relatively small fraction of these enciphered messages fell into U.S. hands. For a time during 1942, the Soviets lacked the generating and printing resources needed to keep up with demand for one-time pads and therefore resorted to using individual pages in two different books. They were fully aware of the theoretical risk in doing so, but also knew that to take advantage of it the Americans would first have to intercept two different messages that just happened to have used the same key page. Then, even if they did, to find them they would have to compare every intercept to every other intercept and that, even then, detecting that the same key had been used to encrypt two different pieces of cyphertext would be a challenging task. So they believed that, in practice, they were still effectively using one-time pads and therefore their communications were secure.
Unfortunately, for the Soviets, when they made the decision to re-use pad pages in 1942 they could not predict the processing capabilities that would be available later nor could they predict how seriously the U.S. would take safeguarding its nuclear secrets. When the Soviets detonated their first atomic bomb in 1949 it shocked the rest of the world, particularly the U.S., who firmly believed that it would take the Soviets much longer than that -- unless they had had help. The U.S. had retained all of the message traffic it had intercepted during the war (and afterwards) and, since the the U.S. emerged from WWII as the world's most powerful economy by a very wide margin, the U.S. had the willingness and the resources to undertake the Herculean task that the Soviets had assumed no country could possibly manage. In a project known as Venona, enough instances of key re-use were detected to permit the NSA to break perhaps one percent of the messages it had captured. But, as a result, it was discovered that the Soviets had had active espionage activities within the Manhattan Project during WWII and several Soviet spy rings were discovered and investigated. In the most famous case, Julius and Ethel Rosenburg were charged with conspiracy to commit espionage, convicted, and on 19 June 1953 sent to the electric chair at Sing Sing prison.
Although the codebooks containing re-used pads were only produced in 1942 and all of them had been used by 1948 (the vast majority had been used by 1945), the NSA kept examining the intercepts, and occasionally breaking a new one, until 1980 when it concluded that it had found all of the instances it was going to and shut the project down.
NOTE: These are pretty much in random order at the present time. They need to be organized and annotated.
http://en.wikipedia.org/wiki/Data_Encryption_Standard
http://en.wikipedia.org/wiki/Code_talker
http://www.counton.org/explorer/codebreaking/transposition-ciphers.php
Singh, Simon, The Code Book: The Evolution of Secrecy from Mary Queen of Scots to Quantum-Cryptography (New York, Doubleday, 1999).
Hinsley, Harry and Stripp, Alan (editors), Code Breakers: The Inside Story of Bletchley Park (Oxford, Oxford University Press, 1993).
Kahn, David, Seizing the Enigma: The Race to Break the German U-Boat Codes, 1939-1943 (New York, Barnes and Noble Books, 2001).
http://www.dragonwins.com/crypto/modular_arithmetic_intro.htm#Modular%20Multiplicative%20Inverse
http://en.wikipedia.org/wiki/Caesar_cipher
http://www.rivier.edu/departments/mathcs/Resources/LectureSeries/CryptographyThroughTheAges.ppt
http://www.tandf.co.uk/journals/press/ucry_pr2.pdf
http://en.wikipedia.org/wiki/Ethel_and_Julius_Rosenberg
http://en.wikipedia.org/wiki/Venona