Cryptography - Spring 2001

Dr. Amos Beimel

Webster dictionary defines cryptography as: ``The enciphering and deciphering of messages in secret code or cipher.'' However, modern cryptography is a much broader field; it provides algorithms and protocols which protect honest parties from malicious parties. Malicious parties can, for example, eavesdrop to the communication on the Internet and try to read messages sent by other parties; they can try to impersonate other parties, or login to computers without permission. Basic topics in cryptography include secure encryption, digital signatures, and authentication.

In this course I will discuss these topics, their realizations, and applications. The material covers cryptosystems that are both practical and theoretically interesting. To achieve this goal, I'll also teach some background in number theory that is necessary to understand modern cryptosystems such as RSA. This is a 4-credit course, consisting of two weekly 2-hour meetings. It is intended for graduate students as well as third year undergraduate students. Pre-required course is the algorithms course.

Exercises and Exams:

Exercise 1, due 26.3.01.
Exercise 2, due 16.4.01.
Exercise 3, due 30.4.01.
Exercise 4, due 14.5.01.
Exercise 5, due 4.6.01.
Final Exam (Moed A) (ps file) (word file)
Final Exam (Moed B) (ps file) (word file)

Course Book:

D. R. Stinson. CRYPTOGRAPHY: Theory and Practice. CRC Press. 1995.

Lectures:

All chapters refer to the above book. Some parts are not covered by the book, references appear below. All lectures are two hours unless indicated otherwise.

Num.	Topic	Date	Handouts, exercises	textbook
1	Introduction. Classic Encryption Systems	5.3.01	Announcement, syllabus
2 (3 hours)	Classic encryptions; their cryptanalysis. Perfect encryption: examples, limitations.	6.3.01		Chapter 1 Chapter 2.1
3 (3 hours)	Data Encryption Standard (DES).	26.3.01	DES, Ex1	Chapters 3.1-3.4
4 (3 hours)	Attacks on DES. Advanced Encryption Standard (AES).	27.3.01		[Matsui] Rijndael
5 (3 hours)	Introduction to Number Theory: modular arithmetic, Euclid's algorithm.	2.4.01	EX2	Chapters 1.1.1, 4.2, 4.4
6 (3 hours)	Number Theory: Chinese remainder theorem, structure of Zp, Quadratic Residues.	3.4.01		Chapter 4.2
7	The RSA public key encryption.	16.4.01	Ex3	Chapters 4.3, 4.4
8	RSA: Implementations and Attacks.	17.4.01		[Boneh]
9	Diffie-Hellman Key Exchange, ElGamal Encryption.	23.4.01		Chapters 5.1 (until p. 166), 8.2.2
10	Digital Signatures: Definitions, Rabin's Signature scheme.	30.4.01	Ex4	Chapter 6.1, Chapter 4.7 (modified)
11	ElGamal Signature scheme. One-time signature schemes.	1.5.01		Chapter 6.2
12	Digital Signature Standard (DSS).	7.5.01		Chapter 6.3, [DSS]
13	Cryptographic Hash functions.	8.5.01		Chapters 7.1-7.3,7.6
14	Message Authentication Codes (MAC), CBC-MAC.	14.5.01	Ex5	Chapter 3.4.1
15	HMAC and MAC based on universal hashing.	15.5.01	[BCK1] (ps) (pdf)	[BCK1] [BCK2]
16	Secure Socket Layer (SSL).	21.5.01	Slides: (1) (2) (3) (4) (5)	[Stallings,Chapters 14.1, 14.2]
17	SSL (cont.), Brief description of IPsec.	22.5.01		[Stallings, Chapters 13]
18	Threshold Secret Sharing Schemes.	5.6.01		Chapter 11.1
19	Private Information Retrieval	11.6.01
20	Summary of Course.	12.6.01
21	Example questions	2.7.01

[Matsui] M. Matsui. Linear Cryptanalysis Method for DES Cipher. In EUROCRYPT 93, vol. 765 of Lecture Notes in Computer Science, pages 386--397, Springer-Verlag, 1994.
[Boneh] D. Boneh. Twenty years of attacks on the RSA Cryptosystem. In Notices of the American Mathematical Society (AMS), Vol. 46, No. 2, pp. 203--213, 1999.
[DSS] NIST, FIPS 186-2, Digital Signature Standard (DSS).
[BCK1] M. Bellare, R. Canetti, and H. Krawczyk. The HMAC Construction (ps) (pdf). CryptoBytes, Vol. 2, No 1, pages 12-15, 1996.
[BCK2] M. Bellare, R. Canetti, and H. Krawczyk. Keying Hash Functions for Message Authentication. Abridged version appears in CRYPTO '96, vol. 1109 of Lecture Notes in Computer Science, pages 1-15, Springer-Verlag, 1996.

Other Books:

A. J. Menezes, P. C. van Oorschot and S. A. Vanstone. The Handbook of Applied Cryptography. CRC Press. 1996. Available online.
W. Stallings. Cryptography and Network Security. Second Edition. Prentice Hall. 1998.

Grades:

Final exam, 70%. Students MUST PASS the exam to pass the course.
Homework assignments, 30%. There will be 5 homework assignments.

Information:

Lectures hours:	Monday 18-20, Room 224 Building 90
	Tuesday 18-20, Room 224 Building 90
Reception hours:	Monday 13-15, Room 205 Building 58 (Math and CS)
E-mail:	beimel at cs.bgu.ac.il
Phone:	647 7858