CS547 Cryptography and Data Security
Instructor: Prof. Claude Crépeau
Office :
Room 109, McConnell Eng. Building
3480 University Street
phone: (514) 398-4716
email: crepeau@cs.mcgill.ca
T.A.: Simon-Pierre Desrosiers
Office :
Room 238, McConnell Eng. Building
3480 University Street
phone: (514) 398-7071 x0699
email: simonpie@cs.mcgill.ca
Office Hours:
Claude : Monday + Wednesday 10h00 - 12h00, McConnell 109.
Simon-Pierre : Monday + Wednesday 13h45 - 15h45, McConnell 235.
Description: (3 credits, 3 hours).
This course presents an in-depth study of
modern cryptography and data security. The basic
information theoretic and computational properties of classical and
modern cryptographic systems are presented, followed by a
cryptanalytic examination of several important systems. We will study
the application of cryptography to the security of electronic
mail, timesharing systems, computer networks and data bases. We will
end with an examination of current literature.
Objectives:
Discover how Alice may send a secret message to Bob
that nobody else can understand,
how he may be certain that this message came from Alice,
how she can prove him who she is with revealing anyhting about
the proof (!) etc.
Mandatory textbook:
Cryptography - Theory and Practice by Doug Stinson.
CRC Press, Inc.
ISBN 0-8493-8521-0
Evaluation:
There will be 5 homework assigments worth 50% of your final grade
and a final exam worth 50%.
Course outline:
- Classical Cryptography
- Some Simple Cryptosystems
- The Shift Cipher
- The Substitution Cipher
- One-time pad
- Stream Ciphers
- Enigma
- Shannon's Theory
- Perfect Secrecy
- Entropy
- Huffman Encodings and Entropy
- Properties of Entropy
- Spurious Keys and Unicity Distance
- Secret Sharing Schemes
- Introduction: The Shamir Threshold Scheme
- Authentication Codes
- Introduction
- Computing Deception Probabilities
- Universal Hashing Functions
- Perfect or nearly perfect MACs
- The Data Encryption Standard
- Introduction
- Description of DES
- An Example of DES Encryption
- DES Modes of Operation
- Advanced Encryption Standard (AES)
- Pseudo-random Number Generation
- Introduction and Examples
- Indistinguishable Probability Distributions
- Next Bit Predictors
- The Blum-Blum-Shub Generator
- Pseudo-random functions
- Identification procotol
- Key Distribution and Key Agreement
- Introduction
- Diffie-Hellman Key Exchange
- The Station-to-station Protocol
- The RSA System and Factoring
- Introduction to Public-key Cryptography
- More Number Theory
- The Euclidean Algorithm
- The Chinese Remainder Theorem
- Other Useful Facts
- The RSA Cryptosystem
- Implementing RSA
- Probabilistic Primality Testing
- Attacks On RSA
- The Decryption Exponent
- Partial Information Concerning Plaintext Bits
- The Rabin Cryptosystem
- Factoring Algorithms
- Probabilistic Encryption
- Other Public-key Cryptosystems
- The ElGamal Cryptosystem and Discrete Logs
- Algorithms for the Discrete Log Problem
- Bit Security of Discrete Logs
- Finite Field and Elliptic Curve Systems
- Galois Fields
- Elliptic Curves
- Signature Schemes
- Introduction
- The ElGamal Signature Scheme
- The Digital Signature Standard
- One-time Signatures
- Hash Functions
- Signatures and Hash Functions
- Collision-free Hash Functions
- The Birthday Attack
- A Discrete Log Hash Function
- Extending Hash Functions
- Hash Functions From Cryptosystems
- The MD4 Hash Function
- Timestamping
- Identification Schemes
- Introduction
- The Schnorr Identification Scheme
- Converting Identification to Signature Schemes
- Zero-knowledge Proofs
- Interactive Proof Systems
- Perfect Zero-knowledge Proofs
- Bit Commitments
- Computational Zero-knowledge Proofs
- Zero-knowledge Arguments
- Quantum Cryptography