<? print $coursetitle ?> - <? print $id_sem_and

-

General Information

Time	:	MW 2:00pm - 3:20pm
Location	:	VKC 101
Instructor	:	Bill Cheng, Office Hours: TuTh 1:30pm - 2:30pm in SAL 228, E-mail: <bill.cheng@usc.edu> or <william@bourbon.usc.edu> (Please do not* send HTML-only e-mails. They will not be read.)*
TA	:	Anand Narayanan, E-mail: <aknaraya@usc.edu> Office Hours: Wed, 9:00am - 11:00am in SAL 211
Grader	:	Roshan Kotian E-mail: <kotian@usc.edu>, (The grader will hold office hours the week after the announcement of each homework assignment's grades.)
Midterm Exam	:	in class, Mon, 10/22/2007 (firm)
Final Exam	:	2pm-4pm, Fri, 12/14/2007 (firm)
Msg Archives	:	messages from Bill, messages from Anand, messages from Roshan

Class Resources

Description	:	textbooks, topics covered, grading policies, additional resources, etc.
Papers	:	required technical papers
Lectures	:	slides from lectures in HTML and PDF formats
Homeworks	:	homework assignments (please also see important information about programming assignments at the bottom of this page.)
Moodle	:	social forum can be used for students-to-students discussions about assignments.

News

(in reversed chronological order)

12/5/2007: The final 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 final exam will cover everything from DES (slide 33 of lecture 14) to the end of the last lecture. Here is a quick summary of the topics (not all topics covered are listed):
- stream ciphers
  - synchronous vs. self-synchronizing stream ciphers
  - LFSR
    - connection polynomial
    - math background
      - number theory
      - abstract algebra
        
        group
        ring
        field
        polynomial ring
        finite field
    - 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
    - SEAL
- Block Ciphers
  - 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
  - AES
    - structure of Rijndael
    - 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
- 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
  - MDCs based on block ciphers
    - Matyas-Meyer-Oseas
    - Davies-Meyer
    - Miyaguchi-Preneel
    - MDC-2 and MDC-4
  - customized hash functions based on MD4
    - MD5
    - SHA-1
  - MACs based on block ciphers
    - CBC-based MACs
- Digital Signatures
  - classification of digital signature schemes
    - digital signature schemes with appendix
    - digital signature schemes with message recovery
    - key generation
    - signature generation
    - verification
    - redundancy function
  - forging digital signatures
    - selective forgery
    - existential forgery
  - digital signature schemes with message recovery
    - RSA
      - multiplicative property
      - reblocking problem
- HW5, HW6, HW7

11/29/2007: Office hour today has been moved up by 15 minutes. Sorry about the inconvenience.

11/26/2007: Office hour on 11/27/07 has been cancelled. Sorry about the inconvenience.

11/6/2007: Please check out the announcement for the SS12 event.

10/24/2007: Office hour on 10/25/07 is moved to 11:00am-12:00pm. Sorry about the inconvenience.

10/17/2007: The midterm exam will be held in VKC 101. It is 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 cryptanalysis of classical ciphers (last slide is slide 32 of lecture 14 on 10/15/2007).
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
- 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
- block ciphers
  - attacks
    - complexity of attacks
  - modes of operation
    - ECB
    - CBC
    - CFB
    - OFB
  - cascade cipher and multiple encryption
    - meet-in-the-middle attacks
    - known-plaintext unicity distance
  - 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
    - unicity distance
    - language statistics
    - method of Kasiski
    - index of coincidences
- HW1, HW2, HW3, HW4
10/17/2007: Office hour on 10/18/07 has been cancelled. Sorry about the inconvenience.

10/7/2007: Office hour on 10/9/07 has been moved to 10:30am-11:30am on Monday, 10/8/07. Sorry about the inconvenience.

10/3/2007: Office hour on 10/4/07 is moved to 11:00am-12:00pm. Sorry about the inconvenience.

10/1/2007: Office hour on 10/2/07 is moved to 10:45am-11:45am. Sorry about the inconvenience.

9/6/2007: The change of office hour on 9/6/07 has been canceled. It's back on regular time. Office hour on 9/11/07 is moved to 2-3pm instead. Sorry about the inconvenience!

9/5/2007: Office hour on 9/6/07 is moved to 2-3pm. Sorry about the inconvenience.

8/23/2007: There are no office hours during the first week of class. If you need to see me, please make an appointment by sending an e-mail to me. Sorry about the inconvenience.

8/22/2007: Registering with the class mailinglist is required for this class. If you have not done so, please visit the mailinglist page. (You do not have to be registered for the course to register with the class mailinglist.)

8/7/2007: Watch this area for important announcements.

Prerequisites

CS 102L (Data Structures) or graduate standing. It is assumed that you know how to write programs, and how to debug them and make them work correctly.

Important Information about Programming Assignments

All homework assignments are programming assignments to be done in C/C++. No other programming language will be accepted and your program must compile and run with a Makefile on nunki.usc.edu. (Sorry, no Java.) You must be familiar with the UNIX development environment (vi/pico/emacs, cc/gcc or g++/CC, make, etc.)

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!