Message Authentication Codes

 Message Authentication Codes (MAC)

What is Message Authentication?

Message authentication ensures that:

• The message comes from the correct sender
• The message is not altered
• The message is fresh (not replayed)

Authentication Requirements

Requirement	Meaning	Real-Life Example
Data Integrity	Message not changed	Sealed courier
Authentication	Sender identity verified	OTP verification
Non-repudiation	Sender cannot deny	Digital signature
Freshness	No replay attack	Session token

Authentication Functions

Authentication functions verify data integrity and sender identity.

Types of Authentication Functions

Method	Key Used	Security Level
Encryption	Secret key	Medium
MAC	Secret key	High
Hash function	No key	Integrity only
Digital Signature	Public/private	Very high

Message Authentication Code (MAC)

A MAC is a fixed-size code generated using:

• Message
• Secret key

MAC Formula

$$MAC=F(K,M)$$

Where:

• K = secret key
• M = message

Verification: Receiver recomputes MAC and compares.

Example 

• Bank message + secret PIN
• If PIN matches → message accepted

Real-Life Use

• ATM communication
• Online payments
• Secure APIs

Hash Functions

A hash function converts data of any size into a fixed-length value.

Hash Function Properties

Property	Meaning
Fixed length	Output size constant
One-way	Cannot reverse
Fast computation	Quick processing
Avalanche effect	Small change → big difference

Hash Formula

$$h=H(M)$$

Real-Life Example

• Password storage
• File integrity check
• Blockchain

Birthday Attacks

A birthday attack exploits the probability of hash collisions.

Birthday Paradox

• Only 23 people needed for same birthday probability > 50%

In Hashing

For n-bit hash, collision possible in:

$$2^{n/2}$$

Example: 128-bit hash → attack possible at 2⁶⁴ tries

Impact

• Breaks digital signatures
• Weakens hash security

Security of Hash Functions

Security Requirements

Property	Description
Pre-image resistance	Cannot find message from hash
Second pre-image resistance	Cannot find same hash
Collision resistance	No two inputs same hash

Weak Hash Example

• MD5
• SHA-1 (deprecated)

Secure Hash Algorithm (SHA)

What Is SHA?

SHA is a family of cryptographic hash algorithms developed by NIST.

SHA Variants

Algorithm	Output Size	Status
SHA-1	160-bit	Broken
SHA-256	256-bit	Secure
SHA-512	512-bit	Secure
SHA-3	Variable	Very Secure

SHA-256 Working (Simplified)

• Message padding
• Divide into blocks
• Compression function
• Produce hash

Real-Life Use

• Password hashing
• Blockchain (Bitcoin)
• SSL certificates
• Digital signatures

Comparison Table: Hash vs MAC

Feature	Hash	MAC
Secret key	No	Yes
Integrity	Yes	Yes
Authentication	No	Yes
Used in	Passwords	Secure communication

Final Quick Revision Table

Topic	Key Point
Authentication	Verify sender + data
MAC	Keyed integrity
Hash	One-way function
Birthday Attack	Collision attack
Hash Security	Pre-image resistance
SHA	Secure hash family

Digital Signatures

What is a Digital Signature?

A digital signature is a cryptographic technique used to:

• Verify the identity of the sender
• Ensure message integrity
• Provide non-repudiation (sender cannot deny)

Simple Meaning: A digital signature is like a handwritten signature, but for digital documents, secured using mathematics and cryptography.

Why Digital Signatures Are Needed

Requirement	Explanation	Real-Life Example
Authentication	Confirms sender	Email sender verification
Integrity	Message not altered	Legal document protection
Non-repudiation	Sender cannot deny	Online contracts
Security	Tamper-proof	Banking transactions

How Digital Signature Works (Basic Flow)

• Sender hashes the message
• Hash is encrypted using private key
• Receiver decrypts using public key
• Hash is compared

Digital Signature Formula

$$Signature=Encryp{t}_{PrivateKey}(Hash(Message))$$

Real-Life Applications

• Online banking
• E-tendering
• Income tax filing
• Software updates
• Legal documents

ElGamal Digital Signature Technique

What is ElGamal Digital Signature?

ElGamal is a public key digital signature algorithm based on the Discrete Logarithm Problem (DLP).

Security Basis

• Security relies on difficulty of solving:

$$g^x\mathrm{m}\mathrm{o}\mathrm{d}p$$

ElGamal Signature Components

Symbol	Meaning
p	Large prime number
g	Primitive root of p
x	Private key
y	Public key = g^x mod p
H(m)	Hash of message

ElGamal Signature Generation Steps

• Choose large prime p and generator g
• Select private key x
• Compute public key:

$$y=g^x\mathrm{m}\mathrm{o}\mathrm{d}p$$

• Choose random k such that gcd(k, p−1)=1

• Compute:

$$r = g^k \mod p$$

• Compute:

$$s=(H(m)-x\cdot r)\cdot k^{-1}\mathrm{m}\mathrm{o}\mathrm{d}(p-1)$$

Signature = (r, s)

ElGamal Signature Verification

Verify:

$$g^{H(m)}\equiv y^r\cdot r^s\mathrm{m}\mathrm{o}\mathrm{d}p$$

If true → signature valid.

Real-Life Use

• Secure email systems
• Digital certificates
• Basis for DSA

Digital Signature Standard (DSS)

What is DSS?

DSS (Digital Signature Standard) is a U.S. government standard published by NIST.

Algorithm Used

• DSA (Digital Signature Algorithm)
  (Based on ElGamal concept)

DSS Key Features

Feature	Description
Hash function	SHA-1 / SHA-2
Key type	Public key
Security base	Discrete logarithm
Usage	Digital signatures only

DSS Working (Simplified)

• Message hashed using SHA
• Signature generated using DSA
• Verification done using public key

DSS vs RSA

Feature	DSS	RSA
Purpose	Signature only	Encrypt + Sign
Speed	Faster signing	Faster verification
Security base	DLP	Factorization

Proof of Digital Signature Algorithm

What is Proof?

Proof shows that:

• Only sender could create signature
• Receiver can verify signature
• Signature cannot be forged

Proof Concept (Simplified)

Let:

$$S=Encryp{t}_{PrivateKey}(Hash(M))$$

Receiver computes:

$$Decryp{t}_{PublicKey}(S)$$

If:

$$Decryp{t}_{PublicKey}(S)=Hash(M)$$

Then:

• Message is authentic
• Signature is valid
• Sender cannot deny

Mathematical Proof (RSA-Based)

Encryption:

$$S=H(M{)}^d\mathrm{m}\mathrm{o}\mathrm{d}n$$

Verification:

$$H(M) = S^e \mod n$$

Since:

$$(d\cdot e)\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}\phi (n)$$

Correctness is guaranteed.

Why Digital Signature Is Secure

Reason	Explanation
Private key secrecy	Only owner can sign
Hashing	Message integrity
Public verification	Anyone can verify
Mathematical hardness	Cannot forge

Final Revision Table

Topic	Key Idea
Digital Signature	Authentication + Integrity
ElGamal Signature	DLP based
DSS	NIST standard
Proof	Mathematical correctness
Security	Non-repudiation

MCA Exam Writing Tips

• Start with definition
• Write algorithm steps
• Include formula
• Add real-life example
• Draw simple block diagram