Tel Aviv University School of Computer Science

Fall 2007-2008
Introduction to Modern Cryptography

0368.3049.01

http://www.cs.tau.ac.il/~bchor/crypto07.html

Benny Chor

Tuesdays 10-13, Dan David 003

   

Class Bulletin-Board:

Date

Announcement

 January 29

Assignment 1 was launched.
 February 3  Lecture 3 has two online presentations - math and crypto.
 February 5  Updated versions of both parts of lecture 3 were uploaded.
 Mostly they contain fixes to minor bugs, but on the AES part
 a slightly expanded explanation of culomn mixing is included.
 February 5  Students who have exams in the current week (Feb 3-8) can submit
 HW1 till Sunday, Feb 17 (together with their partners if applicable).
 The submitted homework should, in addition, include some printouts
 confirming registration to a course and exam date(s).

 Students who have exams in the week of Feb 10-15) should send
email to Benny Chor and indicate the date(s) of these exams, in order
to obtain a slightly extended extension.
 February 16  The first make-up class will take place on Friday, Feb. 22, 10-13, in Dan David 003.
 A follow up session (optional) will be held subsequently in the outside swimming pool, rain or shine!
 March 10  On March 11, we will again start at 9am. Following a number of requests, I will devote the first hour to going over
material from lecture 3 dealing with the algebraic components of the class (finite groups, rings, and fields). If you
feel this is of little or no help to you, you are welcome to show up at 10:05.

Contact Info:
Email Phone Office Office Hours
Instructor: Benny Chor benny AT cs.tau.ac.il 640-5977 Schreiber 329 By e-appointment
TA/grader Rani Hod ranihod AT post.tau.ac.il 640-5398 Open space

Prerequisites

Linear Algebra; Probability; Algorithms (formerly “efficiency of computations”); Computational Models, 
and most importantly, "mathematical maturity".

 

Course Outline
This course will discuss basic building blocks of modern cryptography. Tentative topics include encryption,
data integrity, authentication  and identification, digital signatures, elementary number theory, randomness
and pseudo-randomness, cryptographic protocols, and real world security systems.
 

Course Plan (will be updated incrementally):

            Typically each lecture will have two major parts. The "crypto part" will be presented with slides, while the "mathematical background" (number        
           theory/algebra) part will often be on the black board.  Textbooks references corresponds to both parts.
 
Lecture
___________
Date
______
Crypto Subject
______________________________________
Mathematics Background  
_______________________
Textbook Reference
__________________
 1

22/1/08
 23/10/08
Elementary introduction to Modern Crypto;
 Administrativia, course topics, etc. 

Groups, rings, fields;
 The ring ZN ;
Euler's totient (phi) function
  Stinson 1.1.1
 Shoup 2.1-2.4; 3.1-3.4
    2
29/1
Pseudo random generators and permutations. Symmetric Stream and Block Ciphers
and their modes of operation
 Euclid gcd  algorithm, extended gcd.
Groups and subgroups
  Stinson 3.7
Katz-Lindell 3.3, 3.4, 3.6
          
            3

    5/2

Symmetric block ciphers:  DES and AES

Groups, Rings, Finite fields   Stinson 3.1, 3.4, 3.5, 6.4
Katz-Lindell 5.3, 5.5, 7.1
            4  12/2
Iterated Ciphers;
Message Authentication;
 Cryptographic Hash Functions.
   
  Stinson 4.2.1
Katz-Lindell 4.1-4.7, 5.4
            5    19/2
 Extended gcd; Time analysis
   of the Euclid gcd algorithm;		  Stinson 5.2.1, 5.4
Katz-Lindell 7.1, 7.3, 9.4, 11.1
            6
Friday
   22/2
Chinese remainder theorem
  Stinson 5.2, 5.4, 5.3
Katz-Lindell 7.2, 10.4
            7   26/2
RSA public key cryptosystem


Stinson 5.3, 5.5, 5.6 Katz-Lindell 7.2, 8.1
    8 (and 1/3)    4/3   Solutions to PS1
Factoring Algorithms:
   Pollard rho method		 Stinson 5.3, 5.5,5.6,6.1
Katz-Lindell 7.2, 8.1,10.4,10.5
   9 (and 2/3)    11/3 Elgamal Public Key Cryptosystem
Digital Signatures
 Groups, Rings, Finite fields 

Discrete Log Algorithms: 1.Shank's baby-step giant-step

Coin flipping over the phone  		Stinson 6.1-6.2, 7.1-7.4
Katz-Lindell 8.2, 10.5, 12.1-12.4, 12.7
 10  (and 2/3)    18/3

Coin flipping over the phone
Hard core bits for one way functions
Zero Knowledge: the Ali Baba example.


Discrete Log Algorithms:
2. Pollard rho method
(Maple code - updated 17/3)


 Stinson 5.9, 6.2, 6.7.1
Katz-Lindell 6.3, 8.2
  11 (and 2/3)   25/3
1/1/08		 Zero knowledge proofs: 3 coloring 
(Slides by Maurice Herlihy, Brown University)

Identification Schemes.
 
 n-out-of-n secret sharing schemes  (maybe)

Solution to Assignment 2 (certainly)
שיעור חזרה
 27/3
3pm
Solution to Assignment 3
Solution to Moed A, 2002


Homework Assignments

Assignment

Date Handed

Submission Deadline*

Remarks

 Assignment 1

January 29, 2008

 February 12

Assignment 2
 

 February 17, 2008

March 4

Assignment 3

March 10, 2008

 March 25


 




 



 

Moed A exam


Feedback

Based on the feedback forms, most students thought the course was way too hard. A few thought it was worth the effort.
This leaves the lecturer puzzled as to why so many (approx. 85) insisted on taking it.
As for students in future generations of this course (and same lecturer) - caveat emptor!

Administrativia

Reading

Textbooks:              
  1. J. Katz and Y. Lindell, Introduction to Modern Cryptography, Chapman & Hall/CRC Press, 2007.                                                                                                                 (The book was published in August 2007 and ordered October 2007, so it should be at TAU library by now.)  
  2. V. Shoup, A Computational Introduction to Number Theory and Algebra (Version 1), 2005. Available online.
  3. D. Stinson, Cryptography Theory and Practice, CRC Press, 1996.
Recommended books:      
  1.     A. Menezes, P. Van Oorschot, S. Vanstone, Handbook of Applied Cryptography, Available onlline.
  2.     B. Schneier,  Applied Cryptography, Willey & Sons, 1996.
Classical Articles: Not So Classical Reading:

Moed A, the winter 2002 exam.