Cryptography - Spring 2003

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 third year undergraduate students as well as for graduate students. Pre-required courses are design of algorithms and probability.

Announcements:

A lecture before the exam will be held on Sunday 22.6.03 at 11:00 in room 106 building 28. Please give me in advance questions for the lecture.
Ex 4 is checked. You can collect it in frount of the CS secretaries' office.
Ex 5 is checked. You can collect it in frount of the CS secretaries' office.
list of the grades of the exercises. The exercise grade is calculated as the average of the best 4 exercises.
MOED B Exam (pdf file), (word file).
MOED A Exam (pdf 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	24.2.03	Announcement
2	Classic encryptions (continued); their cryptanalysis.	25.3.03	Frequency Table Vigenre Applet	1
3	Perfect encryption systems.	3.3.03	EX1	2.1
4	Basic Number Theory	4.3.03	Proof from class
5	More Number Theory	10.3.03		5.2
6	Chinese Remainder	11.3.03		5.2
7	Quadratic Residues	24.3.03	EX2
8	Number Theory: Summary	25.3.03
9	RSA public key encryption.	31.3.03		4.3, 4.4
10	RSA: Implementations and Attacks. Diffie-Hellman Key Exchange	1.4.03		[Boneh] 4.5 8.2.2
11	ElGamal Encryption.	7.4.03		5.1 (until p. 166)
12	Data Encryption Standard (DES).	8.4.03	DES, Ex. 3 (ps) (word)	3.1-3.3
13	Attacks on DES. Linear Cryptanalysis.	28.4.03		[Matsui]
14	Modes of Operations. Advanced Encryption Standard (AES).	29.4.03	Ex 4 (ps) (word)	3.4 Fips 197
15	Digital Signatures: RSA and Rabin's Signatures.	12.5.03		6.1, 4.7 (modified)
16	ElGamal Signature scheme.	13.5.03		6.2
17	Digital Signature Algorithm (DSA).	19.5.03		6.3
18	Cryptographic Hash functions.	20.5.03		7.1-7.3,7.5.
19	Authentication, CBC-MAC. HMAC.	26.5.03	Ex 5 (ps) (word) [BCK1] (ps) (pdf)	3.4.1.
20	Secure Socket Layer (SSL).	27.5.03	Slides: (1) (2) (3) (4) (5)	[Stallings, 14.1, 14.2]
21	Threshold Secret Sharing.	2.6.03		11.1
22	Secret Sharing.	9.6.03		11.2
23	Summary Lecture.	10.6.03
24	Example questions.	22.6.03

[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.
[Stallings] W. Stallings. Cryptography and Network Security. Second Edition. Prentice Hall. 1998.

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, 75%. Students MUST PASS the exam to pass the course.
Homework assignments, 25%. There will be about 5 homework assignments. These assignments do not include any programming.

Information:

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

Syllabus

All chapters refer to the book of Stinson. Some parts are not covered by the book.

Introduction
- Overview of course.
- Classical cryptography [parts of Chapter 1].
Secret Key Encryption
- Perfect Secrecy - One time pads [Chapter 2.1].
- Stream ciphers and the Data Encryption Standard (DES) [Chapter 3 (excluding 3.6)].
- The Advanced Encryption Standard (AES) - adopted September 2000.
Public Key Encryption
- Factoring and the RSA encryption [Chapter 4.1 - 4.4].
- Discrete log. Diffie-Hellman Key Exchange [Chapter 8.4 (only pages 270-273)].
  ElGamal encryption [Chapter 5 (only pages 162-164)] .
Digital Signatures [Chapter 6 (excluding 6.5 - 6.6)]
- One-time signatures.
- Rabin and ElGamal signatures schemes.
- Digital Signature Standard (DSS).
Hashing
- Motivation and applications. Cryptographically Secure Hashing. [Chapter 7.1-7.3,7.6]
- Message Authentication Codes (MAC). CBC-MAC, HMAC.
Network Security
- Secure Socket Layer (SSL).
- IPsec.
Secret Sharing
- Definition. Shamir's threshold scheme [Chapter 11.1].
- Visual secret sharing schemes.

Old Exams (in Hebrew)

Spring 2000:: Moed A (ps file) , Moed B (ps file)
Spring 2001:: Moed A (ps file), (word file). Moed B (ps file), (word file)
Spring 2002:: Moed A (ps file), (word file). Moed B (ps file), (word file) Moed C (ps file), (word file).