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.