



Lesson#23

HASH FUNCTION AND MESSAGE DIGEST




There are two terms that you should note here – hash function
and message digest. Hash function is a oneway
mathematical function applied to a message. Result of the hash
function is unique to each message
called Message Digest. A message digest is a single large number
typically between 128 to 256 bits in length.
Thus, we can have up to 2256
different messages each having a unique
message digest associated with it. This
gives rise to almost an incalculable figure. We can safely
assume that each different message that can
possibly be typed would have a unique message digest on applying
a hash function. A hash function is said
to be one way because we cannot go back to the original text on
applying the hash function to a message
digest. Basically, the concept of hash function and message
digest is used to confirm the integrity of a
message. Following is the example of a hash function that can be
used in a code (no need to prepare it for
exam)
“char XORhash( char *key, int len)
{
char hash;
int i;
for (hash=0, i=0; i<len; ++i) hash=hash^key[i];
return (hash%101); /* 101 is prime */
}”
Following example shows how a text message is encrypted and
digitally signed using public key
cryptography:
First of all, the sender types a text message “Together, we
shall make Pakistan strong…”. A hash function is
applied on the message to get the message digest. Assume the
message digest comes to be “1967…” in this
case. The message is encrypted using public key of the receiver,
thus it becomes scrambled or confidential.
Then the sender adds his private key in the obtained message
digest to create his digital signatures. This
digitally singed message is received by the receiver, who
applies the pubic key of the sender to decrypt the
digital signature and reveal the message digest. Then the
receiver uses his private key to unscramble the
message itself, and applies the same hash function received from
the sender to get a message digest. The
receiver compares this message digest with the one sent by the
sender through digital signature. If both are
the same it ensures that the message has not been altered during
its transmission.
Process of Sending Messages Using Public Key Cryptography
Fig. 5 below shows the working of the digital signature
technology:
105
Original
Message
Scrambled
Message
Public Key receiver
IInnteterrnneett
Scrambled+Signed
Message
Original
Message
Private Key receiver
The Process of Sending Messages Using Public Key Cryptography
How Digital Signature Technology
Works?
Sender Receiver
Message Digest + Private Key of
sender Public Key sender
to reveal
Message Digest
Hash Hash
Fig. 5
Note that following steps are involved in the digital signature
process:
1. Hash function is applied to the original message in order to
find the message digest.
2. Public Key of the receiver is used to encrypt the message.
3. A digital signature is attached to the scrambled message by
signing the message digest with
Private Key of the sender.
4. The encrypted message, the digital signature and the hash
function are sent to the receiver.
5. Public Key of the sender is used by the receiver to reveal
the message digest and, thus, to
confirm identity/authenticity of the sender. In this regard, the
receiver finds the digital
certificate certifying the public key of the sender and checks
whether the digital signature can
be decrypted with the public key on the certificate and whether
or not this certificate had been
issued to the sender by a trustworthy certification authority.
6. Receiver uses his/her Private Key to decrypt the message.
Private Key is a secret key only
known to the user.
7. Receiver applies hash function to the received original
message and computes the message
digest. If this message digest matches with the one received
from the sender, it confirms that
the message has not been altered during transmission. This
ensures integrity of the message.
Note that a symmetric key can also be used for encrypting a
message instead of using the pair of public and
private keys. The advantage of using symmetric key is that since
symmetric algorithms are faster as
compared to asymmetric, therefore, the encryption of a message
with the symmetric key takes place quickly.
In order to send the symmetric key to the receiver, however, the
asymmetric cryptography has to be used.
PGP uses this system. See Fig. 6 below.
106
Original
Message
Scrambled
Message
Symmetric Key
IInnteterrnneett
Scrambled+Signed
Message
Original
Message
Symmetric Key
The Process of Sending Messages Using Public Key Cryptography
How Digital Signature Technology
Works?
Sender Receiver
Message Digest + Private Key of
sender Public Key sender
to reveal
Message Digest
Hash Hash
Fig. 6
Where only the authenticity is to be ensured and not the
integrity, then a name or a piece of text can be
chosen to create the digital signatures. In Fig. 7 below, the
word “Imran” has been used to create a digital
signature which can commonly be used for all different messages.
Note that a digital or electronic signature is believed to be
more reliable as compared to paper signatures
because it is not ordinarily possible to copy or forge an
electronic/digital signature. But, that is very much
possible in case of paper signatures.
Original
Message
Scrambled
Message
Symmetric Key
InInteterrnneett
Scrambled+Signed
Message
Symmetric Key
Imran + Private Key of sender Public Key sender
to reveal the
word Imran
Public Key Infrastructure (PKI)
A PKI is defines as a structured system that provides key
management facilities, storage and management
facilities of digital certificates and involves a certification
authority. PKI has its application in online
contracts, ebanking, electronic payment systems such as
electronic checks, credit card based systems,
electronic cash, micro payment systems etc.
Key Length
A cryptographic key is represented as a string of binary digits
– 0’s & 1’s inside a computer. If a key is 1 bit
in length it means two possible keys, that is, 0 and 1. If a key
is 2 bits in length it means four possible key
values, 00, 01, 10 and 11. A Key having 3 bits length means 8
possible values 
000,001,010,011,100,101,110,111. From this, one can derive a
general formula, that is, Number of keys =
2(number f bits)



