CS547 Cryptography and Data Security
Instructor: Prof. Claude Crépeau
Office :
Room 109/302, McConnell Eng. Building
3480 University Street
phone: (514) 398-4716
email: crepeau@cs.mcgill.ca
T.A.: George Savvides
Office :
Room 235, McConnell Eng. Building
3480 University Street
phone: (514) 398-7071 x0699
email: gsavvi1@cs.mcgill.ca
Office Hours:
Claude : Tuesday + Thursday 13h00 - 15h00, McConnell 109/302.
George : TBA, McConnell 235.
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 (second edition) by Doug Stinson.
Chapman and Hall/CRC Press, Inc.
ISBN 1-58488-206-9
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 worth 20%.
Honnêteté
académique:
L'université McGill attache une haute importance à
l'honnêteté
académique. Il incombe par conséquent à tous les étudiants
de comprendre
ce que l'on entend par tricherie, plagiat et autres infractions
académiques, ainsi que les conséquences que peuvent avoir de telles
actions, selon le Code de conduite de l'étudiant et des procédures
disciplinaires (pour de plus amples renseignements, veuillez consulter
le site www.mcgill.ca/integrity).
Academic integrity:
McGill University values academic integrity. Therefore all students
must understand the meaning and consequences of cheating, plagiarism and
other academic offences under the Code of Student Conduct and
Disciplinary Procedures (see www.mcgill.ca/integrity for more
information).
Course outline (Subject to small modifications):
- Mathematical Background
- Number Theory
- Finite Fields
- 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
- 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
- Authentication Codes and Hash Functions
- Introduction
- Computing Deception Probabilities
- Universal Hashing Functions
- Perfect or nearly perfect MACs
- Collision-free Hash Functions
- The Birthday Attack
- A Discrete Log Hash Function
- Extending Hash Functions
- Hash Functions From Cryptosystems
- The MD4 Hash Function
- Key Distribution and Key Agreement
- Introduction
- Diffie-Hellman Key Exchange
- The Station-to-station Protocol
- Public-key Cryptography and The RSA System
- 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
- Discrete Logarithm based 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
- Signatures and Hash Functions
- The ElGamal Signature Scheme
- The Digital Signature Standard
- Undeniable Signatures
- Public-key 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