An Uncrackable Code?

The snoops may finally have met their match

Almost as soon as humans learned to write, they were devising ways to keep their messages secret. The Old Testament tells how the Prophet Jeremiah used a code word for Babylon. Julius Caesar often encrypted his messages by substituting letters three places farther on in the alphabet, i.e. D replaces A; E replaces B. But no matter how clever they may have been, the codes of antiquity--or of more recent times--rarely withstood the efforts of skilled code breakers. Mary Queen of Scots was ordered beheaded after Queen Elizabeth's chief spy intercepted and decoded Mary's letters, which revealed that she was plotting against Elizabeth. In World War II, the U.S. victory in the Pacific and the defeat of the Third Reich were partly due to the cracking of Axis military codes.

In today's world, the integrity of secret messages can be crucial not only to national security but to commercial and industrial operations as well. Yet as society becomes increasingly reliant on electronically relayed communications--and more sophisticated new gadgetry is developed to intercept them--it is becoming harder than ever to keep a transmitted secret. But now the code breakers may finally have met their match. As a result of recent work by Stanford University scientists, ciphers that are for all practical purposes unbreakable can be produced easily. Says Scientific American Mathematics Columnist Martin Gardner: "The breakthrough bids fair to revolutionize the entire field of secret communication.''

For years governments and military commands have been sending secret messages by so-called onetime pads. These involve the use of keys--the instructions for encoding and decoding a message--made up of long lists of randomly picked numbers that determine the letters to be used as substitutes. Thus if the numbers were 7 and 11, the word "GO" might be encoded as "MY" (G + 6 more letters, O + 10 more letters). After each transmission, the key is changed, so that even if one message becomes available in decoded form, it will not help unravel the next coded communication. Nonetheless, onetime pads have shortcomings. Since both sender and receiver require the same key, it must be sent out beforehand, exposing it to interception. The system is also cumbersome. Because military and diplomatic messages nowadays involve hundreds and even thousands of words, and each message requires a separate key, devising and distributing the different keys can be agonizingly difficult.

Stanford's Whitfield Diffie and Martin E. Hellman, together with Graduate Student Ralph Merkle, overcame this fundamental obstacle with a dazzlingly simple yet ingenious scheme: they proposed the use of two separate but mathematically related keys--one for encoding a message, the other for decoding it. Thus if a group of intelligence agents or businessmen wanted to communicate secretly with one another, they would not have to send a new key prior to each message. On the contrary, the encrypting key could well be made public in a handbook like a telephone directory. In that way, someone who wanted to communicate with the group would simply look up the necessary key and use it to encode a message. Yet even if someone could intercept this transmission, he could not interpret it without access to the second, or decoding, key. Diffie compares this seemingly paradoxical system to a bank's night-deposit box: anyone can put money in, but only authorized employees can take it out.

Putting the Stanford idea into actual practice, a team of computer scientists at M.I.T. led by Ronald Rivest has devised a novel approach. It involves what mathematicians call prime numbers--numbers (e.g., 2, 3, 5, 7, 11, ad infinitum) that can be divided evenly only by themselves or by 1. Under the M.I.T. scheme, each public, or encoding, key is based on the product of two large prime numbers--that is, the result of multiplying these numbers by each other. This result may be a figure several hundred digits long. The private, or decoding, key, on the other hand, is derived from the original prime numbers. To use a simple example: if the encoding key were 323, the decoding key would have to be 17, 19 (since 17 X 19 = 323). If a code breaker wanted to decipher the secret message, he would first have to factor the product--in other words, extract the original two prime numbers that are the source of the decoding key. But even in the computer age, factoring, which can involve trying out seemingly endless combinations of numbers, is an extremely time-consuming process. While it may be easy to factor a low number like 323, Rivest calculates that if the product were, say, 200 digits long, it would take even the fastest and most powerful computers millions of centuries to factor it. Unless some mathematical whiz devised a new high-speed factoring technique, the code would, in effect, be uncrackable.

Keenly aware of the urgent need for better coding techniques, the National Bureau of Standards recently approved its own IBM-designed standard encoding system. It uses more traditional coding techniques rather than the dual-key Stanford system, and could be used to encipher nonclassified electronic data, like the flow of Federal Reserve funds. In fact, appropriately programmed "chips," or microcircuits, could be built directly into computers so that all messages would be automatically encoded and decoded at the terminals. Still, the Government clearly does not want to go too far. Only recently the National Security Agency, the U.S.'s chief cryptographic arm, tried briefly to keep a University of Wisconsin-Milwaukee scientist from patenting a new coding device. It also apparently exerted behind-the-scenes pressure to make the IBM system less secure than it might have been. It fixed the length of the key at 56 bits of computer information rather than, say, 128, which would have been far more difficult to decipher. In both cases, NSA appears to have acted out of the same motive: sensitive to its intelligence responsibilities, it does not want either foreign governments or private groups to learn codes that it cannot break.

This file is automatically generated by a robot program, so viewer discretion is required.