The obvious use of public key cryptography is to allow secret communications in the absence of prior secure contact.
Publish your public key. People can send you messages that no one but you can read.
That's simple enough. But if other people don't really know who you are, why would they send you messages that need to be encrypted?
A big corporation could put a one-way hash or checksum of its public key on its billboards or its magazine ads, to make you feel safe about sending your credit card number to it over the Web with that public key. However, things are usually done a bit differently.
Another use of some public key algorithms, particularly RSA, is digital signatures. Suppose you encrypt a message using your private key. Then, anyone can decrypt it who knows your public key; but only you could have encrypted it in the first place. Thus, you've proved that you saw that message, and chose to encrypt it.
So, one of the commonest uses of digital signatures is in key certificates. The company that wrote your web browser includes, built right into the program, the public key of a company that certifies the ownership of other public keys. When you visit a site where you want to make a credit card order, your browser can then check that the public key you will use to encrypt your credit card number really belongs to the company you think you're ordering from.
Certificates can also be used in a less hierarchial fashion. A program like PGP allows your friends to vouch for the key of any new person you wish to use PGP to communicate with, and uses a system of weighting to consider certificates from a friend of a friend; this system is called the 'web of trust'.
Just as a public key algorithm can be used to encrypt the key (for use with a conventional algorithm like DES) by which a message is encrypted, rather than the whole message, to sign a message you can simply encrypt a good one-way hash of that message rather than the message itself.
Some types of digital signature don't require public-key cryptography, only hash functions. To prove that you knew something a year before you're willing to make it public, publish today a one-way hash of what you know, and a year later, publish what you had hashed then. This technique was used hundreds of years ago; the discovery that Venus has phases like the moon, and the discovery that Saturn has rings, were both claimed prior to publication by the act of publishing phrases which were anagrams of the statements of the discoveries.
The Diffie-Lamport signature scheme is closely related to this idea of using a hash of a message to sign that message in advance of sending it. To be able to sign a single message to be sent in the future, without knowing its text in advance, generate a pair of DES keys for every bit in the message or a hash of the message. Publish a plaintext/ciphertext pair of blocks for each of these keys, indicating which two pairs correspond to a given bit in the message to be signed, and which one corresponds to that bit being a 0, and which one corresponds to that bit being a 1.
Then, when the time comes to sign the message, release the keys which correspond to the actual values of the bits in the message, and only those keys.
Note that the signature is 56 times as long as the message. This can be reduced to 7 times, by generating DES keys in sets of 256, only one of which will be released, corresponding to the actual value of a byte in the message.
Note also that the plaintext/ciphertext pairs of blocks are functioning as a one-way hash of the key, so this scheme could be implemented equally well if one generated a pair of random messages for each bit of the message to later be sent and signed, and released their hashes in advance along with the bit values to which they corresponded, and then released the actual messages corresponding to the actual bits of the message to be signed.
Because the only information released corresponds to the actual bits of the message being signed, it does not allow other messages to be forged. Thus, the large ensemble of keys or messages that are randomly calculated can only be used to sign one message.
If only authentication, rather than a signature, is desired, then a very much simplified procedure can be used. First, make available a random plaintext block, and its encrypted form, again under conditions where that is known to be authentic. Then, send the message to be authenticated, along with its hash, encrypted by the same key. Finally, reveal the key. This proves to the recipient that you have sent the message, although it now reveals enough data to forge messages. Thus, the reciept of the message to be acknowledged has to be securely confirmed before the key is revealed.
Signing an individual message is one form of authentication; for a user to demonstrate his identity in response to a challenge, with the assumption that the communications channel used at the time of the challenge will not be later interrupted with a spurious message, is a less ambitious form of authentication that can more easily be performed with only classical techniques.
A device like the one illustrated below in the form of a slide:
is more usually used in the form of a disk, with the vertical window showing ten numbers in the diagram in the form of ten individual holes staggered in a spiral.
In use, the holder of such a device would prove his posession of it by responding "536" to a challenge of VY2 or CP2, for example.
Such devices have been used as a means of copy protection for computer games, where the letters may be replaced with the names of items in the game, and the three-digit numbers by numbers of five or six digits. Devices of a somewhat similar nature were used during World War II to authenticate unencrypted communications, and apparently this was true of the conflicts in Korea and Vietnam as well.
Skip to Next Chapter
Table of Contents