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.: Geneviève Arboit
Office :
Room 104, McConnell Eng. Building
3480 University Street
phone: (514) 398-7071 x7064
email: garboit@cs.mcgill.ca
Office Hours:
Claude : Tuesday + Thursday 13h00 - 15h00, McConnell 109.
Geneviève : Wednesday + Friday 9h30-11h00, McConnell 104.
Description: (3 credits, 3 hours).
This course presents an in-depth study of
modern cryptography and data security.
We investigate four important subjects of
cryptography: data encryption, message authentication,
user identification and key distribution.
The basic information theoretic and computational
security of classical and modern cryptographic
systems are analysed. The course is self-contained
and all necessary mathematical background will
be explicitely covered.
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 (!) , and how they can exchange a secret key
using dim pulses of laser light, 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%. The homeworks will have some theoretical
components worth 30% and applications using Maple 7 worth 20%.
Course outline:
- Historical 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
- Authentication Codes
- Introduction
- Computing Deception Probabilities
- Universal Hashing Functions
- Perfect or nearly perfect MACs
- The Data Encryption Standard and Advanced Encryption Standard
- Introduction
- Description of DES
- An Example of DES Encryption
- DES Modes of Operation
- Advanced Encryption Standard (AES)
- Description of 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
- Undeniable 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
- Identification Schemes
- Introduction
- The Schnorr Identification Scheme
- The Guilloux-Quisquater Identification Scheme
- Converting Identification to Signature Schemes
- Zero-knowledge Proofs
- Interactive Proof Systems
- Perfect Zero-knowledge Proofs
- Zero-knowledge Proofs of Identity
- Quantum Cryptography