Digital Signatures

Signatures play an important role in proving ownership. The key properties of signatures are described below:

The signature is not reusable. The signature is part of the document or message that is being signed. A signature cannot just be moved to another document.
The signature cannot be changed once a document is signed.
The signature is proof that the signer signed the document. No-one else can forge it.
The signature is authentic. It is done deliberately by the signer.
Once a document is signed, the signer cannot claim that they did not sign it.

These properties are true whenever anyone signs a document in the real world. The same properties are present when a digital signature is applied to a document. The digital signature is authentic, cannot be changed, cannot be reused, and acts as proof that the signer signed it.

Signatures are used in public key cryptography. The protocol which is used to sign documents is described below.

The sender encrypts the document with their private key. This signs the document.
The sender sends the message to the receiver.
The receiver looks up the sender's public key and decrypts the message.

The properties of a signature are all satisfied.

The signature is not reusable. Since the message was encrypted with a private key to form a signature, the actual data is directly related to the signature. The signature is formed based on the encryption of the specific data that was sent, therefore, the same signature cannot be generated with a different set of data.
The signature cannot be changed. If someone attempted to change the signature, the decrypted data would not match the original data that the sender had.
No-one else can forge this signature because it was generated with the sender's private key. No-one else has the value of this key.
It must be an authentic signature since the public key decrypts the data. The public key decrypts the data encrypted with the private key, therefore, the owner of the public / private pair of keys must have meant to sign it.
It is impossible for the sender to claim he didn't sign it! His public key decrypts the message.

While the above example demonstrates a signature, it does have a potential problem. The receiver can keep a copy of the signed document and use it multiple times since the public key will always verify the signature. This could be an issue if the encrypted document is a cash withdrawal request. The receiver could forward the signed document to a bank more than once and the cash could be removed from the account on two different occasions. This is known as the replay attack.

The best method to guard against this problem is to use a timestamp. A timestamp gives the date and time that the message is sent. The timestamp can be part of the message that is encrypted. Therefore, the first time a receiver gets the message, it can verify its authenticity with the public key and record the date and time. If it gets the same message again, it will use the public key to verify the signature. But then it can check the date and time to make sure it has changed. If the date and time is identical to the last transaction, the receiver can report an error. A hacker cannot easily change the date and time. Since the date and time are part of the encrypted data, the date and time cannot change unless the signature changes. The signature cannot be changed by a hacker because he will not know the value of the private key. Therefore, the replay attack has been guarded against.

Another problem encountered with digital signatures is the time that it takes to sign a document. The RSA algorithm is cumbersome and it could take a very long time to sign a message. One solution to this problem is to use a one way function. A one way function is a mathematical function with the following properties:

Given x, it is relatively easy to calculate the one way function, f(x).
Given f(x), it is very hard to determine x. "Very Hard" means that it may take computers many years to calculate x.
f(x) should be collision free. This means that just about any x should result in a unique f(x).

A simple way of thinking about one way functions is to pretend you are in the first grade. You have learned multiplication, but have not learned division yet. In addition, you are very smart. Therefore, you are given:

f(x) = 2x

x = 5

Since you know your multiplication tables, you know that f(x) will equal 10. But, let's assume you know the following:

f(x) = 30

f(x) = 2x

Since you don't know how to divide yet, it is hard for you to determine the value of x given these numbers. You'll have to guess values of x and multiply them by two until you get thirty. From your perspective, this is a one way function.

A common one way function is a hash or message digest. A hash function takes a variable length message and coverts it to a fixed length message.

An example can best illustrate this idea. Consider a sender that has three messages that it wants to send to a receiver. The sender's messages are:

Hello.
How are you today?
Who won the game last night?

The number of letters, spaces, and punctuation marks in each message is:

These messages have variable length since the number of letters, spaces, and punctuation marks is different.

A hash is a one way function that converts each message to a fixed length. Let's assume that the hash takes the first two letters of each phrase. Therefore, the hash of each message is:

Clearly, each message now has a fixed length of 2 characters. Notice that this is a one way function. It is very hard to determine the original message from this hash.

Obviously, hashes use more complex mathematical functions than the illustration above. It needs to use these functions be collision free. In the above example, it would be possible to generate the same hash for two different messages. For example, consider the following two phrases:

How are you?
How is it going?

Both phrases would have the hash Ho. This is not good. Therefore, more intense mathematical functions are needed. It is very important that each message generate a unique hash. In addition, longer fixed message lengths are used. If a 160 bit hash is used, the odds of another message having the same has is one in 2¹⁶⁰.

Therefore, a hash can be used to speed up the digital signature process. The hash of the message can be calculated and then signed. The signature time will be shortened since a smaller, fixed length message will be signed.

The public key cryptography protocol that can be used to implement a hash and signature is described below:

The sender produces a hash of the message it is going to send.
The sender encrypts the hash with the private key.
The sender sends the message and encrypted hash to the receiver.
The receiver calculates the hash of the message.
The receiver decrypts the hash that came from the sender. The decryption is done using the sender's public key.
If the hash calculated in step 4 equals the hash calculated in step 5, then the signature is valid.

The message cannot be tampered with since the hash is a one way function. Tampering with the message will result in the hash generated in step 4 differing from the hash decrypted in step 5. Each hash corresponds to a unique message.

The hash is encrypted with a private key to prevent a hacker from changing the message and changing the corresponding hash. The hacker does not have the private key, so he can only change the message and calculate the hash. He can't encrypt it properly. Therefore, the receiver would detect an error.

Encrypting the hash is quicker than encrypting the entire message. The hash is much smaller than the original message. Therefore, this approach leads to a quicker, secure mechanism of passing data from a sender to a receiver.

For more information:

Definition of Digital Signature is available at http://whatis.com/digitasi.htm.
"Digital Signatures" by David Cyganski, John A. Orr and Richard F. Vaz is available at http://www.ece.wpi.edu/infoeng/textbook/node215.html. January 26, 1998.