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

- 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