Published on November 7, 2007

The digital signature

In the situation when there is the need to send, through an insecure environment (internet), a message that is not secret (a public document), among two entities A (emitter) and B (receiver), its encryption is not necessary.

There is the possibility in this situation, because of different reasons, that a third entity C to want to change the message sent from A to B, after it was sent from A and before to be received by B.

This technique where the messages are intercepted and modified without either A or B to know that the link between them is compromised is called man-in-the-middle attack. Doing so, from B point of view, C acts as if he would be A.

There is also the possibility that at a later time (after the emitter transmitted the public document) the emitter not to recognize that he sent the message.

To prevent this kind of situations the digital signature can be used.

A signature must be:
1. authentic – to prove that it is the signature of the author of the document;
2. unforgeable – to prove that the signature was produced by the declared signer and not by somebody else;
3. not reusable – the signature of one document can’t be moved onto another document;
4. unalterable – once the document is signed, the document can’t be modified;
5. non repudiable – in case when A does not recognize that he signed a message, a judge must be able to solve the dispute between A and B;

The digital signature solves both the problem of emitter authentication and the problem of data authentication.

Asymmetric algorithms based on public keys allow a simple implementation of digital signatures.

Figure 1As presented in Figure 1, the method based on asymmetric algorithms uses in the signing phase the secret key of the emitter, and in verification phase the public key of the emitter.

Doing so, the signature of the message can be produced only by the authentic emitter (the only one that knows the secret key) but can be verified by any person that knows the public key of the emitter.

In practical implementation, asymmetric-key algorithms are very slow and inefficient to make digital signature for a big document. To gain time, the digital signature process uses a hash function, which realize a summary (hash value) for the document. A hash value (also called digest) is a short representation of a longer message or document where from the hash value was computed.

The basic requirements for a hash function (H) used in cryptology are:
1. input message can have any length;
2. output message has a fixed length, usually much smaller than the document;
3. H(x) is relatively easy to compute for any input message x;
4. H(x) is a one way function;
5. H(x) does not have collisions;

A hash function, H, is said to be one way if for a given output result ‘h’ it is impossible to find out the input ‘x’ (H(x) = h); from the hash value it is impossible to obtain the initial document.

A hash function is strong from the collisions point of view, if for any x and y input messages there is a very small chance to obtain the same output (H(x) = H(y)); for two different documents it is impossible to obtain the same hash value.

Because of these properties the digest (hash) of a document can be imagined as a fingerprint of that document.

The digital signature process using hash functions is presented in Figure 2:
1. Using a hash function is built the fingerprint of the document (hash).
2. The fingerprint of the document is encrypted with the private key of the emitter; the encrypted fingerprint is the signature of the document;
3. The document and the signature are sent to the receiver;
4. The receiver verify the signature in 3 steps:
4.1. It is created a new fingerprint (hash) of the received document;
4.2. The received signature of the document is decrypted with the public key of the emitter;
4.3. The two fingerprints are compared. If they are equals the signature is valid;

Figure2The digital signature performed as above satisfies the conditions specified at the beginning of the document.

The signature is:
1. authentic – because it can be verified only with the public key of the emitter;
2. unforgeable – because only the emitter have his own secret key;
3. not reusable – because it is calculated from the document;
4. unalterable – because any change in the document leads to a fail at the verification phase;
5. non repudiable – because the receiver of the document does not need the assistance of the emitter to verify the signature, as long as he does have the emitter’s public key;

Now, if C (the interceptor) would change the text in the document M, in the verification phase, the hash of the changed M (step 4.1.) would be different than the hash of the initial document M (step 4.3.). The receiver who would read the modified document M could notice the modification, because he could see that the signature from the emitter contains another hash value than the one he computes from the changed document M.

Also, the interceptor C can’t modify the signature with the hash of the changed document because he does not have the secret key of the emitter. If he would use another secret key to make the signature, the receiver would not be able to decrypt the signature with the public key of the emitter (step 4.2.) and so would realize that the message was changed.

In case when both the encryption and the signing of one document are desired the emitter first make the signing of the document with his private key then the encryption with the receiver’s public key.

Many countries have legislation regarding the digital signature, so that the signature that follows the legislation can be used with legal implications (for example in Romania there is the law about the electronic signature no. 455/2001).

Examples of algorithms used by existing systems that are performing digital signatures are:
• For the hash of the document: MD2 (Message Digest 2), MD5, SHA1 (Secure Hash Algorithm)
• For signature: RSA (Rivest,Shamir, Adleman), El Gamal, DSA (Digital Signature Algorithm).