Cryptography is the branch of applied mathematics concerned with protecting information. Confidentiality is the protection of data against unauthorized access or disclosure through application of functions that transform messages into seemingly unintelligible forms and back again. These processes are called encryption and decryption. One kind of cryptography that can provide confidentiality, authentication, and integrity is symmetric key cryptography, in which an algorithm makes use of a single key used to encrypt data. The same key is also used to decrypt or return the encrypted data into its original form. This one key, called the symmetric key, is very efficient in terms of processing speed and using minimal computing resources, but is limited in the sense that it is difficult to exchange the key securely without introducing public key cryptography, and because both the sender and the receiver of a message share the same symmetric key, the authentication and integrity is not provable to a third party who does not also hold the key—thus, symmetric cryptography cannot provide the additional security service called non-repudiation.
Public key cryptography is an attempt to solve these particular shortcomings of symmetric key cryptography (Ferguson et al., 2010). Public key cryptography employs an algorithm using two different but mathematically related keys, one for creating a digital signature or decrypting data, and another key for verifying a digital signature or encrypting data. Computer equipment and software utilizing such key pairs are often collectively termed an asymmetric cryptosystem. The complementary keys of an asymmetric cryptosystem for PKI technology are arbitrarily termed the private key, which is known only to the holder, and the public key, which is more widely known. If many people need the public key for various PKI applications, the public key must be available or distributed to all of them, perhaps by publication in an online repository or directory where it is easily accessible. Although the keys of the pair are mathematically related, if the asymmetric cryptosystem has been designed and implemented securely it is computationally infeasible to derive the private key from knowledge of the public key. Thus, although many people may know the public key of a given holder, they cannot discover that holder’s private key. This is sometimes referred to as the principle of irreversibility.
Another fundamental process, termed a hash function, is used in PKI technologies. A hash function is an algorithm that creates from a message a digital representation or fingerprint in the form of a hash value or hash result of a fixed length (Spillman, 2005). The hash result is usually much smaller than the message, but nevertheless substantially unique to it. Any change to the message produces a different hash result when the same hash function is used; the hash is unique to a given message for all practical purposes. In the case of a secure hash function, sometimes termed a one-way hash function, it is computationally infeasible to derive the original message from knowledge of its hash value. Hash functions therefore enable the PKI application software to operate on smaller and more predictable amounts of data, while still providing robust correlation to the original message content.
Digital signatures are created and verified by public key cryptography. The signer has a key pair consisting of a private key and a public key. The signer holds a private key known only to the signer, which the signer uses to create the digital signature. The signer also has a public key, which is used by a relying party to verify the digital signature. Relying parties must obtain the signer’s public key in order to verify the signer’s digital signature. As applied here, the principle of irreversibility means that it is computationally infeasible to discover the signer’s private key from knowledge of the public key and use it to forge digital signatures. The digital signature cannot be forged unless the signer loses control of the private key by divulging it or losing the media or device (smart card) in which it is contained, or an attacker is, through the application of massive computing resources-performing cryptographic analysis, able to derive the private key from the public key.
This impossibility for retrieval of the input message is pretty logical if we take into account that a message’s hash value 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 infeasible 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 (see also Stallings, 2006). From a technical point of view, the digital signing of a message is performed in two steps, and as depicted in Figure 1.
Calculating 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 (e.g., 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 mathematical transformations such that when just a single bit from the input message is changed, a completely different digest is obtained.
Calculating the Digital Signature
In the second step of digitally signing a message, the information obtained in the message’s first-step hash value (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. 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). Typically, a digital signature (the transformed hash result of the message) is attached to its message and stored or transmitted with its message. It may also be sent or stored as a separate data element, so long as it maintains a reliable association with its message.
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 designed 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 (e.g., 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 are not able 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 as depicted in Figure 2.
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 is 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 one 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. 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 that one person owned several different valid public keys 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.