Module 5

Digital Signature
and
Authentication Protocols
Authentication Requirements, Authentication Functions, Message
Authentication Codes, Digital Signature Authentication,
Authentication Protocols, Digital Signature Standards, RSA
Digital Signature, Elgamal based Digital Signature, Authentication
Applications: Kerberos, X.509 Authentication Service, Public Key
Infrastructure (PKI)

Dr. Islabudeen
 Digital Signatures
A Digital Signature is an authentication
mechanism that enables the creator of the
message to attach a code that acts as a
signature. The Signature guarantees the source
and integrity of the message.
 Digital Signatures
It must have the following properties:
• It must verify the author and the date and time of the
signature.

• It must to authenticate the contents at the time of the

signature.

• It must be verifiable by third parties, to resolve disputes.

Thus, the digital signature function includes the

authentication function.
Digital Signature Model
 Digital
Signature
Model
 Digital Signature Requirements (Or)
Authentication Requirements
➢ must depend on the message signed
➢ must use information unique to sender to
prevent both forgery and denial
➢ must be relatively easy to produce
➢ must be relatively easy to recognize & verify
➢ be computationally infeasible to forge
⚫ with new message for existing digital signature
⚫ with fraudulent digital signature for given message
➢ be practical save digital signature in storage
 Message Authentication Functions

• These may be grouped into three classes.

• Hash function: A function that maps a message of any length into a fixed-length
hash value, which serves as the authenticator
• Message encryption: The ciphertext of the entire message serves as its
authenticator
• Message authentication code (MAC): A function of the message and a secret
key that produces a fixed-length value that serves as the authenticator

7
Message Encryption

8
 MESSAGE AUTHENTICATION CODE

• A message digest guarantees the integrity of a message.

• It guarantees that the message has not been changed.

9
 Cont..
• To ensure the integrity of the message and the data origin authentication, we moved on
from modification detection code (MDC) to a message authentication code (MAC). No
Confidentiality!!!!!
• More commonly, message authentication is achieved using a message authentication code
(MAC) or cryptographic checksum, or keyed hash function
• Typically, MACs are used between two parties that share a secret key to authenticate
information exchanged between those parties.
• A MAC function takes as input a secret key and a data block and produces a hash value,
referred to as the MAC, which is associated with the protected message.
• If the integrity of the message needs to be checked, the MAC function can be applied to the
message and the result compared with the associated MAC value.
• An attacker who alters the message will be unable to alter the associated MAC value
without knowledge of the secret key.
• In practice, specific MAC algorithms are designed that are generally more efficient than an
encryption algorithm.

10
1. The receiver is assured that the message has not been altered.
• If an attacker alters the message but does not alter the MAC, then the receiver’s
calculation of the MAC will differ from the received MAC.
• Because the attacker is assumed not to know the secret key, the attacker cannot
alter the MAC to correspond to the alterations in the message.
2. The receiver is assured that the message is not from the attacker.
Because no one else knows the secret key, no one else could prepare a message
with a proper MAC.

• A MAC function is similar to encryption. One difference is that the MAC

algorithm need not be reversible, as it must be for decryption.

11
MAC structure / diagram

12
MAC = C(K, M)
where
• M = input message
• C = MAC function
• K = shared secret key
• MAC = message authentication code
• The message plus MAC 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 MAC.
• The received MAC is compared to the calculated MAC.
• If we assume that only the receiver and the sender know the identity of the secret
key, and if the received MAC matches the calculated MAC, then it will accept
otherwise, it will reject.

13
Basic Uses of Message Authentication code (MAC)

Confidentiality,
Integrity and
Authentication is
achieved

14
 Direct Digital Signatures
• involve only sender & receiver
• Confidentiality can be provided by encrypting the
entire message plus signature with a shared secret
key (symmetric encryption). Note that it is
important to perform the signature function first
and then an outer confidentiality function.
• important that sign first then encrypt message &
signature
• security depends on secret key
 Direct Digital Signatures
• In case of dispute, some third party must view the message and its
signature. If the signature is calculated on an encrypted message,
then the third party also needs access to the decryption key to
read the original message.
• However, if the signature is the inner operation, then the recipient
can store the plaintext message and its signature for later use in
dispute resolution.
• The validity of the scheme just described depends on the security of
the sender’s private key. If a sender later wishes to deny sending a
particular message, the sender can claim that the private key was
lost or stolen and that someone else forged his or her signature.
• One example is to require every signed message to include a
timestamp (date and time) and to require prompt reporting of
compromised keys to a central authority.
• Another threat is that some private key might actually be stolen
from X at time T. The opponent can then send a message signed
with X’s signature and stamped with a time before or equal to T.
 Authentication Protocols
Authentication protocols are procedures used in computer networks
to verify the identity of communicating entities (users, systems, or
devices) before allowing secure communication. These protocols
define a sequence of message exchanges and cryptographic
operations to ensure that the parties involved are genuine.

Objectives of Authentication Protocols

• Authentication protocols aim to provide:
• Entity Authentication – Confirms the identity of a user or system.
• Message Integrity – Ensures that messages are not altered during
transmission.
• Confidentiality Support – Helps establish secure communication.
• Protection Against Attacks – Prevents replay attacks,
masquerade attacks, and man-in-the-middle attacks.
Authentication protocols usually use cryptographic mechanisms such
as encryption, digital signatures, timestamps, and nonces.
 Authentication Protocols
Kerberos Authentication Protocol
• Kerberos is a trusted third-party authentication protocol
designed to provide secure authentication in distributed
networks.
• Key Idea
• Kerberos uses a central authentication server and secret-
key cryptography to verify users and services.

X.509 Authentication Service

• X.509 is a certificate-based authentication framework
used in public key infrastructures (PKI).
• It relies on digital certificates issued by a trusted authority
called a Certificate Authority.
Digital Signature Standard (DSS)
• US Govt approved signature scheme
• designed by NIST & NSA in early 90's
• published as FIPS-186 in 1991
• revised in 1993, 1996 & then 2000
• uses the SHA hash algorithm
• DSS is the standard, DSA is the algorithm
• FIPS 186-2, subsequently updated to FIPS 186-3 in
2009 includes alternative RSA & elliptic curve
signature variants
• DSA is digital signature only unlike RSA
• is a public-key technique
DSS vs RSA Signatures
Digital Signature Algorithm (DSA)
➢creates a 320-bit signature
➢with 512–1024-bit security
➢smaller and faster than RSA
➢security depends on difficulty of computing
discrete logarithms
➢variant of ElGamal & Schnorr schemes
 DSA Key Generation
• have shared global public key values (p,q,g):
– choose 160-bit prime number q
– choose a large prime p with 2L-1 < p < 2L
• where L= 512 to 1024 bits and is a multiple of 64
• such that q is a 160-bit prime divisor of (p-1)
– choose g = h(p-1)/q mod p
• where 1<h<p-1 and h(p-1)/q mod p > 1
• users choose private & compute public key:
– choose random private key: x<q
– compute public key: y = gx mod p
 DSA Signature Creation
➢ to sign a message M the sender:
⚫generates a random signature key k, k<q
⚫k must be random, be destroyed after use,
and never be reused
➢ then computes signature pair:
r = (gk mod p)mod q
s = [k-1(H(M)+ xr)] mod q
➢ sends signature (r,s) with message M
 DSA Signature Verification

• having received M & signature (r,s)

• to verify a signature, recipient computes:
w = s-1 mod q
u1= [H(M)w ]mod q
u2= (rw)mod q
v = [(gu1 yu2)mod p ]mod q
• if v=r then signature is verified
DSS Overview
RSA Digital Signature
RSA DS stands for RSA Digital Signature, which is a method
used to verify the authenticity, integrity, and non-repudiation
of a message using the RSA Algorithm.
It is widely used in secure communications, software signing,
SSL/TLS certificates, and email security.

What is RSA Digital Signature?

RSA Digital Signature is a cryptographic technique where a
sender signs a message using their private key, and the
receiver verifies it using the sender’s public key.
This ensures:
Authentication – verifies the sender
Integrity – message is not altered
Non-repudiation – sender cannot deny sending the message
RSA Digital Signature
RSA Digital Signature
RSA Digital Signature
 ElGamal Digital Signatures
• signature variant of ElGamal, related to D-
H
– so uses exponentiation in a finite (Galois)
– with security based difficulty of computing
discrete logarithms, as in D-H
• use private key for encryption (signing)
• uses public key for decryption (verification)
• each user (eg. A) generates their key
– chooses a secret key (number): 1 < xA < q-1
xA
– compute their public key: yA = a mod q
 ElGamal Digital Signature
• Alice signs a message M to Bob by computing
– the hash m = H(M), 0 <= m <= (q-1)
– chose random integer K with 1 <= K <= (q-1) and
gcd(K,q-1)=1
K
– compute temporary key: S1 = a mod q
– compute K-1 the inverse of K mod (q-1)
– compute the value: S2 = K-1(m-xAS1) mod (q-1)
– signature is: (S1,S2)
• any user B can verify the signature by computing
m
– V1 = a mod q
– V2 = yAS1 S1S2 mod q
– signature is valid if V1 = V2
 ElGamal Signature Example
• use field GF(19) q=19 and a=10
• Alice computes her key:
16
– A chooses xA=16 & computes yA=10 mod 19 = 4
• Alice signs message with hash m=14 as (3,4):
– choosing random K=5 which has gcd(18,5)=1
5
– computing S1 = 10 mod 19 = 3
– finding K-1 mod (q-1) = 5-1 mod 18 = 11
– computing S2 = 11(14-16.3) mod 18 = 4
• any user B can verify the signature by computing
14
– V1 = 10 mod 19 = 16
– V2 = 43.34 = 5184 = 16 mod 19 = 16
– since 16 = 16 signature is valid
 Schnorr Digital Signatures

• also uses exponentiation in a finite (Galois)

– security based on discrete logarithms, as in D-H
• minimizes message dependent computation
– multiplying a 2n-bit integer with an n-bit
integer
• main work can be done in idle time
• have using a prime modulus p
– p–1 has a prime factor q of appropriate size
– typically p 1024-bit and q 160-bit numbers
 Schnorr Key Setup
• choose suitable primes p , q
q
• choose a such that a = 1 mod p
• (a,p,q) are global parameters for all
• each user (eg. A) generates a key
– chooses a secret key (number): 0 < sA < q
-sA
– compute their public key: vA = a mod p
 Schnorr Signature
• user signs message by
– choosing random r with 0<r<q and computing
x = ar mod p
– concatenate message with x and hash result to
computing: e = H(M || x)
– computing: y = (r + se) mod q
– signature is pair (e, y)
• any other user can verify the signature as follows:
– computing: x' = ayve mod p
– verifying that: e = H(M || x’)