Home‎ > ‎

CS 428: Applied Cryptography (Sem II of 2015-16)



Time span: Dec 31, 2015 to April 28, 2016

Instructor: Souradyuti Paul (Office hrs: Tue & Th. 5:45 to 6:30pm in faculty lounge@palaj, or by appointment, Office: S5-324)

Goals and coverage: Cryptography deals with the techniques of secret writing. Some of the basic goals of the subject are data confidentiality, data integrity and entity authentication. This course covers a fair number of basic algorithms achieving these goals; some of them are quite well-known and used in practice (DES, RSA, HMAC and DSA, to name a few). These algorithms are taught with examples, home assignments and exercises, where sufficient care is given to the details. We also study the security properties of these algorithms at some depth; however, a full and rigorous mathematical analyses of the security properties are beyond the scope of this course. It is our hope that a student will be able to pursue any advanced study/course/research in cryptography after attending this course. For details of the course coverage read this.   

Lecture times: Tue & Th. 6:30 to 8:00pm, Room: 7/105@palaj

Group email: 2016-CS428.pvtgroup@iitgn.ac.in  (private group, reg. required)

Teaching assistant: Sudhakar Kumawat & Ananya Shrivastava (office hours by appointment)

Main textbook: 
- Cryptography: Theory and Practice, D. Stinson, 3rd Edition

Additional reference books:
- Handbook of Applied Cryptography, A.J.Menezes, P.V. Oorschot and S.Vanstone 
  (available online freely)
- Cryptography and Network Security, W. Stallings (5th Edition)

Target audiences: B.Tech (third/fourth year), M.Tech/M.Sc and PhD

Pre-requisites: 
- CS 321 (Algorithm analysis and design)
- MA 101, 102, 201 and 202 (for mathematical maturity)
- ES 102 (Introduction to computing) or ES 112 (Computing)
- At least one CS project 
- Some familiarity with prime/composite numbers
- Absence of hatred/fear of math

Total course credits: 4

Schedule:                     
 Lect
   #.		  Day  Date  Topics, lecture notes and further reading*  Home assignments**  Practice Problems***
 1  Th  31/12  Admin info. and introduction    
 2  Tu   5/1 Introduction (cont.): Shift cipher, (bad) multiplicative cipher  
 3  Th   7/1 (Good) multiplicative cipher: Note 1, Note 2
Th: mod inverse exists if and only if gcd=1		    
 4  Tu  12/1  Euclid's algos. for GCD and modular inverse  HA1  Problem set 1
 5  Tu  19/1 Computing phi(N), where N = p x q (Class note 1) 
       Algebraic proof:
          Ingredient 1: bijection from Z_N*--> Z_p* x Z_q*
Ingredient 2: Chinese remainder th. (Ch. 5.2.2)
      Combinatorial proof: inclusion-exclusion
    
 6  Th  21/1 Polyalphabetic ciphers; 
Intro. to public key crypto. (Ch. 5.1)
    
 7  Th  28/1 RSA cryptosystem and correctness (Ch 5.3.0)
(correctness proof: class note 2)
Ingredient: Fermat's little th. (Ch 5.2.3, corro. 5.5) 
    
 8  Tu  2/2 Implementing RSA  (Ch. 5.3.1) 
Ingredient 1: Sq-and-mult. algo.
Ingredient 2: GCD, Inverse (see above)
Ingredient 3: Rabin-Miller Primality test (see below)
Quadratic residue (definition) & Proof of Euler's criterion
(Ch 5.4.1, only pages 179 and 180 & Th. 5.9)
     Ingredient 1: # soln of a poly. eq. mod p (class note 3)
     Ingredient 2: Fermat's little th.(see above)		  HA2  
 9  Th  4/2 Primality testing: Rabin-Miller (Ch. 5.4.3)
    
 10  Tu  9/2 Exercises on theorems taught in 2/2    
 11  Th  11/2 Analysis, and correctness of Rabin-Miller Primality
(Ch 5.4.3)
          Ingredient 1: Fermat's little th. (see above)
          Ingredient 2: Euler's criterion (see above)
Rabin's crypto: description, correctness, and security
(Ch. 5.8.0) 
          Ingredient 1: CRT (see above)
          Ingredient 2: QR and Euler's criterion (see above)
Ingredient 2: bijection from Z_N--> Z_p x Z_q
Ingredient 3: How to compute QR mod p?
 
 12  Tu  16/2 Rabin's crypto: security (Ch. 5.8.1, Algo. 5.12)
Attacks on RSA  
 - If phi (N) is revealed (Ch. 5.7.1)
 - if decrypt. exponent d is revealed (Ch 5.7.2, Algo 5.10)
    Ingredient: a^{phi(N)-1}=1 mod N (Ch 5.2.3, corro. 5.6) 
    
 13  Th  18/2 Defn. of a (cyclic) group, order of a group element
order of an element in Z_p* divides (p-1)
# of generators of Z_p* = phi (p-1)
   - Ingredient 1: Z_p* is a cyclic group (special note)
   - Ingredient 2: if g is a generator, so is g^d for all (d,p-1)=1
(Class note 4 for all above except Ingredient 1)
Discrete log problem (Ch 6.1)
El-gamal Crypto: desc, correctness and security (Ch. 6.1) 
    
       Midsem exam    
 14  Tue  8/3  Blockcipher based encryption: ECB, CBC, OFB, CFB and CTR (note)    
 15  Th  10/3  Random Oracle (note), Ideal hash, 
Birthday paradox (Ch. )		    
 16  Tu  15/3  Blockcipher-based hash, Blockcipher DES (Class note)    
 17  Th  17/3  RSA-based signature (Ch 7.1)  HA3  
 18  Mo  28/3  El-gamal Signature scheme (Ch. 7.3)    
 19  Tue  29/3  Quiz 1    
 20  Th  31/3  Diffie-Hellman Key agreement protocol (11.1, 11.2.0 and 11.2.1)    
 21  Tu  5/4  Public-key based Identification schemes (Ch. 9.0, 9.1 and 9.3)
Parallel session attack on Protocol 9.7		    
 22  Th  7/4  Schnorr Identification scheme (9.4.0, Protocol 9.8)    
 23  Tu  12/4  Secret sharing schemes (Ch. 13.1, 13.1.1 )    
 24  Tu  19/4  Quiz 2    
 25  Th  21/4  Re-look at various problems    

*Additional reading materials, in most cases, can be found in lecture notes. Some more advice.
**Instruction on how to submit assignments: here.
***Each lecture note contains a number of examples and practice problems.