Digital Signatures

When classified information is sent electronically from one individual to another, some form of encryption must be used to protect the information from prying eyes. Because internet technology relies on the transmission of data through the public domain, this encryption is absolutely essential to preserving the security of electronically-transmitted information. Public key encryption, which was first developed in the 1970s, has gradually come to dominate the "cryptology market" because of its innate advantages over private-key methods of encrypting data; unlike its counterpart, public key encryption does not require that individuals share a secret key.

Although public key encryption algorithms such as RSA have achieved universal acceptance in the modern cryptology arena, they remain vulnerable to many potential security threats. For example, because public key encryption involves the "receiver" providing a public key to any "senders" who wish to send him confidential information (the receiver uses a different, private key to decrypt the data), it is entirely possible for a devious individual to send an encrypted message to the receiver that appears to have been sent from someone else; after all, the public key used to encrypt this message is fully available to everyone. In other words, public encryption systems such as RSA do not intrinsically protect against false sender identification.

In order to avoid this potential pitfall, a "digital signature" is used to ensure that the receiver indeed receives the information from whoever he thinks sent it. In its simplest implementation, making a "digital signature" involves adding one's name along with a timestamp to the document one is sending, encrypting this document (or at least the "signature" part) with one's own private key, encrypting it again with the receiver's public key, and then sending it. The receiver can then decrypt the document by first applying his own private key to it, and then applying the sender's public key to the result. Because the receiver uses the sender's public key to decrypt the "signature," he can be certain that the sender's private key was used to encrypt it, and thus is assured that the person who sent the document was indeed the expected sender.

Unfortunately, while this technique for digital signing is theoretically feasible, the public-key algorithms that it depends on are generally too inefficient and require too much computation to be used in practical implementations. To save time, digital signature protocols therefore utilize a "one-way hashing function" to generate a sender's signature for a given document. The implementation of this technique is fairly simple: the sender first produces a "one-way hash" of the document he wishes to send and encrypts this hash with his private key. The sender then encrypts the document itself with the receiver's public key and sends the document, along with the "signed" hash, to the receiver. The receiver decrypts the document (with his private key) and applies the same one-way hash to it. Finally, he applies the sender's public key to the "signed" hash (the hash that was sent to him). The signature is validated if the hash that the receiver generated from the document matches the decrypted "signed" hash the he received from the sender.

This one-way hashing technique for generating digital signatures has several advantages over the simpler signing technique described earlier. One important feature of one-way hashing is that it enables the sender to "sign" only a small piece of the original document, thus greatly reducing the time needed to "prepare" (encrypt) the document for sending. Another benefit of this protocol is that its digital signatures can be kept separate from their originating documents. This feature allows us to efficiently process multiple signatures of a single document. For example, if multiple users are to "sign" a document, the former method of digital signing requires that one user sign the document, and subsequent users sign the document "on top" of preceding signatures. Unfortunately, such a system requires one to verify all of the signatures if he wants to verify the first signature. With a one-way hash signing system, each user simply signs a hash of the document, and each of these signatures can be individually verified.