4

I awoke after a time to find that the boys had left. So too had the girl with the book. They were replaced by a middle-aged man and his dog. Both the man and the dog had long shaggy hair, although the dog's hair was fuller than that of the man, for the man had a bald area on the crown of his head.

A jogger crossed in front of me on the path. The sun had moved and I was no longer shaded by the branch over my head. With the movement of the sun further down on the horizon the shadows had lengthened and the heat had subsided. A light breeze ruffled the leaves and cooled my face.

I wondered how I should explain the EFT situation to Ms. Cryer. My next chance would very likely be my last one. Did she know anything about cryptology? I doubted it; it is not a very popular field. I knew nothing at all about her personal background. If I was lucky, she would have an understanding of basic mathematics. That would make things easier. While the science of cryptology is quite complex and requires a deep grasp of number theory, complexity theory, group theory, and various other sub-disciplines of mathematics and formal reasoning, it can also be understood at a more intuitive level provided one has a head for science in general. Still not fully awake, I leaned forward and rested my elbows on my knees and reviewed in my head the content of a cryptology primer I presented to co-workers when I still worked at AT&T.

Cryptology has a long history. Early examples date back to pre-history, to a time before accurate records were kept. Early documented examples of cryptography include the private communications of Julius Caesar. Caesar wrote to Cicero and others using a cipher that is commonly referred to today as a Caesar cipher.

The Ceaser cipher is familiar to readers of Usenet, for it is essentially the same thing as ROT-13. ROT-13 encrypts a message (of alphabetic characters) by replacing each letter with the letter that occurs thirteen positions beyond it in the alphabet. For letters M-Z, the sequence wraps back around to A. So A is replaced with N, B with O, C with P, and so on. Because of the wrapping, M is replaced with A, N with B, etc. When Caesar used this technique to obscure the content of his messages, he rotated each letter by three positions instead of the thirteen used on Usenet.

How hard is it to crack a Caesar cipher? Well, while it was good enough for Caesar to fool Brutus, ROT-13 can't stop a child from decrypting material in Usenet. ROT-13 is only used to temporarily obscure offensive news articles so that the reader has a moment to reflect on the decision to view it before it appears on the screen. It is a way to incorporate warnings into news-readers that were not designed for ``rated'' material. Nothing more. It is not any more ``secure'' than using Control-L to give the reader a chance to avoid a spoiler before inadvertently reading it on the screen.

In fact, Edgar Allan Poe's short story, The Gold Bug, describes all the cryptanalysis one would need to successfully crack a Caesar cipher and other similar ciphers. In addition to using exhaustive search of all possible keys (there are only 25 --- hardly a big search problem!), one can use statistical methods based upon the non-uniform frequency with which various letters occur in the English language. For example, as any scrabble player knows, the letter E occurs much more frequently than any other letter, and the letter X is relatively infrequent.

The strength of a Caesar cipher breaks down quickly once the enemy knows the algorithm. With only 25 possible keys, the key-space is ridiculously small. Even without computers to search the key-space, an enemy can make short work of finding the key, given even just one encrypted message. Whether he was aware of it or not, Julius Caesar was relying upon the obscurity of his method rather than the secrecy of the key. Today we realize that a far less delicate situation is to assume that the enemy is fully aware of the algorithm used but that the same enemy remains unaware of the key. A crypto-system that remains strong even after the algorithm is known is far more flexible; it is easy to change keys but hard to invent (and evaluate) new algorithms. This principle was first put forward by A. Kerckhoffs in the 19th century. If one applies Kerckhoffs' Principle, then all of the security of a crypto-system is concentrated in the secrecy of the keys. There is no harm in divulging the algorithm. Indeed, there are advantages to making the algorithm public; if there are any flaws in the algorithm that might be exploited by your enemies, making the algorithm public gives the general population an opportunity to study your algorithm and perhaps find the flaws for you. An algorithm that has been subjected to wide-spread peer-review is much more reliable than one that has been reviewed behind closed doors by only a limited number of people.

There are three aspects to a Ceaser cipher that make it very different from modern encryption methods. The first, as already pointed out, is that it violates Kerckhoff's law. The second is that both of the communicating parties must share knowledge of the secret code. Third, it is a weak code, in that the key is easily guessed. So weak, in fact, that even in its hay-day a Ceaser cipher was vulnerable. It is not just with recent advances that we are able to look back and crack these types of codes. Even if Brutus was unable to crack Julius Caeser's code, others of that era could. Given the overall lack of respect that Julius Caeser had for mathematics, it isn't surprising that he placed his confidence in such a weak cipher. This is the same Caeser that ransacked Alexandria and burned its libraries.

Still, one cannot fault Julius Caeser entirely for using a weak crypto-system. He had little choice. At that time, all known crypto-systems were only slightly stronger than the known attacks. The defensive side of the science, called cryptography was only one small step ahead of the offensive side of the science, called cryptanalysis. For two centuries there were no codes that where impervious to attacks based upon technology of the same era.

This all changed in the twentieth century. First, early in the twentieth century, 1926 to be exact, G. S. Vernam invented a cipher that is unbreakable. At the time Vernam published his work the cipher was only thought to be unbreakable; today we know that it is indeed unbreakable. It has been proved with mathematical rigor.

Vernam was an engineer working for AT&T. This was always a point of pride when I presented this material at AT&T. I used to devote considerable time to Vernam and his work, describing his career with the company as well as his technical contributions to the field. Vernam wasn't the only modern cryptographer to work for a telecommunications company; many of the recent advances in cryptology have come from the communications industry.

Vernam's innovation was to use keys only once. Not only does this mean that the key must be changed for every message sent, but it also means that each bit of the key can only be applied to a single bit of the message. Each bit of plain-text is treated as a separate message and is encrypted with a new (single-bit) key. Clearly this scheme has disadvantages: the key must be as long as the message and must be changed as frequently as the message. At the same time, the key must be known to both communicating parties. If one can exchange long keys securely, and do it frequently, then why bother with encryption at all? Just use whatever mechanism you are using to exchange keys to exchange the messages themselves! It is for this reason that the Vernam cipher is of limited practical use.

One example of a Vernam cipher is to rotate letters in precisely the same way as one does in a Caesar cipher, except the amount of rotation varies for each letter of the message. For example, suppose we wish to encrypt the plain-text message:

Please meet me at the corner in one hour

PLEASEMEETMEATTHECORNERINONEHOUR

5 8 12 2 0 8 22 5 18 25 3 0 10 3 3 15 19 12 15 3 8 5 22 20 0 1 6 2 24 16 23 4

UTQCSMIJWSPEKWWWXODUVJNCNPTGFERV

The important thing to remember when using a Vernam cipher is that the rotation for each letter in the message must be completely independent of the rotations for the other letters. Furthermore, the key must be selected randomly (or as close to randomly as is feasible). In the key sequence above (which I chose arbitrarily but not randomly), each member of the sequence is a number between 0 and 25, inclusive.

In practice, Vernam ciphers are applied bit-by-bit. The message is viewed as a bit-string and the key too is a bit-string. Each bit of the key specifies a rotation in the range of 0 and 1. In other words, the exclusive-or operation is used; a Vernam cipher is nothing more than an exclusive-or of the message with a one-time key of equal length. This is often referred to as ``blinding'' or using a one-time-pad.

Vernam ciphers have application in military settings, where a large number of one-time-pads can be distributed ahead of time via a secure means and then used to exchange encrypted messages at a later time in a hostile environment. Code-books, where soldiers in the field must decrypt messages by looking up words in a printed book and replacing each word of the code with the appropriate word from the book, are an example of a Vernam cipher (provided the keys are only used once and the set of replacement words and code words are selected from dictionaries of the same size). In 1949 C. E. Shannon published a paper on information theory entitled, Communication Theory of Secrecy Systems. This marked the dawn of modern cryptology, for it was this paper that established a firm scientific basis for crypto-systems.

Shannon was an electrical engineer by training and another telecom employee, working for Bell Telephone. By 1949 he had already published a soon-to-become legendary paper on communications theory in general. Indeed, today Shannon is probably better known for his 1948 paper on communications theory than the 1949 paper on cryptology. But it is the 1949 paper that established the science of cryptology.

Prior to Shannon's work, cryptology can better be described as an art rather than a science. The best cryptographic algorithms in the pre-1949 era were developed in an ad hoc fashion, with cryptographers haphazardly permuting and convoluting the input until it seemed unfathomable that anybody could unravel the process without knowing the key. Of course, without any basis for this belief, cryptographers had no way of assessing their position. Usually it was only a matter of (sometimes brief) time before a clever cryptanalyst broke the code and the cryptographers had to start all over again.

With Shannon's work, for the first time we had a theory upon which to base the development of cryptographic algorithms. A cryptographers job is to find one-way trap-door functions. A one-way function is a computable function for which the inverse cannot be computed. The inverse of a function, f, is normally denoted by f^-1 and it is the ``undo'' relation. In other words, for any value of x, f^-1(f(x)) = x. Now f^-1 won't always be a function; sometimes it will map more than one input to the same output. In other words, there are two distinct values, x and y, such that f(x) = f(y), and therefore f^-1(f(x)) is undetermined because it may be either x or y.

A one-way trap-door function is a function that is not actually one-way at all; it has an inverse, and the inverse is itself a function, but the inverse function is difficult to compute (without the key). It is important that the inverse be a function and be computable, because the recipient of an encrypted message has to have some way to decrypt it (the ``undo'').

So how difficult is it to compute the inverse of a one-way trap-door function? Mathematicians are able to classify the difficulty of solving a problem by ranking the efficiency of the best (known) algorithms for solving the problem. A one-way trap-door function is a function that can be computed efficiently but for which the inverse function cannot be computed efficiently.

Cryptographic hash functions are one-way functions, with the added requirement that they be collision-free. Suppose h is a cryptographic hash function. Because h is one-way, it is easy to compute y = h(x) for all x, but hard to compute x = h^-1(y) for any y. The collision-free requirement means that given the value y₀ = h(x₀), it is computationally infeasible to find x₁ != x₀ such that h(x₁) = y₀, even if such an x₁ exists.

As important as Shannon's work was, it did not have an immediate impact. It is only now, in retrospect, that we recognize and appreciate the importance of that paper. It established the necessary ground-work that we rely upon today but did not excite sufficient interest to spur further activity in the field. It wasn't until 1976 that the field really took off. In that year W. Diffie and M. E. Hellman published their revolutionary work entitled New Directions in Cryptography. The significance of this work is that it showed for the first time that private communication was possible even when the communicating parties shared no prior secrets. In other words, encryption did not require a ``key'' in the traditional sense. Up until 1976, all encryption algorithms relied upon a secret key that the two parties shared prior to exchanging encrypted messages. This ``key'' might be the secret algorithm, as in the case of a Ceaser cipher, or more recently SkipJack and Clipper. Or, it might be a one-time pad, as in the case of a Vernam cipher.

The traditional crypto-systems with a single key are called symmetric-key systems. In their 1976 paper, Diffie and Hellman introduced a new kind of crypto-system with two keys; one private key and one public key. The private key, which is not shared with anybody and is known only to the encrypting party, is used to encrypt messages. the public key, which is known to everybody, contains all the information needed to decrypt that message.

Suppose Alice wants to send a private message to Bob (it is customary when giving examples of cryptography to use Alice and Bob). With symmetric-key encryption, Alice and Bob would have to first agree on a key to use to encrypt and decrypt the message. But with public-key encryption Alice can use Bob's public key. There is no need to meet in person or exchange by some other means a shared secret key. There is no boot-strapping problem. Once Alice has encrypted the message using Bob's public key, only Bob knows how to decrypt the message. Even Alice cannot decrypt the message (of course, she has no need to do so since she knows the plain-text anyway, having created it herself). Bob uses his private key, which he divulges to nobody, to decrypt the message and recover the plain-text. If Bob wants to send a reply, he uses Alice's public key to encrypt a message for her eyes only. She then uses her own private key, known only to her, to decrypt Bob's reply.

By far the most common public-key algorithm in use today is RSA, which was invented in 1978 by R. L. Rivest, A. Shamir, and L. Adleman (hence the name, derived from the last initials of the three inventors). The RSA trapdoor one-way function is the discrete exponentiation

where x is a nonnegative integer less than n=pq and where the trapdoor is the three values p, q, and e. The secret values of p and q are carefully chosen large primes. The values of n and e are public. These two values comprise the public key. The private key is the factorization of n, namely p and q.

Anybody that has a good method for factoring large numbers can crack RSA. That person can factor the public value of n to obtain the unique prime factorization pq and thereby obtain the back-door values of p, q, and e (the last of which is public knowledge). Fortunately for those of us that rely on RSA, factoring is widely accepted as a very difficult problem, with no known efficient solutions. The best known factoring algorithms have exponential running-time and would require vast computing resources to factor large numbers. Mathematicians have been searching for better factoring algorithms for centuries. Their failure to find better algorithms is strong evidence that such algorithms don't exist, or if they do then their discovery is not imminent. (The popularity of RSA is not a significant motivator in the search for factoring algorithms, when viewed in the context of the full history of mathematics.)

I personally contributed in cracking one specific RSA key. I was working for a small telecommunications company at the time, Multi-Media Telecom, having left AT&T. The key we helped crack was 129 bits long, which would seem to be long enough to be impervious to a factoring attack. Nonetheless it was broken in April of 1994 in response to a public challenge first posed in the pages of Scientific American in 1977. The puzzle was cracked using a variation of the quadratic sieve factoring method. The program required about 5000 mips-years and was carried out in eight months by about 600 volunteers from more than 20 countries. The entire effort was conducted and coordinated over the Internet. I had one of my machines cranking round-the-clock on RSA-129. The challenge cipher-text was published as:

9686961375462206147714092225435588290575999112 4574319874695120930816298225145708356931476622 883989628013391990551829945157815154

1143816257578888676692357799761466120102182967 2124236256256184293570693524573389783059712356 3958705058989075147599290026879543541

3490529510847650949147849619903898133417764638 493387843990820577 * 32769132993266709549961988190834461413177642967 992942539798288533

10669861436857802444286877132892015478070990663 39378628012262244966310631259117744708733401685 97462306553968544513277109053606095

200805001301070903002315180419000118050019172105 011309190800151919090618010705

THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE

The complexity of the factoring problem grows roughly exponentially with the length of the key. The above example used a key of 129 bits. Using the same methods and the same amount of computing power, a 130-bit key would take roughly twice as long to crack. Such is the nature of exponential problems. In fact, a year later a 130-bit RSA challenge was solved in the same way, over the net. Both of these public efforts made use of an awesome amount of computing power, harnessing the power of the Internet. These were world-wide cooperative efforts, the likes of which are not normally available to spies, thugs, and other evil-doers. Still, just to be on the safe side, people typically use RSA key lengths of 768 or 1024 bits, and sometimes even 2048 bits. Remember, each additional bit in key-length doubles the resources needed to crack the code. Barring a revolutionary advance in computational number theory, using key sizes of at least 1024 bits for RSA is quite safe.

The next big advance after public-key cryptology came in 1984, when Gustavus J. Simmons published his work on the theory of authenticity. This opened up a new side of the field, demonstrating that cryptology can be used to establish communication channels that are resistant to tampering. Moreover, the property of information integrity and message authenticity, as this came to be known, can be separated from the property of message privacy. Cryptography can be used to achieve integrity without privacy or privacy without integrity (or both together of course). This opens up new areas for cryptographic applications, where secrecy is not important but integrity is. The work of Simmons, Shamir, Rivest, Adleman, Diffie, Hellman, and others has gone a long way toward moving the field of cryptology out of the back-rooms of espionage and into the fore-front of the contemporary computing and telecommunications industries. The recent blossoming and merging of those two industries has sealed the fate of modern cryptology --- it is indespensible to the manner in which we exchange information today.

The significance of public-key cryptography cannot be over-estimated. When used for information integrity and authenticity, the advantages become greater still. Public-key encryption can be used ``backwards'' to achieve a digital signature. If Alice uses her private key to scramble a plain-text message, then while anybody can regain the original plain-text because everybody knows Alice's public key, only Alice can scramble a message in this way. There is no privacy when Alice uses her private key in this manner, but there is integrity and non-repudiation. If Bob has both the plain-text version of a message and the version created with Alice's private key, then Bob can be sure that Alice is the one that created the scrambled version; nobody else has the ability to scramble the bits in a way that will produce the original message when Alice's public key is applied to it. Without Alice's private key, forgeries are computationally infeasible.

Digital signatures are much more secure than hand-written signatures. There is no known way to forge a digital signature. So long as Alice keeps her private key secret, nobody can forge her signature. Therefore, if a signed message conforms to Alice's public key, then she cannot deny having signed it without also accepting that she has allowed her private key to be released to a third party.

Another advantage that digital signatures have over hand-written signatures is that the signature is applied to the entire message. Every bit of the digital message is perturbed by the signing key. A hand-written signature is applied to the bottom of a paper document. There is nothing that prevents alteration of the text appearing above the penned signature while leaving the signature intact. Such alterations are not possible with digital signatures. Changing even a single bit of a signed message will cause the verification procedure to fail.

It is important to recognize that while public-key cryptography eliminates the need for a private channel to exchange keys, it still requires that there be a tamper-proof channel. If one party can be tricked into accepting the wrong public key for the other party, then the system is compromised. If Alice sends a private message to Bob, but uses Joe's public key instead of Bob's key because Joe has fooled Alice, then Joe will be able to impersonate Bob. He will be able to read all of the private messages that Alice intends to send to Bob, messages that were meant to be for Bob's eyes only.

Thus, integrity and authenticity remain essential. If the two parties share no prior information (public or otherwise) then this can pose a serious problem. One solution is to rely upon physical integrity. For example, if one party broadcasts his public key on the nightly news over network television, it is unlikely that the signal has been altered or that he has been replaced by an actor. If the viewer calls up close friends and relatives to confirm that they saw the same broadcast and the same public key was conveyed, she can be still more confident. Still, can one be completely certain? What if you have no idea what the person is supposed to look like? Is there a more practical solution?

The common solution, which is already being deployed in industry, is to use something called certificates. A certificate is somewhat analogous to a driver's license. I can be confident that a public-key belongs to the person claiming ownership of that key provided somebody I know and trust vouches for that person. A certificate authority provides this service. To be a certificate authority, a company must be widely known and highly trusted. That company must be trusted to behave honestly, but also must be trusted to act with competence and diligence. If I receive a certificate with your name and public key, and if that certificate is digitally signed by a certificate authority I trust, then I can be confident that the public-key does indeed belong to you.

Why? Well, first of all I am confident that the signature cannot be produced by any entity other than the certificate authority; digital signatures are unforgeable. Second, I have placed my trust in the certificate authority to take whatever steps are needed to verify your identify. For example, perhaps you are required to show up in person and produce undeniable evidence of your identity (e.g. a fingerprint, a retina scan). I can now take the contents of the certificate at face value: you claim the stated public key as your own.

Certificate authorities reduce the problem of distributing public-keys in a insecure environment to the problem of distributing only one public-key --- that of the certificate authority. Once everybody has that key, all other public keys can be safely distributed using signed certificates. This greatly simplifies the infra-structure needed for public-key cryptography. The public key for the certificate authority is very public. Everybody knows it and uses it (to verify certificates). There is only one such key (or a very small number, one for each certificate authority). Because it is so widely known and widely used, it is easily verified. Because of the small number of certificate authorities, their keys can be broadcast in various news media that are hard to alter. The New York Times is one example. Or on network television much like lottery numbers are announced. Or ---

I suddenly looked at my watch. I had let myself drift off in thought and lost track of the time. My watch said 5:40. I still had plenty of time to get back to Ms. Cryer's building before 6:15, but it would be silly to cut it close when I wasn't doing anything other than sitting around day-dreaming. I might as well head back and wait in the lobby.

I stood up, stretched, and began to retrace my steps toward Michigan Avenue and the walk back north. Would the black Caprice still be there? I wondered.