[10.0] Digital Ciphers & Public-Key Cryptography

v2.4.0 / chapter 10 of 13 / 01 sep 16 / greg goebel

* Although mechanical and electromechanical code machines persisted into the postwar period, the future clearly lay with electronics, and they were increasingly replaced by electronic code machines as time went on. The rise of the programmable digital computer, a "universal" machine that could be programmed to perform almost any sequence of logic operations, provided an ideal tool for generating codes and cracking them. A computer could not only perform high-speed searches and statistical analyses of ciphertext, it could perform a set of scramblings on data that would be insanely complicated to implement with rotors or electromechanical devices, and do it much more quickly and reliably. This chapter provides a history of the evolution of modern digital cipher technology.

[10.5] RSA


* In the years immediately following World War II, telecipher systems remained one of the most important cryptographic tools for high-level communications. Following the creation of the NSA in 1952, the agency decided to bring telecipher technology into the electronic age. Howard Barlow, head of the NSA's record and data group, initiated development of a purely electronic telecipher system, the "TSEC/KW-26", or just "KW-26" for short.

An NSA team under two engineers, Joe Hannan and Vern Ziegler, put together a prototype, which was demonstrated in the field in 1954. Hannan had already contracted with Burroughs Corporation in 1953 to build preproduction units of the KW-26, with the preproduction batch undergoing trials beginning in 1955. Full-production machines went into service beginning in 1957, and over 15,500 KW-26s were built.

The KW-26 consisted of a rack of equipment about the size and form-factor of a good-sized refrigerator, and consumed a kilowatt of power. Its electronics were built around about 50 vacuum tubes and 800 bits of "magnetic core" memories -- tiny donuts of a magnetic "ferrite" material that were threaded into a grid of wires. A core could be selected from the grid by electrically activating the proper combination of wires, either to change its magnetic polarity from "north" to "south", or to read out its magnetic polarity. A 21st-century digital kid's toy has vastly more computing horsepower than the KW-26, but it was what could be done in the 1950s.

The KW-26 apparently used a encryption scheme based on a shift register -- more on this general concept later. A daily key was provided on a punch card. The punch card was inserted into the unit and left in place behind a little door for operations during the day; when a new card was inserted the next day, the old one was automatically shredded. The KW-26 remained in service until the mid-1980s, when it was replaced by a solid-state unit, the "TSEC/KG-84".

* By that time, the era of widespread computing had arrived and the future of cryptography clearly belonged to the reprogrammable digital computer. A reprogrammable computer was far more flexible, able to be adapted to new tasks by changing its software -- though that was by no means always a trivial task. Of course, that didn't mean that dedicated cryptographic machines went away, since the military required such things, but increasingly crypto machines had a reprogrammable computer at the core and not a purpose-designed electronic circuit.

In any case, two classes of "digital" ciphers were developed: "stream" ciphers and "block" ciphers. However, before discussing them, it is useful to establish a few definitions.

Data on a computer is generally stored in "files", which are electronically equivalent to paper files in a file cabinet. Each computer file has a name and stores specific data. The data in the file is the form of a sequence of binary bits. These binary bits may represent a "text file", with each eight-bit sequence in the file representing an ASCII character, or they may make up a digitized picture, or digitized sound or music, or digitized video, or other kinds of data.

The essential point is that a data file does not inherently represent a text message. While traditional encryption schemes based on manipulating text can be implemented with a computer program by manipulating ASCII codes, and in fact this is often done to produce programs that simulate Enigma machines and the like, in practice it is much more useful to encrypt data files at the bit level. Instead of "plaintext" and "ciphertext", we now have "plaindata" and "cipherdata".

By the way, the term "file" is actually a little too restrictive. Instead of speaking of encrypting a data file, computer cryptographers think in slightly more general terms and speak of encrypting a data "stream". This just means any sequence of bits flowing from one place to another. For example, if Alice sends a data file to Bob over the internet by email, the data flowing over the internet can be regarded as a stream.

Another example is a voice conversation between two users with digital phones, which convert their analog voice signals into a digital stream. Of course this digitized voice conversation could be encrypted using the same basic techniques as used on a file, with the constraint that the encryption and decryption have to be done on an ongoing "real-time" basis. The conversation is just another digital stream and so there is no reason to develop specialized voice scrambler technologies to encipher it.

* A stream cipher is really very similar to the telecipher systems in the last chapter. It operates by taking a stream of plaindata bits and XORing them on a bit-by-bit basis with a secret "keystream" of more or less random bits. The cipherdata stream can then be deciphered by XORing it again with the same keystream.

Ideally, the secret keystream should be completely random. This would produce a completely uncrackable cipher, a binary form of a one-time-pad cipher. In practice, that approach suffers from the same two problems as the one-time-pad cipher: the difficulty of producing a truly random sequence of data, and of distributing the cipher keys.

A computer cannot really generate a truly random keystream, but it can generate a "pseudo-random" keystream using various algorithms. Again, this can be seen to be very similar to the approach used by telecipher machines, but a computer is far more flexible and powerful, and can generate a much more formidable pseudo-random keystream.

The pseudo-random keystream generation procedure, or "algorithm", used by the computer can be given an initial, relatively short "seed" of bit values, with different seeds resulting in different keystream values. The algorithm should be "nonlinear", in that changing even a single bit between one seed and another will produce an entirely different keystream. The seed can be used as a cipher key.

* One of the more popular approaches to pseudo-random keystream generation in stream ciphers is what is called a "linear feedback shift register (LFSR)".

A "shift register" is a form of sequential memory device commonly used in computers and other digital devices. It can be thought of as a set of memory "cells", each of which can store a single bit, linked end-to-end.

A conventional digital system like a personal computer is controlled by a series of "clock" pulses that synchronize the operation of all the digital circuits in the system. Everything changes when the clock pulse occurs, setting up new digital values for the next set of operations that take place when the next clock pulse appears. Without a clock, the values used by the digital system might get out of sync with the operations performed, a problem that is known as a "race condition".

If that seems unclear, just take it for granted that a computer has a system clock to generate pulses that step everything along, like the beat of a drum controlling the steps of a marching band. Without the drum beat, the band will get out of step and fall into disorder.

In the case of a shift register, the clock causes the bits stored in it to shift memory cells, with a new bit "shifting in" to one side of the shift register and an old bit shifting out of the other side of the shift register. For example, consider an 8-bit shift register that shifts to the right, set up with the bit pattern "01001101" as follows:

8-bit shift register

Notice that a "1" is wired to the left end of this shift register. The shifts take place with each clock pulse as follows, with the shift register representation simplified for clarity:

   1 -->  0  1  0  0  1  1  0  1  --> 1

   1 -->  1  0  1  0  0  1  1  0  --> 0

   1 -->  1  1  0  1  0  0  1  1  --> 1

   1 -->  1  1  1  0  1  0  0  1  --> 1

   1 -->  1  1  1  1  0  1  0  0  --> 0

   1 -->  1  1  1  1  1  0  1  0  --> 0

-- and so on. In a "linear feedback" shift register, various cells in the shift register are XORed back to the input to generate a lengthy bit output. For example, the shift register shown above might wired back a follows:

linear feedback shift register

Given the same sequence of initial bits as used earlier:

   0  1  0  0  1  1  0  1 

-- then this LFSR would generate the following sequence of output bits (with the bits to be XORed marked by a "*"):

   *              *     *
   0  1  0  0  1  1  0  1  -->  1
   0  0  1  0  0  1  1  0  -->  0
   1  0  0  1  0  0  1  1  -->  1
   0  1  0  0  1  0  0  1  -->  1
   1  0  1  0  0  1  0  0  -->  0
   0  1  0  1  0  0  1  0  -->  0
   0  0  1  0  1  0  0  1  -->  1
   1  0  0  1  0  1  0  0  -->  0
   0  1  0  0  1  0  1  0  -->  0

-- and so on. The LFSR can be loaded with an arbitrary sequence of bits as a seed or key for the sequence, which means that in this example:

   0  1  0  0  1  1  0  1 

-- would be the cipher key used by Alice to produce the cipherdata, and by Bob to read the cipherdata. An LFSR can be implemented in computer hardware or by a computer program. Apparently the KW-26 used an LFSR, with the key value provided by the punchcard.

This LFSR design was picked at random, but in practice extensive research has been done on the appropriate design of LFSRs to generate a keystream as long and unpredictable as possible. However, even the best LFSR is no longer adequate to ensure security, and so in practice several LFSRs are wired together in complicated ways to generate the keystream. Such a scheme of ganged LFSRs is called a "shift register cascade".

* In 1973, the US National Bureau of Standards (NBS, now the National Institute of Standards & Technology, or NIST) issued a request for a standard encryption scheme that US businesses could use in their commercial transactions. The NBS effort received a boost the next year from the US Privacy Act of 1974, which specified legal requirements for government agencies and certain government contractors to ensure the security of critical records in their possession.

IBM Corporation was already using a digital encryption scheme known as "Lucifer" that was a plausible candidate for the US national cipher standard. Lucifer had been developed early 1970s by Horst Feistel, who had been born in Germany and emigrated to the US before World War II. Feistel had originally started with a "Demonstration Cipher", with the name truncated to "Demon", which led logically to the name "Lucifer", which incidentally suggests "Lu(cipher)".

Lucifer was a block cipher. A block cipher involves breaking up the stream into a set of blocks, and then scrambling each block, as opposed to a stream cipher, which encrypts the entire file in a continuous, bit-by-bit, fashion. Lucifer uses a 64-bit block, as did most early block ciphers, due to constraints in the computing power available.

The scrambling is performed as follows:

The procedure is reversed to decrypt the message. In general, block ciphers work on data in blocks of blocks of 64 or 128 bits at a time, with each block run through a mathematical mangling function, as directed by the encryption key. Feistel's scheme used multiple rounds of scramblings for each block, and so it is known more specifically as an "iterated" block cipher.

A block cipher may encrypt each block of the message independently of all the others. This approach is known by the somewhat odd term of "electronic code book (ECB)" encryption. For greater security, the result of each block encryption can be XORed with the next block before its encryption. This approach is known by the much more intuitive name of "cipher block chaining (CBC)" mode. There are also "feedback block chaining (FBC)" and "output block chaining (OBC)" modes that are similar to CBC modes, but perform the encryption and XORing in different sequences.

Incidentally, Lucifer was designed so that small changes in plaintext will result in substantially different ciphertext, a property referred to as an "avalanche effect". It prevents a codebreaker from cracking a message by enciphering sample plaintext and then converging on a solution by tweaking the sample and encrypting it until the encryption matches the ciphertext to be cracked.

* As mentioned, digital ciphers use a key that is a string of binary digits. In general, a longer key provides greater security, since the number of possible keys doubles with each additional bit, doubling the effort needed to crack a message using a brute-force search of all possible keys.

The NBS selected a version of Lucifer using 56-bit keys as the US national "Data Encryption Standard (DES)" in November 1976, with the standard going into effect in 1977. Incidentally, the key is actually 64 bits long, but eight bits are reserved for error correction, giving an effective key length of 56 bits. A 56-bit key gives 7.21E16 possible keys. DES uses a "look-up" scheme referred to as an "S-box" in which the key is an index into a table of unrelated values to ensure nonlinearity.

There have been suspicions there is a "trapdoor" feature in DES that allows the NSA to easily crack it, and the NSA is also suspected to have pressured NBS to specify a key with 56 bits so that the agency could crack messages enciphered with DES. Other popular modern block ciphers use keys 128 or 256 bits long. The number of possible keys with 256 bits is 2^256 = 1.16E77, providing much greater security than the 56-bit key used by DES.

By 1984, the NBS had certified over 35 different integrated circuit implementations of DES. DES is required for electronic financial transactions of the US government, in accordance with ANSI standard "X9.9", which is written around DES.

* An "extended DES (DESX)" was later developed with additional security. This just an improved DES that XORs a block with a 64-bit key before encryption and XORs the block with another 64-bit key after encryption. There are other improvements and variants on DES.

Other well-known block ciphers in common use include the "International Data Encryption Algorithm (IDEA)", developed by ETH of Zurich and available without charge for noncommercial use; "Blowfish", developed by Bruce Schneier of Counterpane Internet Security in San Jose, California, and his improved version, known as "Twofish"; and "RC2", "RC5", and "RC6", all developed by Ron Rivest of RSA Security in Bedford, Massachusetts. More is said about Rivest later.

The most advanced digital ciphers can use keys of varying lengths, to provide additional security when necessary, and sometimes variable-length block sizes as well.



* The development of stream and block ciphers meant that as computer networking spread and blossomed into the global internet, there were ciphers that provided adequate security for online transactions. There was only one catch: key distribution.

Key distribution had traditionally been a weak link in cipher security, as the British grabs of German Enigma codebooks demonstrated, but the nature of the internet made the problem that much greater. The internet was an open environment, implying a certain "promiscuity" in handing out keys. A large online merchandising firm, for example, might normally deal with tens of thousands of customers a day, each one requiring cipher security for an online transaction. The online firm could not reasonably issue all the customers individual cipher keys, and even if they could, security would be difficult to maintain with so many people involved.

* In the early days of computer networking a number of cryptographers attempted to tackle the key distribution problem. In 1974, a free-lance cryptographer named Whitfield Diffie, a long-haired hacker type, was pondering the issue when he heard that a Stanford University professor named Martin Hellman was working on the same thing. Diffie immediately packed up his things, drove from the East Coast to the West Coast, and quickly struck up a working relationship with Hellman, working as a graduate student. They were soon joined by another cryptographer named Ralph Merkle. The Stanford group discussed the key distribution problem and explored different ideas. They knew of a conceptual scheme that hinted it might be possible to send messages without concern about having the cipher key intercepted.

Suppose Alice wanted to send a secret message to Bob through the mails and be certain that it could not be read in transit. She could send it in a box locked with a padlock, but then she would have to send the key as well, and the key might be intercepted and used to open the box before it got to Bob.

But now suppose the box was designed to permit the use of two padlocks, side by side? Alice could use her own padlock on the box, and send it to Bob. She would keep her own key. Bob would attach his padlock to the box and send it back, keeping his own key. On receiving the box, Alice would remove her padlock and send the box back to Bob, who would then be able to open it.

That would be a cumbersome procedure, but it had the important feature that no key would ever change hands. It seemed plausible that the same trick could be used with ciphers. Alice could encipher a message with her own key and send it to Bob, who would encipher it with his key and send it back to Alice. Alice could decipher the message with her key and send it back to Bob, who would then decipher the message with his key.

However, this wouldn't work. The order of encipherment in this scenario is:

The problem is that the order of encipherment is important. All the ciphers that Diffie, Hellman, and Merkle knew about that were more than trivial would only work in this order:

The actual scenario with the useful ciphers available was not like having a box that could be fitted with two padlocks. It was like Alice having a small box that could be padlocked, and Bob having a bigger box that could be padlocked as well. Alice could send her small locked box to Bob, who would be able to put it inside his own big box and lock it, but then Alice would have no access to her own locked box when she received Bob's box. This neat-sounding keyless exchange scheme broke down in the real world.



* Although the double-locked-box scenario didn't provide a useful answer to the key distribution problem, it did get the group thinking about possibilities. Consider the following scenario, which gives a logical scheme for key exchange in which the actual key is never transferred, but which has a cartoonishly obvious flaw:

STEP 1: Alice and Bob each think of a secret number, which we'll call "A" and "B" respectively, and do not tell each other what their numbers are. The two secret numbers will be used to build a common secret key. Alice actually picks a secret value of A = 7 and Bob picks a secret value of B = 39.

STEP 2: They talk to each other and agree to a third non-secret value, which we'll call "C" and say is 27. A malicious eavesdropper, appropriately named "Eve" by cryptographic tradition, hears this value and writes it down.

STEP 3: Now, Alice adds her secret value, A = 7, to C = 27, and sends the sum, which turns out to be 34, to Bob. Eve overhears and writes down this sum.

STEP 4: Bob adds his secret value, B = 39, to C = 27 and sends the sum, 66, to Alice. Eve can also hear and write down this sum.

STEP 5: Bob takes the sum sent by Alice, 34, and adds his secret value, B = 39, to get 73.

STEP 6: Alice similarly takes the sum sent by Bob, 66, and adds her secret value, A = 7 , to get 73.

Now both Alice and Bob have the same key, which has the value A + B + C = 73, and they've never told each other, or Eve, what the actual value of the key was.

* However, the flaw in this argument is that it is ridiculously easy for Eve to backtrack and find the values of A and B. If Alice sends a value of 34 to Bob, then Eve would know immediately that A = (34 - 27) = 7. If Bob sends a value of 66 to Alice, then Eve would immediately know that B = (66 - 27) = 39. The key value is then 7 + 39 + 27 = 73.

Hellman later said that their group was perfectly willing to come up with ridiculous ideas, because sooner or later one of them might pay off. The flaw in the scheme outlined above is that it is entirely trivial to backtrack the addition operation. Addition is a "reversible" operation. If we add two numbers to get a result, we can take the result, subtract one of the numbers and get the other number immediately. In more formal terms, subtraction is the "inverse" operation to addition.

However, not all mathematical operations are so easily reversed. The Stanford group began to investigate "one-way operations". The Stanford group investigated one-way operations based on "modular" or "modulo arithmetic", and the effort paid off. They found a secure key-exchange algorithm.

* Modulo arithmetic involves calculations performed with a limited range of values in the result. This sounds hard to understand, but we more or less do modulo arithmetic with clocks all the time, and in fact, modulo arithmetic is also called "clock arithmetic". For example, ignoring the issue of whether an hour is AM or PM, if it's 3:00 now, then the time ten hours later is 1:00. In modulo arithmetic terms, we express this as:

   (3 + 10) MOD 12 = 13 MOD 12 = 1

-- where MOD defines the modulo operation. We can calculate the hour for other time increments in the same way:

   12 hours later:  (3 + 12) MOD 12 = 15 MOD 12 = 3:00
   15 hours later:  (3 + 15) MOD 12 = 18 MOD 12 = 6:00
   18 hours later:  (3 + 18) MOD 12 = 21 MOD 12 = 9:00
   23 hours later:  (3 + 23) MOD 12 = 26 MOD 12 = 2:00
   36 hours later:  (3 + 36) MOD 12 = 39 MOD 12 = 3:00

-- and so on. Clock calculations aren't quite a perfect example of modulo math, since by the rules of modulo arithmetic we end up with the following calculation:

   21 hours later:  (3 + 21) MOD 12 = 24 MOD 12 = 0:00

This doesn't reflect how we tell time, since instead of using the mathematically logical sequence:

   ...  11:58  11:59  00:00  00:01 ...  00:58  00:59  01:00  01:01 ...

-- we actually count time like this:

   ...  11:58  11:59  12:00  12:01 ...  12:58  12:59  01:00  01:01 ...

The first set of times is correct for modulo math, while the second set is correct for how we tell time. However, the two schemes are otherwise very similar.

We can imagine modulo addition with other "bases" besides 12. For example, with modulo math with a base of 7, we get the additions:

   (3 + 10) MOD 7 = 13 MOD 7 = 6
   (3 + 15) MOD 7 = 18 MOD 7 = 4
   (3 + 22) MOD 7 = 25 MOD 7 = 4
   (3 + 25) MOD 7 = 28 MOD 7 = 0
   (3 + 33) MOD 7 = 36 MOD 7 = 1

-- and so on. In essence, a modulo operation is simply dividing the result by the base and only keeping the remainder from the division. Modulo arithmetic is one of those ideas that is so simple that it is a bit hard to explain, although this is also partly because it's hard to see what the point of it is. Incidentally, as mentioned, in the old days the XOR operation was called "modulo-2 addition", and it should now be clear why:

   0 XOR 0 = 0         (0 + 0) MOD 2 = 0 MOD 2 = 0
   0 XOR 1 = 1         (1 + 0) MOD 2 = 1 MOD 2 = 1
   1 XOR 0 = 1         (0 + 1) MOD 2 = 1 MOD 2 = 1
   1 XOR 1 = 0         (1 + 1) MOD 2 = 2 MOD 2 = 0

In the current case, the point of modulo arithmetic is that it makes backtracking the original values of an operation from its result very difficult. If we add a secret value to 3 in modulo 7 math and get a result of 1, then the secret value might actually be 5, or 12, or 19, or any one of an infinite list of consecutive values. Also, if we try to perform a series of guesses at the secret value, the results we get generally don't tell us if we are getting warmer or colder.

Modulo arithmetic leads to one-way operations, and so the Stanford team was very interested in modulo arithmetic. Hellman settled on a modulo operation of the form:

   ( Y^X ) MOD P

Using this operation, he was able to come up with a workable key exchange algorithm, which works as follows:

STEP 1: Once again, Alice and Bob choose their secret values, A and B. Alice actually chooses A = 9 and Bob chooses of B = 7.

STEP 2: In this case, however, instead of choosing a third non-secret value C, they agree on two non-secret values, one for the variable Y in the formula above, the other for the variable P. Y must be less than P. For example, they agree on Y = 5 and P = 17, and then plug them into the modulo formula defined above, yielding:

   ( 5^X ) MOD 17.

STEP 3: Now Alice plugs her secret value A = 9 into the operation:

   ( 5^A ) MOD 17  =  ( 5^9 ) MOD 17  =  1,953,125 MOD 17  =  12

She sends that value to Bob.

STEP 4: Bob similarly plugs his secret value B = 7 into the operation:

   ( 5^B ) MOD 17  =  ( 5^7 ) MOD 17  =  78,125 MOD 17  =  10

He sends the result to Alice.

STEP 5: Now here's where the really surprising thing happens. Alice takes Bob's result of 10 and plugs it into her operation as:

   ( 10^A ) MOD 17  =  ( 10^9 ) MOD 17  =  1,000,000,000 MOD 17  =  7

STEP 6: Similarly, Bob takes Alice's result of 12 and plugs it into his operation as:

   ( 12^B ) MOD 17  =  ( 12^7 ) MOD 17  =  35,831,808 MOD 17  =  7

The results are the same for Alice and Bob. Alice and Bob will always get the same value if they follow this procedure, and that value is the cipher key, in this case with a value of 7. Proving this neat symmetry is true is a job for the professionals, but the rest of us can take it as a given that it is.

Of course, 7 is a feeble value for a cipher key, and in practice Alice and Bob would pick much bigger values for Y and P to obtain a much longer cipher key. However, the calculations quickly become burdensome and simple examples as used here must use small values to keep calculations manageable. They still often overflow the resolution of a pocket calculator and generally require an indefinite-precision math software package.

The important feature of this scheme is that Eve can listen in on all the information transferred between Alice and Bob, and will still not be able to figure out what the key is. She has to know the secret values of A and B. Alice hasn't told anyone what the value of A is, and Bob hasn't told anyone what the value of B is. They don't have to tell anyone, not even each other, and so in this scenario there is no opportunity for Eve to intercept their values and determine the key.

While Hellman actually dreamed up the scheme, he believed that he couldn't have got from here to there without resonating with Diffie and Merkle, and so this scheme has become known as the "Diffie-Hellman-Merkle key exchange algorithm". In practice, it's just referred to as "Diffie-Hellman" for short.



* The Stanford team had taken a major step forward, but the key exchange algorithm they devised was only part of the answer. It worked fine for a one-to-one internet transaction, but it was impractical for a large online firm trying to deal with a large number of customers. Incidentally, lest we forget, in the 1970s there were no online firms as we think of them now, which hints at how foresighted the Stanford group really was.

The next major insight was Whitfield Diffie's, though it was only half a step. While agonizing over the key exchange problem, he thought up the other part of the solution: "public key cryptography".

Traditional ciphers involve a single key, which is used to both encrypt and decrypt a message, and as mentioned computer block ciphers use a key that is a pattern of randomly-chosen bits.

What makes public key ciphers different is that they have two keys, one that is "public", available to anyone, that can be used to encipher a message; and one that is "private", known only to one person, that can be used to decipher a message. The bizarre thing about a public key cipher is that the public key can be used to encipher a message, but once that message is enciphered, the public key cannot be used to decipher it. Only the private key can decipher the message. In cryptographic terms, public key ciphers are "asymmetric" ciphers, while the traditional "single key" ciphers are "symmetric" ciphers.

In public key cryptography, if Bob wants to send an encrypted message to Alice, he obtains her public key. This key can be distributed to anyone and everyone. Alice could put it on her business card or even her website for anybody to use.

Bob encrypts his message using Alice's public key, and then sends the ciphertext to Alice. Although anyone could intercept the message and obtain Alice's public key, it would do no good, since Bob can't decrypt his own message once he's encrypted it. The public key is one way: it can be used to encrypt, but not decrypt.

Alice, however, can decrypt the message using her private key, which only she knows. Bob doesn't know and doesn't need to know Alice's private key to send her encrypted messages.

This was a brilliant insight, but the catch was that Diffie didn't know how to do it. His public key cryptography scheme was strictly a "what-if" scenario: "What if we could do this? Wouldn't that be cool?"

Despite this limitation, or because of it, in the summer of 1975 the Stanford team published a paper titled "New Directions in Cryptography" to explain their group's key exchange scheme and outline the concept of public key cryptography. They wanted to introduce the idea of public key cryptography to the world to get other cryptographers thinking about it, and published their key exchange scheme to help give the others ideas. It is not always productive to rely on serendipity to get things done, but in this case it paid off well.


[10.5] RSA

* In the summer of 1977, about two years after the Stanford team published their paper, three researchers at the Massachusetts Institute of Technology (MIT) computer science department named Ron Rivest, Adi Shamir, and Ron Adleman announced that they had developed a public key cipher, named "RSA" after their initials.

The RSA scheme involves a combination of one-way modulo math algorithms and a key value that is the product of two large prime numbers. Multiplication is a type of one-way operation, since given a very large key value, say hundreds of digits long, the only known way of factoring it into the two primes that created it is through time-consuming "sieve" algorithms that amount to a trial and error exercise.

In more detail, the RSA scheme works as follows:

STEP 1: Alice begins by selecting two large prime numbers, P and Q. Since this is an example, we'll actually select two small primes, P = 13 and Q = 31, but nobody would actually select such small values in practice. The values of P and Q are secret. They are not exactly Alice's private key, but they are used to produce it, as will be shown presently.

STEP 2: Alice then multiplies P and Q together to get N. In this example:

   N = P * Q = 13 * 31

The result is 403.

STEP 3: Alice then picks another value, E. In this example, we select E as 17. The values of N and E are her "public key" and Alice can put them on her website or her business card. By the way, to ensure security, the value of N must be unique to Alice, or put another way every individual using RSA must have a different value of N. However, the value of E does not need to be unique to Alice.

STEP 4: Once Alice has determined a value for E, she can then use P, Q, and E to build her actual private key, which is known as D and is obtained from the relationship:

   ( E * D ) MOD ((P - 1) * (Q - 1)) = 1

In this case, the values are:

   ( 17 * D ) MOD ((13 - 1) * (31 - 1)) = 1
   ( 17 * D ) MOD ( 12 * 30 ) = 1
   ( 17 * D ) MOD 360 = 1

A trial and error solution to this relationship gives a value for D of 233. Trial and error is impractical for realistic values of E, P, and Q, but a modification of Euclid's algorithm for computing the greatest common divisor of two numbers can be used to obtain the value of D in an efficient fashion. For the curious, how this is done is shown at the end of this section.

STEP 5: Now Bob can use Alice's public key values to send her a message. He does this by converting the message into a binary number, M, and then performing the calculation:

   ( M^E ) MOD N

Suppose that Bob simply sends the message "?" to Alice. In ASCII, this has a binary value of 0011 1111 and an equivalent decimal value of 63. The calculation is then:

   ( M^E ) MOD N
   (63^17) MOD 403

The result is 280, which is the ciphertext message C. Bob sends this to Alice.

STEP 6: Now Alice can decipher the message using the calculation:

   ( C^D ) MOD N
   ( 280^233 ) MOD 403

The result is 63, which evaluates to the ASCII code for a "?".

* Sending a message consisting of a single character is silly, but the message value M has to be smaller than the key value N, since a MOD of a value by N won't give a remainder bigger than (N - 1). Since we're using an unrealistically small value of N in this example, we're stuck with enciphering unrealistically small messages. However, in practice the value of N is always well over a hundred digits, and even if the message is divided into 128-bit blocks for encipherment, the biggest binary values of the message are less than 40 decimal digits long.

Furthermore, RSA isn't generally used to encipher long messages anyway. In the first place, the indefinite-precision exponential + MOD calculation used in RSA is more computation-intensive than the simpler scrambling operations used in block ciphers, meaning enciphering a message with RSA is slow, in fact about a thousand times slower than enciphering a message with an ordinary block cipher.

In the second place, RSA and other public key ciphers are "subexponential", meaning that doubling the key length does not square the amount of effort needed to track down the proper key, making them weaker than good block ciphers. In very broad terms, a 100-bit key for a good block cipher offers about the same security as a 1,000-bit RSA key.

For these reasons, RSA is normally used to encipher a key for a block cipher, not the actual message, which is encrypted with the block cipher. This is known as "hybrid encryption". A short message can be quickly enciphered with RSA, and such a short message also gives less for would-be codebreakers to get a handle on.

In practice, if Bob wants to send an enciphered message to Alice, he creates a long random number as a block cipher key; uses Alice's public key and RSA to encipher the block cipher key, then sends the enciphered key to Alice; and finally enciphers his full message using the block cipher with the random block cipher key, then sends the enciphered message to Alice. The block cipher key is not and should not be used again, and in fact in practice Bob will never even see it, since the encryption software will take care of all such picky details for him.

* As mentioned, a modification of Euclid's algorithm can be used to find the value of "D" in the expression:

   ( 17 * D ) MOD 360 = 1

This is a simple procedure. In this expression, there are three known values:

    17  360  1

The first thing to do is arrange the values in two columns as follows:

    360               360
     17                 1

Now figure out the integer result of dividing 17 into 360 -- which is 21 -- and then multiply the second row by that value:

    360               360
     17 * 21 = 357      1 * 21 = 21

Subtract these new values from the first row -- which gives 3 and 339 -- and plug them into a new row on the bottom, eliminating the original first row:

     17                 1
      3               339

This is the basic cycle of the procedure, and it is repeated in exactly the same fashion. The integer result of dividing 3 into 17 gives 5, and multiplying the second row with 5 gives:

     17                 1
      3 * 5 = 15      339 * 5 = 1,695

Subtracting from the top row gives 2 and -1,694. Now we have:

      3               339
      2            -1,694

In the third cycle of this procedure, of course an integer divide of 3 by 2 gives 1, so:

      3               339
      2 * 1 = 2    -1,694 * 1 = -1,694

Subtracting through gives 1 and 2,033, and:

      2            -1,694
      1             2,033

The value of 1 in the lower left corner of the grid means that no more cycles should be performed, and the value in the lower right corner, 2,033, is the answer, or at least it is the initial answer. Any value that returned the same value after a MOD by 360 would actually work in this calculation, and so a more minimal value can be obtained by the operation:

   2,033 MOD 360 = 233

-- which is the known solution in this case. Why this procedure works is another matter for the professionals.



* One of the footnotes to the inventions of the Diffie-Hellman algorithm and RSA was that somebody else had already been there and done that. A group of cryptographers at the British Government Communications Headquarters (GCHQ) in Cheltenham had discovered public key cryptography a few years earlier.

GCHQ was a descendant of the Bletchley Park operation and roughly comparable to the American NSA organization. In the late 1960s, a GCHQ researcher named James Ellis was working for secure military communications, and came up with ideas that by 1969 had evolved into a basic outline of a public-key cryptography system.

Unfortunately, he didn't have the technical ability to implement it himself, and the idea sat idle for several years. Then, in 1973, Clifford Cocks, who had just graduated from Cambridge with a degree in mathematics, joined GCHQ, and was told about Ellis's "wacky" idea. Cocks got to tinkering and almost immediately came up with the RSA algorithm, hardly realizing that he'd done something incredible. Everybody else was impressed, but as the scheme required more computing power than was available at the time, it still went nowhere.

In 1974, another mathematician named Malcolm Williamson joined GCHQ. He was a boyhood friend of Cocks, and when Cocks told Williamson about his public-key cryptography scheme, Williamson was dubious and tried to think of ways to poke holes in it. He failed, but incidentally came up with the Diffie-Hellman-Merkle key exchange algorithm.

GCHQ didn't do anything with this, either. As everything the organization did was a deep black secret, Ellis, Cocks, and Williamson couldn't say a word about it, while all the credit went to others outside of the "black" world. Cocks finally got authorization to deliver a lecture on the GCHQ work in December 1997, a month after the death of Ellis.

The belated announcement of the GCHQ work led to a certain amount of derision from the cryptologic community. Since priority in science and invention is awarded to those who publish first, the GCHQ group was not entitled to be given priority, though it appears they recognized and understood this. They simply wanted their work acknowledged.

It is interesting to consider in this light what might have gone on in other black organizations like the American NSA and its counterparts in the Soviet Union and elsewhere. Are there major discoveries lying hidden in their secret archives, possibly even filed away and forgotten? In fact, Admiral Bobby Inman, who ran NSA from 1977 to 1981, reported in the 1990s that the NSA had developed some sort of public-key cryptosystem in the mid-1960s for nuclear weapons security purposes.

A paranoid person might even wonder if US government attempts to control the use of strong ciphers, of which much more is said later, were a sham. Maybe the NSA not only developed such strong ciphers a long time ago, but also learned how to crack them, and is busily reading messages that everyone else assumes are impregnable, just as the Germans never dreamed that their Enigma traffic was almost an open book.