Digital Signatures

Question

Define the term Digital Signatures?

Answer 1

If Alice is sending a message to Bob and all that Bob cares about is having assurance that it came from Alice (he doesn't care about confidentiality) public key technology can be used for authentication. Al ice must encrypt the message using her private key, i.e., C = E(PRA, P). Then when the message is decrypted successfully with Alice's public key, PUA , Bob will know that it must have come from Alice since Alice is the only party that has PRA. (If confidentiality must be maintained the cipher text can be encrypted with Bob's public key, PUB.).

While this approach works fine theoretically, we have not taken into account that public key encryption is very slow and not viable for long messages. Hence we cannot afford to encrypt the entire message, P. We need a solution that allows us to encrypt something significantly smaller than P. Fortunately there is a class of functions can be used to give us something small to encrypt-hashing functions.

A Hash function is essentially a one-way "encryption" algorithm. It more or less randomizes the input into a much shorter fixed-length string. Consequently, there is no inverse, because some inputs map to the same output. This is called a homomorphic function, many-to-one. Encryption algorithms are isomorphic functions, each input yields a unique output, one-to-one. (Hashes were originally used to improve searching. Rather than compare lots of variable length strings for a match, the string is "hashed" into a fixed length number and used to index an array, storing all entries with the same hash result in the same row. Then the strings are searched one by one. One still has to compare strings but now it is only necessary to compare a few, rather than on average half of them. A much more efficient process.) Hashing functions have a property that makes it computationally infeasible to determine from the hash what the input to the function was, or other
valid inputs that produce the same result.

The process is to (1) pass the plaintext message through the hash function producing what is called a message digest, (2) encrypt the message digest using the sender's private key producing what is called the digital signature, and (3) send the plaintext message and the digital signature. The following illustrates how the message digest is calculated and sent with the plaintext message. The plaintext message and digital signature are transmitted to Bob. Bob then authenticates the message by applying the following algorithm:

Apply the known hashing algorithm to the received plaintext message to calculate a message digest from the received message, call it MDR.

Decrypt the digital signature using Alice's public key, PUA, yielding the transmitted message digest, MDT

If MDR = MDT we know that the message came from Alice