

Applied Cryptography 
CSCI 531, Spring 2016



General Information


Time 
: 
MW 9:30am  10:50am 
Location 
: 
OHE 100D 
Instructor 
: 
Bill Cheng
(for office hours, please see
instructor's web page),
Email:
<bill.cheng@usc.edu>.
(Please do not send HTMLonly emails. They will not be read.)

TA 
: 
ChienLun Chen,
Email:
<chienlun@usc.edu>,
Office Hours: Fri 3:10pm  5:00pm in PHE 320

Grader 
: 
Peera Yoodee,
Email:
<yoodee@usc.edu>.
(The grader will hold office hours the week after the announcement of each assignment's grades.)

Midterm Exam 
: 
during class, Mon, 3/7/2016 (firm)

Final Exam 
: 
8am10am, Fri, 5/6/2016 (firm)



Class Resources


Description 
: 
textbooks, topics covered, grading policies, additional resources, etc.

Papers 
: 
required and optional technical papers

Lectures 
: 
slides from lectures in HTML and PDF formats

Videos 
: 
information about DEN lectures and discussion sections videos.

Discussions 
: 
information about discussion sections.

Homeworks 
: 
programming assignments
(please also see important information about programming assignments
at the bottom of this page.)

Participation 
: 
rules about roll calls.

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.)
Please do not send request to join this group until 1/13/2016.



News

(in reversed chronological order)
 4/28/2016: The discussion section today is moved to 2:003:00pm
(due to a meeting I have to attend which starts at 12:30pm). Sorry about the inconvenience.
 4/27/2016: The final exam will be closed book,
closed notes, and closed everything, except
for a single (lettersized) "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 12 of lecture 11 on 2/22/2016)
to slide 10 of lecture 25 on 4/20/2016.
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^{8})
 multiplicative inverse in GF(2^{8})
 extended Euclidean algorithm
 table method
 multiplication of polynomials with coefficients in
GF(2^{8})
 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
 primality proving algorithms
 using the factorization of n1
 Pocklington's theorem
 probabilistic primality tests
 Fermat's test
 Carmichael number
 SoloveyStrassen test
 MillerRabin test
 generating probable primes
 generating provable primes
 Publickey 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
 DiffieHellman
 the DiffieHellman problem
 ElGamal
 key generation
 encryption/decryption
 randomized encryption
 Rabin
 key generation
 encryption/decryption
 finding square roots
 Pseudorandom Bit Generators
 linear congruential generator
 polynomialtime statistical tests
 statistics background
 normal distribution
 chisquare distribution
 five basic tests
 frequency (monobit) test
 serial (twobit) test
 poker test
 runs test
 autocorrelation test
 cryptographically secure PRBG
 RSA pseudorandom bit generator
 BlumBlumShub pseudorandom bit generator
 Stream Ciphers
 synchronous vs. selfsynchronizing stream ciphers
 LFSR
 connection polynomial
 linear complexity
 BerlekampMassey algorithm
 Nonlinear FSR
 Stream ciphers based on LFSRs
 Geffe generator
 correlation attacks and correlation immunity
 summation generator
 nonlinear 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
 unkeyed hash functions
 hash function properties
 compression
 ease of computation
 preimage resistance
 2ndpreimage resistance
 collision resistance
 computational resistance for MACs
 Yuval's birthday attack
 oneway functions
 compression functions
 DESbased oneway functions
 other oneway functions
 iterated hash functions
 Merkle's metamethod for hashing
 Merkle Damgard strengthening
 padding
 unkeyed hash functions
 singlelength and doublelength MDCs
 MD5
 MD5 & SHA1 seriously broken
 keyed hash functions
 Digital Signatures
 classification of digital signature schemes
 digital signature schemes with appendix
 digital signature schemes with message recovery
 attack on digital signature schemes
 digital signature schemes
 RSA digital signature scheme
 ElGamal digital signature scheme
 DSA
 Onetime digital signatures
 Introduction to Cryptographic Protocols
 protocol and mechanism failures
 key management via symmetrickey techniques
 key management via publickey techniques
 certificate and certificate authority
 trusted third party
 publickey infrastructure
 week 7 discussion
 review of finite field, multiplying & dividing polynomials, modular exponentiation
 week 9 discussion (HW5)
 week 10 discussion
 week 11 discussion (HW6)
 trial division
 Miller Rabin
 random search
 Maurer's algorithm
 week 12 discussion
 review of RSA, Chinese remainder theorem, Garner's algorithm
 week 13 discussion (HW7)
 RC4
 frequency (monobit) test
 serial (twobit) test
 poker test
 runs test
 autocorrelation test
 3/29/2016: The discussion section this Thursday (3/31/2016) is canceled
(due to a meeting I have to attend which starts at 12:30pm and I'm doing CS 531 midterm regrade afterwards).
I'm making it up by extending this Wednesday's office by one hour (from 2pm to 4pm).
Sorry about the inconvenience.
 3/11/2016: The TA has an urgent family matter to take care of and has to cancel his office hours today.
But I will be in my office today between 1pm and 2:50pm. Please feel free to come by my office if you were
planning on seeing the TA today. Sorry about the inconvenience.
 3/2/2016: The discussion section this Thursday (3/3/2016) is moved to 2:003:00pm
(due to a meeting I have to attend which starts at 12:30pm). Sorry about the inconvenience.
 3/1/2016:
 The 2015 Turing Award goes to
Whitfield Diffie and Martin Hellman, cryptographers credited as the inventors of public key cryptography.
 2/22/2016:
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 11 of Lecture 11 on 2/22/2016)
and including topics covered by the first 6 weeks of discussion sections.
Here is a quick summary of the topics (not all topics covered are listed):
 overview
 functions
 bijections and inverses
 oneway functions and trapdoor oneway functions
 permutations
 encryption schemes
 max number of permutations
 model of communication and channels
 types of adversaries
 types of cryptanalysis
 symmetrickey encryption
 model of communication and channels
 block ciphers
 substitution ciphers
 monoalphabetic substitution cipher
 homophonic substitution cipher
 polyalphabetic substitution cipher
 transposition ciphers
 composition of ciphers and product ciphers
 stream ciphers
 Vernam ciphers and onetime pad
 key space issues
 digital signatures
 signing and verification transformations
 authentication and identification
 entity vs. data origina authentication
 publickey cryptography
 necessity of authentication
 digital signature from reversible publickey encryption
 cryptographic hash functions
 onewayness
 weak collisionresistance
 strong collisionresistance
 keyed vs. unkeyed hash functions
 protocols and mechanisms
 key management
 symmetrickey and trusted third party
 publickey and certificate authority
 attacks
 ciphertextonly
 knownplaintext
 chosenplaintext
 chosenciphertext
 security models
 unconditional security
 complexitytheoretic security
 provable security
 computational security
 ad hoc security
 block ciphers
 classical ciphers
 simple transposition ciphers
 monoalphabetic 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
 block cipher analysis
 True Random Cipher
 complexity of attacks
 birthday paradox
 modes of operation
 cascade cipher and multiple encryption
 meetinthemiddle attacks
 knownplaintext unicity distance
 attacks on multiple encryption
 DES
 product ciphers
 Fiestel
 DES algorithm
 DES key scheduling
 DES properties
 DES weak and semiweak keys
 cryptanalysis of DES
 week 1 discussion (HW1)
 hexdump
 base64 encoding/decoding
 week 2 discussion
 converting integers
 bit flipping
 modular arithmetic
 Euclidean Algorithm
 primes
 week 3 discussion (HW2)
 week 4 discussion
 Playfair cipher
 Hill cipher
 Beaufort cipher
 autokey Vigenere cipher
 Jefferson cylinder
 rotorbased machines
 week 5 discussion (HW3)
 full Vigenere cipher
 cryptanalysis
 method of Kasiski
 index of coincidences (autocorrelation only)
 week 6 discussion
 extended Euclidean Algorithm
 multiplicative inverse
 Wilson's theorem
 2/3/2016: The discussion section this Thursday (2/4/2016) is moved to 2:303:30pm
(due to a meeting I have to attend which starts at 12:30pm). Sorry about the inconvenience.
 1/14/2016: I am on jury duty today. Office hour
today is canceled.
 1/12/2016:
 I won't need to go to court tomorrow (Wednesday, 1/13/2016)! Class will be held normally tomorrow.
 According to this article, we need at least 2.7 million people this year
with cloudcomputing skills who also understand information security.
 1/9/2016: Unfortunately, I'm on standby for jury duty during the first week of classes this semester.
I will only know if I need to go to court the night before.
At this point, I know that I will not have to go to court on Monday, 1/11/2016 but I don't know about Wednesday, 1/13/2016.
I will post a news item here Tuesday night on 1/12/2016 so you know if the lecture on Wednesday is canceled or not.
If I have to cancel a lecture, I will find a way make up the lecture soon after.
 1/1/2016:
 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 email address.)
 I have replaced the number theory optional textbook because the previous one was getting expensive.
You don't really have to buy any of the optional textbooks.
 Please do not send request to join the
class Google Group until 1/13/2016.
 Watch this area for important announcements.


Prerequisites

CS 102L (Data Structures) or graduate standing. It is assumed that
you know how to write programs in C/C++, how to use data structures
and algorithms so your program can run efficiently, and how to debug
programs 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 you are not familiar with Unix, please read Unix for the Beginning Mage,
a tutorial written by Joe Topjian.
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!


