Digital Signature and

Cryptographic Hash Function

Dr. Risala T Khan
Professor
IIT, JU
 Topics to be Discussed
❖ Digital Signature
❑ To be familiar with the general idea behind
digital signature
❑ To define security services provided by a
digital signature
❑ To describe some applications of digital
signatures
❖ Cryptographic Hash Function
❑ To introduce general ideas behind hash
function
❑ To discuss the usage and application of hash
function
❑ To know the desirable properties of a hash
Slide-2 function
 What is Digital Signature?
Digital signature is a digital code that can be attached
to an electronically transmitted message that uniquely
identifies the sender and provides the integrity of the
message.
❖ It was first proposed in 1976 by Whitfield Diffie of Stanford
University.
Typically the signature is formed by taking the hash of
the message (called message digest) and encrypting
the digest with the creator’s private key.
❖ The encrypted message digest is known as a digital signature.
❖ The signature is then added at the end of each message that is to
be sent to the recipient.
❖ The recipient decrypts the signature using sender’s public key and
verifies that the message digest is correct and the message has
come from the genuine sender. If the transmitted message is
changed, the digital signature is invalidated.
Like a written signature on a document, the purpose of
a digital signature is to guarantee that the individual
sending the message really is who he or she claims to
Slide-3 be.
 Process of Creating Digital Signature
The process of creating a digital signature is outlined below:
1. Sender generates a message.
2. He/she then creates a “digest” of the message using cryptographic
hash function.

Sender Site
3. Sender encrypts the message digest with his/her private key for
authentication. This encrypted message digest is called digital
signature.
4. Sender attaches the digital signature to the end of the message that is
to be sent. The message attached with digital signature is known as
digitally signed message.
5. The sender encrypts the digitally signed message with the recipient’s
public key and sends it to the recipient.
6. After receiving, the recipient decrypts the entire message with his/her
private key.
7. The recipient detaches the message and digital signature.
8. He/she creates a “digest” of the received message using the same
Site
Receiver

hash function the sender used.

9. The recipient decrypts the digital signature and finds the “digest” that
the sender created.
10. The recipient then compares the two digests. If they are equal, the
message is granted, otherwise it will be rejected.
Slide-4
The processes are illustrated in the figure on the next slide..
 Digital Signature Process

Slide-5 Figure: Illustration of digital signature process:

 Digital Signature Vs. Conventional Signature
Key-point Conventional Signature Digital Signature
Inclusion a conventional signature is But, when we sign a document
included in the document; digitally, we send the signature as a
it is part of the document. separate document.; a digital
E.g., when we write a check, signature is a separate
the signature is on the check; document. The sender sends two
it is not a separate document. documents- the message and the
signature. The recipient receives
both documents and verifies that the
signature belongs to the supposed
sender. If this is proven, the
message is kept; otherwise, it is
rejected.
Verification A conventional signature on a For a digital signature, the recipient
method document is verified by receives the message and the
comparing the signature on it signature. The recipient needs to
with the signature on file. apply a verification technique to the
combination of the message and the
signature to verify the authenticity.

Slide-6
 Digital Signature Vs. Conventional Signature
Key-point Conventional Digital Signature
Signature
Relationship For a conventional For a digital signature, there is a
signature, there is one-to-one relationship between a
normally a signature and a message. Each
one-to-many message has its own signature. The
relationship between a signature on one message can not be
signature and used in another message. For example, if
documents. A person Bob receives two messages, one after
uses the same signature another, from Alice, he can not use the
to sign many documents. signature of the first message to verify
the second. Each message needs a new
signature.
Duplicity In conventional signature, In digital signature, there is no such
a copy of the signed distinction unless there is a factor of time
document can be (such as a timestamp) on the document.
distinguished from the For example, suppose Alice sends a
original one on file. document instructing Bob to pay Eve. If
the intercepts the documents and the
signature, she can replay it later to get
money again from Bob.

Slide-7
 Services Provided by Digital Signature

A digital signature serves three important purposes:

1. Provides authentication of the sender
2. Verifies data integrity
3. Provides non-repudiation

Slide-8
 Services Provided by Digital Signature
Message Authentication:
A digital signature’s main function is to verify that a message or document,
in fact, comes from the claimed sender. That is, to provide authentication
is the main function of digital signature.

Message Integrity:
The integrity of the message is preserved even if we sign the whole
message because we cannot get the same signature if the message is
changed. Therefore, digital signature provides the integrity of the
message.

Non-Repudiation:
Attaching a digital signature with message prevents repudiation. This
ensures that the sender should not be able to later deny that he/she sent a
message. Non-repudiation prevents sender and vendor in a transaction or
communication activity from later falsely denying that the transaction
occurred.
N.B. As contrast to encryption scheme, digital signature does not provides the
confidentiality of the message.
Slide-9
Massage Authentication Code (MAC)
• A Message Authentication Code (MAC) is a short piece of information used to
authenticate a message and ensure its integrity. Here’s a brief overview:
1. Purpose: A MAC verifies that the message came from the stated sender
(authenticity) and that it hasn’t been altered (integrity).
2. How It Works:
1. Key Generation: A secret key is generated and shared between the sender
and the receiver.
2. MAC Generation: The sender uses the secret key and a MAC algorithm to
produce a MAC tag from the message.
3. Transmission: The message and the MAC tag are sent to the receiver.
4. Verification: The receiver uses the same secret key and MAC algorithm to
generate a MAC tag from the received message and compares it with the
received MAC tag. If they match, the message is verified as authentic and
unaltered
 Message Authentication Code (MAC) Vs. Digital Signature

Is a message digest the same as a message authentication code?

The MAC value protects both a message's integrity as well as
its authenticity by allowing verifiers (who also possess the
same secret key) to detect any changes to the message
content.
A message authentication code is different than a digital
signature.
❑ MAC values are both generated and verified using the same
secret key.
❖ While using MAC, sender and receiver of a message must agree on
keys before initiating communications. As is the case with private
key encryption.

❑ A message authentication code does not provide the

property of non-repudiation offered by digital signature.

Slide-11
 Hash Function
A hash function is a formula or an algorithm that-
❖ takes large data sets of variable length as input, and
❖ returns smaller data sets of fixed length as output.

Since, the output is smaller than the input data, a hash

function compresses an n-bit message string to create an
m-bit string where n is normally greater than m.
The values returned by a hash function are called hash values,
hash codes, hash sums, checksums or simply hashes.
Hash function creates hash value in such a way that it is
extremely unlikely that some other text will produce the same
hash value.

A hash table (also called hash map) is used

to implement an associative array that can
map keys to values. A hash table uses a
hash function to compute an index into an
array of buckets or slots, from which the
correct value can be found.
Slide-12
 Cryptographic Hash Function
A cryptographic hash function is a hash function that takes an
arbitrary block of data as input and returns a fixed-size bit
string as output. The returned value is called the cryptographic
hash value.
Cryptographic hash function creates hash value in such a way
that any (accidental or intentional) change to the data will
change the hash value. Therefore, it is extremely unlikely that
some other text will produce the same hash value.
The data to be encoded are often called the message, and the
hash value is sometimes called the message digest or simply
digest.

Slide-13
 Cryptographic Hash Function
In cryptographic hash function, even a small changes in the input
would cause a large change in the output.
Figure below shows how the slight changes input (here in the word
"over") drastically change the resulting output.

Slide-14
 Illustration: Cryptographic Hash Function
An illustration of the potential use of a cryptographic hash is as
follows:
❖ Alice poses a tough math problem to Bob and claims she has solved it.
❖ Bob would like to try it himself, but would yet like to be sure that Alice
is not bluffing. Therefore, Alice writes down her solution, computes its
hash and tells Bob the hash value (whilst keeping the solution secret).
Then, when Bob comes up with the solution himself a few days later,
Alice can prove that she had the solution earlier by revealing it and
having Bob hash it and check that it matches the hash value given to
him before.

Slide-15
 Use of Hash Function
Cryptographic hash functions have many information security
applications, such as in-
❖ digital signatures
❖ message authentication codes (MACs)

❖ other forms of authentication

Hash functions are primarily used to generate fixed-length

output data that acts as a shortened reference to the original
data. This is useful when the output data is too cumbersome
to use in its entirety.
❖ For example, consider a list of person’s names. Here, name of each
person is of variable length. Searching for a person's name in the list is
slow; time required to retrieve each name may also vary. But if each
name could be hashed to a fixed length integer, then searching and
retrieving each name will be performed in faster with constant time.

Hash functions are also used to accelerate table lookup or data

comparison tasks such as finding items in a database,
detecting duplicated or similar records in a large file, finding
similar stretches in DNA sequences, and so on.
Slide-16
 Hash Functions Used in Cryptography
The two commonly used hash functions are MD5 and SHA-1.
❖ MD5:
❑ MD stands for Message Digest.

❑ Several MD hash algorithms designed by Ron Rivest are MD2, MD4

and MD5.

❑ The last version MD5 is more secured than the previous versions.
❑ It divides the message into blocks of 512 bits and creates a 128-bit
digest.

❑ SHA-1:
❑ SHA stands for Secure Hash Algorithm.

❑ This standard was developed by NIST (National Institute of

Standards and Technology).

❑ This standard is mostly based on MD5.

❑ Several versions of SHA standard were realsed: SHA-1, SHA-224,

SHA-256, SHA-384 and SHA-512.

❑ SHA-1 returns a string of 160 bits.

❑ Both MD5 and SHA-1 hash functions are built with the
Slide-17 Merkle-Damgard construction.
 Application of Hash Function in Cryptography

Hash functions are used for:

❖ Verifying the integrity of message and file
❖ Verifying password for secure login
❖ fingerprints of keys
❖ authentication
❖ digital signatures

Verifying the integrity of files or messages:

❖ An important application of secure hashes is verification of
message integrity. Determining whether any changes have been
made to a message (or a file), for example, can be accomplished
by comparing message digests calculated before, and after,
transmission (or any other event).
❖ For this reason, most digital signature algorithms only confirm the
authenticity of a hashed digest of the message to be "signed".
Verifying the authenticity of a hashed digest of the message is
considered proof that the message itself is authentic.

Slide-18
 Application of Hash Function in Cryptography
Verifying password for secure login:
❖ A related application of hash function is password verification.
❖ Storing all user passwords as plaintext character can result in a massive
security breach if the password file is compromised.
❖ One way to reduce this danger is to only store the hash digest of each
password instead of the plaintext password in the table (a file) that is
stored by user identification.
❖ Any user can read the contents of the file, but, because the hash
function is a one-way function, it is almost impossible to guess the
value of the password.
❖ When the password is created , the system hashes it and stores the
hash in the password file.
❖ When the user sends her user ID and password, the system creates a
hash of the password and then compare the hash value with the one
stored in the file.
❖ If there is a match, the user is granted access; otherwise, access is
denied.

Slide-19
 Application of Hash Function in Cryptography
File or data identifier:
❖ A message digest can also serve as a means of reliably identifying
a file;

❖ One of the main applications of a hash function is to allow the fast

look-up of a data in a hash table. Being hash functions of a
particular kind, cryptographic hash functions lend themselves well
to this application too.

Authentication:
❖ Authentication is the assurance that the communicating entity is
the one that it claims to be.

❖ Cryptographic hash function can be used for provide

authentication.

Slide-20
 Application of Hash Function in Cryptography
Digital Signature:
❖ Digital signature, first proposed in 1976 by Whitfield Diffie of
Stanford University, is a digital code (encrypted message digest)
that can be attached to an electronically transmitted message that
uniquely identifies the sender.
❖ Like a written signature, the purpose of a digital signature is to
guarantee that the individual sending the message really is who he
or she claims to be. It is linked to the data in such a manner that if
the data is changed, the digital signature is invalidated.
❖ When making a digital signature, cryptographic hash functions are
generally used to construct the message digest.
❖ A digital signature servers three important purposes:
❑ Verifies data integrity.
❑ Provides authentication of the sender.
❑ Provides non-repudiation

Slide-21
Properties of Cryptographic Hash
Function
• Deterministic: A hash function must consistently produce the same output
for the same input.
• Fixed Output Size: The output of a hash function should have a fixed size,
regardless of the size of the input.
• Efficiency: The hash function should be able to process input quickly.
• Uniformity: The hash function should distribute the hash values uniformly
across the output space to avoid clustering.
• Pre-image Resistance: It should be computationally infeasible to reverse
the hash function, i.e., to find the original input given a hash value.
• Collision Resistance: It should be difficult to find two different inputs that
produce the same hash value.
• Avalanche Effect: A small change in the input should produce a
significantly different hash value.
 Simple Hash Function
Some Popular Hash Function:
Here are some relatively simple hash functions that have been
used:
Division-remainder method
Mid-square method
Folding method

Division-remainder method:
Using this method, choose a number m that is larger than
the number n of keys in K (K is a set of keys). Generally,
the number m is chosen to be a prime number. The hash
function H is defined as:
H(k)= k (mod m) or, H(k)= k (mod m)+1
Here k (mod m) denotes the remainder when k is divided
by m.
The second formula is used when we want the hash
Slide-23 addresses to range from 1 to m rather than from 0 to m-1.
 Simple Hash Function
Example: Division-remainder method:
Suppose a company with 68 employees assigned a 4-digit employee number
to each employee which is used as the primary key. Apply the division
method of hash function to each of the following employee number:
3205, 7148, 2345
Solution:
Since, there are 68 employees in the company, two digit employee
number is sufficient to represent them.
Highest 2 digit number is 99 and 97 is the nearest 2 digit prime
number of 99. So, we divide each of the 4 digit employee number by
97.
H(3205)= 3205 (mod 97)= 04.
H(7148)= 7148 (mod 97)= 67
H(2345)= 2345 (mod 97)= 17
In the case that the memory addresses begin with 01 rather than 00,
we choose that the function H(k) = k(mod m)+1 to obtain. H(3205)=
3205 (mod 97)+1= 4+1=05
Slide-24
Simple Hash Function
(Mid-Square Hashing)
• Mid-Square hashing is a hashing technique in which unique keys are
generated.
• In this technique, a seed value is taken and it is squared.
• Then, some digits from the middle are extracted.
• These extracted digits form a number which is taken as the new seed.
• This technique can generate keys with high randomness if a big enough
seed value is taken.
• However, it has a limitation.
• As the seed is squared, if a 6-digit number is taken, then the square will
have 12-digits.
• This exceeds the range of int data type. So, overflow must be taken care
of.
 Simple Hash Function
Example: Mid-square method
Suppose a company with 68 employees assigned a 4-digit employee number
to each employee which is used as the primary key. Apply the mid-square
method of hash function to each of the following employee number:
3205, 7148, 2345
Solution:

K 3205 7148 2345

K2 10272025 51093904 5499025
H(k) = I 72 93 99

Observe that the 4th and 5th digits counting from right are chosen for
the hash address.

Slide-26
Simple Hash Function

Folding method:
Folding Method in Hashing: It breaks up a key value into precise segments that are added
to form a hash value

Algorithm:
•The folding method is used for creating hash functions starts with the item being
divided into equal-sized pieces i.e., the last piece may not be of equal size.
•The outcome of adding these bits together is the hash value, H(x) = (a + b + c) mod
M, where a, b, and c represent the preconditioned key broken down into three parts
and M is the table size, and mod stands for modulo.
•In other words, the sum of three parts of the preconditioned key is divided by the
table size. The remainder is the hash key.

Slide-27
• Example 1: The task is to fold the key 123456789 into a Hash
Table of ten spaces (0 through 9).
• It is given that the key, say X is 123456789 and the table size (i.e., M =
10).
• Since it can break X into three parts in any order. Let’s divide it evenly.
• Therefore, a = 123, b = 456, c = 789.
• Now, H(x) = (a + b + c) mod M i.e., H(123456789) =(123 + 456 +
789) mod 10 = 1368 mod 10 = 8.
• Hence, 123456789 is inserted into the table at address 8.
SHA-256
• SHA 256 is a part of the SHA 2 family of algorithms, where SHA stands for
Secure Hash Algorithm. Published in 2001, it was a joint effort between the
NSA and NIST to introduce a successor to the SHA 1 family, which was
slowly losing strength against brute force attacks.
• The significance of the 256 in the name stands for the final hash digest
value, i.e. irrespective of the size of plaintext/cleartext, the hash value will
always be 256 bits.
Characteristics of SHA-256
• Some of the standout features of the SHA algorithm are as
follows:
• Message Length:
• The length of the cleartext should be less than 264 bits. The size needs to be in
the comparison area to keep the digest as random as possible.
• Digest Length:
• The length of the hash digest should be 256 bits in SHA 256 algorithm, 512 bits
in SHA-512, and so on. Bigger digests usually suggest significantly more
calculations at the cost of speed and space.
• Irreversible:
• By design, all hash functions such as the SHA 256 are irreversible. You should
neither get a plaintext when you have the digest beforehand nor should the digest
provide its original value when you pass it through the hash function again.
Algorithm
1.Message Padding:
• The original message is padded so that its length is 64 bits less than a multiple of 512. This
padding includes a single ‘1’ bit followed by ‘0’ bits, and the length of the original message is
appended at the end.
2. Message Parsing: T
The padded message is divided into 512-bit blocks.
3. Initialization of Buffers:
Eight 32-bit words are used as initial hash values. These are constants derived from the
fractional parts of the square roots of the first eight prime numbers.
4. Processing Blocks:
Each 512-bit block is processed in a series of 64 rounds involving bitwise operations, modular
additions, and compression functions. This step uses a set of 64 constant values derived from
the fractional parts of the cube roots of the first 64 prime numbers.
5. Final Hash Value:
After all blocks are processed, the final hash value is produced by concatenating the hash
values from the eight buffers.
Application of SHA-256
• Digital Signature Verification:
• Digital signatures follow asymmetric encryption methodology to verify the
authenticity of a document/file. Hash algorithms like SHA 256 go a long way in
ensuring the verification of the signature.
• Password Hashing:
• As discussed above, websites store user passwords in a hashed format for two
benefits. It helps foster a sense of privacy, and it lessens the load on the central
database since all the digests are of similar size.
• SSL Handshake:
• The SSL handshake is a crucial segment of the web browsing sessions, and it’s
done using SHA functions. It consists of your web browsers and the web servers
agreeing on encryption keys and hashing authentication to prepare a secure
connection.
• Integrity Checks:
• As discussed above, verifying file integrity has been using variants like SHA 256
algorithm and the MD5 algorithm. It helps maintain the full value functionality of
files and makes sure they were not altered in transit.
Message Authentication Code (MAC) Vs. Hash Code
MAC is a technique for message authentication which involves the use of a
secret key to generate from a small block of data, known as a message
authentication code, that is appended to the message.
This technique assumes that two communicating parties, say Alice and
Bob, share a common secret key KAB. When Alice has a message to send to
Bob, she calculates the message authentication code as a complex function
of the message and the key: MACM = F(KAB, M).

The message plus code are

transmitted to the intended
recipient.
The recipient performs the
same calculation on the
received message, using the
same secret key, to generate a
new message authentication
code.
The received code is compared
to the calculated code.

Slide-29
Message Authentication Code (MAC) Vs. Hash Code
If we assume that only the receiver and the sender know the identity
of the secret key, and if the received code matches the calculated
code, then

1. The receiver is assured that the message has not been altered.
❖ If an attacker alters the message but does not alter the code, then the
receiver’s calculation of the code will differ from the received code.
❖ Because the attacker is assumed not to know the secret key, the
attacker cannot alter the code to correspond to the alterations in the
message.

2. The receiver is assured that the message is from the alleged sender.
❖ Because no one else knows the secret key, no one else could prepare a
message with a proper code.

3. If the message includes a sequence number (such as is used with X.25,

HDLC, and TCP), then the receiver can be assured of the proper
sequence, because an attacker cannot successfully alter the sequence
number.

Slide-30
Message Authentication Code (MAC) Vs. Hash Code

An alternative to the message authentication code is the one-way hash

function.
A hash function accepts a variable-size message M as input and
produces a fixed-size message digest H(M) as output. The purpose of
a hash function is to produce a “fingerprint” of a file, message, or
other block of data.
Typically, the message is padded out to an integer multiple of some
fixed length (e.g., 1024 bits) and the padding includes the value of the
length of the original message in bits.
Unlike the MAC, a hash function does not take a secret key as input.
To authenticate a message, the message digest is sent with the
message in such a way that the message digest is authentic.

Slide-31
Message Authentication Code (MAC) Vs. Hash Code
Figure below illustrates three ways in
which the message can be
authenticated using a hash code.
❑ The message digest can be encrypted
using symmetric key encryption (part a); if
it is assumed that only the sender and
receiver share the encryption key, then
authenticity is assured.

❑ The message digest can also be encrypted

using public-key encryption (part b);

❑ Part c illustrate a technique, known as a

keyed hash MAC where authentication is
done without using encryption. It assumes
that two communicating parties, say A and
B, share a common secret key K which is
incorporated into the process of generating
a hash code.
❑ When A has a message to send to B, it calculates the hash function over the
concatenation of the secret key and the message: MDM = H(KMK). It then sends
[ MMDM] to B. Because B possesses K, it can recompute H(KMK) and verify MDM.
Because the secret key itself is not sent, it should not be possible for an attacker
to modify an intercepted message. As long as the secret key remains secret, it
should not be possible for an attacker to generate a false message.
Slide-32
 Discussion Points

❖ Digital Signature
❑ To be familiar with the general idea behind
digital signature
❑ To define security services provided by a
digital signature
❑ To describe some applications of digital
signatures
❖ Cryptographic Hash Function
❑ To introduce general ideas behind hash
function
❑ To discuss the usage and application of hash
function
❑ To know the desirable properties of a hash
Slide-37 function