Sunday, April 27, 2008

Digital Signature

by: Wale Wahab

A digital signature is a data item, which accompanies a digitally encoded message, and which can be used to ascertain both the originator of the message and the fact that the message has not been modified since it left the originator. It is a form of authentication method which is used to authenticate the identity of the sender by convincing the recipient of a document that the person to whom the signature belongs actually signed it. An electronic document in other words can be described as any instrument that is created or stored on a computer. These include electronic mail (e-mail), letters, memos, contracts and images.

Digital signatures are mathematically tied to the document they are intended to authenticate. The most widely used type of digital signature relies on public/private key encryption. A public / private key encryption system involves two mathematically related keys that are like large passwords for each user. The private key, known only by the “signer”, can encrypt a message that only their public key can decrypt. Once the private/public keys are generated using a valid certificate authority, they remain associated with the person who generates the two keys.

The certificate authority is a trusted entity that issues certificates to end entities and other Certificate Authorities. Another important thing that Certificate Authority does is to issue Certificate Revocation Lists (CRLs) periodically and post certificates and CRLs to a database or repository.

The overall process is illustrated in the figure below:

Note: The text editor refused to accept the diagram. To view the diagram, click the website link in the resource box of the author and click on the recent articles.

System A performs a sign operation that uses A’s private key to generate the signature. System B performs a verify operation that uses system A’s public key and that allows system B to be sure that a received message originated from system A and that the contents were not modified since it left system A.

In some respects, a digital signature is similar to an integrity check value (check digit). However, there is one major difference. A digital signature must be able to support non-repudiation, that is, a recipient of a message must be able to use the digital signature to convince a third party as to the identity of the originator. A digital signature may need to be used as the basis for resolving a dispute between the originator and recipient of a message, such as a check (cheque), or business document.

RSA Digital Signature

This is a simplistic digital signature technique (named after its creators – Ronald Rivest, Adi Shamir and Len Adleman). It is one of the most popular public – key algorithms. It can be used for both encryption and digital signature. The originator of a message generates an encrypted version of the message, using RSA in authentication mode (that is, the encryption key is the private key of the originator). This encrypted version of the message is sent attached to a copy of the plaintext message. The recipient’s system, (which needs to know the corresponding decryption key - the public key of the originator), decrypts the encrypted version of the message content and compares it with the plaintext version. If the two are the same, the recipient can be assured that the originating system possessed the encryption key, and that the message contents were not changed en route.

The above scheme has some problems in terms of processing and communications overhead costs. Encryption and decryption have to be applied to the entire message contents and the volume of data sent is at least double the original message size. To overcome this problem, a hash function, which is a one-way function that maps values from a large domain into a comparatively small range, is used to generate from the content of the message to be signed, a fixed – length data item known as a message digest. The digest has the property that, in general, any change to the message will result in a different digest.

With this scheme, the originating system applies the hash function to obtain the digest, then RSA encrypts the digest to give the signature which is transmitted with the message, upon receiving the message, the recipient’s system re-computes the digest, and also RSA decrypts the signature. It then compares these two values. If they match, the recipient is assured that the originator knew the encryption key and that the message contents were not changed en route. There are several other techniques for providing digital signature