3 credits, Fall semester 2008
Schedule of lectures: Tue (0200), Fri (0300)
Venue: Raman Hall, Sai Trinity Building
Course Objective
This course uncovers the mathematical foundations of Cryptography, the art and science of keeping/breaking secrets. The course aims to provide theory, algorithms and implementation of cryptographic techniques.
Course Evaluation
Mid semester examination: 25%
Project: 25%
End semester examination: 50%
Project involves computational implementation and a touch of research. Practice problems will be handed out in the class, but will not be graded. However, these practice problems will definitely give a flavor of the type of problems that will appear in the exams and the students are strongly encouraged to solve them.
Pre-requisites:
Enthusiasm to compute Greatest Common Divisor of two numbers and enjoying playing with numbers. Some basics of probability theory is desirable. Knowledge of algebra and number theory is not needed as the required basics will be taught in the course. Programming in MATLAB/C/JAVA/MATHCAD/FORTRAN/ANY-OTHER-COMP-LANG is needed for the computer project.
Textbook for the Course (available online):
1. “Handbook of Applied Cryptography” by A. Menezes, P. van Oorschot, S. Vanstone, CRC Press. All the chapters of this book are available online for free download: http://www.dms.auburn.edu/hac/ OR http://www.cacr.math.uwaterloo.ca/hac/
Reference Books:
1. “An Introduction to The Theory of Numbers” by Ivan Niven, Herbert S. Zuckerman and Hugh L. Montgomery, John Wiley and Sons Inc. (Chapters 1, 2 and 3 only)
2. “A First Course in Abstract Algebra” by John Fraleigh, Addison Wesley
3. “Topics in Algebra” by I. N. Herstein, 2nd edn., John Wiley and Sons Inc.
Popular Books (for fun reading):
1. “The Code Book” by Simon Singh
2. “The Codebreakers” By David Kahn
Classic papers in the subject (e-version will be distributed)
Shannon’s 1949 paper
Shamir's "How to share a secret"
Diffie Helman's paper "New directions in cryptography"
RSA paper
Vaidya and He paper on Chaotic Crypto
Quantum Crypto
Topics covered in the course:
1. The Origins/History of Cryptography
Pre-Shannon Cryptography
Post-Shannon or Modern Cryptography: Shannon's 1949 paper on Cryptography
The basic cryptographic system - definitions
Notion of Perfect Secrecy or Unconditional Security
Perfect Secrecy Systems (One Time Pads) - their strengths and drawbacks
Practical Cryptography and applications
2. A Brief Tour of Mathematical Foundations
Probability theory, Information theory, Computational Complexity definitions
Number Theory - Divisibility, GCD, euclidean algorithm, prime numbers, fundamental theorem of arithmetic, binomial theorem, congruences, solutions of congruences, Fermat’s Little Theorem, Euler’s Theorem, Wilson’s Theorem, Chinese Remainder Theorem, Prime Power Moduli, Hensel’s lemma, Prime Modulus, Primitive Roots and Power Residues, Quadratic Residues, Legendre Symbol, Quadratic Reciprocity, Gaussian Reciprocity Law, Jacobi Symbol, Euler Phi function, Prime numbers and Primality testing basics
Abstract Algebra - groups, normal subgroups, homomorphisms, integral domains, rings, fields, finite fields, polynomial rings, euclidean domain, Euclidean algorithm for polynomials, arithmetic of polynomials, Discrete logarithm problem, splitting fields, efficient algorithm implementation
3. Pseudo-random number generators (PRNGs)
Perfect randomness and Pseudo randomness, Statistical tests for randomness, Examples of PRNGs, Physical realization of RNGs
4. Private Key Cryptography
Stream ciphers - Classification, LFSRs, Berlekamp-Massey Algorithm, Nonlinear LFSRs, Block ciphers, Standards: DES, AES.
5. Public Key Crytography: Basics
Public key cryptosystems: RSA,Rabin, ElGammal, McEliece, Knapsack, Shamir's cryptanalysis of Knapsack, Probabilistic public key encryption, Elliptic Curve Cryptography (basics)
Secure Key Exchange and Secret Sharing: Diffie Helman key exchange algorithm, Shamir's secret sharing algorithm
6. Miscellaneous topics (Applied Cryptography)
Data origin authentication, identification, digital signatures, hash functions,
Zero Knowledge proofs
7. Cryptanalysis: Basics
Brute force attack, Linear cryptanalysis, Differential cryptanalysis, Statistical attacks, Known/chosen Plaintext attacks, Known/chosen plaintext-ciphertext pair attack, Side-channel attacks
8. Quantum Cryptography (a brief introduction) special lecture.
9. Chaotic Cryptography
A brief introduction to Chaos, Properties of Chaos and its relevance to Cryptography, Private and Public key Chaotic Cryptography, Pitfalls of Chaotic Cryptography, Future of Chaotic Cryptography