CS 555 Class


These files are for the use of students in CS 555 Spring, 2018, at Purdue University

Instructor: Samuel S. Wagstaff, Jr.

Phone: 49-46022; E-mail: ssw@cerias.purdue.edu

Prerequisites: CS 251, CS 381, CS 426 and MA 351.

Class web page: https://www.cs.purdue.edu/homes/ssw/cs555/index.html

The real prerequisites for CS 555.

Syllabus for CS 555.

Text: Introduction to Modern Cryptography, second edition, by J. Katz and Y. Lindell, Chapman and Hall/CRC Press, 2015, ISBN 978-1-4665-7026-9. See also the errata here.

Recommended additional reading: Applied Cryptography (2nd edition), by Bruce Schneier, Wiley, 1996. See also the errata here.

See also here for the new Advanced Encryption Standard algorithm Rijndael.

The overall course policies are the same as Spaf's.

Link to a list of web sources on cryptography and security.

Location and Time: LWSN B134, Tue-Thu 1:30 PM - 2:45 PM.

Office: LWSN 1167; Office hours: Monday 2-3 PM, Thursday 3-4 PM.

Grading: Homework: 20%; Midterm exam 20%; Project 20%; Final exam 40%.

Day-by-day list of topics covered.

Please use a word processor like Latex or MS Word to format your homework solution. Use at least 12 point type. If we can't read your answer, then it is wrong!

All regrading of homework, midterm exam and the project must be done within two weeks after the work is returned to the class.

Solution to homework and a summary of your grades on the midterm.

Sample Midterm exam. Try to do it in 50 minutes with no references.

Homework # 1, due Tuesday, January 23, 2018, 1:30 PM, on paper, in class. In question 2, your reasoning is much more important than the numbers you give as the answers. Unsupported guesses are worthless, even if correct. Text of the questions.

Homework # 2, due Tuesday, January 30, 2018, 1:30 PM, on paper, in class. In question 1, your reasoning is much more important than the numbers you give as the answers. Unsupported guesses are worthless. Text of the questions.

Homework # 3, due Tuesday, February 6, 2018, 1:30 PM, on paper, in class. Text of the questions.

Homework # 4, due Tuesday, February 13, 2018, 1:30 PM, on paper, in class. Text of the questions.

Homework # 5, due Tuesday, February 20, 2018, 1:30 PM, on paper, in class. Text of the questions.

Homework # 6, due Tuesday, February 27, 2018, 1:30 PM, on paper, in class. Text of the questions.

Homework # 7, due Tuesday, April 3, 2018, 1:30 PM, on paper, in class. Text of the questions.

Homework # 8, due Tuesday, April 17, 2018, 1:30 PM, on paper, in class. Text of the questions.

2018 project assignment.

Please sign up for your project demonstration using this doodle. All members of each team should put their names on one entry for one time. The demonstrations will be held on April 18-20 and should take about 15 minutes. Thanks.

slides from an old lecture.

Review 1: Basic probability and hash.

Review 2: Remainders, arithmetic, divisibility, gcd, primes.

Review 3: primes, congruences, Caesar cipher.

Review 4: Fermat, Euler, fast exponentiation, public-key ciphers.

Review 5: CRT, solving quadratic congruences, oblivious transfer.

2009 slides, part 1.

2009 slides, part 2.

Block, stream ciphers, LFSRs, meet-in-the-middle attacks.

An LFSR with 4 bits.

DES (by Prof Kak).

AES and Rijndael.

Rijndael, the new AES.

More about AES in comics.

Divisibility, Arithmetic with large integers, GCD.

Examples of the Extended Euclidean Algorithm and the Chinese Remainder Theorem

Prime numbers.

Congruences: Definition and single linear ones.

2009 slides, part 3, congruences, Fermat, Euler.

Congruences for fun and profit.

Fermat, Euler, fast exponentiation, finding large primes.

Diffie-Hellman key exchange, discrete logs, P-H, RSA, ElGamal, Massey-Omura ciphers, RSA signatures, ElGamal public-key cryptosystem, Mental poker and quadratic residues.

2009 slides, part 4, more about RSA.

2009 slides, part 5, groups and DLP.

Much more about discrete logs.

Chinese remainder theorem, Solving quadratic congruences, Oblivious transfer and Zero-knowledge proofs.

Chinese remainder theorem, Solving quadratic congruences, Oblivious transfer and Zero-knowledge proofs. II.

Examples of numbers in oblivious transfer and coin-tossing protocols.

More about zero-knowledge proofs.

MACs and Hash functions.

Example of a letter with many variations.

Hash and other one-way functions.

More about hash functions.

Threshold schemes, Digital Signature Standard and Subliminal Channels.

More about threshold schemes.

Large primes via Pocklington-Lehmer.

Elliptic curves.

Signing contracts by e-mail. (revised)

Signing contracts by e-mail.

Digital cash.

Electronic voting.

Construction of large primes.

Construction of large primes (2).

Simple factoring methods.

Key exchange algorithms.

Kerberos.

Random number generation.

An attack on RSA.

Midterm Exam, Tuesday, March 6, 1:30 PM - 2:30 PM, Room LWSN B134. Do not bring cell phones, laptop computers, or any other device that communicates to the exam.

Final Exam, Thursday, May 3, 2018, 8 - 10 AM, Room LWSN B134. Do not bring cell phones, laptop computers, or any other device that communicates to the exam.

Ph.D. Qualifying Exam Supplement, date, time, room TBA. Do not bring cell phones, laptop computers, or any other device that communicates to the exam.

Transposition ciphers and substitution ciphers, IC.

Substitution ciphers, product ciphers.

P-H, RSA, ElGamal, Massey-Omura ciphers, signatures.

ElGamal public-key cryptosystem.

Diffie-Hellman key exchange, discrete logs.

Mental poker and quadratic residues.

Euler's Criterion, Legendre symbol.

Caesar cipher, CRT.

Quadratic congruences, Oblivious transfer, Zero-knowledge proofs.

MD5 and SHA.

The Birthday paradox.

Threshold schemes.

Digital Signature Standard.

Subliminal channels; the one in DSA.

Some old slides you might enjoy.

Information theory: Definition of entropy.

Information theory: Rate, perfect secrecy.

Key equivocation, unicity distance.

Transposition ciphers and substitution ciphers, IC.

Synchronous and self-synchronous stream ciphers, CBC.

Congruences: CSR, XEuclid, multiplicative inverses.

Fermat, Euler, fast exponentiation, finding large primes.

Digital cash.

More about Digital cash.

IDEA.

Entropy question and proposed solution.

Alice and Bob

Substitution ciphers, product ciphers.

PGP.


Send e-mail to Sam Wagstaff


(This page last modified April 28, 2018)