The fundamental weakness associated with symmetric (also called private key) encryption algorithms is that the users must find a secure way to communicate the key to each other. In 1976, two researchers revealed the first asymmetric algorithm that bypassed this problem. Public key (asymmetric) encryption is becoming increasingly more important, and for more reasons other than just security.

In November 1976 two researchers at Stanford University, Whitfield Diffie and Martin Hellman, published their paper ‘New Directions in Cryptography’. The paper put forward a revolutionary method of cryptography: asymmetric or public key cryptography.

Public key cryptography was different from private key in that instead of using the same key for encryption and decryption, it employed a corresponding pair of keys: a public key and a private key. The public key is published while the private key is kept secret.

Supposing Fahad wants to send Ahmed a secure message, Fahad would encrypt the message using Ahmed’s public key. The only feasible way to decrypt the message is to use Ahmed’s private key (which only he has).

Furthermore, Ahmed can send messages encrypted with his private key. Although these messages are not secure (because the public key for decrypting such a message is publicized and therefore available to anyone, not just the intended recipient), successful decryption using Ahmed’s public key indicates that the message definitely originated from Ahmed (unless, of course, he hasn't kept his private key secret). This is the basis for what is known as digital signatures.

The digital signature is a code (or large number) that is unique for each message and to each message originator. Authentication using digital signatures not only assures the receiver that the message was from the expected sender, it can also confirm that the message is complete and has not been altered (either accidentally or purposefully).

Processing a message with a hash function produces a small digest of information that is dependant upon each bit of the information. Because the digest incorporates information about each bit of data in the whole message, a different hash function will be produced if even one bit of the message is altered.

The digest authenticates the message; it can then be encrypted by the user with their private key producing an electronic signature that (virtually) guarantees the origin of the message, and the messages integrity. Obviously anyone can now use the appropriate public key to decrypt the message; to secure the message it would be necessary to encrypt it using the public key of the destination person.

Anyone using a public key to send an encrypted message needs to be confident that the key is truly the public key of the person associated with it. In a small community of users this is unlikely to be a problem; however, the need to adequately publicize a public key and to make it available to strangers suggests there is a need for some trusted third party to maintain a register of public keys and their owners.

The need for procedures to deal with lost keys and retired keys suggests that a formal public key infrastructure is necessary to make the most of this technology. The development of this is largely being driven by the proponents of electronic commerce.

As well as offering security, integrity and authentication, the successful decryption of a message using a public key makes the message non-repudiable: the sender whose public key is used cannot claim not to have sent the message. This is particularly important for electronic commerce.

Perhaps the best known of public key systems is RSA, devised and patented in 1978 at the Massachusetts Institute of Technology by Rivest, Shamir and Adelman. RSA is incorporated in many common software packages and is quickly becoming the de facto standard for public key encryption.

                     Shamir                  Rivest                  Adelman

The main disadvantage of public key encryption is that, because of the large amount of computing necessary for encryption and decryption, it is very slow and inefficient to use. This prevents it being employed in voice applications and also for securing large amounts of information.

A common approach with encryption is to use public key encryption to exchange keys necessary for symmetrical (private) key encryption. This is a logical process when first sharing a private key with another party.

However, if this method is used to periodically update the symmetrical keys (because of a fear they have been compromised), the logic is less sound. As one expert in the field puts it "One is (then) using a system, whose keys never get changed, to exchange secret keys for another system, because it is deemed insecure if the keys don’t get changed".

Public key encryption security theoretically (see opposite box) relies on the difficulty of figuring two large prime numbers when given their product. In other words, factoring a large number is far more difficult than verifying that two or more numbers are prime factors of the same large number.

The public and private keys are functions of a pair of large prime numbers, 100 to 300 digits long.

A new cryptanalytic attack has shaken confidence in the security of the public key encryption scheme. Paul C. Kocher, a cryptography consultant, has, as reported in SCIENTIFIC AMERICAN, March 1996, proven the secret key can be ascertained by observing the time a computer takes to decipher messages.

New Direction

The Basic

Digital Signatures

Hash functions

Key Authentication

Non Repudiation

RSA

Implementation

Theory

 Practice