Loading...
Development

Module 135

Here’s a concise, exam-oriented explanation of Unit II — Mathematical Foundations and Public Key Cryptography. This is structured exactly how toppers revise before exams — only high-weightage concepts, important theorems, formulas, and what examiners love to ask.

1. Mathematical Background (Very Important for Theory + Numerical)

A. Group, Ring, Field, Finite Field GF(p)

  • Group: Set + operation (closed, associative, identity, inverse)
  • Field: Ring with every non-zero element having multiplicative inverse
  • GF(p): Finite field where p is prime. Total elements = p. All operations modulo p.
  • Exam Tip: Always write 4 properties of group and 2 extra for field.

B. Modular Arithmetic (Most Frequently Asked Numericals)

  • (a + b) mod m, (a − b) mod m, (a × b) mod m
  • Very Important: a^(b) mod m → use Modular Exponentiation (Square & Multiply method) → 4–8 marks question guaranteed.

C. Prime & Relatively Prime

  • Two numbers are relatively prime if gcd(a, b) = 1

D. Extended Euclidean Algorithm (8–10 marks question almost every year)

  • Finds gcd(a, b) AND x, y such that ax + by = gcd(a, b)
  • Must know how to write full table and back-substitution
  • Used in RSA for finding private key d

Example expected in exam: Find inverse of 7 modulo 26 → Use Extended Euclidean → Answer: 15 (because 7×15 = 105 = 4×26 +1)

2. Modern Cryptography (Theory + Some Numerical)

A. Fermat’s Little Theorem (Very Important)

  • If p is prime and gcd(a, p) = 1 → a^(p-1) ≡ 1 mod p
    OR a^(p) ≡ a mod p
  • Used for primality testing and finding inverses

B. Euler’s Theorem (Important)

  • If gcd(a, n) = 1 → a^φ(n) ≡ 1 mod n
  • φ(n) = n(1−1/p1)(1−1/p2)... → Euler’s Totient Function
  • RSA is completely based on this

C. Chinese Remainder Theorem (CRT) (5–6 marks)

  • If m1, m2, ..., mk pairwise coprime, then system of congruences has unique solution modulo M = m1m2...mk
  • Frequently asked with RSA (when n = p×q)

D. Discrete Logarithm Problem (DLP)

  • Hard problem → base of Diffie-Hellman, ElGamal
  • "Finding g^x mod p = h → find x" is hard → security of many schemes

E. Primality Testing

  • Fermat Test (probabilistic)
  • Miller-Rabin (most used in practice)

F. AES (Only high-level for exams)

  • Block size: 128 bits
  • Key sizes: 128, 192, 256 → rounds: 10, 12, 14
  • 4 steps per round: SubBytes → ShiftRows → MixColumns → AddRoundKey
  • Last round: No MixColumns
  • Exam: Mostly theory (rarely internal details)

3. Public Key Cryptography (HEART OF THE UNIT — 50% weightage)

A. Principles of Public Key Cryptography

  • Two keys: Public (e, n) → encrypt, Private (d, n) → decrypt
  • Trapdoor one-way function
  • Requirements:
    1. Easy to generate keys
    2. Easy to encrypt with public, decrypt with private
    3. Hard to find private key from public

B. RSA Algorithm (15–20 marks question guaranteed)

Key Generation:

  1. Choose two large primes p, q
  2. n = p × q
  3. φ(n) = (p−1)(q−1)
  4. Choose e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1 (common e = 65537)
  5. Find d such that e × d ≡ 1 mod φ(n) → use Extended Euclidean
  6. Public key: (e, n) | Private key: d

Encryption: c = m^e mod n
Decryption: m = c^d mod n

Why it works?
Because m^(e×d) = m^(k×φ(n) + 1) = (m^φ(n))^k × m ≡ 1^k × m ≡ m mod n (by Euler’s theorem)

C. Security of RSA

  • Depends on difficulty of factoring n into p and q
  • Attacks:
    • Brute force factoring
    • Fermat’s factorization (if p and q close)
    • Pollard’s Rho
    • If d is small → Wiener’s attack
    • If e is small and m small → Coppersmith attack
  • Common modulus attack, chosen ciphertext attack

Most Expected Exam Questions (Practice These 100%)

Theory (5–8 marks each):

  1. Explain working of RSA with example (full steps)
  2. State and prove Euler’s theorem
  3. Differences between symmetric and asymmetric cryptography
  4. Explain Extended Euclidean algorithm with example
  5. What is Discrete Logarithm Problem? Why is it hard?

Numerical (8–15 marks):

  1. Perform encryption/decryption using RSA (small numbers)
  2. Find multiplicative inverse using Extended Euclidean
  3. Solve system using Chinese Remainder Theorem
  4. Modular exponentiation: 7^59 mod 13 (use square & multiply)
  5. Full RSA key generation given p=11, q=17, e=7 → find d, encrypt 5, decrypt

Quick Revision Checklist Before Exam

  • Extended Euclidean table
  • RSA full example (p=3, q=11 or p=7, q=13)
  • Fermat vs Euler theorem
  • φ(n) calculation for n=pq
  • One Chinese Remainder Theorem problem
  • AES round structure diagram

This unit has 60–70% numerical + 30–40% theory. Master RSA and Extended Euclidean → you’ll easily score 80%+.

All the best! You got this! 🚀