USC CSD Home
 

Course Description - CSCI 531, Spring 2016

Links to sections on this page:
  • Focus
  •     
  • Late Policy
  •     
  • Fairness
  • CS 530 & CS 556
  •     
  • Note From A Doctor
  •     
  • Auditing
  • Textbooks
  •     
  • Regrade Policy
  •     
  • E-mail
  • Syllabus / Topics Covered
  •     
  • Office Hours
  •     
  • Academic Integrity Policy
  • Homework Assignments
  •     
  • Extra Credit
  •     
  • Diversity Statement
  • Exams
  •     
  • Implicit Student Agreement
  •     
  • Academic Calendar
  • Grading
  •     
  • Student Responsibilities
  •     
  • Additional Resources
  •  
    Focus
    Cryptography provides a critical foundation upon which much of computer security is based. Cryptography is necessary to provide both integrity and confidentiality of the data that is exchanged in a computer network. There are many methods of encryption, and each has its strengths and weaknesses in terms of performance, security, and requirements for management of secret information used to hide or disclose information.

    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.

     
    Relationships to CS 530 and CS 556
    I have received many inquires regarding the difference between this class and the Introduction to Cryptography class (CS 556).

    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 two-week overlap between the Applied Cryptograph class and CS 530.

     
    Textbooks
    Required: Optional:
     
    Syllabus / Topics Covered
    The following schedule and topics are tentative and are subject to change without notice. (The "Handbook of Applied Cryptography" is denoted as "HAC" below and the "Applied Cryptography" book by Schneier is denoted as "AC" below.)
    • Wk 1-3: Overview of Cryptography (HAC Ch 1)
      • Introduction to various cryptographic concepts
      • Attacks
      • Security models
    • Wk 4-5: Block Ciphers (HAC Ch 7)
      • Classical ciphers and their cryptanalysis
      • Modes of operations
      • DES
    • Wk 6-7: AES
      • Math background for AES (HAC Ch 2)
      • The AES Block Cipher (FIPS publication 197)
    • Wk 8: 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 9: Public Key Cryptography
      • Number-theoretic Reference Problems (HAC Ch 3)
        • Integer factorization
        • RSA problem
        • Diffie-Hellman problem
        • Square root modulo n problem
        • Discrete logarithm problem
      • 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 10: Pseudorandom Generators and Stream Ciphers
      • Pseudorandom Bits and Sequences (HAC Ch 5)
        • Normal and Chi-square distributions
        • Five basic statistical tests for randomness
        • Cryptographically secure pseudorandom bit generators
      • Stream Ciphers (HAC Ch 6)
        • LFSR (Linear Feedback Shift Register)
        • Non-linear FSR
        • Stream ciphers based on LFSR
        • RC4
    • Wk 11: Hash Functions and Digital Signatures
      • Hash Functions and Data Integrity (HAC Ch 9)
        • MAC (message authentication code)
        • MDC (modification detection code)
        • OWHF (one-way hash function)
        • CRHF (collision resistant hash function)
        • Yuval.s birthday attack
        • Breaking of hash functions
      • Digital Signatures (HAC Ch 11)
        • RSA signature scheme
        • Fiat-Shamir signature scheme
        • ElGamal signature scheme
        • One-time signature schemes
    • Wk 12: Authentication & Key Management (HAC Ch 10, 12, 13)
    • Wk 13-15: Cryptographic Protocols
      • Basic cryptographic protocols (AC Ch 3)
      • Intermediate cryptographic protocols (AC Ch 4)
      • Advanced cryptographic protocols (AC Ch 5)
      • Esoteric cryptographic protocols (AC Ch 6)
     
    Homework Assignments
    There will be 6-8 homework assignments consisting of small programming assignments.
     
    Exams
    A midterm and a final examination will be given. The dates for these exams are posted near the top of the class home page. Any scheduling conflicts regarding the midterm exam date must be resolved with the instructor at least one week before the exam date. The date of the final examination is firm and cannot be changed.

    Exam Frequently Asked Questions

    I often get questions such as (1) can I get a copy of an old exam and (2) what types of questions should I expect? The answer to question (1) is "no". I'm sorry, but I do not give out old exams. That's just my policy. The answer to question (2) is the following.

    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 for the midterm exam and some practice problems for the final exam (access restricted for both). In general, you need to show your work so I know how you got your answers. If you just give a numerical answer without any justification, you may not get any credit.

    The second type is to ask you to give the best answer for a word question. (If a question says, "In N words or less...", it's giving you a hint that the answer should be N words or less. You don't have to answer in N words or less. There is one exception though. If the question is of the fill-in-the-blanks type where N is small, then you must not use more than N words.)

    For this type of question, you get credit for including the "best answer". You may get deductions for including "bad answers". What you need to demonstrate is that you can distinguish between answers of different quality and write down the best answer. (For these questions, there is no need to write complete English sentences when you answer exam questions. Just give me the important stuff!)

    An example is, "In N words or less, what is the definition of X." You get full credit if you include all the important words in the definition of X and don't mention anything incorrect. The more of the important words you missed, the less partial credit you will get.

    Exam Grading

    In order to be fair to the entire class, we can only grade based on what you put down on the exam paper. We must not take into consideration what's in your mind when you wrote your answers. We have to assume that you wrote what you meant and meant what you wrote.

    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 partial credit for it! You need to answer a specific question with a specific answer. On the other hand, if the question called for a general answer and the answer you gave only applies to some specific examples, you probably will get very little partial credit for your answer. You must not give examples to answer general questions.

    If I asked a question straight from the lecture slides, the best/correct answer is the one on the lecture slides. If you disagree with what's on the slides, you must complain when you are studying for the exam, i.e., before the exam. Once the exam starts, it's too late to complain that you don't like the answer on the lecture slides. In an exam, if you give an answer that's different from the lecture slides, you may receive partial credits, at the discretion the TA. Finally, I reserve the right to ask about things that I think you should know and not on lecture slides.

     
    Grading
    The grading breakdown is as follows:
    Participation:   4%  (extra credit)
    Homeworks:   35%  
    Quizes:   0%  
    Midterm Exam:   30%  
    Final Exam:   35%  
    The above percentages will be used to calculate a numeric score.

    Two methods will be used to calculate your final letter grade:

    (1)    Use a modified curve (i.e., we won't necessarily assign an equal number of failing grades as passing grades) based on the numeric score calculated above
     
    (2)    Use the following fixed scale (to encourage cooperation and friendly association amongst students):
    Percentage Letter Grade
    91% or higher A
    82-91% A-
    73-82% B+
    64-73% B
    55-64% B-
    46-55% C+
    37-46% C
    28-37% C-
    below 28% F
    Your class letter grade will be the higher grade based on (1) or (2).

    Pleaes also note the following:

    • 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!)

    • According to the above guidelines, it should be clear that it is possible to get a grade of C or below for individuals who perform very poorly (i.e., you should not assume a B- or even C+ if you perform very poorly, according to the guidelines above.) However, we hope that everyone will perform well.

    • We will not assign incompletes unless it is for a documented illness or family emergency (in accordance with USC policy).
     
    Late Policy
    All homeworks must be turned in on time. Late submissions will receive severe penalties. Due to clock skews, electronic submissions of homework assignments will be accepted within 15 minutes after the specified deadlines without penalties. If you submit within the next 24 hours, you will receive 90% of your grade. Although right after midnight, you will lose 1% every 5 minutes. When the penalty reaches the day limit, it flattens out. For example, if your submission has a timestamp that is 32 minutes after the grace period, 7% will be deducted from your assignment after grading; if your submission has a timestamp that is 1 day, 7 hours, and 30 minutes after the grace period, you will receive a score of zero (and your assignment will not be graded). The figure below summarize the deductions.

    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.

     
    Note From A Doctor
    Recently, there has been a change in the policy at the Student Health Center regarding giving a "note from the doctor" to you to bring to a faculty member so that you can be execused from deadlines. Basically, they will not give you such a note any more. What they would give you is an Authorization for Disclosure of Medical Information form. With this form, you give them permissions to discuss your illness with me.

    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.

     
    Regrading Policy
    All requests to change grading of homework or exams must be submitted in writing within one week of the time the initial grade was given. Requests must be specific and explain why you feel your answer deserves additional credit. A request to re-grade an assignment can result in the entire assignment being re-evaluated and as a result the score of any part of the assignment be increased or lowered as appropriate.
     
    Office Hours
    My office hours are held two hours each week. Please feel free to come to chat with me to clarify lecture material and get hints about programming assignments. You do not need an appointment to see me during office hours.

    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.

     
    Extra Credits
    No extra credit assignments will be given for this class. So, there is not need to ask. Try your best from the beginning!
     
    Implicit Student Agreement
    All work including homeworks, programming assignments and exams must be that of the individual student. It is often productive to study with other students. However, if any portions of homeworks or programming assignments are found to be shared between two (or more) students, zero credit will be given to all students concerned and all students will be disciplined. This policy is in the interest of those students who do their own work, which hopefully applies to all of you in this class.

    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.

     
    Student Responsibilities
    During the semester you are responsible for completing the assigned readings, homeworks, programs, and exams.

    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.

     
    Fairness
    The instructor must treat all students equally and cannot give special treatment to any particular student. Therefore, please do not ask special favors from the instructor because of your circumstances. This may seem unfair to you because you believe that your circumstances are special (understandably, everone does). But the rule the instructor must follow is that whatever he offers you, he must offer to the entire class.
     
    Auditing
    Auditing "unofficially" is not permitted for this class.
     
    E-mail
    E-mail is a serious communication tool. For this class, you should setup your e-mail server so that you do not drop any e-mail from me.

    Pretty much all class related announcements will be sent through the class Google Group. Therefore, you are required to be a member of this Google Group. As messages are posted to the class Google Group, you will receive e-mail notifications and you should read all these class-related e-mails. Please see instructions on how to get on this group (you should do this as soon as possible).

    You are strongly encouraged to send private e-mail messages to me if you have questions about programming assignments or lectures. If the answer is appropriate for the entire class, I would normally anonymize the reply and send the reply through the class Google Group and bcc a copy to you. So, please don't be shy to ask questions!

    One type of question I often get over e-mail or see in the class Google Group is:

    Here is my understanding of X. Am I right (or is this correct)? Correct me if I'm wrong...
    Although this type of question is perfectly fine during office hours, this is really not a good way to ask questions over e-mail. If no one corrects you, you must not conclude that you were correct! If you see "X" defined or described in lecture slides or in the textbook, you should try to understand why it was stated that way. A better question to ask over e-mail would be to ask about why it was stated that way.

    Another type of question I often get is the following:

    I am thinking about not following the spec or grading guidelines and would like to do this instead. Is it acceptable (or is this okay)?
    What you are really asking is whether you will receive full credit or not. Please just stick to the spec and the grading guidelines.
     
    Academic Integrity Policy
    Please make sure you read the Academic Integrity Policy of this course.
     
    Diversity Statement
    The diversity of the participants in this course is a valuable source of ideas, problem solving strategies, and engineering creativity. I encourage and support the efforts of all of our students to contribute freely and enthusiastically. We are members of an academic community where it is our shared responsibility to cultivate a climate where all students and individuals are valued and where both they and their ideas are treated with respect, regardless of their differences, visible or invisible.
     
    Academic Calendar
    A link to the USC Spring 2016 academic calendar is provided here for your convenience.
     
    Additional Resources
    (The resources below are provided for your information. Please note that the instructor has not read most of them. Please use these resources at your own risk!)

    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
    UNIX:
     

    [Last updated Sat Sep 19 2020]    [Please see copyright regarding copying.]