Business and technology have driven each other since recorded history. We see business changing to exploit the efficiencies afforded by new technologies. Also, we see technologies developed to satisfy the demands of new business practices. We see new technologies opening new business possibilities, and just as often we see new technologies decimating entire industries. We are at the beginning of yet another cycle of technology and business: this is the technology of cryptography enabling a revolutionary business paradigm, e-commerce. Digital signatures represent the key (yes, pun intended) technology for e-commerce. This paper addresses introduces technology of digital signatures and the role of digital signatures in e-commerce. This paper was written for the uninitiated (some would argue uncontaminated), so you should not be concerned if you can't spell "cryptography", yet alone understand it.

The Business Imperative

Real business progress is the result of finding and implementing the answers to the following "how do" questions:

• How do we improve productivity?

• How do we speed up our business?

• How do we better satisfy current customers?

• How do we reach new customers?

• How do we better reach our employees?

• How do we better manage our suppliers and partners?

People are looking to information technology, IT, as a key component of these answers. IT has been useful in automating business practices: from simple accounting to complete enterprise resource planning systems. Even though we have seen great progress in the last 20 years, the combination of the Internet and IT is likely to revolutionize the way we do business, as commerce becomes e-commerce. This change will affect consumer-to-merchant commerce, e-retailing, and business-to-business commerce, e-business.

There are two big problems that must be solved before e-commerce is a reality. First we must be able to identify and authenticate our remote business partner: with whom are you doing business? The second problem is that of repudiation: how can we make and enforce contracts when our sole method of communication is through electronic messages? The appropriate use of a cryptographic technique called Digital Signatures is the technology for solving the authentication and non-repudiation problem.

The Digital Signature

The concept of a Digital Signature mimics that of a handwritten signature. That is, the signer appends his or her signature to a document (e.g. a credit card sales draft) and the verifier verifies the signature by comparing the signature to a known signature (e.g. the signature on the back of the credit card). In this manner the verifier can authenticate the identity of the signer. In many cases, the verifier files the signed document in the eventuality that the signer disputes the fact that the document was signed by him or her. In such cases, the signed document is taken to an impartial third party (e.g. a court) and a determination is made whether the signature is that of the signer and whether the document has been changed since it had been signed. In this manner, the signed document prevents the signer from repudiating his or her involvement with the document. In this manner the signature provides non-repudiation of the document.

A handwritten signature is an ink scrawl appended to a document. It is important that the signature is in ink, so it cannot be changed later. It is also important for the document to be printed in indelible ink, so the document cannot be altered. Now that we know the features of handwritten signatures that make them useful in commerce, how can we provide similar features for electronic messages?

The Digital Signature has two phases: signing and verifying. Let us suppose that you wish to sign an electronic document, a file or e-mail message. You begin the signature phase by making the electronic message "indelible". Since electronic messages can be changed at will, we cannot directly use the concept of indelible ink. Rather, we will take a different approach, which does not prevent the message from being altered, but it does allow the verifier to detect if the electronic message has been altered. This approach uses the technology of message digests.

Message Digest

We begin our signature process by creating a message digest of the document. By the way, the message digest is also known as a secure hash. The message digest algorithm is a specially designed mathematical formula that produces a number (typically 40 or 50 digits) whose value is determined by the content of the message. A good message digest algorithm exhibits the following properties:

• Every message has a different message digest. Actually, a mathematician will tell you that the chance of two different messages having the same digest is about one out of 10⁵⁰, which is a very unlikely event.

• While it is easy to go from a message to the message's digest, it is impossible to start with a message digest and find a message that has that digest. Actually, a mathematician will correct this statement and tell you that you must try about 10⁵⁰ messages in order to find a message that has a specified message digest, which is practically impossible.

We pass our electronic document (a short e-mail, a novel, or a contract) though a message digest algorithm to produce the message digest. If we send the message digest as well as the electronic document to our partner, our partner can use the message digest to test if the message has been altered. Our partner simply passes the received message through his message digest algorithm and compares the resulting message digest with the message digest received from us. If the two digests are the same, our partner knows that the received message has the same digest and the transmitted message, so the message has not been altered.

This simple scheme works, but it is not secure. This is because any sophisticated cheat can change the message, recomputed the message digest, and append the new message digest to the altered message. Our partner will be deceived, because our partner's message digest will match the message digest computed by the cheat: our partner will not detect the adulteration of the message. Therefore, a simple message digest is not sufficient to protect against malicious alteration of the message.

Public Key Cryptography

In order to prevent a cheat from modifying the message and recomputing the message digest, we must process the message digest in a way the cheat cannot repeat. There are many ways of doing this but the most promising is to secure the message digest with a public key cryptographic algorithm. As with all public key cryptographic systems, each user of the system has two cryptographic keys. One key is the user's private key and the other is the user's public key. Each of these keys is about 20 times longer than your social security number, so these are very long numbers. There is a sophisticated mathematical relationship between the public and private keys of each key pair. As the names imply, the private key is known only to the key's owner and the public key is known to everyone. The interesting property of public key cryptosystems is that the owner can perform mathematical operations using his private key and the partners can verify those mathematical operations using the public key. Furthermore, it is impossible to compute the private key from the public key, so even though the public key is known by all, the private key remains securely with the key's owner.

Suppose we generate a digital signature by perform a public key operation (typically "encryption") on the message digest, before we append the message digest to the message. Our partners can use our public key to verify two facts:

• the digital signature was produced using our private key

• the digital signature was produced using the message digest of the received message

This means that our partners can check the integrity of the message (Does the received message produce the same message digest that was used to generate the digital signature?). Our partners can also check if the digital signature was produced by our private key (Did we sign the message?). Note that this scheme prevents a cheat from changing the message, because the cheat does not have our private key and can therefore not generate a new signature on the changed message digest.

These digital signatures support non-repudiation if we make the assumption that the owner of the key, and only the owner of the key, has access to the private key. Consider the following scenario where you are a supplier of custom products. Suppose you receive a purchase order for a million custom widgets. This purchase order is an electronic document that includes your customer's digital signature. You verify the signature by using your customer's public key and find that the electronic message was indeed signed by your customer and it had not been altered. You forge ahead and build the widgets and notify the customer that you are ready to ship. To your great surprise, the customer replies that he had never placed the order and will not accept the widgets. What do you do? You take the customer to court or to binding arbitration. You are armed with a digitally signed document. You can prove to the judge or arbitrator that the signature on the document is your customer's and the document clearly orders the one million widgets. Most states have enacted electronic commerce legislation that makes this digital signature as binding as a handwritten signature. Furthermore, the Federal Government is in the process of enacting national digital signature laws. Therefore, the judge is armed with the technology and law to rule in your favor. Unfortunately, your customer declares bankruptcy, and you are stuck with a million trinkets. See digital signatures cannot address all commerce pitfalls.

Smart Cards

There are still a couple of open questions. First is where do these keys live? They are obviously too big to remember and even if you could remember your private key, you could not manually perform the cryptographic operations -- these require a computer. Here are a few options:

• Store the keys in an encrypted file on your computer. The keys are typically decrypted for use by a pass phrase that the key's owner and only the owner knows. Once the keys are decrypted by the pass phrase the private key can be used to sign electronic documents with software that runs on the computer.

• Store the keys on a smart card. This is a credit-card sized device that includes a small, embedded computer. The private keys are securely stored in the computer's memory and never leave the smart card. The smart card communicates with the rest of the world through a smart card reader, which is usually connected to a personal computer. The computer on the smart card actually performs the cryptographic operations to produce the digital signatures.

• Store the keys on a token. The token is a portable device that is smaller than your thumb. It contains a computer and stores the private keys (similar to the smart card). The token usually plugs into a USB port on a personal computer. The computer in the token performs the digital signatures.

Therefore, there are many options for storing keys and performing digital signatures. Today, most web browsers have the ability to perform digital signatures in software, with the private keys on the PC's hard drive.

Public Key Infrastructures

Another good question is how do we obtain our partner's public key. Since the partner's identity is closely tied to the public key, we must prevent others from masquerading as our partner and giving us a phony public key. If a masquerader fools us into using the wrong public key, they can assume the identity of our partner for all e-commerce exchanges. This poses a significant risk. Therefore, we need a trusted way of distributing public key values.

There are at least two general approaches for distributing public keys. The simplest is for business partners to exchange keys similarly to the ways partners exchange billing and shipping information. The value of the partner's public key simply becomes another field in the partner's account record, joining such information as billing address, credit limit, payment history and the like. This method is sometimes referred to as the account authority, where the partners use the account record as the authority for the public key. The problem with the account authority is that there is no codified mechanism for exchanging public keys. The specifics of and security of these key exchanges is really governed by the peculiarities of the business relationship.

The second, and more popular, method of public key distribution is through a Certificate Authority, or CA. If we momentarily return to the example of handwritten signature, we noted that many merchants rely on the signer's driver license to bind the signature to the signer's identity. In this way, the merchant is trusting the state department of motor vehicles to vouch for "Joe Smith": this is Joe's name, birth date photograph, and signature. The CA plays a similar role as that department of motor vehicles. The CA produces certificates (analogous to driver licenses) that bind the user's identity to his or her public key. This certificate can be trusted since the certificate is signed by the CA's private key. In this manner, the CA's signature serves a similar role to the seal of authenticity (typically a hologram) on a driver's license.

The idea behind the CA is the following. I obtain a certificate from a CA that I trust and my partners trust. I send my certificate to any partner. They verify the certificate by verifying the CA's signature on the certificate. Once the partner is satisfied with the authenticity of the certificate, the partner now has my identity and my public key.

The CA concept is plagued by a couple of "details". First, what entity serves the role of the CA? The CA must have my trust and the trust of my partners. It is not clear who can play this role. The second problem is the revocation of certificates. In the driver's license analogy, a license is revoked by the state physically repossessing the physical license. Unfortunately, the digital certificate is an electronic document, so it is easily copied. Therefore, repossessing is not an option. Rather, the CA is forced to publish a certificate revocation list. This is a list of certificates for which the CA no longer honors. This maintenance and distribution of this list presents a significant implementation challenge.

Summary

Electronic commerce demands the safe guards that have evolved over the centuries for protecting classic commerce. Foremost, is the ability to authenticate partners in commerce, ensure the integrity of documents, and provide non-repudiation for contracts and other documents of commitment. Fortunately, there is a body of cryptographic tools that support these features in cyberspace. Chief among these is the technology of digital signatures.

About the Author:

Chuck Williams is a Fellow of The Business Forum Association.  He is the Chief Scientist at Cylink Corporation in Santa Clara California.  Cylink is the leading supplier of network security solutions.  Dr. Charles Williams has 10 years of experience in information security scientific development, covering the emerging technology areas of network security, key recovery mechanisms, cryptographic algorithms, and public key infrastructures. He invented and has led for many years the development of Cylink's frame and IP security products.  He also invented the first SNMP-based security management solution.

Prior to joining Cylink Corporation, Chuck worked for more than 10 years in the field of telephone and data networks, including pioneering work in Asynchronous Transfer Mode networks.  He has served on the faculty of the Electrical Engineering department at Stanford University and went on to develop and teach a course on Broadband Networking for the University of California Berkeley Extension program. Chuck is also a senior member of IEEE and a member of Eta Kappa Nu and Tau Beta Pi.