The following is intended for limited-distribution, educational purposes only.... Citation: The Economist, Sept 21, 1991 v320 n7725 p104(2) COPYRIGHT Economist Newspaper Ltd. (UK) 1991 ---------------------------------------------------------------------- Title: A cure for the common code: computer cryptography. ---------------------------------------------------------------------- Subjects: Public key cryptosystems_Standards Digital signatures_Standards Data encryption_Research United States. National Institute of Standards and Technology_Laws, regulations, etc. Reference #: A11286848 ====================================================================== Summary: Advances in the mathematics of prime factorization algorithms have led to a technology that, once standardized, will dramatically improve public-key cryptography. The RSA algorithm is popular in the computer industry, but the government favors an alternative. ====================================================================== ANYONE can sign a postcard, but how do you sign a piece of electronic mail? Without a "signature" to demonstrate that, say, an electronic transfer of funds really comes from someone authorised to make the transfer, progress towards all-electronic commerce is stymied. Ways of producing such signatures are available, thanks to the technology of public-key cryptography. They will not work to everyone's best advantage, though, until everyone uses the same public-key system. It is an obvious opportunity for standards-makers - but in America they have turned up their noses at all the variations on the theme currently in use. The alternative standard for digital signatures now offered by America's National Institute of Standards and Technology (NIST) has brought a long-simmering controversy back to the boil. Public-key cryptography could become one of the most common technologies of the information age, underpinning all sorts of routine transactions. Not only does it promise to provide the digital equivalent of a signature, it could also give users an electronic envelope to keep private messages from prying eyes. The idea is to create codes that have two related keys. In conventional cryptography the sender and receiver share a single secret key; the sender uses it to encode the message, the receiver to decode it. In public-key techniques, each person has a pair of keys: a disclosed public key and a secret private key. Messages encoded with the private key can only be decoded with the corresponding public key, and vice versa. The public keys are published like telephone numbers. The private keys are secret. With this technology, digital signatures are simple. Encode your message, or just the name you sign it with, using your private key. If the recipient can decode the message with your public key, he can be confident it came from you. Sending a confidential message - putting electronic mail in a tamper-proof envelope - is equally straightforward. To send a secret to Alice encode it with her public key. Only Alice (or someone else who knows her private key) will be able to decode the message. The heart of any system of public-key cryptography is a mathematical function which takes in a message and a key, and puts out a code. This function must be fairly quick and easy to use, so that putting things into code does not take forever. It must be very hard to undo, so that getting things out of code does take forever, unless the decoder has the decoding key. Obviously, there must be no easy way to deduce the private key from the public key. Finding functions that meet these criteria is "a combination of mathematics and muddle", according to Roger Needham of the Cambridge Computer Laboratory. The greatest successes to arise from the muddle so far are those using functions called prime factorisation algorithms. They are based on the mathematical insight that, while it is easy to multiply two numbers together, it is very hard to work backwards to find the particular two numbers which were multiplied together to produce some given number. If Alice chooses two large prime numbers as her private key and publishes their 150-digit product as her public key, it would probably take a code-breaker thousands of years to work backwards to calculate her private keys. A variety of schemes have been worked out which use this insight as the basis for a workable public-key code. Most popular of these is the so-called RSA algorithm, named after the three MIT professors who created it - Ronald Rivest, Adi Shamir and Len Adleman. It has been patented and is sold by a Silicon Valley company, called RSA, that employs 15 people, most of them ex-MIT graduate students. Faculty firms are to computer start-ups what family firms were to the industrial revolution. RSA has attracted both academic praise and a range of heavyweight commercial customers: Microsoft, Sun Microsystems, Digital Equipment and Lotus Development. But, despite repeated applications, it has never been endorsed by those in government. Rumours abound that the code-breakers in the National Security Agency have discouraged standard-setters from recommending RSA because they do not want to promote the use of codes they cannot break. RSA, for obvious reasons, does not discourage the rumours. Whatever the reason, the standard-setters at the NIST have side-stepped the debate over RSA with their new algorithm, DSA. As set out in the standard, DSA verifies the identity of the sender, but does not encrypt the message. It appends to the message a number calculated from the message and the sender's private key. The recipient can then use this number, the message and the sender's public key to verify that the message is what it seems. The NIST says that this technique is well suited to "smart cards" and other applications where there is not a lot of computing power available for working out codes. Because it hopes that DSA Will be used for verifying the identity of everyone from welfare recipients to military contractors, its flexibility is a boon. Meanwhile, however, more and more companies are choosing a public-key cryptography system for communicating confidentially - often RSA, sometimes something different. Someday, probably soon, governments will want to choose, too. Watch out for fireworks when they do. ------------------end forwarded article-------------------------- Russell Earl Whitaker whitaker@eternity.demon.co.uk Communications Editor 71750.2413@compuserve.com EXTROPY: The Journal of Transhumanist Thought AMiX: RWHITAKER Board member, Extropy Institute (ExI) [.sig revised 1 October 1992 /// Send mail to eternity node] -----BEGIN PGP PUBLIC KEY BLOCK----- Version: 2.0 mQCNAiqwg10AAAEEAMVNMI766ljeuW01xqXKYYV5lmDPvb+6dCQK3m1iBQdan0no pm35j1DIRp3UJZogAe5eimsQg1TALDhTq310OZs9+L6B/HxeX3+4BadIDad4g+xI lvaFY1Ut/hMdZNkw0tzNZOdUPiO4jYIyirReAUiMCm6jXzkTRITj7/vxxWtPAAUR tDNSdXNzZWxsIEUuIFdoaXRha2VyIDx3aGl0YWtlckBldGVybml0eS5kZW1vbi5j by51az4= =LOCL -----END PGP PUBLIC KEY BLOCK-----