Opening the "Trapdoor Knapsack"

By Philip Faflick

An Israeli mathematician cracks a formidable code

Five years ago, computer scientists at Stanford and M.I.T. made a pair of chummy but keenly competitive $100 bets. A team at each university had devised a secret code to protect computers from electronic intruders by scrambling and unscrambling the data in a complex fashion. Each team offered cash to the first mathematician who could crack its code, figuring that the deciphering could not be done in much less than a million years. To the surprise of all concerned, however, the Stanford scheme sprang a leak this year, putting $100 in the pocket of a determined young Israeli theoretician and raising troublesome, and potentially costly, questions about whether computers can ever be made to keep their secrets.

In the past, such a breakthrough in cryptography might have mattered only to a few hundred cryptanalysts and a handful of spies. Today, however, the demonstration of a code's vulnerability nevitably has worrisome implications for the way banks and multinational firms do business. Consider the stakes: the U.S. banking system alone moves some $400 billion by computer around the country every day; yet many banks pump money onto the wires and over satellite networks with little or no encryption, or coding, at all. Predicts Mathematician Ralph Merkle, a member of the Stanford codemaking team: "One of these days someone will break into a wire-transfer banking network and siphon off all the contents. Then there will be a lot of interest in cryptography."

The Stanford coding system was cracked by Adi Shamir, 30, an Israeli expert in the branch of mathematics known as complexity theory. Shamir was at M.I.T. in the late '70s as an associate professor of mathematics, and in fact helped write the M.I.T. code that competes head-on with Stanford's. Last spring, back in his spartan, second-floor office in the Weizmann Institute of Science in Rehovot, the lean, blue-jeaned mathematician settled the old wager: he found a way to unravel the original Stanford system. The code Shamir broke after four years of hard work was no Buck Rogers-Dick Tracy cipher. It was a charter member, along with the M.I.T. code, of the new "public key" family of encryption schemes, so called because one of their secret code words, or keys, can be made public without giving anything away.

Most codes have only one key, usually a string of letters or numerals, that determines how a piece of plain text is to be scrambled and unscrambled. By permitting their key to be openly published, the new codes have a great advantage over all conventional message scramblers, including the popular Data-Encryption Standard (DBS) code, developed by IBM and endorsed by the National Bureau of Standards. To send one message with a DES code requires at least two separate transmissions: one to send the coded text and another to send the secret key that unlocks it. "The big problem in data encryption is managing the keys," says one executive in charge of computer security. "That's the thing that drives people crazy." With a large electronic mail system, in which users send each other notes by computer, each user sending coded messages needs separate keys for every combination of sender and receiver. One thousand users require nearly half a million keys. In 1976 Merkle and two other researchers at Stanford, Martin Hellman and Whitfield Diffie, attacked the unwieldy problem of key distribution. In one of the cleverest shortcuts in modern cryptography, they replaced the single key used in conventional schemes with two separate keys related only by a complex and deliberately dense mathematical formula.

Electronic mailboxes can be set up with two keys for each subscriber to the system. Dick Tracy, should he choose to subscribe, would select his own two keys, much as a bank will permit customers to choose their own cash-machine passwords. If Buck Rogers wants to send Dick Tracy a secret communication, he simply looks up Dick's public encoding key in a directory and uses it to garble his message. No one without access to Dick's secret decoding key, not even Buck himself, can read the resulting scramble of letters and numbers.

In Israel, Shamir challenged a version of this dual-key scheme. The Stanford code, based on a conundrum known among mathematicians as the "trapdoor knapsack," was thought to be so fiendishly complex that even the world's most powerful computers could not crack it. But Shamir proved otherwise. Exploiting recent advances in an obscure branch of number theory, he bore into the trapdoor knapsack system and revealed that the secret decoder could in fact be unraveled by analysis of the encoder that was published. "I was sitting alone staring at the wallboard on which some equations were written," he recalls. "Suddenly everything fell into place, all the pieces. I saw the missing links and I knew just what to do." Insists Lee Segel, head of Weizmann's faculty of mathematical sciences: "He kicked the competition in the teeth."

The public-key concept may survive Shamir's master stroke. Secret codes, like fine wines, tend to improve with age. The competing code system Shamir co-authored at M.I.T. remains, for the moment, uncracked. But the discovery of so basic a flaw in the Stanford scheme is no small matter. When public-key codes first started appearing in scientific journals, Admiral Bobby Inman, then head of the National Security Agency and until recently deputy director of the CIA, worried in public about the Soviets' and other hostile nations' learning to develop uncrackable codes simply by studying published U.S. encryption work. But that fear may lave been misdirected: on the contrary, the real security problem for the electronic age may be that no computer can be made completely safe from intruders determined to break in. --By Philip Faflick. Reported by Russell Leavitt/Los Angeles and Martin Levin/Jerusalem

With reporting by Russell Leavitt, Martin Levin

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