Public Key Systems

The problems with conventional cryptography are elegantly solved by
public-key cryptography. Based on the Diffie-Hellman approach, a public-key
cryptosystem works something like a doorlock with two keys. One key locks
the door, and a different key unlocks it. In a public-key cryptosystem
system, every participant has two related, complementary digital keys:

   * A public key, which can be widely known and could even be published in
     an digital directory like a phone number.
   * A private key, that only you know and that you guard very closely.

Each key decrypts the cipher that the other creates. When Alice wants to
send Bob a private message, she uses his public key to scramble the text of
her message. The scrambled message can now be unscrambled only by Bob when
he applies his private key.

Even Alice cannot unscramble the message she scrambled using Bob's public
key. Similarly, when Bob wants to reply to Alice's message, he encrypts
using Alice's public key (which she may have sent along to him in her
message if he didn't already have it) and Alice then decrypts using her
private key.

Privacy and authentication
The privacy advantages of a public-key cryptosystem on large networks are
obvious:

   * Anyone can send a private message to anyone else simply by using the
     intended recipient's public key which is readily available to encrypt
     it.
   * Anyone who intercepts the message will not be able to read it, even if
     they have the sender's or the recipient's public key.
   * Since knowing someone's public key provides no clues to their private
     key, only the intended recipient, using their private key, can decrypt
     and read it.
   * The number of key exchanges on a network is minimal. For a network of
     1,000 users, only 2,000 public-key exchanges are needed for everyone to
     communicate privately with everyone else.

Beyond privacy, public-key cryptography provides another capability not
readily available in any other cryptosystems: the ability to "sign" a
document digitally. Alice applies her digital signature to the message by
first encrypting it with her private key and then re-encrypting it with
Bob's public key.

When Bob decrypts the message using his private key, he finds Alice's
digital signature, thus assuring him that the message did indeed come from
Alice (or at least from someone who has gotten hold of Alice's private key.)

Application of a digital signature to electronic messaging is immensely
important for carrying on business and financial transactions over computer
networks since it:

   * Proves to Bob or anyone else with Alice's public key that a message
     signed by Alice, really did come from Alice. This function is known as
     authentication.
   * Assures both Alice and Bob that no one has intercepted or altered the
     message, since any such alteration would automatically be detected and
     an alert posted in the message.
   * Prevents the forgery of digital documents, since only Alice can sign
     Alice's digital signature.
   * Prevents Alice from later claiming the document did not come from her.

These functions open a vast new world of other privacy possibilities for
public-key cryptosystems, including untraceable digital cash, anonymous
electronic voting, digital pseudonyms, electronic "reputations," anonymous,
but trusted, financial transactions, and so on, and these are only a few
that people have thought of so far.

If allowed to flourish, public-key cryptography could become one of the most
widespread technologies of the information age. This is a big "IF," however,
because government pressure, export laws, and patent questions have so far
worked together to limit its use.

The patents will expire by the end of the decade,1 but the hand of the
government promises to weigh heavily on the world of private information
transfer for decades to come. While public-key cryptosystems are still
perfectly legal for anyone to use, the NSA has consistently resisted
attempts to incorporate true public-key cryptography into the Federal
Information Processing Standard (FIPS), thus preventing it from replacing
the aging DES or being used as a Digital Signature Standard (DSS). Despite
this negative pressure, one public-key cipher may already be on its way to
becoming the de facto standard, again demonstrating the momentum of a
powerful idea whose time has come.

RSA: Public-Key Enters the Mainstream
The work of Diffie and Hellman was largely theoretical, demonstrating what
could be done with public-key cryptography. It took a trio of MIT
mathematicians to develop a workable public- key system employing the
Diffie-Hellman algorithm. Supported partly by money from the National
Science Foundation and the US Navy, Professors Ronald Rivest, Adi Shamir,
and Leonard Adleman published their method, known as the RSA (named for
their initials) public-key cryptosystem in 1978.

Fearful that the government would hold up their patents or block civilian
use of their system, Rivest, Shamir, and Adleman rushed their method into
publication even before patenting it. By so doing they sacrificed their
international patent rights, although they were still able to patent it in
the US. MIT initially held the US patent for public-key cryptography
(#4,405,829, issued September 20, 1983). Both the Diffie-Hellman and RSA
patents are now held by Public Key Partners (PKP), which has licensed them
to RSA Data Security, Inc., Redwood City, California, the largest marketer
of public-key technology in the world.

RSA is rarely used by itself, but is typically incorporated into other
software to provide data security. RSA Data Security's president Jim Bidzos
compares the system to the Dolby noise suppression technology used in stereo
systems. "We're to computers what Dolby is to tape decks," says Bidzos. "We
get built in and we stay ahead of the market by innovating." RSA has so far
been included in millions of software packages both in the US and in the
rest of the world and is seen by many as the de facto standard for
commercial data communications security, especially outside the US.

Whether RSA will ever replace the DES has been the focus of a raging
political storm since the late 1980s. Twice the National Institute of
Standards and Technology (NIST) has proposed RSA as the digital security
standard, and twice NSA, without any direct authority over civilian data
security, has nevertheless managed to slap it down, proposing instead
systems where data security and privacy plays a secondary role to electronic
surveillance. (See The NSA Vs. RSA.)

How RSA Works
RSA cryptosystems provide three basic functions:

Key management
     The creation of public and private keys; the transmission of public
     keys; assuring the security of private keys.
Privacy
     The encryption of messages in the equivalent of digital envelopes that
     can only be opened using the addressee's private key.
Creation and verification of digital signatures
     Ensuring that the contents of a message are correct and complete and
     have not been tampered with.

The essence of the RSA cipher lies in an age-old mathematical problem: It is
very difficult to factor large prime numbers. While the math of RSA is
beyond the scope of this book, a brief, simplified explanation may be useful
for understanding the cipher's strengths and weaknesses. First, a couple of
definitions.

Prime number
     A prime number, or simply, a prime, is any number that is evenly
     divisible only by 1 and itself. Small prime numbers include 3, 5, 11,
     13, 17, 19, and 23. In RSA, the keys are based on the product of two
     prime numbers that may be hundreds of digits long.
Factoring
     Factoring means dividing a whole number into its component parts. The
     factors of 25 (not a prime) are 25 & 1, and 5 & 5. The factors of 23, a
     prime, are 23 & 1. Breaking RSA requires factoring the 100+ digit-long
     product of the multiplication of two large primes to discover what
     those two initial primes were. If you had to determine the two primes
     that made up 21, a few seconds of thought would tell you they were 3
     and 7. But if the number has hundreds of digits, the task becomes as
     difficult as any in mathematics, even with the help of the most
     powerful computers in the world.

Sending a message with RSA
Here's what happens when you send a message using an RSA cipher:

Step 1: Create public and private keys
     First you need to create a public and a private key. You need only do
     this once.

The RSA software does this automatically by multiplying two long, randomly
chosen prime numbers together. The product then undergoes a series of
mathematical transformations that result in a private key and a related
public key. Actually, these keys are very large numbers the software uses to
scramble the message. So large are the numbers involved, that knowing one
key will not help you deduce the other.

Your public key is clearly readable, although it looks like a random
collection of letters. Your private key is encrypted with a password or pass
phrase that you select and keep in a safe place, preferably your memory.

Step 2: Convert the message to numbers
     Using a relatively straightforward algorithm, the characters that
     comprise the message are transformed into numbers (eg, A=17, B=12, ...,
     Z=516). Once converted to numbers, they can be easily manipulated in
     any imaginable way by complex mathematical functions.
Step 3: Encrypt
     Once Alice's message is converted to numerical values, applying Bob's
     public key plus the RSA algorithm scrambles the message beyond
     recognition. In effect, Alice has placed her message in a digital
     envelope that only Bob can open.
Step 4: Decrypt
     Upon receiving Alice's message and noting it has been sealed inside an
     envelope using his public key, Bob simply applies his private key to
     the message using the same RSA software system, thus revealing the
     contents of the message in normal- looking text (plaintext).

Go to Encryption Always Wins
Return to Table of Contents

[Want to keep the snoopers out of your private life? Wantcontinued access to this HyperBook? Then beam us $9.95 now!Here's how!]

We want to hear from you. Send us feedback! And/or submit your writing and
art to Smart Publications for inclusion in Tools For Privacy!

Tools For Privacy copyright 1995 Smart Publications

smart@crl.com