MTH332: An Introduction to Cryptography


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)

 

  1. Shannon’s 1949 paper
  2. Shamir's "How to share a secret" 
  3. Diffie Helman's paper "New directions in cryptography"
  4. RSA paper
  5. Vaidya and He paper on Chaotic Crypto
  6. 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