What are Digital Signatures? Compute and Verify a Digital Signature Using Java

Digital Signature is one of the most widely misunderstood terms in the area of computer security. People often either confuse it with scanning a manually signed paper, or just know that somehow something happens mysteriously and we can obtain a digital signature! Let us understand what digital signatures are, and how to work with them in Java; in the course of this article.

In one of our earlier articles, we have seen the concept of message digests, also called as hashes. A message digest (or hash) is a
fixed-length value obtained on some message. This message digest value is always guaranteed to be the same for the same message. If we change
the message even by a single bit, the message digest would change. Hence, message digests can be used to ascertain the fact that a message has not been changed or tampered with, since it was created. However, it suffers from two problems:

1. An attacker can modify both the original message and the computed message digest. Therefore, the receiver has no way of knowing
   if this is the case, or indeed the original message and the message digest have been the same as what the sender had initially sent.
2. A message digest does not prove if the message was indeed sent by the sender, or by someone else. After all, a message digest algorithm can be run by anyone, even by an attacker. So, if a bank receives an instruction to transfer USD 1,000 from Account A to Account B, the bank has no way of knowing if this instruction is genuine, or fake. Just because the payment instruction accompanies with a message digest does not prove (or disprove) this. All it says is whether a message was changed since it was first created.

More specifically, we want to deal with two problems. The first one is to ensure message integrity (check if the message has been tampered with) and the second one is to ensure style=”font-weight: bold;”>non-repudiation
(ensure that the sender of the message cannot refuse having sent it).
Using a message digest as the base, how can we achieve this? Well, we cannot. And this is where a digital signature steps in. A digital signature can be used to guarantee, beyond doubt, the validity of message integrity and that of non-repudiation. Let us understand this now. For this purpose, let us quickly review the message digest computation process, shown in the diagram below.

Figure 1 –
Message digest computation process

We know that the main problem in this scheme is that the attacker can easily alter the original message and rerun the same message digest algorithm on the altered message. This can lead to the modified message digest, thus making it difficult for us to catch the attacker. How can we prevent this? If we can modify the above process by hiding the message digest, or if not hiding it, making it almost impossible to change it, we can fulfill our objective. The simplest way in which this can be done is to encrypt it. This is shown in the diagram below.

Figure 2 –
Message Digest Encryption

Therefore, what we are saying now is that the message digest must be encrypted before it is sent to the receiver. The receiver would simply reject the message if a message digest, which is not encrypted, accompanies it. Of course, the whole point here is that:

1. The genuine sender should be somehow able to perform this encryption operation, and the genuine receiver should be able to verify this encryption operation; but
2. An attacker should not be able to perform this encryption operation

Note that the attacker would still be able to perform the operation of computing the message digest. But the attacker must not be able to encrypt the message digest thus obtained. How can this be possible? Very clearly, we must have a scheme whereby only the genuine sender and the genuine receiver share some secret. This secret can be used as the key for encrypting the message digest. However, in real life situation, sharing secrets beforehand is not always possible.
Imagine, for example, that we are ordering books online in India using a site hosted in America. The bookseller and we have no prior relationship or agreement. How can we share secrets?

This is where the concept of public key cryptography (also called as asymmetric key cryptography) comes into picture. The idea is this: the sender and only the sender knows something, which can be used
to encrypt the message digest to produce the output as shown in the earlier diagram. The receiver and anyone else knows something else, which is related to the sender’s secret in such a way that only this something else can be used to decrypt the message digest successfully. If we understand this, we can now replace something with the sender’s private key, something else with the sender’s public key, and the output with digital signature. Thus:

1. On the sending side, the sender would encrypt the message digest with her private key. The sender must secretly hold the private key at all times.
2. The output of this process is called as the digital signature for this particular message.
3. The sender sends the original message and the digital signature to the receiver.
4. The receiver verifies (decrypts) the digital signature using the sender’s public key, which is available very openly. This should give the receiver a message digest, say MD-1.
5. The receiver also computes a fresh message digest on the original message, say MD-2.
6. If MD-1 = MD-2, we achieve both message integrity (message has not been tampered with, because the attacker does not know the sender’s private key) and non-repudiation (the message is proven to be sent by the sender, since only she knows the private key corresponding to this public key).

This is shown in Figure 3.

Figure 3 – Digital Signature – Process at Sender’s and Receiver’s End

Following is a simple program in Java, which performs digital signature and then allows us to verify it as well. In real life, of course, the program that verifies the signature would be different from the one that creates it in the first place. Also, the private and public keys would be predefined and not generated at run time, as we are doing here.

—

Atul Kahate writes about Security in this monthly column on IndicThreads.com. Atul is the author of 13 books including Cryptography and Network Security“.

He is currently a Project Manager at i-flex solutions limited, Pune, India. Atul can be reached at (akahate at gmail dot com)

Related

• AJAX Security Threats and Performance Challenges
• Returning Arrays or Objects – A Security Problem in Java
• IndicThreads.com Conference On Java Technology 2007, Pune – India