Applied Cryptography - CSCI 531, Spring 2015

Time	:	MW 9:30am - 10:50am
Location	:	OHE 100D
Instructor	:	Bill Cheng (for office hours, please see instructor's web page), E-mail: <bill.cheng@usc.edu>.   (Please do not send HTML-only e-mails. They will not be read.)
TA	:	(none)
Grader	:	Feng Wen, E-mail: <fengwen@usc.edu>.  (The grader will hold office hours the week after the announcement of each assignment's grades.)
Midterm Exam	:	during class, Wed, 3/11/2015 (firm), in MHP 101 (MHP is located in section 7D of the campus map)
Final Exam	:	8am-10am, Fri, 5/8/2015 (firm), in SLH 102 (SLH is located in section 6C of the campus map)

Description	:	textbooks, topics covered, grading policies, additional resources, etc.
Papers	:	required technical papers
Lectures	:	slides from lectures in HTML and PDF formats
Participation	:	rules about roll calls.
Homeworks	:	homework assignments (please also see important information about programming assignments at the bottom of this page.)
Newsgroup	:	Google Group for discussing course materials and programming assignments. You are required to be a member of this group. (This group is by invitation only.)

• 4/27/2015: I have to leave campus at 12:30pm tomorrow (Tue, 4/28/2015). So, I have to cancel tomorrow's office hour. Sorry about the inconvenience and the short notice.

• 4/27/2015: The final exam will be closed book, closed notes, and closed everything, except for a single (letter-sized) "crib sheet / cheat sheet". (You can write or print whatever you want on it on both sides of the cheat sheet. Magnifying glasses are not allowed, so don't print too small! You will be required to turn in the cheat sheet together with the exam paper.)

  Also, no calculators, cell phones, or any electronic gadgets are allowed. Please bring a photo ID. Your ID will be collected at the beginning of the exam and will be returned to you when you turn in your exam. There will be assigned seating.

  The final exam will cover everything from math background for AES (slide 4 of lecture 12 on 2/25/2015) to slide 16 of lecture 25 on 4/22/2015. Here is a quick summary of the topics (not all topics covered are listed):

  • Block Ciphers
    • AES
      • math for Rijndael
        • xtime()
        • multiplication in GF(2⁸)
        • multiplicative inverse in GF(2⁸)
          • extended Euclidean algorithm
          • table method
        • multiplication of polynomials with coefficients in GF(2⁸)
      • components and structure of Rijndael
        • SubBytes() and InvSubBytes()
        • ShiftRows() and InvShiftRows()
        • MixColumns() and InvMixColumns()
        • AddRoundKey()
        • key expansion
      • equivalent inverse cipher
      • security of Rijndael
  • Generating Primes
    • math background
      • quadratic residue
      • square root
      • Legendre and Jacobi symbols
      • pseudosquares
      • Blum integers
      • integer factorization
        • Pollard's rho factoring algorithm
      • primality proving algorithms
        • using the factorization of n-1
        • Pocklington's theorem
    • probabilistic primality tests
      • Fermat's test
      • Carmichael number
      • Solovey-Strassen test
      • Miller-Rabin test
    • generating probable primes
      • RANDOM-SEARCH(k,t)
      • incremental search
    • generating provable primes
      • Maurer's algorithm
  • Public-key Encryption
    • background
      • extended Euclidean algorithm
      • modular exponentiation algorithm
      • Chinese remainder theorem
      • residue number system
      • Garner's algorithm
    • RSA
      • the RSA problem
      • key generation
      • security of RSA
        • small exponent problem
        • forward search attack
        • multiplicative properties
        • common modulus attack
        • cycling attack
        • message concealing
    • Diffie-Hellman
      • the Diffie-Hellman problem
    • ElGamal
      • key generation
      • encryption/decryption
      • randomized encryption
    • Rabin
      • key generation
      • encryption/decryption
      • finding square roots
  • Pseudorandom Bit Generators
    • linear congruential generator
    • polynomial-time statistical tests
      • statistics background
        • normal distribution
        • chi-square distribution
      • five basic tests
        • frequency (mono-bit) test
        • serial (two-bit) test
        • poker test
        • runs test
        • autocorrelation test
    • cryptographically secure PRBG
      • RSA pseudorandom bit generator
      • Blum-Blum-Shub pseudorandom bit generator
  • Stream Ciphers
    • synchronous vs. self-synchronizing stream ciphers
    • LFSR
      • connection polynomial
      • linear complexity
      • Berlekamp-Massey algorithm
    • Non-linear FSR
      • de Bruijn FSR
    • Stream ciphers based on LFSRs
      • Geffe generator
      • correlation attacks and correlation immunity
      • summation generator
      • non-linear filter generator and knapsack generator
      • clock controlled generators
        • alternating step generator
        • shrinking generator
    • Stream ciphers not based on LFSRs
      • RC4 (FMS attack excluded)
      • SEAL
  • Hash Functions
    • keyed hash functions
      • MACs
    • unkeyed hash functions
      • MDCs
        • OWHF
        • CRHF
    • hash function properties
      • compression
      • ease of computation
      • preimage resistance
      • 2nd-preimage resistance
      • collision resistance
    • computational resistance for MACs
    • Yuval's birthday attack
    • one-way functions
      • compression functions
      • DES-based one-way functions
      • other one-way functions
    • iterated hash functions
    • Merkle's meta-method for hashing
    • Merkle Damgard strengthening
    • padding
    • unkeyed hash functions
      • single-length and double-length MDCs
      • MD5
      • MD5 & SHA-1 seriously broken
    • keyed hash functions
      • CBC-based MACs
      • HMAC
  • Digital Signatures
    • classification of digital signature schemes
      • digital signature schemes with appendix
      • digital signature schemes with message recovery
        • redundancy function
    • attack on digital signature schemes
    • digital signature schemes
      • RSA digital signature scheme
        • reblocking problem
      • ElGamal digital signature scheme
      • DSA
      • One-time digital signatures
        • Lamport
        • Rabin
        • Merkle
  • Introduction to Cryptographic Protocols
    • protocol and mechanism failures
    • key management via symmetric-key techniques
    • key management via public-key techniques
      • certificate and certificate authority
      • trusted third party
      • public-key infrastructure
  • HW6, HW7

• 4/22/2015: I have to leave campus at 2pm tomorrow (Thu, 4/23/2015). So, I have to shorten tomorrow's office by half an hour. Sorry about the inconvenience and the short notice.

• 3/29/2015: To accommodate CS 531 midterm regrades, I have to adjust my office hours this week (3/30-4/2) and just for this week. On M/W, I will need to end my office hours half an hour early. On Tu/Th, I will need to move my office hours half an hour earlier. So, my office hours this week will be:
  • Monday (3/30): 2-2:30pm
  • Tuesday (3/31): 1-2pm
  • Wednesday (4/1): 2-2:30pm
  • Thursday (4/2): 1:30-2:30pm

• 3/15/2015: One way to keep a private key private is to keep it inside a hardware chip. (You've seen the movies... if you open up the chip, smoke comes out and the key self-destructs.) Here's a recent article on how to use Power Analysis to sniff out a private key in a TPM chip (also known as the "crypto co-processor") on your Windows 8 machine.

• 2/25/2015: The midterm exam will be closed book, closed notes, and closed everything (and no "cheat sheet"). Also, no calculators, cell phones, or any electronic gadgets are allowed. Please bring a photo ID. Your ID will be collected at the beginning of the exam and will be returned to you when you turn in your exam. There will be assigned seating.

  The midterm exam will cover everything from the beginning of the semester till the end of DES (slide 3 of Lecture 12 on 2/25/2015).

  Here is a quick summary of the topics (not all topics covered are listed):

  • overview
    • functions
      • bi-jections and inverses
      • one-way functions and trapdoor one-way functions
      • permutations
    • encryption schemes
      • max number of permutations
      • model of communication and channels
    • types of adversaries
    • types of cryptanalysis
    • symmetric-key encryption
      • model of communication and channels
      • block ciphers
        • substitution ciphers
          • mono-alphabetic substitution cipher
          • homophonic substitution cipher
          • polyalphabetic substitution cipher
        • transposition ciphers
        • composition of ciphers and product ciphers
      • stream ciphers
        • Vernam ciphers and one-time pad
      • key space issues
    • digital signatures
      • signing and verification transformations
    • authentication and identification
      • entity vs. data origina authentication
    • public-key cryptography
      • necessity of authentication
      • digital signature from reversible public-key encryption
    • cryptographic hash functions
      • one-wayness
      • weak collision-resistance
      • strong collision-resistance
      • keyed vs. unkeyed hash functions
    • protocols and mechanisms
      • protocol failures
    • key management
      • symmetric-key and trusted third party
      • public-key and certificate authority
    • attacks
      • ciphertext-only
      • known-plaintext
      • chosen-plaintext
      • chosen-ciphertext
    • security models
      • unconditional security
      • complexity-theoretic security
      • provable security
      • computational security
      • ad hoc security
  • block ciphers
    • classical ciphers
      • simple transposition ciphers
      • mono-alphabetic substitution cipher
      • polygram substitution cipher
      • homophonic substitution cipher
      • cryptographic codes
      • polyalphabetic substitution cipher
        • Vigenere cipher and variants
        • Jefferson cylinders and rotors and the Enigma machine
    • cryptanalysis of classical ciphers
      • language statistics
      • method of Kasiski
      • index of coincidences (auto-correlation only)
    • block cipher analysis
      • True Random Cipher
      • complexity of attacks
      • birthday paradox
    • modes of operation
      • ECB
      • CBC
      • CFB
      • OFB
    • cascade cipher and multiple encryption
      • meet-in-the-middle attacks
      • known-plaintext unicity distance
      • attacks on multiple encryption
    • DES
      • product ciphers
      • Fiestel
      • DES algorithm
        • P
        • S
        • E
      • DES key scheduling
        • V
        • PC1
        • PC2
      • DES properties
      • DES weak and semi-weak keys
      • cryptanalysis of DES
  • HW1, HW2, HW4

• 2/23/2015:
  • Office hour this Tuesday (2/24/2015) is cancelled and moved to Wednesday (2/25/2015) 3:00pm - 4:00pm. Sorry about the inconvenience and the short notice.
  • Interesting article about Microsoft and Apple trying to get rid of the use of password authentication.

• 1/20/2015: I have to leave campus right after lecture today. So, I have to cancel office hours today. Sorry about the inconvenience and the short notice.

• 12/28/2014:
  • In case you did not hear the user ID and password for accessing protected area of this web site during the first lecture, please visit the request access page after semester starts and submit the requested information. (You do not have to be registered for the course to get the password. You just need to have an USC e-mail address.)

  • Watch this area for important announcements.

If a student signs up late for this class, he/she is still required to turn all projects and homeworks on time or he/she will receive a score of 0 for these assignments. No exceptions!