Tel Aviv University School of Computer Science

Fall 2007-2008
Introduction to Modern Cryptography


Benny Chor

Tuesdays 10-13, Dan David 003


Class Bulletin-Board:



 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 640-5977 Schreiber 329 By e-appointment
TA/grader Rani Hod ranihod AT 640-5398 Open space


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.

Crypto Subject
Mathematics Background  
Textbook Reference

Elementary introduction to Modern Crypto;
 Administrativia, course topics, etc. 

Groups, rings, fields;
 The ring Z;
Euler's totient (phi) function
 Stinson 1.1.1
 Shoup 2.1-2.4; 3.1-3.4
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


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
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
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)

שיעור חזרה

Solution to Assignment 3
Solution to Moed A, 2002

Homework Assignments


Date Handed

Submission Deadline*


 Assignment 1

January 29, 2008

February 12

Assignment 2

February 17, 2008

March 4

Assignment 3

March 10, 2008

March 25




Moed A exam


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!



  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.