Tel Aviv University School of Computer Science

Fall 2001-2002
Introduction to Modern Cryptography

0368.3049.01

http://www.cs.tau.ac.il/~bchor/crypto-course.html

Benny Chor

Wednesdays 14-17 Schreiber 006

 
 

Contact Info:
 
    Email Phone Office Office Hours
Instructor:  Benny Chor benny@cs.tau.ac.il 640-5977 Schreiber 223 By  e-appointment 

 
 
 

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:

            Typically each lecture will have two major parts. The "crypto part" will be presented with slides, while the

"number theory" part will be on the black board.  Textbook  reference corresponds to the latter.
 
Lecture
___________
Date
______
Crypto Subject
______________________________________
Number Theory Topic 
_______________________
Textbook Reference
__________________
     1
24/10/01
Introduction and administrativia 
(pdf, printer friendly pdf)
 The ring Zm
  1.1.1
     2
31/10
Symmetric Stream 
and Block Ciphers
(pdf, printer friendly pdf)
 Euclid gcd  algorithm
  4.2.1
         3
(Prof. Safra)		   5/12
 Groups, rings and fields;AES
(pdf, printer friendly pdf)
    
            4  12/12
 Message Authentication,
 Collision resistant hashing. 
(pdf, printer friendly pdf))
   Extended gcd; Time analysis of Euclid gcd;
  4.2.1
            5  19/12
  Introduction to 
Public Key Cryptography; 
Diffie-Hellman key exchange 
(pdf, printer friendly pdf)
Quadratic Residues in Zp;
  Birthday paradox wrap up 		  4.5;
 7.3
            6  26/12   Testing Primitive Elements in Zp
    Primality Testing 
(pdf, printer friendly pdf)
Chinease remainder theorem
  4.2.2
            7  2/1/02
RSA public key cryptosystem
(pdf, printer friendly pdf)
Density of Primes
            8    9/1  Random self reducibility of RSA
 A remark on using RSA with low exponents
 Coin flipping over the phone		  Factoring Algorithms:
  1. Pollard p-1 method
  2. Pollard rho 		 Chapter 3 in the Handbook of Applied Cryptography
            9    16/1 El-Gammal Public Key Cryptosystem Discrete Log Algorithms:
  1. Shank's baby-step 
          giant-step 		 Chapter 3 in the Handbook of Applied Cryptography
           10    23/1 Digital Signatures (pdf, printer-friendly pdf)

Solutions to PS2

 Discrete Log Algorithms:
2. Pollard rho method
        (Maple code)		 Chapter 3 in the Handbook of Applied Cryptography
           11    30/1 Secret Sharing Schemes: 
  n-out-of-n, and Shamir's t-out-of-n.
Introduction to threshold cryptography:
n-out-of-n RSA signatures.
n-out-of-n ElGamal decryption.		 Lagrange Polynomial interpolation.
           12      6/2   Identification Schemes.
  Zero knowledge proofs.
  (pdf, printer friendly pdf)
Chapter 9

Problem Sets

Problem set 1

Problem Set 2

Problem Set 3.

Problem Set 4.

Administrativia

Reading

Moed A  and Homework Assignment 4.

Moed A exams were graded, and the results should be available on Feb. 20, 2002 or soon afterwards.
The final grade was calculated using  (nominal exam grade + 10) * 0.7 + homeworks grade * 0.3.
The published "exam grade" equals nominal exam grade + 10.
In the few cases were the nominal exam grade was lower than 45, the final grade is "fail".

Statistics for final grades: Average = 82.4,  standard deviation = 13.9.

Graded assignment 4 (as well as older assignments not claimed before) are available in "khadar targilim",
1st floor of Schreiber building.


Moed B.

Moed B exams were graded, and the results should be available on Sept. 19, 2002 or soon afterwards.
The final grade was calculated using      exam grade * 0.75 + homeworks grade * 0.25. 

Statistics for final Moed B grades: Average = 89.7,  standard deviation = 5.1.