Tel Aviv University School of Computer Science
Contact Info:
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 up4.5;
7.36 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 phoneFactoring Algorithms:
1. Pollard p-1 method
2. Pollard rhoChapter 3 in the Handbook of Applied Cryptography 9 16/1 El-Gammal Public Key Cryptosystem Discrete Log Algorithms:
1. Shank's baby-step
giant-stepChapter 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
Homework submition in pairs. There will be a total of 4 problem
sets, involving both "dry" assignments
and "wet" ones (in MAPLE). The homework portion of the grade is determined
by the best 3-out-of-4.
R. Rivest, A. Shamir, and L. Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", CACM 21, pp. 120--126, Feb. 1978.
A. Shamir, "How
to Share a Secret", CACM 22, pp. 612--613, November 1979.
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 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.