Computers in the secret world of codes

Press, 27 October 1982, Page 14

Computers in the secret world of codes

From “The Economist,” London

Cryptography, long a black art monopolised by spies and codebreakers, is about to become a normal part of business life. Computers are the reason. Computer data, stored and transmitted electronically, cannot be guarded by simple physical precautions. Today's crooks can tap into a computer system using a remote terminal, then alter, damage or read unprotected data stored in it as easily as if someone had left the safe door open. Now one standard cryptography scheme is about to spread rapidly through America’s financial system; small businesses relying on micro-computers can buy, for a few hundred dollars, cryptographic devices that will protect their files. Cryptography is essentially a branch of higher mathematics. To understand look at a simple substitution cypher. If each letter of the English alphabet is swapped for a randomly chosen substitute, thus: ABCDEFGHIJKLMNO ... THUVICWBNFSPODZ ...

a cryptanalyst looking at the result is, in theory, faced with 400 million billion billion possible ways in which the swap might have been made. In practice, the English language possesses a high degree of redundancy. That means that it is easy to guess what any message is supposed to mean even if large numbers of letters or words are unknown. A simple substitution cypher can usually be broken with a message only 25 letters long.

The ideal solution is to encipher the first letter of the text with one substituion-alphabet, then the second with a second alphabet, the third with a third and so on.

If the key (which determines which alphabet is used for which letter of the text) is as

long as the message, there is perfect security. This sytsem — known as the one-time pad — is used for the MoscowWashington “hot line,” which is simply an enciphered telex link.

The snag with one-time pads is that both parties to the communication must possess — but hold in perfect secrecy — keys of considerable length. The keys are too long simply to be memorised. The problems of producing and distributing the keys in perfect secrecy become much worse if there are several potential parties to the conversation, as is usually the case in commercial communications.

In practice, only a highpriority arrangement between co-operating governments, such as the hot line, is likely to make one-time pads feasible. Shorter keys, repeated as necessary until each letter of a text is enciphered, are more practical. Snag: the shorter the key, the easier the codebreaker’s task. The solution lies in increasing the "work factor” for the hypothetical cryptanalyst adversary. By combining substitution schemes; by repeated encipherment, using different keys, of the same text, and by transposing the letters in the text several times, the work factor could be increased dramatically. The aim is not to make cracking the code impossible but to make it impractical.

These are the principles on which America’s Data Encryption Standard (D.E.S.) is based. The D.E.S., adopted by the National Bureau of Standards in 1977, draws on work done by 1.8. M. for a computer-security product called Lucifer. However, whereas ' Lucifer had a key 128 bits long (a bit is

a basic unit of computer information) the D.E.S. has a kev that is only 56 bits long. That makes it more convenient, but more vulnerable.

Although conventional computers contain one central processing unit, which carries out one operation at a time, it is possible to build "parallel processors” which link together lots of different processing units to carry out many such operations simultaneously. Any organisation, which really wanted to crack commercial codes, could build a dedicated parallel-processing computer (using 1 million chips) to carry out 1 million key trials a second. Other techniques (including “pipelining") can be added to speed up the process still further — to produce a codebreaking machine that would have a high probability of producing the key in one day. A government could easily afford such a machine, for which cost estimates range from $4 million to $2O million. Commercial firms, most probably, could not.

Had the longer, 128-bit key been chosen for D.E.S., the cost of an average solution would rise dramatically. Mr James Bamford, in his recent book on the National Security Agency, “The Puzzle Palace,” estimates that such a cypher would cost would-be breakers $200,000,000,000,000,000,000,000, ,000 a solution, putting breaking of commercial codes outside even a government’s budget.

Critics, including computer scientists working in cryptography, ask whether the D.E.S. was designed to make it safe in ordinary use but vulnerable to America's National Security Agency.

Whatever one makes of this accusation, users of the D.E.S. can make their codes much more secure by repeating the

encipherment of the message using a different key (and/or using a technique known as “chaining”). A second encipherment, for instance, takes the effective key length up to 75 bits; any subsequent encipherment raises it further. So far, the National Bureau of Standards has approved only 20 commercial implementationfe of D.E.S. Controversy over the length of its key is one reason. Another cause of delay has been lengthy discussions within the banking industry about a whole series of auxiliary standards that must be agreed before the D.E.S. can go into widespread use for electronic funds transfer. Most of these issues have now been settled, and, says the. National Bureau of Standards' Dr Dennis Branstadt, the use of D.E.S. will be growing “pretty close to exponentially" in the next few years. Lots of unexpected uses are emerging. The D.E.S. is available on a chip from several vendors, making it a cheap way for almost anybody to protect valuable data. Cable and satellite television operators, wishing to conceal their programming from viewers who have not paid for it, are thinking about using D.E.S. chips to encode their video signals. Also, firms are offering plugin D.E.S. boards to allow small businessmen to hide their data from an increasingly com-puter-literate world. One such board, the Encryptor, made by Jones Futurex of Fair Oaks, California, costs $295 if supplied for the 1.8. M. personal computer. The D.E.S. is not' the only method of encryption that could, find a market in the private sector. Academic cryptologists invented an entirely new type of cypher, which has advantages for anybody who needs to swap information with

a number of correspondents. The new schemes, called “pub-lic-key cryptography," also provide a foolproof way of determining who sent any particular message. Traditional cyphers have only one key, used both to encode a message and to decipher it. The new type of cypher uses two different keys. A firm could make the encoding key public, so anybody could send it messages, but keep the decoding key private, so as to guard the messages from interception.

Alternatively, it could keep the encoding key secret, so anybody receiving its messages could use a publicly available key to decipher them, but would know the identity of the author. By encoding twice, once with a public and one with a private key, both parties to the transaction could be confident of the secrecy of the message and the identity of the other correspondent.

This neat idea works by exploiting certain “one-way" mathematical functions. A oneway function can best be described by analogy with simple arithmetic.

Most people can multiply 12 by 343 (equals 4116) in their heads without too much difficulty, few people could divide 4116 by 343 in their heads. Oneway functions take that example to extremes: they are easy to calculate one way, but almost impossible, even for computers, to calculate in reverse.

One such problem is the “knapsack problem." Imagine you nave been given a knapsack filled with packages of various weights. You know the weight of the empty knapsack, the weight of the various potential items inside, and the total weight of the filled knap-

sack. Can you use this knowledge to determine which items are actually inside? Finding the total weight of the knapsack and its contents together is a trivial problem in addition. Doing it the other way round is enormously difficult: the solution can take millions of years of computer time.

In fact, the “knapsack" problem is one of a category of one-way functions which contain “trapdoors" or short-cuts to the answer if you are given the right clue.

Mr Adi Shamir, of the Weizmann Institute, discovered earlier this year that it was possible to use recent mathematical discoveries to uncover the tell-tale “trapdoor" clue. This August, at a cryptography conference at the University of California at Santa Barbara. Mr Leonard Adleman of the University of Southern California, demonstrated that Mr Shamir’s discovery worked. Using an Apple computer, he cracked overnight a code devised by Mr Shamir. Mr Adleman and Mr Shamir are themselves co-authors (along with Mr Ronald Rivest) of a cypher based on a much more difficult mathematical problem, that of speedily dividing into factors (whole numbers) the sum produced by multipying two very large prime numbers (that is. numbers that can be divided only by one or by themselves).

The Rivest-Shamir-Adleman (R.S.A.) scheme, based on this problem, is likely to prove much more robust than those based on the knapsack problem. But mathematics continues to make progress, and difficult mathematical problems may not prove intractable for long. Already, say some cryptographers, people using the R.S.A. scheme should make sure they use prime numbers 200 digits long.