An Introduction to Cryptography Cryptography, the art or science of making and breaking ciphers has long been the purview of the government--no longer. With the onset of the information age, keeping secrets and discovering other people's secrets has turned into an extremely important exercise. However, to the uninitiated, cryptography seems like magic. A strange combination of mathematics, computer science, and guesswork is used in what turns out to be a centuries old art. Herein is a basic introduction to cryptography from a somewhat different viewpoint. The purpose of a cryptographic scheme is to allow authorized people to communicate without permitting unauthorized people to understand what the message; that is, to be able to transmit these messages in such a way that even if the message falls into the hands of an adversary, it is useless to them. By tradition, one of the earliest ciphers used is writing itself. Indeed writing has all the markings of a complex code, except that almost everyone today knows this system and uses it so frequently that many don't even realize that it is a code. When one talks of bokken, the reader might or might not know what is being referred to. Le livre might make sense to some other people, referring to the same thing, but to many, the book is the form they would be familiar with, again referring to the same object. Each of those means the same thing, they are a representation of an object, but they are not the object itself. A cipher is a way of representing a message, by changing the message according to some set pattern or method to preserve meaning, and make it possible to decrypt or change the message back into its original form. Many ciphers could be thought of as filters, and this sense is how ciphers mentioned here will be looked at. The basic idea behind cryptography is as follows. The message passes through a filter to encrypt the message into the ciphertext. The ciphertext goes to the receiver who passes the ciphertext through a related filter to decrypt the message and obtain the plaintext. After a while, too many people learned the code called writing to allow messages to be securely transmitted in that manner. A new method of keeping messages secret had to be obtained. One of the first such methods is called the Caesar cipher. So called because it was used in the time of the Romans, this cipher would take each letter of the plaintext and replace it with a letter three letters later in the alphabet. In the case of letters near the end, the alphabet was looped around back on itself, so Z would be replaced by C. The Caesar cipher is sometimes referred to as a rot-3 cipher to use computer terms and a form of this scheme is still in limited use today. On occasion on the Internet, a message that could be considered offensive, or to avoid casual scrutiny would be sent in rot-13 format. In this case, the characters are shifted to a character 13 larger. This filtering method of rotation is a rather simple and easy to express filter. A character is put through the filter and a single character comes out according to a very simple preset rule. Unfortunately, this method is considered highly insecure today, and was quickly broken. The filter is flat, each letter gets the same change no matter what it may be. Another similar cipher which again sees limited use today, but not for security, is a substitution cipher. Here, instead of a preset rule to always substitute each letter with another letter, each time a character is shown, a certain other character is written. This cipher could be described as 26 separate band pass filters which each are highly specific, they only act on one letter in the alphabet. All 26 filters are combined to form a single filter that has no overlaps, as each letter in the alphabet has a unique representation in the ciphertext. Here again, the filter would be rather simple, in that it is constant in how it changes each letter. So for example, such a cipher may send A to T, B to K, C to Q, D to G, and so on. However, each letter in the ciphertext stands for one and only one letter in the plaintext, and each letter in the plaintext has a unique mapping into the ciphertext. Or, in mathematical terms, the filter is one to one and onto. While used commonly in newspaper puzzles, this method is only slightly more secure than the rotation cipher. The primary attack is based on letter frequency counts and other rules of formation for a word, like all words have a vowel--one of six letters. So if a one letter word is found for a ciphertext of a formal English message, it is obvious that the letter is either an I or an A. Here the problem of capitalizing versus non capitalizing is ignored. Over time, the method of a cyclic cipher was developed. The problem with the standard substitution cipher is that once a letter is broken, it is broken for the whole message, making guess attacks for each letter a feasible method for cryptanalysis. In this new method, a filter is applied to the filter, where the master filter is a time dependent filter with the lower level filter being time independent. In other words, a regular rule is used to transcribe one letter to another, perhaps a rotation. But instead of a constant rotation, the cipher rule or lower level filter is then changed according to a regular pattern before encrypting the next character. The lower level filter which actually encrypts the message is changed each time by the higher level filter which controls the lower level one. A simple example would be two rotates combined. The lower level cipher would rotate the character by some number of letters. The number of letters would cycle on a 26 long cycle. So while the first occurrence of an A might go to B, in the word AARON, the second A would go to C. The obvious advantage is that this method makes the previous modes of attack much less feasible. To decrypt the message, it is necessary not only to know what the two filters are, but also to know what the initial settings on the higher level filter were. The code can be reused simply by changing the starting point of the higher level filter. This introduces the concept of the key as commonly thought of today: a (usually) short set of information that is required in addition to knowledge of the method used to decrypt the ciphertext (see glossary). This idea of a cylic cipher leads to one of the most famous examples of cryptography, Enigma. In the early part of the twentieth century, a machine was developed for commercial use in Germany called Enigma. This machine was considered extremely secure given that the number of possible keys was enormous. There were several different wheels with a slightly different filter on each, and the combination of any three wheels, combined with what setting the wheels began at made up the key. One of the flaws of Enigma is that a letter could not come up as itself in the encryption. This may not seem as a flaw until you realize that this means that the cryptanalyst can automatically rule out one letter of the alphabet for that character being examined--the letter that appears. Enigma ended up being broken by a machine known as the bombe. One of the first computers, this machine broke the Enigma codes in under 24 hours on average by the end of the war, despite the German use of five wheels by then (instead of three earlier in the war), and regardless of which wheels were used, which order, and what the initial settings were. To give an idea of how much more difficult a key search is with five wheels than three, each wheel having 26 possible settings, and seven possible wheels means 26 * 7 possible settings just for the first wheel in the machine. The second wheel would have 26 * 6 possible settings. And so on down to 26 * 3 possible settings for the third wheel. Multiplying that all together yields 2.994 x 10^10 possible settings for the machine. The early version had five possible wheels so it had a "mere" 1054560 possible keys. The computer had entered the scene by breaking a system believed unbreakable by the Germans, pernamently securing the computer an important place in the list of tools of a cryptanalyst. All was not lost for this relatively simple style of cipher however. Another type of code, called the one time pad, invented in the 1920's, ended up being proven the most secure code of all as long as it was properly used. Enigma relied on a cycle of known length and a system of known length to filter each character into the ciphertext. The one time pad is based on the idea of not having a set cycle of finite length at all. Instead, a key as long as the message is prepared and then used to filter the plaintext to produce the ciphertext. The security comes when a truly random filter is used to filter the data. Since the filter used is random, the outputted data is random. This ciphertext is transmitted to the receiver, who then filters the ciphertext with the same random filter used to encrypt the message, and which causes the plaintext to reappear. Today, the bit representations of the characters is used to simplify the task. The filter is a random bit stream (sequence of ones and zeros), and the data is expressed as bits. By the extended ASCII code, every eight bits makes up one character so the result is actually in the bits, though characters are frequently used as a compact way of expressing the data. Two major problems arise in the one time pad. The first major problem is that the data must be truly random. This means that the receiver must meet beforehand with the transmitter to exchange this random bit stream. Truly random is defined as when any arbitrary bit is chosen, it has no impact on what any other bits in the bit stream are. One way to describe this is by rolling dice. Each die roll is independent of the other rolls, and each roll in itself is random. However, given the size that the filter must be, the person might end up having to do over 8 million die rolls to get a suitable large bit stream to transmit even a fairly ordinary amount of information securely. The second major problem is that the random data can only be used once. If the key is reused, then new attacks appear that could be used to break the cryptoscheme, meaning that the system is no longer truly secure. Despite the problems with the one time pad, it is still considered to be the best possible security. When used properly, it is completely unbreakable. It is just as likely to translate a sequence of ciphertext into MacBeth as it would be to translate the ciphertext into the lectures of a Botany professor, meaning that unless the key is compromised in some manner, the cryptanalyist has no way of knowing when they have successfully guessed the key. The problems of this method show up quite clearly however, and one time pads are not considered acceptable for common use. In an effort to further complicate the job of the cryptanalyst and make codes more secure, cryptographic schemes began to work on blocks of some number of letters at a time, called block ciphers. These ciphers are in common private use today. Before private key schemes are discussed, the concept of the round must be introduced. Sometimes in cryptography it is desirable to take a filter that isn't too complex, but to make the method secure by applying the filter repeatedly over the ciphertext. As all crypto schemes so far examined are letter ciphers (they work on one letter at a time), each letter would be encrypted, then that encrypted letter would be encrypted again, and so on. The number of times the filter is applied over the area is called the number of rounds. Enigma for example used in its most famous form three wheels (later to be upgraded to five) and each wheel was a very closely related filter, but could be set differently, so each wheel used was a round in the encryption. The private key ciphers have been advocated by the US government for private use for many years now. One of the most famous examples is DES or Data Encryption Standard. Another more recent example is called SKIPJACK. Both have been proposed by the government for private use. What the government uses for itself is a matter of speculation and inappropriate for a low level introduction like this paper. The basic idea behind the private key system is that a private key is used to filter the message through some complex but reversible filter. The message is typically filtered through a number of rounds, 32 being the new standard. 32 rounds means that each block of code is sent through the filter 32 times before taking the output. The filter is created to be extremely complex to make reversing the filter a difficult job at best. The entire code would become worthless if a filter were to be created that without the key used could in "reasonable" time recreate the plaintext. DES derives much of its security from the use of multiple rounds like Enigma. Unlike Enigma however, DES will take a block of plaintext and encrypt that entire block. It will then take the next block and encrypt that, and so on until it finishes the message. Commonly blocks are 64 bits in length, or 8 characters. Full DES uses 16 different rounds. In order to provide security for each individual message, a key is used. DES uses a key of 56 bits in length. While this may seem short, being only a few characters in length, this provides for more than 7.2 x 10^16 possible keys. It is only today almost 20 years after DES was adopted as a national standard that DES is considered not secure enough for users who truly insist upon high security. Interestingly, the flaw in DES is considered to be the limited key size. For this reason, modern cryptosystems use keys of much greater length, SKIPJACK using a key of 80 bits in length. Public key systems on the other hand tend to be favored by academia. The most famous example of a public key system is probably RSA. Instead of one function doing both the encryption and the decryption, a slightly different function is used. The function to encrypt a message is published in an electronic phone book, but the function to decrypt is kept secret. This way, anyone can send a person a secret message, but only the appropriate receiver can read it. Imagine if you will having two complementary filters. These two filters are nearly identical for everyone, except for the key used to initialize them. The filters are used to create the ciphertext which is sent to the receiver. The receiver uses the complimentary filter initialized by their private key to decrypt the message. This system makes it easy to add a new person to the list of people who can receive secure communication, without having to compromise another persons security. However, the security of public key systems rests in unproven mathematical assumptions. For example, RSA relies on the difficulty of factoring the product of two extremely large primes (order of magnitude 100 digits). If a method were to be implemented to quickly factor the product of two primes of arbitrary length, then RSA would be completely unsecure, despite being today considered one of the more secure algorithms available for public use. A filter may not be quite the most accurate way to describe a cryptosystem, but it is hoped that the idea behind the cryptosystems described is communicated more effectively to the reader. Given that for the most part, cryptography is a specialized field for highly technical experts, the analogy is useful in describing a subject that is rapidly coming into the public eye today.