# How Digital Signatures Work: Digitally Signing Messages

This article is part two in a series of articles on digital document signing in Java-based web applications. View part one in this series for information on basic concepts of digital signatures and PKI.

Public key cryptography gives a reliable method for digital signing and signature verification based on public/private key pairs. A person can sign a given digital message (file, document, e-mail, and so forth) with his private key. From a technical point of view, the **digital signing of a message** is performed in two steps:

*Click here for a larger image.*

### Step 1: Calculate the Message Digest

In the first step of the process, a **hash-value** of the message (often called the **message digest**) is calculated by applying some cryptographic **hashing algorithm** (for example, MD2, MD4, MD5, SHA1, or other). The calculated hash-value of a message is a sequence of bits, usually with a fixed length, extracted in some manner from the message.

All reliable algorithms for message digest calculation apply such mathematical transformations that when just a single bit from the input message is changed, a completely different digest is obtained. Due to this behavior, these algorithms are very steady in cryptanalytical attacks; in other words, it is almost impossible, from a given hash-value of a given message, to find the message itself. This impossibility for retrieval of the input message is pretty logical if we take into account that a hash-value of a message could have a hundred times smaller size than the input message. Actually, the computing resources needed to find a message by its digest are so huge that, practically, it is unfeasible to do it.

It is also interesting to know that, theoretically, it is possible for two entirely different messages to have the same hash-value calculated by some hashing algorithm, but the probability for this to happen is so small that in practice it is ignored.

### Step 2: Calculate the Digital Signature

In the second step of digitally signing a message, the information obtained in the first step hash-value of the message (the message digest) is encrypted with the private key of the person who signs the message and thus an encrypted hash-value, also called **digital signature**, is obtained. For this purpose, some mathematical cryptographic **encrypting algorithm** for calculating digital signatures from given message digest is used. The most often used algorithms are **RSA** (based on the number theory), **DSA** (based on the theory of the discrete logarithms), and **ECDSA** (based on the elliptic curves theory). Often, the obtained digital signature is attached to the message in a special format to be verified later if it is necessary.

### Verifying Digital Signatures

Digital signature technology allows the recipient of given signed message to verify its real origin and its integrity. The process of **digital signature verification** is purposed to ascertain if a given message has been signed by the private key that corresponds to a given public key. The digital signature verification cannot ascertain whether the given message has been signed by a given person. If we need to check whether some person has signed a given message, we need to obtain his real public key in some manner. This is possible either by getting the public key in a secure way (for example, on a floppy disk or CD) or with the help of the Public Key Infrastructure by means of a digital certificate. Without having a secure way to obtain the real public key of given person, we don't have a possibility to check whether the given message is really signed by this person.

From a technical point of view, the verification of a digital signature is performed in three steps:

*Click here for a larger image.*

### Step 1: Calculate the Current Hash-Value

In the first step, a hash-value of the signed message is calculated. For this calculation, the same hashing algorithm is used as was used during the signing process. The obtained hash-value is called the **current hash-value** because it is calculated from the current state of the message.

### Step 2: Calculate the Original Hash-Value

In the second step of the digital signature verification process, the digital signature is decrypted with the same encryption algorithm that was used during the signing process. The decryption is done by the public key that corresponds to the private key used during the signing of the message. As a result, we obtain the**original hash-value**that was calculated from the original message during the first step of the signing process (the original message digests).

### Step 3: Compare the Current and the Original Hash-Values

In the third step, we compare the current hash-value obtained in the first step with the original hash-value obtained in the second step. If the two values are identical, the verification if successful and proves that the message has been signed with the private key that corresponds to the public key used in the verification process. If the two values differ from onr another, this means that the digital signature is invalid and the verification is unsuccessful.

### Reasons for Invalid Signatures

There are three possible reasons for getting an invalid digital signature:

- If the digital signature is adulterated (it is not real) and is decrypted with the public key, the obtained original value will not be the original hash-value of the original message but some other value.
- If the message was changed (adulterated) after its signing, the current hash-value calculated from this adulterated message will differ from the original hash-value because the two different messages correspond to different hash-values.
- If the public key does not correspond to the private key used for signing, the original hash-value obtained by decrypting the signature with an incorrect key will not be the correct one.

If the verification fails, in spite of the cause, this proves only one thing: The signature that is being verified was not obtained by signing the message that is being verified with the private key that corresponds to the public key used for the verification. Unsuccessful verification does not always mean that an attempt for digital signature adulteration is detected. Sometimes, verification could fail because an invalid public key is used. Such a situation could be obtained when the message is not sent by the person who was expected to send it or when the signature verification system has an incorrect public key for this person. It is even possible for one person to own several different valid public keys along with valid certificates for each of them and the system attempted to verify a message received from this person with some of these public keys but not with the correct one (the key corresponding to the private key used for signing the message).

In order for such problems to be avoided, most often when a signed document is sent, the certificate of the signer is also sent along with this document and the corresponding digital signature. Thus, during the verification, the public key contained in the received certificate is used for signature verification; if the verification is successful, it is considered that the document is signed by the person who owns the certificate. Of course, it is always necessary that, when certificates are used, we should believe the certificate only if its validity is verified or the certificate is self-signed but is obtained from the sender in a secure way (not from the Internet).

My next article will introduce the class libraries for working with digital signatures and certificates on a Java 2 platform and gives a short description of the most important classes and interfaces from Java Cryptography Architecture (JCA) and Java Certification Path API that concern the use of digital signatures and certificates.

#### About the Author

Svetlin Nakov is part-time computer science lecturer in Sofia University,
Bulgaria. He has over 5 years of professional software engineering and
training experience and currently works as IT consultant in a leading
Bulgarian software company. His areas of expertise include Java and related
technologies, .NET Framework, network security, data structures and
algorithms, and programming code quality. More information on his research
background, skills and work experience is available from his home site
www.nakov.com.

*This article was originally published on October 16, 2003*