Course Description - CSCI 531, Spring 2014

Focus		Note From A Doctor		Auditing
CS 530 & CS 556		Regrade Policy		E-mail
Textbooks		Office Hours		Academic Integrity Policy
Syllabus / Topics Covered		Extra Credit		Diversity Statement
Homework Assignments		Newsgroup		Academic Calendar
Exams		Implicit Student Agreement		Additional Resources
Grading		Student Responsibilities
Late Policy		Fairness

This course will provide an intensive overview of the field of cryptography, providing a historical perspective on early systems, building to the number theoretic foundations of modern day cryptosystems. Students will learn how cryptosystems are designed, and to match cryptosystems to the needs of an application. Students will also study basic cryptanalysis and will be presented with real life breaches of common cryptosystems so that they better understand the dangers that lurk in cryptosystem design and in the design of systems that rely on cryptography.

Please note that this is a Computer Science class and not a "tech class", i.e., it is not about the latest products and standards. The course material and assignments are meant to give students background in understanding the cryptographic techniques used in the current products and standards.

CS 556 should be viewed as a "fundamnetal" cryptography class with emphasis on the theoretic side of cryptography. CS 531 is a more "introductory" cryptography class with emphasis on the applied side of cryptography (less emphasis on mathetical proofs). Almost all mathematical theorems presented in CS 531 will be introduced as facts and without rigorous proofs. For CS 531, there are no written homework assignments. All homeworks assignments are programming assignments.

There is about a one-week overlap between the Applied Cryptograph class and CS 530.

• A. J. Menezes, P. C. Van Oorschot, S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1996.
  (An online version of this book is available at http://www.cacr.math.uwaterloo.ca/hac/. In order to save some trees, please do not print out the whole book because we are not covering the whole book! Also, please make sure you follow the Copyright Notice there.)

• S.Y. Yan, Number Theory for Computing, 2nd Edition, Springer, 2002.
  (If you are not comfortable with Number Theory, this is a good book to start to get you warmed up.)

• Wk 1-3: Overview of Cryptography (HAC Ch 1)
  • Introduction to various cryptographic concepts
  • Attacks
  • Security models
• Wk 4-6: Block Ciphers (HAC Ch 7)
  • Modes of operations
  • Classical ciphers and their cryptanalysis
  • DES
• Wk 7-8: The AES Block Cipher (FIPS publication 197)
• Wk 9: Public-key Parameters (HAC Ch 4)
  • Legendre and Jacobi symbols
  • Primality tests (Fermat.s test, Miller-Rabin test, AKS test)
  • Generating probable prime numbers
  • Generating provable prime numbers
• Wk 10: Number-theoretic Reference Problems (HAC Ch 3)
  • Integer factorization
  • RSA problem
  • Diffie-Hellman problem
  • Square root modulo n problem
  • Discrete logarithm problem
• Wk 11: Public-key Encryption (HAC Ch 8)
  • Chinese remainder theorem and residue number system
  • RSA public-key encryption
  • Diffie-Hellman key exchange
  • ElGamal public-key encryption
  • Rabin public-key encryption
• Wk 12: Pseudorandom Bits and Sequences (HAC Ch 5)
  • Normal and Chi-square distributions
  • Five basic statistical tests for randomness
  • Cryptographically secure pseudorandom bit generators
• Wk 13: Stream Ciphers (HAC Ch 6)
  • LFSR (Linear Feedback Shift Register)
  • Non-linear FSR
  • Stream ciphers based on LFSR
  • RC4
• Wk 14: Hash Functions and Data Integrity (HAC Ch 9)
  • MAC (message authentication code)
  • MDC (modification detection code)
  • One-way hash function
  • Collision resistant hash function
  • Yuval.s birthday attack
  • Breaks of hash functions
• Wk 15: Digital Signatures (HAC Ch 11)
  • RSA signature scheme
  • Fiat-Shamir signature scheme
  • ElGamal signature scheme
  • One-time signature schemes

Exam Frequently Asked Questions

There are two types of exam questions that I usually ask. The first type is numerical and you need to calculate something (usually arithematics with small integers). I have provided some practice problems (access restricted).

The second type is in the following form: "In N words or less, what is the answer to the following question?"

For this type of question, you can write as many words as you'd like, but I will only read the first N words of your answer! You don't need to count the number of words in your answer, you just need to make sure that the most important part of your answer appears in the first N words! (There is no need to write complete English sentenses when you answer exam questions. Just give me the important stuff!)

The reason I'm doing this is that I don't want a brain dump of everything you know about a topic and tell me that the answer is there and that I have to look for it! I want you to tell me what part of your answer you think is important and you need to distinguish between answers of different quality and put the best answer up front.

Let me give a couple of silly examples (with questions that's not in the scope of any exam).

• "In 20 words or less, for our programming assignments, when is 'plagiarism' considered taking place? If your answer is "when you take someone else's work and claim it to be yours", then you will get full credit. If your answer is, "when you submit someone else's work", you probably will not get full credit.

• "In 20 words or less, what is the fairness policy of this class?" If your answer is, "whatever the instructor offer to one student, he must offer it to the rest of the class," then you will get full credit. If your answer is, "the instructor must be fair to every student," you probably will not get much credit.

• "In 20 words or less, what is the definition of X."

In general, better answers may score more points. If you give very high level and generic answer that's generally true or basically just repeat the question, you probably will get very little credit for it! You need to answer a specific question with a specific answer.

Participation:		3%	(extra credit)
Homeworks:		35%
Midterm Exam:		30%
Final Exam:		35%

Pleaes also note the following:

• The above percentages will be used to calculate your total score. Final grades (A,B,C,D,or F) will be determined using a modified curve (i.e., we won't necessarily assign an equal number of failing grades as passing grades) based on this total score. No other methods will be considered. (So, please do not ask the instructor to take how much you have improved since the beginning of the semester into account. You are expected to try your best from the beginning!)

• We will assign grades of C and below to individuals who do not perform satisfactorily in the above areas. (i.e., you should not assume a B- or even C if you perform unsatisfactorily.) However, we hope that everyone will perform well.

• Your assignments are your own work! No group assignments are allowed or will be tolerated. You are free to talk to other students about assignments but no actual material (files, code fragments, etc.) should be shared. We will act harshly at any sign of copying.

• We will not assign incompletes unless it is for a documented medical reason (in accordance with USC policy).

If you are unable to complete a homework assignment due to illness or family emergency, please see the instructor as soon as possible to get an extension. A doctor's note is required as proof of illness or emergency. In general, when you get sick, it's best to see a doctor and get a note just in case you may need it later.

So, if you visit a doctor at the Student Health Center, please make sure you fill out one of these forms, check the "limited discussion with faculty" checkbox, get it stamped, signed, and dated by someone there (a clerk/receptionist would sign at the "witness" line), and bring it back to me. This would satisfy the "note from a doctor" requirement so that you can get an extension.

If you visit a doctor somewhere else, please either bring a "note from the doctor" or a similar authrozation letter so I can contact them.

If you need to see me outside of office hours, it's best that you make an appointment (and reserve a timeslot) so I can make sure to be in my office when you visit. Making an appointment is not a big deal! Just send an e-mail to me and tell me when you are available to meet and go from there.

The instructor may not normally read this forum. Please do not post questions directed to him here.

Please make sure that you have read the Academic Integrity Policy of this course.

This policy also holds for programming assignments. In this class, we will use sophisticated automated program checkers to detect cheating. Be aware that the program checkers have demonstrated very good results and are widely used within the academic community. Any student caught cheating will be given zero credit and will be disciplined.

It is the students responsibility to submit their assignments in time.

There is no specific prerequisites for this course, but students are expected to be familiar with programming in C/C++ on the UNIX platform. No special assistance or consideration will be offered if your background is inadequate.

You are expected to read all the papers in detail. Not all details will be covered in class.  We will assume knowledge of material covered in EE450 and a C language programming proficiency from CSci402 or its equivalent. If you covered the introductory material at some other school it is YOUR responsibility to fill in any missing background. Feel free to ask me for advice on appropriate introductory readings if you feel your background is insufficient.

We expect you to attend every class meeting. If you do happen to miss a session, you are responsible for finding out what material was covered and if any administrative announcements were made. You must do so BEFORE the next session (e.g., if there is an assignment given during the missed session, you are still responsible for completing it by the next week along with the other students).  You are advised to read the papers for a particular lecture before attending the lecture. This will greatly enhance your understanding of the subject matter.

Please do not ask the following types of questions in your e-mail (although they are appropriate for office hours):

• Here is my understanding of X. Am I right (or is this correct)?
  (You can do this for just about everything and in many different ways. I do not have the bandwidth to deal with too many questions like this.)

• I don't understand X. Could you explain X to me?
  (It's your responsiblity to come to lectures and ask questions during lectures if there is something you do not understand.)

• OpenSSL
• AES

Programming:

• C Programming (by Steve Holmes at the University of Strathclyde in Glasgow, England) - includes notes on make, separate compilation, file I/O, etc.
• Makefile tutorial (at Colby College)
• Steve's Software Trek (by Steve Karg) - includes some useful C/C++ source code for string manipulation, INI file manipulation, etc.
• C Examples - lots and lots of sample C code for basic stuff.
• C/C++ at USC from USC ITSWeb
• Online Judge online portal for IT interview

• Ubuntu Linux
• cygwin (BSD system with X11R6 on Windows XP)
• Some Often-used UNIX Commands
• Unix commands (more complete, from University of Utah)
• UNIX Shell Programming (Chapter 2 of this book gives a good introduction to UNIX)
• UNIXhelp for Users from the University of Edinburgh
• UNIX Tutorial for Beginners from the University of Surrey
• Introduction to the Unix Shell from the Canisius College
• Introduction to C Shell Programming from the Canisius College
• C/C++ Documentation (compiling, linking, additional libraries, include files) from USC ITSWeb
• Understanding C by learning assembly
• UNIX Documentation (concepts, commands, X-Windows) from USC ITSWeb
• Editors on most UNIX systems
  • Vi Text Editor Documentation from USC ITSWeb
  • EMACS Text Editor Documentation from USC ITSWeb
  • Pico Text Editor Documentation from USC ITSWeb
• Beej's Quick Guide to GDB
• Richard Stallman's gdb Tutorial
• General information on operating systems, productivity applications, Internet connectivity, e-mail and web publishing at USC, can be found at the ITS software site. You can click on your operating system and download useful software from there. For example, for the Windows platform, you can find things like X-Win32, FileZilla, and PuTTY there.