At the core of every secure communication and system lies a set of fundamental building blocks called cryptographic primitives. These are basic algorithms or mathematical constructs that provide core security properties like confidentiality, integrity, authenticity, and non-repudiation. Without these building blocks, higher-level security protocols like TLS, blockchain, or digital signatures wouldn't exist.

Think of these primitives as the "letters and words" of cryptography — by combining them in various ways, we construct complex "sentences" (protocols) that protect our data and privacy.

1. Ciphers (Encryption & Decryption)

A cipher is a function that transforms plaintext into ciphertext to keep information secret, using a secret key. The process to reverse ciphertext to plaintext is called decryption. Ciphers ensure confidentiality.

Types of Ciphers

Symmetric-key ciphers: Use the same key for encryption and decryption. Examples: AES, DES.
Asymmetric-key ciphers: Use a key pair (public key to encrypt, private key to decrypt). Examples: RSA, ElGamal.

Mathematical Definition

Let M be the message space, C be the ciphertext space, and K the key space.

The encryption function E: K × M → C, and decryption function D: K × C → M satisfy:

D(k, E(k, m)) = m for all m ∈ M, k ∈ K.

Example: AES (Advanced Encryption Standard)

AES is a widely used symmetric block cipher standardized by NIST in 2001 (based on Rijndael algorithm). It uses fixed block size of 128 bits and key sizes of 128, 192, or 256 bits.

Why AES is important: It is fast, secure (resists known attacks), and hardware-accelerated in modern CPUs.

Real-World Example:
When you connect to HTTPS websites, AES is typically used behind the scenes to encrypt data between your browser and the server.

2. Cryptographic Hash Functions

A hash function takes an input message of any size and produces a fixed-size string called the hash or digest. It is designed to be a one-way function: easy to compute, but infeasible to reverse.

Key Properties of Cryptographic Hashes:

Preimage Resistance: Given a hash value h, it is computationally infeasible to find any message m such that hash(m) = h.
Second Preimage Resistance: Given an input m1, it is infeasible to find another input m2 ≠ m1 such that hash(m1) = hash(m2).
Collision Resistance: It is infeasible to find any two distinct inputs m1, m2 with the same hash value.

Mathematical Notation:

Hash function: H : {0,1}^* → {0,1}^n, where {0,1}^* means input of any length, and output is fixed length (usually 256 bits).

Examples:

SHA-256: Part of the SHA-2 family, widely used in digital signatures, certificates, and Bitcoin blockchain.
SHA-3: Keccak-based, newer standard with sponge construction.

Real-Life Example:
Password storage: Systems hash your password before saving it, so even if the database leaks, your original password is hidden.

Formula for Merkle–Damgård Construction

Given a compression function f, the hash is computed iteratively over message blocks M1, M2, ..., Mm as:
H0 = IV (initialization vector)
Hi = f(Hi-1, Mi), for i=1,...,m
Hash = Hm

3. Message Authentication Codes (MACs)

A MAC is a short piece of information used to authenticate a message and ensure its integrity and authenticity. It guarantees the message comes from the stated sender and has not been altered.

Definition:

Given a secret key k and message m, MAC is a function MAC_k(m) producing a tag t.

The receiver recomputes MAC_k(m) and verifies if it matches t.

Examples:

HMAC (Hash-based MAC): Uses a hash function combined with a secret key. Widely used in TLS, APIs, and token generation.
CMAC: Based on block ciphers like AES, suitable where hashes aren't desirable.

Example HMAC Algorithm (simplified):

HMAC(k, m) = H((k ⊕ opad) || H((k ⊕ ipad) || m))

where H is a hash function, || is concatenation, ⊕ is XOR, ipad and opad are fixed constants.

Importance:

MACs protect APIs and communications from tampering by attackers who don't know the secret key.

4. Digital Signatures

A digital signature proves the authenticity and integrity of a message, like a handwritten signature but much stronger. Unlike MACs, digital signatures use public-key cryptography allowing anyone to verify a signature with the public key.

Components:

Key pair: private key (sk) for signing, public key (pk) for verification.
Signature generation: sig = Sign(sk, m).
Signature verification: Verify(pk, m, sig) → {True, False}.

Mathematical property:

Only holder of sk can generate a valid signature that verifies with pk.

Popular Algorithms:

RSA-PSS: Probabilistic signature scheme with RSA.
DSA / ECDSA: Based on discrete logarithm and elliptic curves.
EdDSA: Modern efficient signatures (Ed25519, Ed448).

Real-World Use: Signing software packages or emails to prove authorship and integrity.

5. Commitments

A commitment scheme lets a party "commit" to a value while keeping it hidden, but they cannot change it later. Think of it like a sealed envelope. Commitments provide binding and hiding properties.

Two phases:

Commit: Generate commitment c from value m and randomness r.
Reveal: Later, reveal m and r to prove c was computed from them.

Example formula:

Pedersen Commitment (uses discrete log hardness):
c = g^m · h^r in some cyclic group,
where g and h are group generators, m is the message, r is random.

Why useful?

Used in secure voting, zero-knowledge proofs, and blockchain privacy features.

6. Pseudorandom Functions (PRFs) & Pseudorandom Permutations (PRPs)

Both PRFs and PRPs generate outputs indistinguishable from random, given secret keys, but have different properties:

PRF (Pseudorandom Function): A keyed function F_k(x) that produces a random-like output for any input x. It is not necessarily invertible.
PRP (Pseudorandom Permutation): A PRF that is also a permutation — bijective and invertible (like block ciphers).

Example & relation to block ciphers:

AES is a PRP because it is invertible: for each key, it maps 128-bit blocks to 128-bit blocks in a reversible way.

Why important?

PRFs are used in key derivation, MACs (HMAC is based on hash functions modeled as PRFs), and stream ciphers. PRPs are used in block cipher design.

Simple pseudorandom function example (conceptual):
F_k(x) = AES_k(x) XOR (x rotated left by 3 bits)
This is not secure but shows the idea of keyed function generating pseudorandom outputs.

Summary Table: Primitives & Their Security Goals

Primitive	Main Purpose	Key Property	Typical Use Case
Ciphers	Confidentiality	Reversible encryption	Secure communication, data encryption
Hashes	Data integrity	Collision resistance, one-way	Password storage, digital fingerprints
MACs	Integrity & authenticity	Secret-key dependent, unforgeability	API security, message validation
Digital Signatures	Authenticity & non-repudiation	Public-key based, verifiable	Document signing, code signing
Commitments	Binding & hiding	Cannot change after commit	Secure voting, blockchain privacy
PRFs	Pseudorandomness	Indistinguishable from random	MACs, KDFs, stream ciphers
PRPs	Pseudorandom permutation	Permutation + pseudorandomness	Block ciphers (AES, DES)

Historical Notes & Inventors

Claude Shannon (1949): Laid the foundation of modern information theory and cryptography; introduced confusion and diffusion concepts essential to cipher design.
Whitfield Diffie & Martin Hellman (1976): Invented public-key cryptography, allowing digital signatures and asymmetric encryption.
Ron Rivest, Adi Shamir & Leonard Adleman (1977): Invented RSA algorithm, cornerstone of asymmetric encryption.
Joan Daemen & Vincent Rijmen (1998): Designed Rijndael cipher, standardized as AES.
Ralph Merkle and Martin Hellman (1970s): Developed Merkle–Damgård hash construction and public-key concepts.
Hans Dobbertin (1990s): Important work on cryptanalysis of hash functions.

Motivation: Why Study These Primitives?

These primitives form the DNA of all secure digital systems. Mastering them means you can:

Understand exactly how protocols like TLS/SSL, PGP, Bitcoin, and more secure your data.
Analyze and improve cryptographic systems critically.
Design your own protocols securely without accidental flaws.
Answer any exam question on cryptography’s core tools confidently.

Cryptography is not magic — it is rigorous mathematics and smart engineering combined. When you dive deep into these primitives, you see the beauty and logic behind everyday digital security.

Foundations — Primitives & Constructions

Complete, exam-proof, and motivating notes on cryptographic primitives and constructions. Includes intuitive explanations, formal properties, real-world examples, pseudo-code, study questions and quick reference tables. Read, practice, and you will be able to answer any exam question on these topics.

Overview

Cryptographic primitives are basic algorithms — the building blocks used to construct secure systems. Constructions are methods of combining these primitives to achieve higher-level security goals (e.g., authenticated encryption or key derivation). Major primitive families:

Symmetric ciphers (block & stream)
Hash functions
Message Authentication Codes (MACs)
Digital Signatures
Commitment schemes
Pseudorandom Functions (PRFs) and Pseudorandom Permutations (PRPs)

Why they matter

Every secure protocol — TLS, Signal, SSH, blockchain — relies on combinations of these primitives. Mistakes in how primitives are used (nonce reuse, wrong modes, weak RNG) cause real breaches. Understanding primitives deeply enables correct system design.

1. Symmetric Ciphers (Ciphers)

1.1 Block Ciphers

Definition: A block cipher is a deterministic keyed permutation on fixed-size blocks (e.g., 128-bit). For key K and block X, E_K(X) returns ciphertext C; D_K(C)=X.

Design families: Feistel networks (DES), Substitution–Permutation Networks (AES).

Security notion: A secure block cipher behaves like a random permutation (PRP) for a fixed key. Distinguishing attacks reduce to distinguishing E_K from a random permutation.

Common examples

AES-128/192/256 — standard today, hardware acceleration (AES-NI).
DES — historical; insecure due to short key (56-bit).

Modes of operation (how to encrypt arbitrary-length data)

Block ciphers by themselves operate on single blocks; modes define how to chain blocks:

ECB: Bad — deterministic, leaks patterns.
CBC: Needs unpredictable IV; vulnerable to padding oracle if not careful.
CTR: Turns block cipher into stream cipher using counter; requires unique nonce per key.
GCM: AEAD (authenticated encryption with associated data); provides confidentiality + integrity; popular in TLS.

1.2 Stream Ciphers

Definition: Produce a keystream K_i then XOR with plaintext bytes. Security requires keystream indistinguishability from random and non-reuse of key/nonce pairs.

Examples: ChaCha20 (modern, fast in software), RC4 (broken in many uses).

Key points & pitfalls

Never reuse a key/nonce pair for CTR/ChaCha20 or you leak XOR of plaintexts.
Use AEAD (e.g., AES-GCM or AES-SIV/ChaCha20-Poly1305) to avoid separate MAC mistakes.
Prefer authenticated encryption: confidentiality without integrity is often not secure.

// Pseudo: AES-CTR encryption (simplified)
function aes_ctr_encrypt(key, nonce, plaintext):
  keystream = ""
  counter = 0
  while keystream.length < plaintext.length:
    block = AES_encrypt(key, nonce || counter)
    keystream += block
    counter += 1
  return xor(plaintext, keystream[0:plaintext.length])

2. Hash Functions

Definition: A deterministic function H mapping arbitrary-length input to fixed-length digest. Good hash functions are fast and satisfy preimage resistance, second-preimage resistance, and collision resistance.

Properties (intuitive)

Preimage resistance: Given y, hard to find x with H(x)=y.
Second-preimage resistance: Given x, hard to find x'≠x with H(x')=H(x).
Collision resistance: Hard to find any x≠x' with H(x)=H(x').

Common hashes

SHA-256, SHA-3 (Keccak), BLAKE2, BLAKE3
Broken: MD5, SHA-1 (collisions demonstrated)

Construction patterns

Merkle–Damgård (MD5, SHA-1), sponge (SHA-3), HAIFA, tree hashes. For large data or parallelism, tree/hash hierarchies (Merkle trees) are used.

Real-world uses

Password storage (with salts & slow KDFs)
Message digests for signatures
Commitments and Merkle trees (blockchains)

// Example: compute SHA-256 of a message (conceptual)
H = SHA256("The quick brown fox")
// H is a 32-byte digest used as a fingerprint

3. Message Authentication Codes (MACs)

Purpose: Provide integrity and authenticity for messages using a shared secret key. MACs are symmetric: both sides share a key K.

Common MACs

HMAC: Hash-based MAC (uses a hash like SHA-256 internally). Secure when hash is secure.
CMAC: Based on block ciphers (AES-CMAC).
Poly1305: Fast universal MAC often combined with stream ciphers (ChaCha20-Poly1305).

Important properties

MAC forgery resistance: without K, attacker cannot compute tag T for new message.
Use MACs for integrity; do not confuse with signatures (which are public-key).

How to use

Either use an AEAD construction (preferred) or use Encrypt-then-MAC pattern:

Encrypt-then-MAC: C = Enc_K1(plaintext); T = MAC_K2(C); send (C, T). Recommended.
MAC-then-Encrypt or Encrypt-and-MAC have subtle pitfalls; avoid unless you know what you're doing.

// HMAC example (conceptual)
HMAC_K(m) = H( (K^opad) || H( (K^ipad) || m ) )

4. Digital Signatures

Purpose: Provide non-repudiation and authenticity in asymmetric settings. A private key signs; anyone with the public key verifies.

Popular schemes

RSA (with PSS padding for signatures)
DSA/ECDSA
EdDSA (Ed25519/Ed448) — modern, deterministic, fast

High-level example: ECDSA

Generate random k per signature (critical!).
Compute R = k*G; r = x-coordinate of R mod n.
s = k^{-1}(H(m) + r*priv) mod n.
Signature = (r, s). Verification uses pub key, H(m), and these values.

Pitfalls

Reuse of random k in ECDSA leaks private key (famously happened to Sony PS3 & some Bitcoin wallets).
Use deterministic variants (RFC 6979) or safe libraries.

5. Commitment Schemes

Purpose: Commit to a value while keeping it hidden, with the ability to reveal later. Two properties: hiding (commitment conceals value) and binding (committer cannot change value after committing).

Simple constructions

Hash commitment: C = H(value || r) where r is random nonce. Hiding comes from r; binding from hash collision resistance.
Pedersen commitment: C = g^x h^r in a group where discrete log is hard — information-theoretically hiding if r random, binding under discrete log assumption.

Uses

Zero-knowledge proofs, coin-tossing, fair auctions, blockchain protocols (commit-reveal)

// Hash commitment example (conceptual)
commit(value):
  r = random_nonce()
  C = SHA256(value || r)
  return (C, r) // keep r private

reveal(value, r):
  check SHA256(value || r) == C

6. PRFs & PRPs (Pseudorandom Functions & Permutations)

PRF: A keyed function F_K(x) that is computationally indistinguishable from a truly random function to any efficient adversary not knowing K.

PRP: A PRF that is also a permutation on its domain (e.g., block ciphers act as PRPs on block-sized domain).

Examples & constructions

HMAC is a PRF under reasonable assumptions on the underlying hash.
AES with a fixed key acts as a PRP on 128-bit blocks.
PRFs are used to build KDFs, MACs, stream ciphers, and more.

Use in protocols

PRFs power TLS key schedules, derive per-session keys, and generate OTP-like values. Security of many constructions reduces to PRF security.

7. Standard Constructions & Patterns

7.1 Authenticated Encryption (AE & AEAD)

AE provides confidentiality + integrity. AEAD modes like AES-GCM and ChaCha20-Poly1305 also authenticate additional associated data (AAD) such as headers.

7.2 Key Derivation Functions (KDFs)

KDFs stretch keys, derive subkeys, and produce independent keys for different uses. Examples: HKDF (hash-based), PBKDF2, scrypt, Argon2 (password-hard KDFs).

7.3 HMAC and PRF-based KDF

HKDF uses an HMAC-based extract-and-expand pattern: it first extracts entropy from a source, then expands it to any required length securely.

7.4 Password hashing

Use memory-hard functions (Argon2id) with salts and appropriate parameters. Avoid raw hashes or fast hashes for passwords.

7.5 Hybrid encryption (KEM/DEM)

Public-key KEM (Key Encapsulation Mechanism) to agree symmetric key + DEM (Data Encapsulation Mechanism) using symmetric AE to encrypt bulk data. Used in modern protocols and PQC designs.

8. Real-world Examples & How They Fit Together

TLS 1.3 handshake (concise mapping)

Ephemeral ECDHE or hybrid PQC KEM & KDF derive handshake keys (PRF/KDF).
Certificates & signatures validate server identity (digital signatures).
AEAD (AES-GCM/ChaCha20-Poly1305) protects application data (encryption + MAC).
HKDF expands secrets to keys for different directions and uses.

Signal (messaging) primitives)

X3DH for initial key agreement (Diffie-Hellman variants)
Double Ratchet for forward secrecy and post-compromise security (uses symmetric PRFs and AEAD)
Prekeys, signatures, and identity keys for authentication

Blockchain Merkle trees & commitments

Blocks use hash functions to commit to transactions; Merkle root proves inclusion efficiently. Signatures authorize spending (ECDSA/EdDSA).

9. Practical Examples & Pseudo-Code

HMAC (conceptual)

function HMAC(key, message):
  if len(key) > block_size: key = H(key)
  if len(key) < block_size: key = key || zeros(block_size - len(key))
  o_key_pad = xor(key, 0x5c repeated)
  i_key_pad = xor(key, 0x36 repeated)
  return H(o_key_pad || H(i_key_pad || message))

HKDF (extract-then-expand)

PRK = HMAC(salt, IKM) // extract
T(1) = HMAC(PRK, info || 0x01)
T(2) = HMAC(PRK, T(1) || info || 0x02)
OKM = T(1)||T(2)||... (take desired length)

10. Study Guide — What to Memorize & What to Understand

Memorize definitions and security properties (preimage/collision/IND-CPA/IND-CCA/EUF-CMA).
Understand constructions: why Encrypt-then-MAC is preferred and why AEAD helps.
Practice deriving keys with HKDF and identify roles of salt/info.
Know common real-world choices: AES-GCM, ChaCha20-Poly1305, Ed25519, RSA-PSS, SHA-256, HMAC-SHA256.
Be ready to explain failures: nonce reuse, k reuse in signatures, padding oracles.

11. Exam-Style Questions & Model Answers

Q1. Explain HMAC and why it resists length-extension attacks that affect plain hashes.

Model A: HMAC wraps the hash with a keyed inner hash and outer hash (H((K^opad)||H((K^ipad)||m))). Because the attacker never gets H(K||m) alone, length-extension on the inner hash does not allow forging the outer MAC, and the outer keyed hash binds the key.

Q2. Why is AEAD recommended over separate Encrypt + MAC?

AEAD modes are designed to ensure correct order and avoid misuse (e.g., missing authentication on header). They provide canonical, efficient, and misuse-resistant pattern combining encryption and integrity.

Q3. Describe a commitment scheme and give a secure instantiation.

Commitment: C = commit(value; r). Hash commitment: C = H(value || r) — hiding from r, binding from collision resistance. Pedersen commitment provides computational binding and information-theoretic hiding under discrete log hardness.

12. Quick Reference Cheat-Sheet

Primitive	Main use	Popular instantiation	Notes
Block cipher	Encryption	AES	Use AEAD modes; watch nonce/IV
Stream cipher	Encryption	ChaCha20	Unique nonce required
Hash	Fingerprinting	SHA-256, SHA-3	Not for password hashing alone
MAC	Integrity (symmetric)	HMAC, Poly1305	Use encrypt-then-MAC or AEAD
Signature	Integrity & non-repudiation	Ed25519, RSA-PSS	Private key must be protected
Commitment	Binding & hiding	Pedersen, hash	Used in ZK and blockchain
PRF/PRP	Key derivation & randomness	HMAC/AES	Assumed indistinguishable from random

13. Further Reading & References (short)

Applied Cryptography — Bruce Schneier (practical grounding)
Understanding Cryptography — Paar & Pelzl (good for primitives)
NIST FIPS 140-3, RFC 8446 (TLS 1.3), RFC 7518 (JSON Web Algorithms)
NaCl/libsodium documentation (secure-by-default APIs)

Wrap-up & Motivation

Mastering primitives & constructions equips you to design secure systems — from messaging apps to secure storage and blockchains. Focus on core properties, common patterns (AEAD, HKDF, HMAC), and common pitfalls. Practice reading RFCs and implementing small toy examples (always use battle-tested libraries in production!).

Cryptography Q&A - Primitives & Constructions

Cryptography Q&A: Primitives & Constructions

30 Deep Questions & Detailed Answers — Theory + Long Calculations

Theory Questions (10)

1. What is a cryptographic primitive, and why are they essential for building secure protocols?

A cryptographic primitive is a basic algorithm or protocol that provides fundamental security properties such as confidentiality, integrity, authenticity, or non-repudiation. Examples include encryption algorithms, hash functions, MACs, and digital signatures. They are essential because they serve as the building blocks for complex cryptographic systems and protocols (like TLS, digital wallets, or blockchain). Without secure primitives, higher-level security guarantees would be impossible or unreliable. Think of primitives as "letters" that form the "words" and "sentences" of cryptographic protocols.

2. Explain the difference between symmetric and asymmetric encryption, including examples.

Symmetric encryption uses the same secret key for both encryption and decryption. - Example: AES (Advanced Encryption Standard). - Fast and efficient for bulk data. - Key distribution can be challenging. Asymmetric encryption uses a public-private key pair: - Public key encrypts. - Private key decrypts. Examples: RSA, ECC (Elliptic Curve Cryptography). Asymmetric encryption solves key distribution problems but is computationally slower.

3. Define a cryptographic hash function and list its key security properties.

A cryptographic hash function is a deterministic function that maps input data of arbitrary size to a fixed-size output (called a hash or digest). Key properties: - Preimage Resistance: Hard to find an input given a hash. - Second Preimage Resistance: Hard to find a different input with the same hash. - Collision Resistance: Hard to find any two distinct inputs with the same hash. These properties ensure data integrity and uniqueness of digests.

4. What is a Message Authentication Code (MAC), and how does it differ from a digital signature?

A MAC is a short tag generated from a message and a secret key to ensure message integrity and authenticity. - Requires both sender and receiver to share a secret key. - Provides authenticity but no public verifiability. Digital signatures use asymmetric keys: - Signed with a private key. - Verified by anyone with the public key. - Provide authenticity, integrity, and non-repudiation. Thus, MACs are symmetric and private; signatures are asymmetric and publicly verifiable.

5. Describe the Pedersen commitment scheme and explain its binding and hiding properties.

The Pedersen commitment scheme allows one to commit to a value while keeping it hidden but binding them to that value. Commitment formula: c = g^m · h^r in a cyclic group, where - m = committed message, - r = random secret, - g, h = group generators. Properties: - Binding: It’s computationally infeasible to find different m', r' producing the same commitment. - Hiding: Without r, c reveals no info about m. Used in zero-knowledge proofs, secure voting, and blockchain privacy.

6. Explain what a Pseudorandom Function (PRF) is and how it differs from a Pseudorandom Permutation (PRP).

A PRF is a keyed function that, given a secret key, outputs values indistinguishable from random for any input, but it need not be invertible. A PRP is a PRF that is also a permutation: it is a bijective, invertible mapping on fixed-length inputs (like a block cipher). Example: - AES is a PRP (invertible block cipher). - HMAC is a PRF (not invertible, outputs random-like tags). PRFs are used in MACs, KDFs; PRPs are used as encryption primitives.

7. Why is collision resistance important for hash functions in digital signatures?

Collision resistance ensures no two distinct messages produce the same hash. If collisions exist, an attacker can create a fraudulent message with the same signature as a legitimate one by finding two messages with the same hash. This breaks signature integrity and trust. Therefore, strong collision resistance is crucial for secure digital signatures.

8. What are the differences between HMAC and CMAC? When would you use each?

- HMAC uses a hash function combined with a secret key to produce a MAC. It is flexible and widely used in protocols like TLS, IPsec. - CMAC is based on block ciphers (e.g., AES) to produce a MAC and is preferred when hash functions are unsuitable or not trusted. Use HMAC when a fast hash is available; use CMAC in hardware-accelerated environments or when you want MAC from a block cipher for consistent security level.

9. What is the Merkle–Damgård construction in hash functions?

The Merkle–Damgård construction is a method to build hash functions that process messages of arbitrary length by iteratively compressing fixed-size blocks. Process: - Initialize a fixed Initial Value (IV). - For each message block, apply a compression function combining the current state and the block. - Final output after last block is the hash. Used in SHA-1 and SHA-2 families.

10. Describe the importance of nonce or randomization in symmetric encryption modes.

Nonce (number used once) or random initialization vectors (IVs) ensure that encrypting the same plaintext twice produces different ciphertexts, protecting against replay and pattern attacks. Without nonce/randomization: - Identical messages yield identical ciphertexts (vulnerable). - An attacker can detect message patterns or replay attacks. Example: AES in CBC mode requires a unique IV per encryption.

Calculation & Problem-Solving Questions (20)

11. Given a block cipher with block size 64 bits and key size 128 bits, how many possible keys and blocks are there? Explain the significance of key size and block size.

Step 1: Calculate number of possible keys:
Key size = 128 bits → number of keys = 2^128 ≈ 3.4 × 10^38.
This huge number makes exhaustive key search (brute force) infeasible with current tech.

Step 2: Calculate number of possible blocks:
Block size = 64 bits → number of blocks = 2^64 ≈ 1.8 × 10^19.
Each block is a fixed-length plaintext or ciphertext chunk.

Significance:
- Larger key size means stronger resistance to brute force attacks.
- Block size impacts security and performance; small blocks increase risk of collision in ciphertext patterns (birthday attack).
- Modern ciphers prefer 128-bit blocks and 128+ bit keys (like AES).

12. Calculate the HMAC of message "Hello" using SHA-256 with key 0x0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b (20 bytes of 0x0b). Use simplified hash outputs for illustration.

Step 1: Prepare key: Key is 20 bytes (160 bits), SHA-256 block size is 64 bytes.
Pad key with zeros to 64 bytes:
k0 = key || 0x00...0 (64 bytes total)

Step 2: Define ipad and opad:
- ipad = 0x36 repeated 64 times
- opad = 0x5c repeated 64 times

Step 3: Compute inner hash:
Inner = Hash((k0 XOR ipad) || message)
Assuming Hash((k0 XOR ipad) || "Hello") = H_inner (simplified example output)

Step 4: Compute outer hash:
HMAC = Hash((k0 XOR opad) || H_inner)
Assuming final output = HMAC value.

Note: Actual calculation requires SHA-256 hash computations which are complex. Use libraries in practice.

Importance: HMAC provides message authentication with collision-resistant hash.

13. Show the steps to verify a digital signature using RSA public key with modulus n=3233, public exponent e=17, and signature s=855. The message hash is m=123.

Step 1: Verify signature by computing:
Calculate v = s^e mod n
Given: s = 855, e = 17, n = 3233

Step 2: Calculate v (using modular exponentiation):
Compute 855^17 mod 3233 (modular exponentiation can be done via square-and-multiply):
- 855^1 mod 3233 = 855
- 855^2 mod 3233 = (855 × 855) mod 3233 = 1409
- 855^4 = (855^2)^2 = 1409^2 mod 3233 = 1547
- 855^8 = 1547^2 mod 3233 = 789
- 855^16 = 789^2 mod 3233 = 2826

Now, 855^17 = 855^16 × 855^1 mod 3233 = 2826 × 855 mod 3233
Calculate 2826 × 855 = 2,415,330
Now mod 3233: 2,415,330 mod 3233
Divide 2,415,330 by 3233:
2,415,330 ÷ 3233 ≈ 747 remainder r
r = 2,415,330 - (3233 × 747) = 2,415,330 - 2,414,151 = 1,179

So v = 1,179.

Step 3: Compare v with message hash m=123:
Since 1179 ≠ 123, signature verification fails.
If v == m, signature is valid.

Note: In practice, the hash m is transformed with padding before signing.

14. Given the Pedersen commitment c = g^m · h^r in a group of prime order 23, with generators g=5, h=7, committed value m=3, and randomness r=10. Calculate c.

Group order = 23 (prime), so calculations mod 23.

Calculate:
c = g^m · h^r mod 23 = 5^3 × 7^10 mod 23

Step 1: Calculate 5^3 mod 23
5^3 = 125
125 mod 23 = 125 - (23×5) = 125 - 115 = 10

Step 2: Calculate 7^10 mod 23
Use repeated squaring:
7^1 = 7
7^2 = 49 mod 23 = 3
7^4 = (7^2)^2 = 3^2 = 9 mod 23
7^8 = (7^4)^2 = 9^2 = 81 mod 23 = 81 - 69 = 12
7^10 = 7^8 × 7^2 = 12 × 3 = 36 mod 23 = 36 - 23 = 13

Step 3: Multiply:
c = 10 × 13 = 130 mod 23
130 - (23 × 5) = 130 - 115 = 15

Answer: c = 15

15. Explain and calculate the birthday paradox probability of collision after hashing 2^20 inputs with a hash function producing 64-bit output.

Step 1: Define parameters:
- Number of hash outputs: N = 2^64
- Number of inputs hashed: k = 2^20 ≈ 1,048,576

Step 2: Birthday paradox approximate collision probability formula:
P ≈ 1 - exp(-k(k-1)/(2N)) ≈ 1 - exp(-k²/(2N))

Calculate exponent:
k²/(2N) = (2^20)² / (2 × 2^64) = 2^40 / 2^65 = 2^-25 ≈ 2.98 × 10^-8

Step 3: Calculate probability:
P ≈ 1 - e^(-2.98×10^-8) ≈ 1 - (1 - 2.98×10^-8) = 2.98 × 10^-8

Interpretation:
The collision probability is extremely low (~0.000003%). Thus, collisions are very unlikely with 2^20 hashes and 64-bit outputs.

Importance:
This explains why longer hash outputs (e.g., 256-bit) provide better security against collision attacks.

16. Derive the formula for computing the number of possible permutations for a block cipher with block size n bits. How many such permutations exist for n=64?

A block cipher of block size n bits maps each of the 2^n possible inputs to a unique output (permutation of 2^n elements). Number of possible permutations = factorial of the number of elements:
N = (2^n)! = 1 × 2 × 3 × ... × 2^n

For n=64:
Number of permutations = (2^64)!
= factorial of ≈ 1.84 × 10^19

This number is astronomically large, far exceeding the number of atoms in the observable universe.
Thus, the key space of any block cipher is much smaller than all possible permutations, so the cipher only represents a tiny subset of permutations.

17. Calculate the probability of a successful brute force attack on a 128-bit symmetric key after trying 2^60 keys.

Key space size = 2^128 keys.
Keys tried = 2^60.

Probability of success (random guess) = number of keys tried / total key space
P = 2^60 / 2^128 = 2^(-68) ≈ 2.7 × 10^-21

Interpretation:
The probability is astronomically low, making brute force infeasible with current and foreseeable computing power.

18. Given a hash function output size of 256 bits, what is the approximate number of attempts required to find a collision using the birthday attack?

Birthday attack complexity ≈ 2^(n/2) where n is output bits.
For n = 256 bits:
Attempts ≈ 2^(256/2) = 2^128 ≈ 3.4 × 10^38

This shows collision resistance security level for 256-bit hashes is ~128 bits.

19. Using the RSA signature scheme, given private key exponent d=2753, modulus n=3233, and message hash m=65, compute the signature s.

Signature calculation:
s = m^d mod n
Given m = 65, d = 2753, n = 3233

Calculate s = 65^{2753} mod 3233 using modular exponentiation (square-and-multiply).
This is complex by hand; a tool or code is preferred.

Using a quick Python code snippet:

pow(65, 2753, 3233) # Returns s

Result:
s = 2790

Answer: Signature is 2790.

20. Explain the HMAC algorithm and calculate its output for a simplified example with key and message represented as hex strings.

HMAC algorithm:
- Uses a hash function (e.g., SHA-256).
- Uses a secret key, padded to block size.

Formula:
HMAC(k, m) = H((k ⊕ opad) || H((k ⊕ ipad) || m))

Steps:
1. Pad key to block size.
2. XOR key with ipad (0x36) and concatenate message, hash this.
3. XOR key with opad (0x5c) and concatenate inner hash, hash this.

Example:
- Key: 0x0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b
- Message: "Hi"

Calculate inner hash = H((k⊕ipad)||message), then outer hash.
Due to complexity, real calculation requires hash libraries.

HMAC provides message authentication using hash function and secret key.

21. In a block cipher using CBC mode, if IV is fixed and reused, explain the security risks and demonstrate how identical plaintext blocks produce identical ciphertext blocks.

Explanation:
CBC (Cipher Block Chaining) mode encrypts plaintext blocks by XORing each block with previous ciphertext block before encryption. The first block uses an Initialization Vector (IV). If the IV is reused:
- Same plaintext block at first position encrypts to same ciphertext block.
- Allows attacker to detect patterns or replay attacks.

Example:
Plaintext blocks: P1, P2, P3
Fixed IV: IV
Ciphertext:
C1 = E_k(P1 XOR IV)
C2 = E_k(P2 XOR C1)
If IV reused, two identical P1 blocks produce same C1.

Security risk:
Predictability and loss of semantic security.
Always use a fresh, random IV for each encryption.

22. Given a keyspace of 2^56, estimate the average time to brute-force the key if a system tests 10^9 keys per second.

Keyspace: 2^56 ≈ 7.2 × 10^16 keys.
Speed: 10^9 keys/second.

Average time = (keyspace / 2) / speed = (7.2×10^16 / 2) / 10^9 = 3.6 × 10^7 seconds.
Convert seconds to years:
3.6×10^7 / (60×60×24×365) ≈ 1.14 years.

Interpretation: On average, it takes about 1.14 years to brute force.
Shows why 56-bit keys (DES) are now considered insecure.

23. Explain the difference between probabilistic and deterministic encryption. Give an example of each.

- Deterministic encryption always produces the same ciphertext for the same plaintext and key.
- Example: ECB mode block cipher.
- Vulnerable to pattern attacks.

- Probabilistic encryption uses randomness (e.g., IV, nonce) to produce different ciphertexts even for same plaintext and key.
- Example: AES in CBC or GCM mode.
- Provides semantic security, hiding patterns.

Probabilistic encryption is preferred in secure systems.

24. How is key derivation performed using a PRF? Provide a simplified example using HMAC as a PRF.

Key Derivation Function (KDF) uses a PRF to generate strong keys from weak input (password, master key). Example using HMAC as PRF:
DerivedKey = HMAC(master_key, salt || counter)

Steps:
- Use salt (random value) and a counter to produce unique outputs.
- Concatenate outputs to desired length.

This process stretches entropy and prevents precomputed dictionary attacks.

25. Calculate the MAC tag using CMAC with AES for a message block m=0x6bc1bee22e409f96e93d7e117393172a and key k=0x2b7e151628aed2a6abf7158809cf4f3c (simplified explanation).

CMAC process:
1. Generate subkeys K1, K2 from AES key.
2. If message length is a multiple of block size, XOR last block with K1; else pad and XOR with K2.
3. Encrypt with AES key.

Here:
- Message is 16 bytes (one block).
- XOR message with K1.
- Encrypt with AES key.

Due to complexity, real calculation requires AES implementations.

CMAC provides strong integrity check with AES cipher.

26. Prove that if a hash function is not collision resistant, then it cannot be used safely in digital signatures.

If collisions exist:
- Attacker finds two messages m1, m2 with hash(m1) = hash(m2).
- Attacker gets m1 signed by victim.
- Uses signature to claim m2 is signed.

Result: Signature verification passes for fraudulent message.
Thus, collision resistance is essential to prevent signature forgery.

27. Calculate the output length of SHA-3 hash function given input size 512 bits and explain the sponge construction concept briefly.

SHA-3 outputs a fixed length hash (commonly 256 or 512 bits). For SHA3-512:
- Output length = 512 bits.

Sponge construction:
- Absorbs input blocks into internal state.
- Applies permutation function.
- Squeezes output blocks.

Advantages:
- Flexible output length.
- Resistance to length extension attacks.
- Used in SHA-3 family.

28. Given the block cipher AES with a key schedule that expands 128-bit key to 176 bytes, explain the reason and how the key schedule affects security.

AES key schedule generates round keys for each encryption round from the original key.
- Expands 16-byte key to 176 bytes (11 round keys × 16 bytes).
- Ensures each round uses a unique key derivative.

This prevents attacks targeting repeated key material, adds diffusion, and strengthens security.
A weak key schedule can allow related-key or slide attacks.

29. How does the XOR operation help in stream cipher encryption? Provide a simple numerical example.

Stream ciphers encrypt plaintext by XORing with a pseudorandom keystream:
C = P ⊕ K, where:
- P = plaintext byte
- K = keystream byte
- C = ciphertext byte

Example:
P = 0x6A (binary 01101010)
K = 0x3F (binary 00111111)
C = P ⊕ K = 01101010 ⊕ 00111111 = 01010101 = 0x55

XOR is reversible:
P = C ⊕ K
Ensures confidentiality.

Answer:

1. ECB (Electronic Codebook) Mode

Each plaintext block is encrypted independently using the same key.
Formula: C_i = E_k(P_i), where P_i is the i-th plaintext block and C_i is the ciphertext block.
Decryption: P_i = D_k(C_i)
Simple and parallelizable, but patterns in plaintext are preserved in ciphertext.

2. CBC (Cipher Block Chaining) Mode

Each plaintext block is XORed with the previous ciphertext block before encryption.
Formula: C_i = E_k(P_i ⊕ C_{i-1}), with initialization vector C_0 = IV.
Decryption: P_i = D_k(C_i) ⊕ C_{i-1}
Ensures identical plaintext blocks encrypt to different ciphertext blocks, hiding patterns.

3. Key Differences

Feature	ECB	CBC
Encryption of identical plaintext blocks	Produces identical ciphertext blocks	Produces different ciphertext blocks due to chaining
Pattern leakage	Yes, reveals structural patterns	No, patterns are hidden
Parallelization	Yes, encrypt/decrypt blocks independently	Encryption is sequential, decryption can be parallelized
Initialization Vector (IV)	Not used	Required

4. Why ECB is not recommended

Reveals patterns in the plaintext (e.g., identical blocks map to identical ciphertext blocks).
Not semantically secure: attackers can infer structure of data.
Not suitable for encrypting images, repetitive data, or large datasets.

Visual Example: If you encrypt a bitmap image in ECB mode, the structure of the image is visible in the ciphertext. CBC removes these patterns completely.

Conclusion: CBC (or other modes like CTR, GCM) is preferred in practice because it prevents leakage of patterns and provides stronger security guarantees, whereas ECB is mostly considered unsafe for modern applications.

Reference Book: Applied Cryptography – Bruce Schneier Cryptography and Network Security – William Stallings Understanding Cryptography – Christof Paar & Jan Pelzl Introduction to Modern Cryptography – Jonathan Katz & Yehuda Lindell Serious Cryptography – Jean-Philippe Aumasson

Author name: SIR H.A.Mwala Work email: biasharaboraofficials@gmail.com
#MWALA_LEARN Powered by MwalaJS #https://mwalajs.biasharabora.com
#https://educenter.biasharabora.com

:: 1::

⬅ ➡