Paper on Learning about Cryptography
8d5dac29372daf7cc9e3a5cbc6547b8376ef421bc903570c432ce5088ebc0460<HTML>
<HEAD>
<TITLE>Learning About Cryptography</TITLE>
<META NAME = "DESCRIPTION"
CONTENT = "A basic introduction to cryptography: ciphers,
keys, keyspace, strength, cryptanalysis, etc.
A Ciphers By Ritter page.">
<META NAME = "KEYWORDS"
CONTENT = "beginning,crypto,cryptography,encryption,cipher,
design,learning,information,introduction,books">
</HEAD>
<BODY>
<H1 ALIGN = CENTER>Learning About Cryptography</H1><BR>
<H2 AlIGN = CENTER>A Basic Introduction to Crypto<BR>
A <A HREF = "http://www.io.com/~ritter/"><I>Ciphers By Ritter</I></A> Page</H2>
<BR><H2 ALIGN = CENTER>Terry Ritter</H2><BR>
<H2 ALIGN = CENTER>Current Version: 1999 Jan 09</H2><BR>
<P>For some reason, good cryptography is just <I>much</I> harder than
it looks. This field seems to have a continuous flow of experts from
other fields who offer cryptographic variations of ideas which are
common in their other field. Now, there is nothing wrong with new
ideas. But there are in fact <I>many</I> extremely intelligent and
extremely well-educated people with wide-ranging scientific interests
who are active in this field. It is <I>very common</I> to find that
so-called "new" ideas have been previously addressed under another
name or as a general concept. Try to get some background before
you get in too deep.
<P>You may wish to help support this work by patronizing
<A TARGET = "Bshop"
HREF = "http://www.io.com/~ritter/BOOKSHOP.HTM">Ritter's Crypto Bookshop</A>.
<P><HR><H3>Contents</H3>
<UL>
<LI><A HREF = "#Fundamental">The Fundamental Idea of Cryptography</A>
<LI><A HREF = "#AConcreteExample">A Concrete Example</A>
<UL>
<LI><A HREF = "#ExSimpCiph">A Simple Cipher</A>
<LI><A HREF = "#ExEnc">Enciphering</A>
<LI><A HREF = "#ExDec">Deciphering</A>
<LI><A HREF = "#ExSingTrans">The Single Transformation</A>
<LI><A HREF = "#ExManyTrans">Many Transformations</A>
<LI><A HREF = "#ExWeakStrong">Weak and Strong Transformations</A>
<LI><A HREF = "#ExKeyspace">Keyspace</A>
<LI><A HREF = "#ExDigElect">Digital Electronic Ciphering</A>
<LI><A HREF = "#ExHugeKeys">Huge Keys</A>
</UL>
<LI><A HREF = "#NaiveCiphers">Naive Ciphers</A>
<LI><A HREF = "#NaiveChallenges">Naive Challenges</A>
<LI><A HREF = "#WhatCryptCanDo">What Cryptography Can Do</A>
<LI><A HREF = "#WhatCryptCanNotDo">What Cryptography Can Not Do</A>
<LI><A HREF = "#CryptWithKeys">Cryptography with Keys</A>
<LI><A HREF = "#ProbsWithKeys">Problems with Keys</A>
<LI><A HREF = "#CryptWithoutKeys">Cryptography without Keys</A>
<LI><A HREF = "#Keyspace">Keyspace</A>
<LI><A HREF = "#Strength">Strength</A>
<LI><A HREF = "#SystemDesignAndStrength">System Design And Strength</A>
<LI><A HREF = "#CryptanalysisVsSubversion">Cryptanalysis versus Subversion</A>
<LI><A HREF = "#SecretCiphers">Secret Ciphers</A>
<LI><A HREF = "#HardwVsSoftw">Hardware vs. Software Ciphers</A>
<LI><A HREF = "#BlockCiphers">Block Ciphers</A>
<LI><A HREF = "#StreamCiphers">Stream Ciphers</A>
<LI><A HREF = "#PublicKeyCiphers">Public Key Ciphers</A>
<LI><A HREF = "#MostImportantBook">The Most Important Book</A>
<LI><A HREF = "#ClassicalCryptanalysis">Classical Cryptanalysis</A>
<LI><A HREF = "#OtherBooks">Other Books</A>
<LI><A HREF = "#CodingTheory">Coding Theory</A>
<LI><A HREF = "#ForDesigners">For Designers</A>
</UL>
<A NAME = "Fundamental"></A>
<P><HR><H3>The Fundamental Idea of
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Cryptography">Cryptography</A>:</H3>
<P>It is possible to transform or
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Encipher">encipher</A> a message or
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Plaintext"><I>plaintext</I></A>
into "an intermediate form" or
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Ciphertext"><I>ciphertext</I></A>
in which the information is <I>present</I> but <I>hidden.</I>
Then we can release the transformed message (the ciphertext)
without exposing the information it represents.
<P>By using different transformations, we can create many different
ciphertexts for the exact same message. So if we select a
particular transformation "at
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Random">random</A>,"
we can hope that anyone wishing to expose the message
("<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Break">break</A>"
the cipher) can do no better than simply trying all available
transformations (or on average, half) one-by-one. This is a
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#BruteForceAttack">brute force attack</A>.
<P>The difference between intermediate forms is the
<I>interpretation</I> of the ciphertext data. Different
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Cipher">ciphers</A> and different
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Key">keys</A> will produce different
interpretations (different plaintexts) for the exact same
ciphertext. The uncertainty of how to interpret any particular
ciphertext is how information is "hidden."
<P>Naturally, the intended recipient needs to know how to transform or
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Decipher">decipher</A> the intermediate form
back into the original message, and this is the
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#KeyDistributionProblem">key distribution
problem</A>.
<P>By itself, ciphertext is literally <I>meaningless</I>, in the
sense of having no one clear interpretation. In so-called
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#PerfectSecrecy">perfect</A> ciphers,
<I>any</I> ciphertext (of appropriate size) can be interpreted as
<I>any</I> message, just by selecting an appropriate key.
In fact, any number of <I>different</I> messages can produce
<I>exactly the same ciphertext,</I> by using the appropriate keys.
In other ciphers, this may not always be possible, but it must
always be considered. To
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Attack">attack</A> and break a cipher, it
is necessary to somehow confirm that the message we generate from
ciphertext is the exact particular message which was sent.
<A NAME = "AConcreteExample"></A>
<P><HR><H3>A Concrete Example</H3>
<P>Most of us have encountered a simple form of ciphering in grade
school, and it usually goes something like this:
<A NAME = "ExSimpCiph"></A>
<H4>A Simple Cipher</H4>
<P>On a piece of lined paper, write the alphabet in order, one
character per line:
<PRE>
A
B
C
...
</PRE>
Then, on each line, we write another character to the right. In
this second column, we also want to use each alphabetic character
exactly once, but we want to place them in some different order.
<PRE>
A F
B W
C A
...
</PRE>
<P>When we have done this, we can take any message and encipher it
letter-by-letter.
<A NAME = "ExEnc"></A>
<H4>Enciphering</H4>
<P>To
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Encipher">encipher</A> a letter, we find
that letter in the left column, then use the associated letter from
the right column and write that down. Each letter in the right
column thus becomes a substitute for the associated letter in the
left column.
<A NAME = "ExDec"></A>
<H4>Deciphering</H4>
<P><A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Decipher">Deciphering</A> is similar, except
that we find the ciphertext letter in the right column, then use the
associated plaintext letter from the left column. This is a little
harder, because the letters in the right column are not in order.
But if we wanted to, we could make a list where the ciphertext
letters were in order; this would be the <I>inverse</I> of the
enciphering transformation. And if we have both lists, enciphering
and deciphering are both easy.
<A NAME = "ExSingTrans"></A>
<H4>The Single Transformation</H4>
<P>The grade school cipher is a
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#SimpleSubstitution">simple substitution</A>
cipher, a
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#StreamCipher">streaming</A> or repeated
letter-by-letter application of the same transformation. That
"transformation" is the particular arrangement of letters in the
second column, a
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Permutation">permutation</A> of the alphabet.
There can be <I>many</I> such arrangements. But in this case the
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Key">key</A> <I>is</I> that particular
arrangement. We can copy it and give it to someone and then send
secret messages to them. But if that sheet is acquired -- or even
copied -- by someone else, the enciphered messages would be exposed.
This means that we have to keep the transformation secret.
<A NAME = "ExManyTrans"></A>
<H4>Many Transformations</H4>
<P>Now suppose we have a full notebook of lined pages, each of which
contains a <I>different</I> arrangement in the second column.
Suppose each page is numbered. Now we just pick a number and
encipher our message using that particular page. That number thus
becomes our
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Key">key</A>, which is now a sort of numeric
shorthand for the full transformation. So even if the notebook is
exposed, someone who wishes to expose our message must try about
half of the transformations in the book before finding the right
one. Since exposing the notebook does not immediately expose our
messages, maybe we can leave the notebook unprotected. We also can
use the same notebook for messages to different people, and each of
them can use the exact same notebook for their own messages to each
other. Different people can use the same notebook and yet still
cipher messages which are difficult to expose without knowing the
right key.
<P>Note that there is some potential for confusion in first calling
the transformation a
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Key">key</A>, and then calling the number
which selects that transformation <I>also</I> a key. But both of
these act to select a particular ciphertext construction from among
many, and they are only two of the various kinds of "key" in
cryptography.
<A NAME = "ExWeakStrong"></A>
<H4>Weak and Strong Transformations</H4>
<P>The
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#SimpleSubstitution">simple substitution</A>
used in our grade school cipher is very weak, because it "leaks"
information: The more often a particular plaintext letter is used,
the more often the associated ciphertext letter appears. And since
language uses some letters more than others, simply by counting the
number of times each ciphertext letter occurs we can make a good
guess about which plaintext letter it represents. Then we can try
our guess and see if it produces something we can understand. It
usually does not take too long before we can
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Break">break</A> the cipher, even
<I>without</I> having the key. In fact, we <I>develop</I> the
ultimate key (the enciphering transformation) to break the cipher.
<P>A "real" cipher will have a far more complex transformation.
For example, the usual 64-bit
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#BlockCipher">block cipher</A>
will encipher 8 plaintext letters at the same time, and a change in
any one of those letters will change all 8 letters of the resulting
ciphertext. This is still simple substitution, but with a huge
alphabet. Instead of using 26 letters, a 64-bit block cipher views
each of 2<SUP>64</SUP> different block values as a separate letter,
which is something like 18,000,000,000,000,000,000 "letters."
<A NAME = "ExKeyspace"></A>
<H4><A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Keyspace">Keyspace</A></H4>
<P>Suppose we have 256 pages of transformations in the notebook;
this means there are exactly 256 different
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Key">keys</A> we can select from.
If we write the number 256 in
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Binary">binary</A> we get "100000000"; here
the leftmost "1" represents 1 count of 2<SUP>8</SUP>, and we call
this an "8 bit" number.
Or we can compute the base 2 logarithm by first taking the natural
log of 256 (about 5.545) and dividing that by the natural log of 2
(about 0.693); this result is also 8. So we say that having 256
key possibilities is an "8 bit"
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Keyspace">keyspace</A>. If we choose one
of the 256 key values at random, and use that transformation to
encipher a message, someone wishing to
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Break">break</A> our cipher should have to
try about 128 decipherings before happening upon the correct one.
The effort involved in trying, on average, 128 decipherings
(a <A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#BruteForceAttack">brute force attack</A>)
before finding the right one, is the design
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Strength">strength</A> of the cipher.
<P>If our notebook had 65,536 pages or keys (instead of just 256),
we would have a "16 bit" keyspace. Notice that this number of key
possibilities is 256 <I>times</I> that of an "8 bit" keyspace, while
the key itself has only 8 bits <I>more</I> than the "8 bit" cipher.
The strength of the "16 bit" cipher is the effort involved in trying,
on average, 32,768 decipherings before finding the right one.
<P>The <I>idea</I> is the same as a modern cipher: We have a machine
which can produce a huge number of different transformations between
plaintext and ciphertext, and we select one of those transformations
with a key value. Since there are many, many possible keys, it is
difficult to expose a message, even though the machine itself is not
secret. And many people can use the exact same machine for their own
secrets, <I>without</I> revealing those secrets to everyone who has
such a machine.
<A NAME = "ExDigElect"></A>
<H4>Digital Electronic Ciphering</H4>
<P>One of the consequences of having a digital electronic machine
for ciphering, is that it operates very, very fast. This means that
someone can try a lot more possibilities than they could with a
notebook of paper pages. For example, a "40 bit" keyspace represents
about 10<SUP>12</SUP> keys, which sounds like a lot. Unfortunately,
special-purpose hardware could try this many decipherings in under 5
seconds, which is not much strength.
A "56 bit" keyspace represents about <NOBR>7 x 10<SUP>16</SUP></NOBR>
different keys, and was recently broken by special
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#BruteForceAttack">brute force hardware</A>
in 56 hours; this is <I>also</I> not much strength.
The current strength recommendation is 112 to 128 bits, and 256 is
not out of the question. 128 bits is just 16 bytes, which is the
amount of storage usually consumed by 16 text characters, a very
minimal amount. A 128 bit key is "strong enough" to defeat even
unimaginably extensive brute force attacks.
<A NAME = "ExHugeKeys"></A>
<H4>Huge Keys</H4>
<P>Under the theory that if a little is good, a lot is better, some
people suggest using huge keys of 56,000 bits, or 1,000,000 bits,
or even more. We <I>can</I> build such devices, and they can operate
quickly. We can even afford the storage for big keys. What we do
<I>not</I> have is a <I>reason</I> for such keys: a 128 bit key is
"strong enough" to defeat even unimaginably extensive brute force
attacks. While a designer might use a larger key for convenience,
even immense keys cannot provide more strength than "strong enough."
And while different attacks may show that the cipher actually has
less strength, a huge keyspace is not going to solve those problems.
<P>Some forms of cipher <I>need</I> relatively large key values
simply to have a sufficiently large keyspace. Most number-theory
based
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#PublicKeyCipher">public key ciphers</A>
are in this class. Basically, these systems require key values in
a very special form, so that most key values are unacceptable and
unused. This means that the actual keyspace is much smaller than
the size of the key would indicate. For this reason, public key
systems need keys in the 1,000 bit range, while delivering strength
comparable to 128 bit
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#SecretKeyCipher">secret key ciphers</A>.
<A Name = "NaiveCiphers"></A>
<P><HR><H3>Naive Ciphers</H3>
<P>Suppose we want to hide a name: We might think to innovate a
different rule for each letter. We might say: "First we have 'T',
but 't' is the 3rd letter in 'bottle' so we write '3.'" We can
continue this way, and such a
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Cipher">cipher</A> could be very difficult to
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Break">break</A>. So why is this sort of
thing not done? There are several reasons:
<OL>
<P><LI>First, any cipher construction must be
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Decipher">decipherable</A>, and it is all
too easy, when choosing rules at random, to make a rule that
depends upon
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Plaintext">plaintext</A>, which will
of course not be present until <I>after</I> the
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Ciphertext">ciphertext</A> is deciphered.
<P><LI>The next problem is remembering the rules, since the rules
constitute the
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Key">key</A>. If we choose from among
many rules, in no pattern at all, we may have a
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Strength">strong</A> cipher, but
be unable to remember the key. And if we write the key down, all
someone has to do is read that and properly interpret it (which
may be another encryption issue). So we might choose among few
rules, in some pattern, which will make a weaker cipher.
<P><LI>Another problem is the question of what we do for longer messages.
This sort of scheme seems to want a different key, or perhaps just
more key, for a longer message, which is certainly inconvenient.
What often happens in practice is that the key is re-used repeatedly,
and <I>that</I> will be very, very weak.
<P><LI>Yet another problem is the observation that describing the
rule selection may take more information than the message itself.
To send the message to someone else, we must somehow transport the
key securely to the other end. But if we <I>can</I> transfer this
amount of data securely in the first place, we wonder why we cannot
securely transfer the smaller message itself.
</OL>
<P>Modern ciphering is about constructions which attempt to solve
these problems. A modern cipher has a large
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Keyspace">keyspace</A>, which might well
be controlled by a
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Hash">hashing</A> computation on a
language phrase we can remember. A modern cipher system can handle
a wide range of message sizes, with exactly the same key, and
normally provides a way to securely re-use keys. And the key can be
much, much smaller than a long message.
<P>Moreover, in a modern cipher, we expect the key to not be
exposed, <I>even if</I>
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Opponent">The Opponent</A> has <I>both</I>
the plaintext <I>and</I> the associated ciphertext for many
messages (a
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#KnownPlaintextAttack">known-plaintext attack</A>).
In fact, we normally assume that The Opponent knows the full
construction of the cipher, and has lots of known plaintext, and
<I>still</I> cannot find the key. Such designs are not trivial.
<A Name = "NaiveChallenges"></A>
<P><HR><H3>Naive Challenges</H3>
<P>Sometimes a novice gives us 40 or 50 random-looking characters and
says, "Bet you can't break this!" But that is not very realistic.
<P>In actual use, we normally assume that a
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Cipher">cipher</A> will be widely distributed,
and thus somewhat available. So we assume
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Opponent">The Opponent</A> will somehow acquire
either the cipher machine or its complete design.
We also assume a cipher will be widely used, so a lot of ciphered
material will be around somewhere. We assume The Opponent will somehow
acquire some amount of
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Plaintext">plaintext</A> and the associated
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Ciphertext">ciphertext</A>. And even in this
situation, we <I>still</I> expect the cipher to hide the key and other
messages.
<A NAME = "WhatCryptCanDo"></A>
<P><HR><H3>What
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Cryptography">Cryptography</A> <I>Can</I> Do</H3>
<P>Potentially, cryptography can hide information while it is in
transit or storage. In general, cryptography can:
<UL>
<LI>Provide <A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Secrecy">secrecy</A>.
<LI><A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Authentication">Authenticate</A> that
a message has not changed in transit.
<LI>Implicitly authenticate the sender.
</UL>
<P>Cryptography hides <I>words</I>: At most, it can only hide
<I>talking about</I> contraband or illegal actions. But in a country
with "freedom of speech," we normally expect crimes to be more
than just "talk."
<P>Cryptography can kill in the sense that boots can kill; that is,
as a part of some other process, but that does not make cryptography
like a rifle or a tank. Cryptography is defensive, and can
<I>protect</I> ordinary commerce and ordinary people.
Cryptography may be to our private information as our home is to
our private property, and our home is our "castle."
<P>Potentially, cryptography can hide <I>secrets,</I> either from
others, or during communication. There are many good and non-criminal
reasons to have secrets: Certainly, those engaged in commercial
research and development (R&D) have "secrets" they must keep.
Professors and writers may want to keep their work private, until
an appropriate time. Negotiations for new jobs are generally
secret, and romance often is as well, or at least we might prefer
that detailed discussions not be exposed.
<P>One possible application for cryptography is to secure on-line
communications between work and home, perhaps leading to a
society-wide reduction in driving, something we could <I>all</I>
appreciate.
<A NAME = "WhatCryptCanNotDo"></A>
<P><HR><H3>What
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Cryptography">Cryptography</A> Can <I>Not</I> Do</H3>
<P>Cryptography can only hide information <I>after</I> it is
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Encryption">encrypted</A> and <I>while</I>
it remains encrypted. But secret information generally does not
<I>start out</I> encrypted, so there is normally an original period
during which the secret is not protected. And secret information
generally is not <I>used</I> in encrypted form, so it is again
outside the cryptographic envelope every time the secret is used.
<P>Secrets are often related to public information, and subsequent
activities based on the secret can indicate what that secret is.
<P>And while cryptography can hide <I>words,</I> it cannot hide:
<UL>
<LI>Physical contraband,
<LI>Cash,
<LI>Physical meetings and training,
<LI>Movement to and from a central location,
<LI>An extravagant lifestyle with no visible means of support, or
<LI>Actions.
</UL>
<P>And cryptography simply cannot protect against:
<UL>
<LI>Informants,
<LI>Undercover spying,
<LI>Bugs,
<LI>Photographic evidence, or
<LI>Testimony.
</UL>
<P>It is a joke to imagine that cryptography alone could protect
most information against Government investigation. Cryptography is
only a small part of the protection needed for "absolute" secrecy.
<A NAME = "CryptWithKeys"></A>
<P><HR><H3><A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Cryptography">Cryptography</A> with
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Key">Keys</A></H3>
<P>Usually, we arrange to select among a huge number of possible
intermediate forms by using some sort of "pass phrase" or
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Key">key</A>.
Normally, this is some moderately-long language phrase which we
can remember, instead of something we have to write down (which
someone else could then find).
<P>Those who have one of the original keys can expose the
information hidden in the message. This reduces the problem of
protecting information to:
<OL>
<LI>Performing transformations, and
<LI>Protecting the keys.
</OL>
<P>This is similar to locking our possessions in our house and
keeping the keys in our pocket.
<A NAME = "ProbsWithKeys"></A>
<P><HR><H3>Problems with
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Keyspace">Keys</A></H3>
<P>The physical key model reminds us of various things that can
go wrong with keys:
<UL>
<LI>We can lose our keys.
<LI>We can forget which key is which.
<LI>We can give a key to the wrong person.
<LI>Somebody can steal a key.
<LI>Somebody can pick the lock.
<LI>Somebody can go through a window.
<LI>Somebody can break down the door.
<LI>Somebody can ask for entry, and unwisely be let in.
<LI>Somebody can get a warrant, then legally do whatever is
required.
<LI>Somebody can burn down the house, thus making everything
irrelevant.
</UL>
<P>Even absolutely perfect keys cannot solve all problems, nor can
they guarantee privacy. Indeed, when cryptography is used for
communications, generally at least two people know what is being
communicated. So either party could reveal a secret:
<UL>
<LI>By accident.
<LI>To someone else.
<LI>Through third-party eavesdropping.
<LI>As revenge, for actions real or imagined.
<LI>For payment.
<LI>Under duress.
<LI>In testimony.
</UL>
<P>When it is substantially less costly to acquire the secret by
means other then a technical attack on the cipher, cryptography has
pretty much succeeded in doing what it can do.
<A NAME = "CryptWithoutKeys"></A>
<P><HR><H3><A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Cryptography">Cryptography</A> without
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Key">Keys</A></H3>
<P>It is fairly easy to design a complex
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Cipher">cipher</A>
program to produce a single complex, intermediate form. In this
case, the program itself becomes the "key."
<P>But this means that the
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Decipher">deciphering</A> program must be
kept available to access protected information. So if someone steals
your laptop, they probably will also get the deciphering program,
which -- if it does not use keys -- will immediately expose all of
your carefully protected data. This is why cryptography generally
depends upon at least one remembered key, and why we need
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Cipher">ciphers</A>
which can produce a multitude of different
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Ciphertext">ciphertexts</A>.
<A NAME = "Keyspace"></A>
<P><HR><H3><A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Keyspace">Keyspace</A></H3>
<P><A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Cryptography">Cryptography</A>
deliberately creates the situation of "a needle in
a haystack." That is, of all possible
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Key">keys</A>,
only one should recover the correct message, and that one key is
hidden among all possible keys. Of course, The
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Opponent">Opponent</A>
<I>might</I> get lucky, but <I>probably</I> will have to perform
about half of the possible
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Decipher">decipherings</A> to find the
message.
<P>To keep messages secret, it is important that a
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Cipher">cipher</A>
be able to produce a multitude of different intermediate forms or
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Ciphertext">ciphertexts</A>.
Clearly, no cipher can possibly be stronger than requiring The
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Opponent">Opponent</A> to check
<I>every possible</I> deciphering. If such a
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#BruteForceAttack">brute force</A>
search is practical, the cipher is weak. The number of possible
ciphertexts is the "design strength" of a cipher.
<P>Each different ciphertext requires a different key. So the
number of different ciphertexts which we can produce is limited
to the number of different keys we can use. We describe the
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Keyspace">keyspace</A>
by the length in
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Bit">bits</A> of the
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Binary">binary</A> value required to
represent the number of possible ciphertexts or keys.
<P>It is not particularly
difficult to design ciphers which may have a design
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Strength">strength</A> of
hundreds or thousands of bits, and these can operate just as fast
as our current ciphers. However, the U.S. Government generally
does not allow the export of data ciphers with a keyspace larger
than about 40 bits, which is a very searchable value.
<P>Recently, a 56-bit keyspace was searched (with special hardware)
and the correct key found in about 56 hours. Note that a 56-bit
key represents 2<SUP>16</SUP> times as many transformations as a
40-bit key. So, all things being equal, similar equipment might
find a 40-bit key in about 3 seconds. But at the same rate, an
80-bit key (which is presumably 2<SUP>24</SUP> times as strong as
a 56-bit key) would take over 100,000 years.
<A NAME = "Strength"></A>
<P><HR><H3><A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Strength">Strength</A></H3>
<P><A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Keyspace">Keyspace</A>
alone only sets an <I>upper limit</I> to
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Cipher">cipher</A> strength;
a cipher can be <I>much weaker</I> than it appears. An in-depth
understanding or <I>analysis</I> of the design may lead to
"shortcuts" in the solution. Perhaps a few tests can be designed,
each of which eliminates vast numbers of keys, thus in the end
leaving a searchable keyspace; this is
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Cryptanalysis">cryptanalysis</A>.
<P>We understand
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Strength">strength</A>
as the ability to <I>resist</I> cryptanalysis. But this makes
"strength" a negative quality (the <I>lack</I> of any practical
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Attack">attack</A>),
which we cannot measure. We can <I>infer</I> the "strength" of a
cipher from the best <I>known</I> attack. We can only <B>hope</B>
that The
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Opponent">Opponent</A>
does not know of something much better.
<P>Every user of cryptography should understand that all known
ciphers (<I>including</I> the
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#OneTimePad">one time pad</A>) are at least
potentially vulnerable to some unknown technical attack.
And if such a
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Break">break</A> <I>does</I> occur, there
is absolutely no reason that we would find out about it. However,
a direct technical attack may be one of the <I>least</I> likely
avenues of exposure.
<A NAME = "SystemDesignAndStrength"></A>
<P><HR><H3>System Design and Strength</H3>
<P>Cryptographic design may seem as easy as selecting a
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Cipher">cipher</A> from a book of ciphers.
But ciphers, <I>per se,</I> are only <I>part</I> of a secure
encryption system. It is <I>common</I> for a cipher system to
require cryptographic design beyond simply selecting a cipher, and
such design is much trickier than it looks.
<P>The use of an
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Break">unbreakable</A> cipher does
<B>not</B> mean that the encryption system will be similarly
unbreakable. A prime example of this is the
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#ManInTheMiddleAttack">man-in-the-middle attack</A>
on
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#PublicKeyCipher">public-key ciphers</A>.
Public-key ciphers <I>require</I> that one use the correct
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Key">key</A> for the desired person. The
correct key must be known <B>to cryptographic levels of assurance</B>,
or this becomes the weak link in the system: Suppose an
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Opponent">Opponent</A> can get us to use
his key instead of the right one (perhaps by sending a faked message
saying "Here is my new key"). If he can do this to both ends, and
also intercept all messages between them (which is conceivable, since
Internet routing is <I>not</I> secure), The Opponent can sit "in the
middle." He can decipher each message (now in one of his keys), then
re-encipher that message in the correct user key, and send it along.
So the users communicate, and no cipher has been broken, yet The
Opponent is still reading the conversation.
Such are the consequences of system design error.
<A NAME = "CryptanalysisVsSubversion"></A>
<P><HR><H3>Cryptanalysis versus Subversion</H3>
<P><A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Cryptanalysis">Cryptanalysis</A>
is hard; it is often tedious, repetitive, and very, very expensive.
Success is never assured, and resources are always limited.
Consequently, other approaches for obtaining the hidden
information (or the key!) can be more effective.
<P>Approaches other than a direct technical attack on ciphertext
include getting the information by cunning, outright theft,
bribery, or intimidation. The room or computer could be bugged,
secretaries subverted, files burglarized, etc. Most information
can be obtained in some way other than "breaking" ciphertext.
<P>When the strength of a cipher greatly exceeds the effort required
to obtain the same information in another way, the cipher is probably
strong enough. And the mere fact that information has escaped does
not necessarily mean that a cipher has been broken.
<A NAME = "SecretCiphers"></A>
<P><HR><H3>Secret Ciphers</H3>
<P>Although, in some cases,
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Cryptanalysis">cryptanalysis</A>
might succeed even if the
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Ciphering">ciphering</A>
process was unknown, we would certainly expect that this would
make The
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Opponent">Opponents'</A> job much harder.
It thus can be argued that the ciphering process <I>should</I>
remain secret. Certainly, military cipher systems are not actually
<I>published</I> (although it may be assumed internally that the
equipment is known to the other side). But in commercial
cryptography we normally assume (see
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#KerckhoffsRequirements">Kerckhoff's
Requirements</A>)
that The Opponents <I>will</I> know every detail of the cipher
(although not the
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Key">key</A>,
of course). There are several reasons for this:
<UL>
<LI>First, it is common for a cipher to have unexpected weaknesses
which are not found by its designers. But if the cipher design is
kept secret, it cannot be examined by various interested parties, and
so the weakness will not be publicly exposed. And this means that
the weakness might be exploited in practice, while the cipher
continues to be used.
<P><LI>Next, if a cipher itself is a secret, that secret is increasingly
compromised by making it available for use: For a cipher to be used,
it must be present at various locations, and the more widely it is
used, the greater the risk the secret will be exposed.
So whatever advantage there may be in cipher secrecy cannot be
maintained, and The Opponents eventually will have the same
advantage they would have had from public disclosure. Only now
the cipher designers can comfort themselves with the dangerous
delusion that their Opponents do <I>not</I> have an advantage they
actually <I>will</I> have.
</UL>
<P>There is another level of secrecy here, and that is the trade
secrecy involved with particular software designs. Very few large
companies are willing to release
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#SourceCode">source code</A>
for their products without some serious controls, and those
companies may have a point. While the crypto routines themselves
presumably might be
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Patent">patented</A>,
releasing that code alone probably would not support a thorough
security evaluation. Source code might reasonably be made available
to customers under a nondisclosure agreement, but this will not
satisfy everyone. And while it might seem nice to have all source
code available free, this will certainly not support an industry of
continued cipher design and development. Unfortunately, there
appears to be no good solution to this problem.
<A NAME = "HardwVsSoftw"></A>
<P><HR><H3><A TARGET = "Gloss"
HREF = "#Hardware">Hardware</A> vs
<A TARGET = "Gloss"
HREF = "#Software">Software</A>
<A TARGET = "Gloss"
HREF = "#Cipher">Ciphers</A></H3>
<P>Currently, most ciphers are implemented in software; that is,
by a program of instructions executed by a general-purpose
<A TARGET = "Gloss"
HREF = "#Computer">computer</A>. Normally, software is
cheaper, but hardware can run faster, and nobody can change it.
Of course, there are levels to hardware, from chips (which thus
require significant interface software) to external boxes with
communications lines running in and out. But there are several
possible problems:
<OL>
<LI>Software, especially in a multi-user system, is almost
completely insecure. Anyone with access to the machine could
insert modified software which would then be repeatedly used
under the false assumption that effective security was still
in place. This may not be an issue for home users, and real
solution here may depend upon a secure operating system.
<LI>Hardware represents a capital expense, and is extremely
inflexible. So if problems begin to be suspected in a hardware
cipher, the expense of replacement argues against an update.
Indeed, a society-wide system might well take years to update
anyway.
</OL>
<P>One logical possibility is the development of ciphering
processors -- little ciphering computers -- in secure packaging.
Limited control over the processor might allow a public-key
authenticated software update, while otherwise looking like
hardware. But probably most users will not care until some
hidden software system is exposed on some computers.
<A NAME = "BlockCiphers"></A>
<P><HR><H3><A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#BlockCipher">Block Ciphers</A></H3>
<P>There are a whole range of things which can distinguish one
cipher from another. But perhaps the easiest and most useful
distinction is that between
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#StreamCipher">stream ciphers</A> and
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#BlockCipher">block ciphers</A>.
<P>Logically, a block cipher is just
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#SimpleSubstitution">simple substitution</A>: A
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Block">block</A> of
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Plaintext">plaintext</A>
data is collected and then
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Substitution">substituted</A> into an arbitrary
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Ciphertext">ciphertext</A> value.
So a toy version of a block cipher is just a
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#SubstitutionTable">table</A> look-up, much
like the amusement ciphers in newspapers.
Of course, a realistic block cipher has a block width which is far
too large to hold the transformation in any physical table. Because
of the large block size, the invertible transformation must be
<I>simulated,</I> in some way dynamically <I>constructed</I> for each
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Block">block</A>
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Encipher">enciphered</A>.
<P>In a block cipher, any possible
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Permutation">permutation</A> of "table"
values is a potential
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Key">key</A>. So if we have a
64-<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Bit">bit</A> block, there would
theoretically be 2<SUP>64</SUP>
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Factorial">factorial</A> possible keys,
which is a huge, huge value. But the well-known 64-bit block cipher
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#DES">DES</A> has "only" 2<SUP>56</SUP> keys,
which is as nothing in comparison. In part, this is because any
real mechanism can only <I>emulate</I> the theoretical ideal of a
huge simple substitution. But mostly, 56-bit keys have in the past
been thought to be "large enough." Now we expect at least 128 bits,
or perhaps somewhat more.
<A NAME = "StreamCiphers"></A>
<P><HR><H3><A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#StreamCipher">Stream Ciphers</A></H3>
<P>If a block cipher is a huge
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#SimpleSubstitution">simple substitution</A>,
a stream cipher can be a <I>small</I> substitution which is in some
way <I>altered</I> for each
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Bit">bit</A> or
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Byte">byte</A> enciphered. Clearly,
repeatedly using a small unchanging substitution (or even a
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Linear">linear</A> transformation) is not
going to be secure in a situation where The
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Opponent">Opponent</A> will have a
substantial quantity of
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#KnownPlaintextAttack">known plaintext</A>.
One way to use a small transformation securely is to use a simple
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#AdditiveCombiner">additive combiner</A> to
mix data with a
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#ReallyRandom">really random</A>
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#ConfusionSequence">confusion sequence</A>;
done properly, this is an "unbreakable"
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#OneTimePad">one-time pad</A>.
<P>Logically, a stream cipher can be seen as the general concept of
repeatedly using a block transformation to handle more than one
block of data. I would say that even the simple repeated use of a
block cipher in
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#ECB">ECB</A>
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#OperatingMode">mode</A> would be "streaming"
the cipher. And use in more complex
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Chain">chaining</A> modes like
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#CBC">CBC</A> are even more clearly stream
meta-ciphers which use block transformations.
<P>One common idea that comes up again and again with novice
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Cryptographer">cryptographers</A>
is to take a textual key phrase, and then add (or
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#ExclusiveOR">exclusive-OR</A>) the key
with the data, byte-by-byte, starting the key over each time it
is exhausted. This is a very simple and weak stream cipher,
with a short and repeatedly-used
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#RunningKey">running key</A> and an
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#AdditiveCombiner">additive combiner</A>.
I suppose that part of the problem in seeing this weakness is in
distinguishing between different types of stream cipher "key":
In a real stream cipher, even a single bit change in a key phrase
would be expected to produce a <I>different</I> running key
sequence, a sequence which would not repeat across a message of
any practical size. In the weak version, a single bit change in
the short running key would affect only one bit each time it was
used, and would do so repeatedly, as the keying sequence was
re-used over and over again. In any additive stream cipher, the
re-use of a keying sequence is absolutely deadly. And a real
stream cipher would almost certainly use a random
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#MessageKey">message key</A> as the key
which actually protects data.
<A NAME = "PublicKeyCiphers"></A>
<P><HR><H3><A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#PublicKeyCipher">Public Key Ciphers</A></H3>
<P>Public key
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Cipher">ciphers</A> are generally
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#BlockCipher">block ciphers</A>, with the
unusual property that one
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Key">key</A> is used to
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Encipher">encipher</A>, and a different,
apparently unrelated key is used to
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Encipher">decipher</A> a message.
So if we keep one of the keys private, we can release the
other key (the "public" key), and anyone can use that to encipher
a message to us. Then we use our private key to decipher any
such messages. It is interesting that someone who enciphers a
message to us cannot decipher their own message even if they
want to.
<P>The prototypical public key cipher is
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#RSA">RSA</A>, which uses the arithmetic
of huge numeric values. These values may contain 1,000
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Bit">bits</A> or more (over 400
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Decimal">decimal</A> digits), in which
each and every bit is significant. The
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Keyspace">keyspace</A> is much smaller,
however, because there are very severe constraints on the keys;
not just any random value will do. So a 1,000-bit public key may
have a
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#BruteForceAttack">brute-force</A>
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Strength">strength</A> similar to a 128-bit
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#SecretKeyCipher">secret key cipher</A>.
<P>Because public key ciphers operate on huge values, they are
very slow, and so are normally used just to encipher a random
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#MessageKey">message key</A>. The message
key is then used by a conventional secret key cipher which
actually enciphers the data.
<P>At first glance, public key ciphers apparently solve the
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#KeyDistributionProblem">key distribution
problem</A>. But in fact they also open up the new possibility of a
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#ManInTheMiddleAttack">man-in-the-middle
attack</A>. To avoid this, it is necessary to assure that one is
using exactly the correct key for the desired user. This requires
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Authentication">authentication</A>
(validation or certification) via some sort of secure channel,
and that can take as much effort as a secure secret key exchange.
A man-in-the-middle attack is extremely worrisome, because it
does <I>not</I> involve
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Break">breaking</A> any cipher, which
means that all the effort spent in cipher design and analysis and
mathematical proofs and public review would be completely
irrelevant.
<A NAME = "MostImportantBook"></A>
<P><HR><H3>The Most Important Book</H3>
<P>The most important book in cryptography is:
<UL>
<LI><I><A TARGET = "Bshop"
HREF = "BOOKSHOP.HTM#Kahn"><B>The Codebreakers</B>,</I>
by David Kahn</A> (Macmillan, 1967).
</UL>
<P><I>The Codebreakers</I> is the detailed <I>history</I> of
cryptography, a book of style and adventure. It is non-mathematical
and generally non-technical. But the author does explain why simple
ciphers fail to hide information; these are the same problems
addressed by increasingly capable cryptosystems. Various accounts
show how real cryptography is far more than just schemes for
enciphering data. A very good read.
<P>Other important books include
<UL>
<LI><I><A TARGET = "Bshop"
HREF = "BOOKSHOP.HTM#Bauer"><B>Decrypted Secrets</B>,</I>
by Friedrich Bauer</A> (Springer-Verlag, 1997).
<UL>
In some ways <I>Decrypted Secrets</I> continues in the style
of <I>The Codebreakers,</I> but is far more technical. Almost
half the book concerns cryptanalysis or ways to attack WWII
ciphers.
</UL>
<P><LI><I><A TARGET = "Bshop"
HREF = "BOOKSHOP.HTM#Menezes"><B>Handbook of Applied
Cryptography</B>,</I> by Menezes, van Oorschot and
Vanstone</A> (CRC Press, 1997).
<UL>
The <I>Handbook of Applied Cryptography</I> seems to be the
best technical reference so far. While some sections do raise
the hackles of your reviewer, this happens far less than with
other comprehensive references.
</UL>
<P><LI><I><A TARGET = "Bshop"
HREF = "BOOKSHOP.HTM#Stallings"><B>Cryptography and Network
Security: Principles and Practice</B>,</I>
by William Stallings</A> (2nd ed., Prentice Hall, 1998).
<UL>
<I>Cryptography and Network Security</I> is an introductory
text and a reference for actual implementations. It covers
both conventional and public-key cryptography (including
authentication). It also covers web security, as in Kerberos,
PGP, S/MIME, and SSL. It covers real ciphers <I>and</I>
real systems using ciphers.
</UL>
<P><LI><I><A TARGET = "Bshop"
HREF = "BOOKSHOP.HTM#Simmons"><B>Contemporary Cryptology</B>,</I>
edited by Gustavus Simmons</A> (IEEE Press, 1992).
<UL>
<I>Contemporary Cryptology,</I> is a substantial survey of
mostly mathematical cryptology, although the US encryption
standard DES is also covered. It describes the state of the
art at that time.
</UL>
<P><LI><I><A TARGET = "Bshop"
HREF = "BOOKSHOP.HTM#Wright"><B>Spy Catcher</B>,</I>
by Peter Wright</A> (Viking Penguin, 1987).
<UL>
<I>Spy Catcher</I> places the technology in the context of
reality. While having little on cryptography <I>per se,</I>
it has a lot on <I>security,</I> on which cryptography is
necessarily based. Also a good read.
</UL>
<P><LI><I><A TARGET = "Bshop"
HREF = "BOOKSHOP.HTM"><B>The Puzzle Palace</B>,</I>
by James Bamford</A> (Houghton Mifflin, 1982).
<UL>
<I>The Puzzle Palace</I> is the best description we have of
the National Security Agency (NSA), which has been the dominant
force in cryptography in the US since WWII.
</UL>
</UL>
<P>Good books on "The Vietnam War" (and which have nothing to
do with cryptography) include:
<UL>
<LI><I><A TARGET = "Bshop"
HREF = "BOOKSHOP.HTM#Sheehan"><B>A Bright Shining Lie</B>,</I>
by Neil Sheehan</A> (Random House, 1988),
<LI><I><A TARGET = "Bshop"
HREF = "BOOKSHOP.HTM#Hackworth"><B>About Face</B>,</I>
by Colonel David H. Hackworth</A> (Simon & Schuster, 1989), and
<LI><I><A TARGET = "Bshop"
HREF = "BOOKSHOP.HTM#Adams"><B>War of Numbers</B>,</I>
by Sam Adams (Steerforth Press, South Royalton, Vermont, 1994).
</UL>
<A NAME = "ClassicalCryptanalysis"></A>
<P><HR><H3>Classical Cryptanalysis</H3>
<P>Normally,
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Cryptanalysis">cryptanalysis</A>
is thought of as the way
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Cipher">ciphers</A> are
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Break">broken</A>. But cryptanalysis
is really <I>analysis</I> -- the ways we come to understand a cipher
in detail. Since most ciphers have weaknesses, a deep understanding
can expose the best attacks for a particular cipher.
<P>Two books often mentioned as introductions to classical
cryptanalysis are:
<UL>
<LI><I><A TARGET = "Bshop"
HREF = "BOOKSHOP.HTM#Gaines"><B>Cryptanalysis</B></I>
by Helen Gaines</A> (1939, but still available from
Dover Publications), and
<P><LI><I><A TARGET = "Bshop"
HREF = "BOOKSHOP.HTM#Sinkov"><B>Elementary Cryptanalysis</B></I>
by Abraham Sinkov</A> (1966, but still available from The
Mathematical Association of America).
</UL>
These books cover some classical "pen and paper" ciphers, which
might be thought to be simpler and easier to understand than modern
ciphers. But, lacking even basic tools like
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Hash">hashing</A>,
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#RandomNumberGenerator">random number
generation</A>, and
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Shuffle">shuffling</A>,
the classical forms tend to be very limited, and so are somewhat
misleading as introductions to modern cryptanalysis. (Except
<I>Decrypted Secrets</I> by Bauer.) For example:
<UL>
<P><LI><B>The Caesar Cipher</B> replaces each plaintext letter with
the letter <I>n</I> (originally 3) places farther along in
the normal
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Alphabet">alphabet</A>.
Classically, the only possible
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Key">key</A>
is the value for <I>n,</I>
but in a computer environment, it is easy to be general: We
can select <I>n</I> for each position in the message by using a
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#RandomNumberGenerator">random number
generator</A>
(this could be a
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#StreamCipher">stream cipher</A>),
and also key the alphabet by shuffling it into a unique
ordering (which is Monoalphabetic Substitution).
<P><LI><B><A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#MonoalphabeticSubstitution">Monoalphabetic
Substitution</A></B> replaces each plaintext
letter with an associated letter from a (keyed) <I>random
alphabet.</I> Classically, it was tough to specify an
arbitrary order for the alphabet, so this was often based on
understandable keywords (skipping repeated letters), which
helped make the cipher easier to crack. But in the modern
computer version, it is easy to select among the set of
<I>all possible</I>
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Permutation">permutations</A> by
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Shuffle">shuffling</A> the alphabet
with a
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Key">keyed</A>
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#RandomNumberGenerator">random
number generator</A>.
<P>Another problem with monoalphabetic substitution is that
the most frequently used letters in the
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Plaintext">plaintext</A>
become the most frequently used letters in the
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Ciphertext">ciphertext</A>,
and statistical techniques can be used to help identify which
letters are which. Classically, multiple different alphabets
(<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#PolyalphabeticSubstitution">Polyalphabetic
Substitution</A>) or multiple ciphertext letters for a single
plaintext letter
(<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#HomophonicSubstitution">Homophonic
Substitution</A>) were introduced to avoid this. But in a
modern computer version, we can continue to permute the
single alphabet, as in
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#DynamicSubstitutionCombiner">Dynamic
Substitution</A> (see my
<A HREF = "ARTS/DYNSUB2.HTM">article</A>). Moreover, if the
original "plaintext" is evenly distributed (which can be
assured by a previous
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Combiner">combining</A>), then
statistical techniques are little help.
<P><LI><B><A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#PolyalphabeticSubstitution">Polyalphabetic
Substitution</A></B> replaces each plaintext
letter with an associated letter from one of multiple
"random" alphabets. But, classically, it was tough to produce
arbitrary alphabets, so the "multiple alphabets" tended to be
different offset values as in Caesar ciphers. Moreover, it
was tough even to choose alphabets at random, so they tended
to be used in rotating sequence, which gave the cryptanalyst
enormous encouragement. On the other hand, a modern improved
version of polyalphabetic substitution, with a special keyed
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#LatinSquareCombiner">Latin square
combiner</A>, with each "alphabet" selected
character-by-character by a keyed random number generator,
can be part of a very serious cipher.
<P><LI><B><A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Transposition">Transposition</A>
Ciphers</B> re-arrange the
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Plaintext">plaintext</A> letters
to form
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Ciphertext">ciphertext</A>.
But, classically, it was tough to form
an arbitrary re-arrangement (or
<I><A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Permutation">permutation</A></I>),
so the re-ordering tended to occur in particular graphic
patterns (along columns instead of rows, across diagonals,
etc.). Normally, two messages of the same
size would be transposed similarly, leading to a "multiple
anagramming" attack: Two equal-size messages were permuted in
the same way until they both "made sense." But, in the modern
general form, a
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Key">keyed</A>
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#RandomNumberGenerator">random number
generator</A> can
<A TARGET = "Gloss"
HREF = "GLOSSARY.HTM#Shuffle">shuffle</A>
blocks of arbitrary size in a general way, almost never
permute two blocks similarly, and work on a randomized
content which may not make sense, making the classical attack
useless (see my
<A HREF = "ARTS/DYNTRAN2.HTM">article</A>).
</UL>
<P>Thus, it was often the restrictions on the general
design -- necessary for "pen and paper" practicality -- which
made these classical ciphers easy to attack. And the attacks
which work well on specific classical versions may have very
little chance on a modern very-general version of <I>the same
cipher.</I>
<P>Other books on cryptanalysis:
<UL>
<LI><I><B>Statistical Methods in Cryptanalysis</B>,</I> by
Solomon Kullback (Laguna Hills, CA: Aegean Park Press,
1976 ; original publication 1938),
<UL>
Basically a statistics text oriented toward statistics
useful in cryptanalysis.
</UL>
<P><LI><I><A TARGET = "Bshop"
HREF = "BOOKSHOP.HTM#Bennett"><B>Scientific and Engineering
Problem-Solving with the Computer</B>,</I>
by William Bennett, Jr</A>. (Prentice-Hall,
1976), Chapter 4, Language, and
<UL>
Basically an introduction to programming in Basic, the
text encounters a number of real world problems, one of
which is language and cryptanalysis.
</UL>
<P><LI><I><A TARGET = "Bshop"
HREF = "BOOKSHOP.HTM#Korner"><B>The Pleasures of Counting</B>,</I>
by T. W. Korner</A> (Cambridge, 1996).
<UL>
An introduction to real mathematics for high-school (!)
potential prodigies, the text contains two or three chapters
on Enigma and solving Enigma.
</UL>
</UL>
<A NAME = "OtherBooks"></A>
<P><HR><H3>Other Books</H3>
<P>A perhaps overly famous book for someone programming existing
ciphers or selecting protocols is:
<UL>
<LI><I><A TARGET = "Bshop"
HREF = "BOOKSHOP.HTM#Schneier"><B>Applied Cryptography</B></I>
by Bruce Schneier</A> (John Wiley & Sons, 1996).
</UL>
The author collects description of many academic ciphers and
protocols, along with C code for most of the ciphers.
Unfortunately, the book does leave much unsaid about <I>using</I>
these tools in real cipher systems. (A cipher system is not
necessarily secure just because it uses one or more secure ciphers.)
Many sections of this book do raise the technical hackles of your
reviewer, so the wise reader also will use the many references to
verify the author's conclusions.
<P>Some other books I like include:
<UL>
<LI><I><A TARGET = "Bshop"
HREF = "BOOKSHOP.HTM#Deavours87"><B>Cryptology Yesterday, Today,
and Tomorrow</B>,</I>
by Deavours, Kahn, Kruh, Mellen and Winkel</A>
(Artech House, 1987),
<LI><I><B>Cipher Systems</B>,</I> by Beker and Piper (Wiley, 1982),
<LI><I><A TARGET = "Bshop"
HREF = "BOOKSHOP.HTM#Meyer"><B>Cryptography</B>,</I>
by Meyer and Matyas</A> (Wiley, 1982),
<LI><I><B>Secure Speech Communications</B>,</I> by Beker and Piper
(Academic Press, 1985),
<LI><I><B>Security for Computer Networks</B>,</I> by Davies and
Price (Wiley, 1984),
<LI><I><B>Network Security,</I> by Kaufman, Perlman and Speciner</B>
(Prentice-Hall, 1995),
<LI><I><B>Security in Computing</B>,</I> by Pfleeger (Prentice-Hall,
1989), and
<LI><I><A TARGET = "Bshop"
HREF = "BOOKSHOP.HTM#Wayner"><B>Disappearing Cryptography</B>,</I>
by Peter Wayner</A> (Academic Press, 1996).
</UL>
<A NAME = "CodingTheory"></A>
<P><HR><H3>Coding Theory</H3>
<P>Although most authors recommend a background in Number Theory,
I recommend some background in Coding Theory:
<UL>
<LI><I><A TARGET = "Bshop"
HREF = "BOOKSHOP.HTM#Golomb"><B>Shift Register Sequences</B>,</I>
by Golomb</A> (Aegean Park Press, 1982),
<LI><I><A TARGET = "Bshop"
HREF = "BOOKSHOP.HTM#Arazi"><B>A Commonsense Approach to the
Theory of Error Correcting Codes</B>,</I>
by Arazi</A> (MIT Press, 1988),
<LI><I><B>Coding and Information Theory</B>,</I> by Hamming
(Prentice-Hall, 1980),
<LI><I><B>Error-Correcting Codes</B>,</I> by Peterson and Weldon
(MIT Press, 1972),
<LI><I><B>Error-Correction Coding for Digital Communications</B>,</I>
by Clark and Cain (Plenum Press, 1981),
<LI><I><A TARGET = "Bshop"
HREF = "BOOKSHOP.HTM#Blahut"><B>Theory and Practice of Error
Control Codes</B>,</I>
by Blahut</A> (Addison-Wesley, 1983),
<LI><I><A TARGET = "Bshop"
HREF = "BOOKSHOP.HTM#Lin"><B>Error Control Coding</B>,</I>
by Lin and Costello</A> (Prentice-Hall, 1983), and
<LI><I><B>The Design and Analysis of Computer Algorithms</B>,</I>
by Aho, Hopcroft and Ullman (Addison-Wesley, 1974).
</UL>
<A NAME = "ForDesigners"></A>
<P><HR><H3>For Designers</H3>
<P>Those who would <I>design</I> ciphers would do well to follow
the few systems whose rise and fall are documented in the open
literature.
Ciarcia [1] and Pearson [5] are an excellent example of how
tricky the field is; first study Ciarcia (a real circuit design),
and only then read Pearson (how the design is broken). Geffe [2]
and Siegenthaler [8] provide a more technical lesson.
Retter [6,7] shows that the MacLaren-Marsaglia randomizer is not
cryptographically secure, and Kochanski [3,4] cracks some common
PC cipher programs.
<OL>
<LI>Ciarcia, S. 1986. Build a Hardware Data Encryptor. <I>Byte.</I>
September. 97-111.
<LI>Geffe, P. 1973. How to protect data with ciphers that are
really hard to break. <I>Electronics.</I> January 4. 99-101.
<LI>Kochanski, M. 1987. A Survey of Data Insecurity Packages.
<I>Cryptologia.</I> 11(1): 1-15.
<LI>Kochanski, M. 1988. Another Data Insecurity Package.
<I>Cryptologia.</I> 12(3): 165-173.
<LI>Pearson, P. 1988. Cryptanalysis of the Ciarcia Circuit Cellar
Data Encryptor. <I>Cryptologia.</I> 12(1): 1-9.
<LI>Retter, C. 1984. Cryptanalysis of a MacLaren-Marsaglia System.
<I>Cryptologia.</I> 8: 97-108. (Also see letters and responses:
<I>Cryptologia.</I> 8: 374-378).
<LI>Retter, C. 1985. A Key Search Attack on MacLaren-Marsaglia
Systems. <I>Cryptologia.</I> 9: 114-130.
<LI>Siegenthaler, T. 1985. Decrypting a Class of Stream Ciphers
Using Ciphertext Only. <I>IEEE Transactions on Computers.</I>
C-34: 81-85.
</OL>
<P><HR>
<I><A HREF = "AUTHOR.HTM"> Terry Ritter</A>, his
<A HREF = "AUTHOR.HTM#Addr">current address</A>, and his
<A HREF = "CRYPHTML.HTM"> top page</A>.</I>
<P>
</BODY>
</HTML>
© 2022 Packet Storm. All rights reserved.
%7Cutmcsr%3D(direct)%7Cutmcmd%3D(none)){kind=small}
Follow us on Twitter
Follow us on Facebook
Subscribe to an RSS Feed