* 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.
* 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 US National Security Agency (NSA) cryptological organization in 1952, the NSA decided to bring telecipher technology into the electronic age. Howard Barlow, head of the agency'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 cheap 21st-century smartphone has vastly more computing horsepower than the KW-26, but it was what could be done in the 1950s.
The KW-26 apparently used an 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 in 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:
1 -->[0] [1] [0] [0] [1] [1] [0] [1]-->
b0 b1 b2 b3 b4 b5 b6 b7
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, until it uselessly fills up with "1s". 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 wire back bits "b0", "b5", and "b7" as follows:
[ XOR(b0,XOR( b5,b7)) ]-->[0] [1] [0] [0] [1] [1] [0] [1]-->
b0 b1 b2 b3 b4 b5 b6 b7
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 XORed bits flagged by an "X"):
X X X 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 punch card.
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 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 -- the "RC" stands for "Rivest Cipher" -- of RSA Security in Bedford, Massachusetts. More is said about Rivest later.
DES itself is now effectively obsolete. DES was a worldwide standard for encryption for over two decades, but by the end of the century, it was clearly running out of steam. New techniques for cracking ciphers were developed, such as "differential cryptanalysis". This is a technique where slightly different plaintexts are enciphered and then the ciphertexts are compared. Differential cryptanalysis can reduce the length of a brute-force search to crack a DES message by a factor of over a thousand.
In 1999, a group of volunteers running a volunteer network of 100,000 personal computers over the internet managed to crack a DES-encrypted message in less than a day. The network was controlled by a software system that assigned each of the PCs a block of possible keys to check, with a PC reporting back after the check to indicate if a match had been found. DES users began to use "triple DES", which involved encrypting a message with DES three times, using 56-bit keys. In principle, triple DES uses three 56-bit keys, but in practice some implementations use only two 56-bit keys, with the same key used for the first and third cycles of encryption.
Well before this, in 1997, NIST realized that DES was close to outliving its usefulness and began an evaluation to select a new cipher, the "Advanced Encryption Standard (AES)". Five finalists were selected and examined for weaknesses. All these candidates were regarded as similar in capability and acceptable, but the winner was a block cipher named "Rijndael", pronounced roughly as "raindoll". It became a US government standard in 2002.
Rijndael was developed by two Belgian cryptographers, Vincent Rijmen and Joan Daemen (a guy, by the way), and was derived from an earlier block cipher named "Square". Rijndael can use blocks and keys with a length of 128, 192, or 256 bits, arranged in any combination for a total of nine possible arrangements of key and block size. The cipher can be easily extended to blocks or keys with lengths in larger multiples of 32 bits. Interestingly, Rijmen and Daemen have made little or no money directly off the adoption of their cipher as a standard. However, the prestige and publicity associated with the award was considerable, and AES is now a big business, with commercial users appreciating the security it offers.
BACK_TO_TOP* 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 obviously broke down in the real world.
BACK_TO_TOP* 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:
Now both Alice and Bob have the same key, which has the value A + B + C = 45, 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 38 to Alice, then Eve would immediately know that B = (38 - 27) = 11. The key value is then 7 + 11 + 27 = 47.
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.
Fortunately, 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. As before, they choose A = 7 and B = 11 respectively.
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 = 7 into the operation:
( 5^A ) MOD 17 = ( 5^7 ) MOD 17 = 78,125 MOD 17 = 10
She sends that value -- 10 -- to Bob.
STEP 4: Bob similarly plugs his secret value B = 11 into the operation:
( 5^B ) MOD 17 = ( 5^11 ) MOD 17 = 48,828,125 MOD 17 = 11
He sends the result -- 11 -- to Alice.
STEP 5: Now here's where the really surprising thing happens. Alice takes Bob's result of 11 and plugs it into her operation, replacing the assumed value of 5:
( 11^A ) MOD 17 = ( 11^7 ) MOD 17 = 19,487,171 MOD 17 = 3
STEP 6: Similarly, Bob takes Alice's result of 10 and plugs it into his operation as:
( 10^B ) MOD 17 = ( 10^11 ) MOD 17 = 10E11 MOD 17 = 3
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 3. 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, 3 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 will require use of indefinite-precision math, meaning math operations carried out to as many digits as needed, possibly hundreds -- which, not incidentally, is laborious to do. A pocket calculator won't do the job.
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.
BACK_TO_TOP* 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.
BACK_TO_TOP* 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 way of factoring it into the two primes that created it is through time-consuming "sieve" algorithms that amount to a methodical trial-&-error exercise.
To use RSA, Alice first chooses two large prime numbers, referred to as "P1" and "P2" here, which are kept secret. She multiplies P1 and P2 to come up with "P12", which is part of both the public and private keys, both keys having two parts. Of course, P12 is not secret.
She then picks an integer "Bp", which is the second part of the public key, the "B" standing for "puBlic". The value has to be greater than 1, less than (P1 - 1) * (P2 - 1), and can share no prime factors with (P1 - 1) * (P2 - 1). A prime number for Bp will work. Since it's part of the public key, it's not secret, and it doesn't have to be unique. One particularly popular value of Bp is 65537 -- which is prime, equal to 2^16 + 1. Why? Ask the mathematicians.
Now Alice computes a number "Vp" that is the second part of the private key, the "V" standing for "priVate". Vp must satisfy the relationship:
( Bp * Vp ) MOD ((P1 - 1) * (P2 - 1)) = 1
Vp can be thought of as a sort of "reciprocal" to Bp. A modification of Euclid's algorithm for computing the greatest common divisor of two numbers can be used to obtain the value of Vp in an efficient fashion. For the curious, how that is done is shown at the end of this section.
OK, so we have P12 and Bp for the public key, and P12 and Vp for the private key. To encrypt a message using Alice's public key, Bob first obtains a copy of the public key, then takes character codes in the message and strings them together as one long binary number. That done, he raises the message to the power Bp, with the result modulo-divided by P12:
( message^Bp ) MOD P12 = ciphertext
Again, this requires laborious extended-precision integer math, using hundreds of digits. Note that this is a mathematical transformation, not encryption with a mask as is typical of traditional ciphers. Anyway, to decrypt, Alice then performs the inverse calculation:
( ciphertext^Vp ) MOD P12 = message
The number derived from the message cannot be longer than P12. If it were, the MOD operation would irreversibly throw away information. To illustrate, all these modulo operations yield the same result:
7 MOD 13 = 20 MOD 13 = 33 MOD 13 = 46 MOD 13 = 7
-- and there's no way to tell what the original number was. Incidentally, there are standard names for these variables:
P1: p P2: q P12: n Bp: e Vp: d
* OK, for a simple example ... first, Alice selects P1 = 13 and P2 = 31. That gives P12 as:
P12 = ( 13 * 31 ) = 403
Second, Alice selects Bp = 17.
Third, she finds a value of Vp that satisfies the relationship:
( Bp * Vp ) MOD (( P1 - 1 ) * ( P2 - 1 )) = 1 ( 17 * Vp ) MOD (( 13 - 1 ) * ( 31 - 1 )) = 1 ( 17 * Vp ) MOD ( 12 * 30 ) = 1 ( 17 * Vp ) MOD 360 = 1
She can write a little brute-force computer program to check out consecutive values of Vp, and see if MOD 360 yields 1. She ends up with Vp = 233.
Now she's ready to go:
public key: P12 = 403 & Bp = 17 private key: P12 = 403 & Vp = 233
Suppose Bob wants to send a message to Alice, and the message is simply the character "?". In ASCII, this has a binary value of 0011 1111, and an equivalent decimal value of 63. The message is then encrypted as:
( message^Bp ) MOD P12 ) = ( 63^17 ) MOD 403 = 280
"280" is the ciphertext. Bob sends this to Alice, who decrypts it with:
( ciphertext^Vp ) MOD P12 = ( 280^233 ) MOD 403 = 63
That is the ASCII code for a "?". Anyone who wants to know exactly how this works again needs to ask the mathematicians -- and have the background to follow the reply -- but it can be broadly said that the MOD operation ensures that it is very difficult to backtrack from the encryption operation.
Sending a message consisting of a single character is silly but again, we can't send a message that encrypts to a number greater than P12. Since we're using an unrealistically small value of P12 in this example, we're stuck with enciphering unrealistically small messages. However, in practice the value of P12 is always well over a hundred digits. Furthermore, RSA isn't generally used to encipher long messages anyway:
For these reasons, RSA is not used to encipher long messages. In practice, if Bob wants to send an enciphered message to Alice, he:
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. This scheme is known as "hybrid encryption".
* 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:
------------------------------------------------
[a] 360 360
[b] 17 1
------------------------------------------------
Now figure out the integer result of dividing 17 into 360 -- which is 21 -- then multiply the second row by that value, and subtract the result from the first row:
------------------------------------------------
[a] 360 360
[b] 17 1
360 MOD 17 = 21
21 * 17 = 357 21 * 1 = 21
360 - 357 = 3 360 - 21 = 339
[c] 3 339
------------------------------------------------
Now we repeat the scheme:
------------------------------------------------
[a] 360 360
[b] 17 1
[c] 3 339
17 MOD 3 = 5
5 * 3 = 15 5 * 339 = 1,695
17 - 15 = 2 1 - 1,695 = -1,694
[d] 2 -1,694
------------------------------------------------
-- and again:
------------------------------------------------
[a] 360 360
[b] 17 1
[c] 3 339
[d] 2 -1,694
3 MOD 2 = 1
1 * 2 = 2 1 * -1,694 = -1,694
3 - 2 = 1 339 + 1,694 = 2,033
[e] 1 2,033
------------------------------------------------
The left-hand value of "1" means we can go no further, we're done:
------------------------------------------------
[a] 360 360
[b] 17 1
[c] 3 339
[d] 2 -1,694
[e] 1 2,033
------------------------------------------------
The value of 2,033 is the answer, or at least it is after performing MOD 360:
2,033 MOD 360 = 233
-- which is the known solution in this case. Why this procedure works is another matter for the professionals.
* Since RSA is computation-intensive, it is slow and cumbersome for use on handheld computing devices with limited computing horsepower. As a result, public-key cryptography software based on a class of one-way operations known as "elliptic curve" functions has been developed, where an elliptic curve function is of the form:
Y^2 + k1 * X * Y + k2 * Y = X^3 + k3 * X^2 + k4 * X + k5
-- where "k1" through "k5" are constant values. For elliptic curve cryptography (ECC), this general form of an elliptic curve function is simplified and modified to:
Y^2 MOD P = (X^3 + k1 * X + k2) MOD P
Without getting into details, this is another algorithm for generating cryptographic keys that are difficult to backtrack, and it can be used to generate schemes along the lines of Diffie-Hellman key exchange and RSA. ECC has two advantages over RSA:
* RSA has another difficulty; as discussed later, ways to factor large numbers are being developed that could break it more or less easily, and apparently ECC isn't secure over the long run, either. The search is on for other schemes of public-key cryptography, one promising approach being "lattice cryptography".
The core idea is simple. Suppose we take a set of one-dimensional arrays or "vectors" of arbitrary numbers, for example:
[ 340 512 76 101 952 ] [ 92 241 53 376 56 ] [ 211 632 717 88 73 ] [ 123 801 91 665 952 ] [ 428 44 739 210 80 ]
Now suppose we add two of these vectors together to produce a sum vector, for example:
[ 92 241 53 376 56 ] + [ 123 801 91 665 952 ] ------------------------------- [ 215 1042 144 1041 1008 ]
A base set of vectors and all the sum vectors that can be derived from them is called a "lattice". Given a sum vector, it is obviously very difficult to backtrack the two vectors that produced it, and gets much harder as the vectors get longer, up into the hundreds of digits. How that can be turned into a public-key cipher scheme is another question; being based on a calculation, presumably a short message will be enciphered as an indefinite-precision number. It can be done; it's just a question of the best way of doing it.
BACK_TO_TOP* 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 on 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, are 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, if not exactly an open book, hardly an unreadable one.
BACK_TO_TOP