Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Module 4 - Hash Functions and Authentication

CSI3002
Applied Cryptography and Network Security Message Authentication Code (MAC), MD5, Secure Hash algorithms
(SHA), HMAC, Digital Signatures, Digital Signature Standard (DSS).
(4 Hours)
By,
[Link].N.G.,
Assistant Professor Senior,
Department of Analytics,
School of Computer Science and Engineering,
Vellore Institute of Technology, Vellore.

Email: [Link]@[Link] Mobile: 8903580808 Cabin: PRP 217-16

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Message Integrity Message and Message Digest

• The cryptography systems that we have studied so far provide secrecy, or • The electronic equivalent of the document and fingerprint pair is the
confidentiality, but not integrity. message and digest pair.
• However, there are occasions where we may not even need secrecy but
instead must have integrity.

Document and Fingerprint

• One way to preserve the integrity of a document is through the use of a
fingerprint.
• If Alice needs to be sure that the contents of her document will not be
changed, she can put her fingerprint at the bottom of the document.
Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 1 of 19
 Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Difference Checking Integrity

• The two pairs (document / fingerprint) and (message / message
digest) are similar, with some differences.
• The document and fingerprint are physically linked together.
• The message and message digest can be unlinked separately, and,
most importantly, the message digest needs to be safe from change.

The message digest needs to be safe from change.

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Cryptographic Hash Function Criteria Pre-Image Resistance

A cryptographic hash function must satisfy three criteria: • This property means that it
should be computationally
• Preimage resistance hard to reverse a hash
function.
• Second preimage resistance • In other words, if a hash
• Collision resistance function h produced a hash
value z, then it should be a
difficult process to find any
input value x that hashes
to z.
• This property protects
against an attacker who
only has a hash value and
is trying to find the input.
Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 2 of 19
 Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Collision Resistance
Second Pre-Image Resistance
• This property means it should be hard to
• This property means given an find two different inputs of any length
input and its hash, it should be that result in the same hash. This
hard to find a different input property is also referred to as collision
with the same hash. free hash function.
• In other words, if a hash • In other words, for a hash function h, it is
function h for an input x hard to find any two different inputs x
produces hash value h(x), then and y such that h(x) = h(y).
it should be difficult to find any • Since, hash function is compressing
other input value y such that function with fixed hash length, it is
h(y) = h(x). impossible for a hash function not to have
• This property of hash function collisions.
protects against an attacker • This property makes it very difficult for an
who has an input value and its attacker to find two input values with the
hash, and wants to substitute same hash.
different value as legitimate • Also, if a hash function is collision-
value in place of original input resistant then it is second pre-image
value. resistant.
Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Relationship among the properties Requirements for a Cryptographic Hash

Function

Weak Hash
Strong
Function
Hash Function

1. A function that is collision resistant is also second pre-image resistant.

2. A function that is second pre-image resistant need not be collision resistant.
3. A function can be collision resistant but not pre-image resistant.
4. A function can be pre-image resistant but not collision resistant.
5. A function can be pre-image resistant but not second pre-image resistant.
Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
6. A function can be second pre-image resistant butAnalytics,not pre-image resistant.
SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 3 of 19
 Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Iterated Hash Function - Merkle-Damgard

Iterated Hash Function
Scheme
• Cryptographic hash functions need to create a fixed length message
digest out of variable length messages.
• It is accomplished by using a hash function with fixed length input
and is used necessary number of times.
• This fixed size input function is referred to as a compression function.
• It compresses n-bit string to create a m-bit string where n>m.
• The scheme is referred to as an Iterated Cryptographic Hash Function

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Two Groups of Compression Functions Message Digest (MD5)

1. The compression function is made from scratch. • The MD5 message-
digest algorithm is a
widely used hash
Message Digest (MD) Secure Hash Algorithm function producing a
(SHA) 128-bit hash value.
• Block Size of MD5 –
512 Bits
2. A symmetric-key block cipher serves as a compression function. • MD5 was designed by
Ronald Rivest in 1991
Whirlpool to replace an earlier
hash function MD4,
and was specified in
1992 as RFC 1321.

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 4 of 19
 Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Working of MD5 - Working of MD5 –

Padding Append Length
• First step is to add padding bits to the original message. • After padding is done, the next step is to calculate the total length of
• Goal: the original message and append it to the end of the message.
• To make the length of the message equal to a value less than 64 bits which is an
exact multiple of 512. • Calculate the length of the message excluding the padding.
• Eg:
• Length of the original message= 1000 bits
• The length is now expressed as a 64 bit value and it is appended to
• Padding bit to be added = – 1000 -64 = 472 bits [padding=-M-64 mod 512] the end of the original message.
• After padding the original message will have a length of 448 bits (1 block), • If the length of the original message exceeds the value 264, then mod
960 bits (2 blocks), 1472 bits (3 blocks) and so on.
of the entire value is taken and it is represented as 64 bit and
• Padding Value: 1000000000 ….. 0 appended to the message.
• NOTE: Padding is always added even if the message length is already 64
bits less than the multiple of 512.
• Padding length = 1 - 512
Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Working of MD5 – Divide the input into 512 bit

Working of MD5 – Initialize Chaining Variable
blocks
• We now divide the input into blocks of 512 bits. • Four Variables (a,b,c,d) are initialized.
• They are called as Chaining variables.
Data to be hashed • Each variable is a 32 bit number.
• The initial values of these variables are given below,
Block 1 Block 2 Block 3 …. Block n
Variable Notation 32 Bit Value
512 Bits 512 Bits 512 Bits 512 Bits A Hex 01 23 45 67
B Hex 89 AB CD EF
C Hex FE DC BA 98
D Hex 76 54 32 10

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 5 of 19
 Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Working of MD5 – Process Block Step Constant table

• A total of 4 Rounds is performed in MD5.
• The 512 bit message block M is divided into 16 32-bit sub blocks.
• M[0],M[1],….M[15]
• Each round has 16 steps.
• In total 64 steps are performed to obtain a 128 bit hash value.
• For each step a separate constant t[i] is used.

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Working of MD5 – Process Block

Circular Left Shift
Permutation
of Message
Block –
Mod Round 1,
232
Round 2
Mod
M[j] 232

Mod
T[K] 232

Mod
232

B=A
C=B
D=C
A=D
Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 6 of 19
 Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Comparison of MD4 Vs MD5

Permutation
of Message
Block – Points of Discussion MD4 MD5
Round 3, Input Blocks of 512 Bits Blocks of 512 Bits
Round 4 Output 128 Bits 128 Bits
Number of Registers/ Chaining 4 – A,B,C,D 4 – A,B,C,D
Variables
Number of Rounds 3 4
Number of Steps 48 64
Use of Additive Constant Not different in all iterations Different in all Iterations
Process P 3 Boolean expressions used 4 Boolean expressions used

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Secure Hash Algorithm (SHA) Introduction

SHA Family Year Variants Hash Output
• SHA was developed by the SHA – 0 1993 160-bit • Message digest creation SHA-512
National Institute of Standards SHA - 1 1995 160-bit
and Technology (NIST) and SHA - 2 2001 SHA-224 → 224-bit digest
SHA-256 → 256-bit digest
published as a federal SHA-384 → 384-bit digest
information processing standard SHA-512 → 512-bit digest
(FIPS 180) in 1993. SHA-512/224 and SHA-
512/256 (variants of SHA-512
• This version, like the others in with shorter outputs)
the SHA family of algorithms, is SHA - 3 2015 SHA3-224 → 224 bits
SHA3-256 → 256 bits
based on the Merkle-Damgard SHA3-384 → 384 bits
scheme. SHA3-512 → 512 bits

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 7 of 19
 Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Message Preparation – SHA 512

Example
• SHA-512 insists that the length of the original message be less than
2128 bits.
• What is the number of padding bits if the length of the original
message is 2590 bits?

|P|= -M – 128 mod (1024)

• |P|= -2590 – 128 mod 1024
= -670
Padding is Mandatory in SHA-512 = 354
Minimum Padding Bits: 1
Maximum Padding Bits: 1024
Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Example Example
• Do we need padding if the length of the original message is already a • Do we need padding if the length of the original message is already a
multiple of 1024 bits? multiple of 1024 bits?

Solution
• Yes we do, because we need to add the length field. So padding is
needed to make the new block a multiple of 1024 bits.

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 8 of 19
 Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

SHA 512 has 80 steps where

Words – SHA 512 Word Expansion – SHA 512 each step utilizes 1 word.

• SHA 512 operates on words.

• It is word oriented.
• A word is defined as 64 bits.
+

ShRn(x)
+ Addition modulo 264

ShRi(X): Shift -right

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Example Message Digest Initialization – SHA 512

• Show how W60 is made.

Solution
• Each word in the range W16 to W79 is made from four previously-
made words.
• W60 is made as
+ + + Generated from first eight prime numbers (2,3,5,7,11,13,17 and 19)

H0 = 191/2 = 4.35889894354 = 4.5BE0CD19137E2179

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 9 of 19
 Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Compression Structure of Each

Function Round

Rotate (A) = ROTR28(A) XOR ROTR34(A) XOR ROTR39(A)

Rotate (E) = ROTR14(E) XOR ROTR18(E) XOR ROTR41(E)

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Compression Function Compression Function

Majority Function Ki

Conditional Function

Rotate Functions
Rotate (A) = ROTR28(A) XOR ROTR34(A) XOR ROTR39(A)

Rotate (E) = ROTR14(E) XOR ROTR18(E) XOR ROTR41(E)

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 10 of 19
 Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Compression Function – Constant Value Example

• There are 80 constants, K0 to K79, each of 64 bits. Similar These • We apply the Majority function on buffers A, B, and C. If the leftmost
values are calculated from the first 80 prime numbers (2, 3,…, 409). hexadecimal digits of these buffers are 0x7, 0xA, and 0xE, respectively,
what is the leftmost digit of the result?
• For example, the 80th prime is 409, with the cubic root (409)1/3 = Solution:
7.42291412044.
• The digits in binary are 0111, 1010, and 1110.
• Converting this number to binary with only 64 bits in the fraction a. The first bits are 0, 1, and 1. The majority is 1.
part, we get
b. The second bits are 1, 0, and 1. The majority is 1.
c. The third bits are 1, 1, and 1. The majority is 1.
d. The fourth bits are 1, 0, and 0. The majority is 0.
• The result is 1110, or 0xE in hexadecimal.
The fraction part: (6C44198C4A475817)16
Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Example Analysis
• We apply the Conditional function on E, F, and G buffers. If the leftmost • With a message digest of 512 bits, SHA-512 expected to be resistant
hexadecimal digits of these buffers are 0x9, 0xA, and 0xF respectively, what to all attacks, including collision attacks.
is the leftmost digit of the result?
• More research is required to confirm this.
Solution:
• The digits in binary are 1001, 1010, and 1111.
a. The first bits are 1, 1, and 1. The result is F1, which is 1.
b. The second bits are 0, 0, and 1. The result is G2, which is 1.
c. The third bits are 0, 1, and 1. The result is G3, which is 1.
d. The fourth bits are 1, 0, and 1. The result is F4, which is 0.
• The result is 1110, or 0xE in hexadecimal.
Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 11 of 19
 Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Comparison of SHA Problems

• In SHA-512, show the value of the length field in hexa decimal for the
following message length,
• 1000 bits - Ans: 0000 0000 0000 0000 0000 0000 0000 03E8
• What is the padding for SHA – 512 if the length of the message is:
• 5120 bits – Ans: 896 bits
• 6143 bits – Ans: 897 bits

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Problem Homework
• Using Word expansion of SHA – 512, find out the word W17 using the • Find the result of conditional (E,F,G) for the given data.
given data. • E= 51 0E 52 7F AD E6 82 D1
• W1 – 1111 • F= 9B 05 68 8C 2B 3E 6C 1F
• W2 – 2222 • G= 1F 83 D9 AB FB 41 BD 6B
• W10 – 3333 • Ans: 1F 85 C9 8C 7B 27 3D 3B
• W15 – 4444 • Find the result of majority (A,B,C) for the given data.
• Solution: • A= 6A 09 E6 67 F3 BC C9 08
• RotShift 1-8-7 (W2) = 3377 • B= BB 67 AE 85 84 CA A7 3B
• RotShift 19-61-6 (W15) =ABBB • C= 3C 6E F3 72 FE 94 F8 2B
• W17 = 2376 • Ans: 3A 6F E6 67 F6 9C E9 2B

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 12 of 19
 Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Message Authentication Modification Detection Code (MDC)

• A message digest does not authenticate the sender of the message. • A modification detection code (MDC) is a message digest that can
• To provide message authentication, Alice needs to provide proof that prove the integrity of the message: that message has not been
it is Alice sending the message and not an impostor. changed.
• The digest created by a cryptographic hash function is normally called
a Modification Detection Code (MDC).
• What we need for message authentication is a Message
Authentication Code (MAC).

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Message Authentication Code (MAC) Message Authentication Code (MAC)

• To ensure the integrity of the message and the data origin
authentication – we need to change the Modification Detection Code
(MDC) to a Message Authentication Code (MAC).

• The difference between MDC and MAC is that, the second (MAC)
includes a secret (key) between the transmitter and the receiver.

The security of a MAC depends on the security of the

underlying hash algorithm.
Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 13 of 19
 Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Message Authentication Code (MAC) Nested MAC

• Prefix MAC : (the key appended to the beginning of the message) • To improve the security of a MAC, the hashing is done in two steps

• Postfix MAC : (the key appended to the end of the message)

• We can combine the prefix and postfix MAC, with the same key or
two different keys

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

K = b → Do nothing
K < b → Append 0 bits to the left of K
so that K=b
Hashed MAC (HMAC) K > b → Hash k to reduce it to length b Digital Signature
• NIST has issued a standard (FIPS198) • Conventional Signature
for a nested MAC which is referred • A person signs a document to show that the document was created by that
to as HMAC (hashed MAC). person or the document is approved by that person.
• The signature is a proof to the recipient that the document comes from the
b- Message block size correct entity.
n- size of Message Digest • Digital Signature
----------------------------------------------- • Alice sends a message to Bob.
ipad – 00110110 – 0x36 • Bob needs to check the authenticity of the message. i.e) the message comes
opad - 01011100 – 0x5C from Alice and not Eve.
Repeat ipad and opad b/8 times • So, Bob asks Alice to electronically sign the message.
• This electronic signature is called as digital signature.
Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore.

Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 14 of 19
 Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Comparison of Conventional Signature with Comparison of Conventional Signature with

Digital Signature Digital Signature
• Inclusion • Relationship
• A conventional signature is included in the document; it is part of the • For a conventional signature, there is normally a one-to-many relationship
document. between a signature and documents.
• But when we sign a document digitally, we send the signature as a separate • For a digital signature, there is a one-to-one relationship between a signature
document. and a message.
• Verification Method • Duplicity
• For a conventional signature, when the recipient receives a document, she • In conventional signature, a copy of the signed document can be
compares the signature on the document with the signature on file. distinguished from the original one on file.
• For a digital signature, the recipient receives the message and the signature. • In digital signature, there is no such distinction unless there is a factor of
• The recipient needs to apply a verification technique to the combination of time on the document.
the message and the signature to verify the authenticity.

Digital Signature Process Digital Signature Process

• The sender uses a signing algorithm to sign the message. Need for Keys:
• The message and the signature are sent to the receiver. • Adding key to the digital signature process
• The receiver receives the message and the signature and applies the
verifying algorithm to the combination.
• If the result is true, the message is accepted; otherwise, it is rejected.

A digital signature needs a public-key system.

The signer signs with her private key; the verifier
verifies with the signer’s public key.

Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 15 of 19
 Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Digital Signature using Symmetric Key

John sends message to Mary. The following disputes may arise when
symmetric key is used for the purposes of signing.
A cryptosystem uses 1. Mary may forge a different message and claim that it came from
the private and public keys of the receiver, John.
A digital signature uses 2. John can deny sending the message. Because it is possible for Mary
the private and public keys of the sender. to forge a message, there is no way to prove that John did in fact
send the message.

Digital Signature Process

Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 16 of 19
 Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Properties of Digital Signature Digital Signature Requirements

• It must verify the author and the date and time of the signature. • The signature must be a bit pattern that depends on the message being
signed.
• It must authenticate the contents at the time of the signature.
• The signature must use some information only known to the sender to
• It must be verifiable by third parties, to resolve disputes. prevent both forgery and denial.
• It must be relatively easy to produce the digital signature.
• It must be relatively easy to recognize and verify the digital signature.
• It must be computationally infeasible to forge a digital signature, either by
constructing a new message for an existing digital signature or by
constructing a fraudulent digital signature for a given message.
• It must be practical to retain a copy of the digital signature in storage.

Digital Signature Schemes/ Protocol Digital Signature Standard (DSS)

• Several digital signature schemes have evolved during the last few
decades.
• RSA Digital Signature Scheme

• ElGamal Digital Signature Scheme

• Schnorr Digital Signature Scheme

• Digital Signature Standard (DSS)

• Elliptic Curve Digital Signature Scheme

Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 17 of 19
 Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Digital Signature Standard (DSS) Digital Signature Standard (DSS)

1<= r <= q
Key Generation
1)Alice chooses primes p and q. q is selected such that (p-1) mod q = 0

2)Alice uses <Zp*, × > and <Zq*, ×>.

𝑝−1
𝑞
3) 𝑒1 = 𝑒0 𝑚𝑜𝑑 𝑝 (Public Key)

4)Alice chooses d and calculates e2 = e1d mod p. (Public Key)

5)Alice’s public key is (e1, e2, p, q); her private key is (d).

Digital Signature Standard (DSS) Digital Signature Standard (DSS)

Example Example
• Alice chooses p = 7; e0=2; q=3; d=5; Signing Process
Key Generation 𝑆1 = (𝑒1𝑟 𝑚𝑜𝑑 𝑝)𝑚𝑜𝑑 𝑞
𝑺𝟏 = 42 𝑚𝑜𝑑 7 𝑚𝑜𝑑 3 = 𝟐
• Alice calculates q, such that 𝑝 − 1 𝑚𝑜𝑑 𝑞 = 0
• Alice calculates e1 = e0 (p−1)/q mod p= 2 (7−1)/3 mod 7= 2 2 mod 7=4 𝑆2 = [(ℎ 𝑀 + 𝑑𝑆1 )𝑟 −1 𝑚𝑜𝑑 𝑞]
• Alice chooses d = 5 as the private key and calculates e2 = e1d mod p = 𝑆2 = [(3 + 5 ∗ 2)2−1 𝑚𝑜𝑑 3]
45 mod 7 = 2. 𝑺𝟐 = 3 + 5 ∗ 2 2 𝑚𝑜𝑑 3 = 𝟐
• Now Alice can send a message to Bob. Assume that h(M) = 3 and
Alice chooses r = 2: 𝑺𝟏 = 2
𝑺𝟐 = 2

Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 18 of 19
 Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Digital Signature Standard (DSS)

Digital Signature Standard (DSS)
Example
Verification Process DSS Versus RSA
• Computation of DSS signatures is faster than computation of RSA
ℎ(𝑀)𝑆2 −1 𝑆1 𝑆2 −1
𝑉 = (𝑒1 𝑒2 𝑚𝑜𝑑 𝑝)𝑚𝑜𝑑 𝑞 signatures when using the same p.

𝑉 = 43∗2 22∗2 𝑚𝑜𝑑 7 𝑚𝑜𝑑 3 = 2 DSS Versus ElGamal

• DSS signatures are smaller than ElGamal signatures because q is
Hence Verified smaller than p.
𝑽 ≡ 𝑺𝟏 ≡ 𝟐

Digital Signature Algorithm

(DSA)

Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 19 of 19