CSG 252   Fall 2008
Cryptography and Communication Security 

Overview

Official summary: Studies the design and use of cryptographic systems for communications and other applications such as e-commerce. Discusses the history of cryptographic systems, the mathematical theory behind the design, their vulnerability and the different cryptanalytic attacks. Topics include: stream ciphers such as shift register sequences; block ciphers such as DES and AES; public-key systems such as RSA, Discrete Logarithms; signature schemes; hash functions such as MD5 and SHA1; protocol schemes such as Identification schemes, Zero-Knowledge proofs, Authentication schemes and Secret Sharing schemes. Key management problems including Needham-Schroeder protocols and certificates will be discussed.

Announcements  

Thu, 18 Dec 2008: Final grades are up on Blackboard. Class average is a B+. Well done everybody.

Mon, 15 Dec 2008: The final exam for the class is tomorrow night, Tuesday Dec 16, 18h30-20h30, in 220 Shillman. It is an open notes and open books exam - no computers or network devices.

Mon, 15 Dec 2008: I should be in my office later this afternoon, from 15h00 on. I may be there before, but it's somewhat unlikely. Feel free to send me email if you have questions.

Fri, 12 Dec 2008: Jeff, our TA, has told me that he will hold special office hours Monday 11h00 to 13h00. As for me, I will be around all day on Monday, although I'll be in and out of the office. If you want to see me, either drop by but be ready to wait if I happen to step out, or send me email and we can agree on a meeting time.

Thus, 11 Dec 2008: Lecture notes on secure multiparty computations are up. They are a bit sketchy though. Note that you are not responsible for this material for the final. You're only going to be tested for material up to and including zero knowledge protocols.

Thu, 11 Dec 2008: Here are the chapters in the textbook corresponding to the various lectures that you should look at. (I did not cover all sections of all the chapters, obviously.) Classical Cryptography: chapter 1, Shannon's Theory: chapter 2, Block Ciphers: chapter 3, Public Key Ciphers: chapters 5 and 6, Hash Functions: chapter 4, Signature Schemes: chapter 7, Secret Sharing: chapter 13, Security Protocols: no corresponding chapter (chapter 10 talks about them somewhat, but in a different way), Key Agreement Schemes: chapter 11 and some part of chapter 12 (on certificates), Zero Knowledge Protocols: no corresponding chapter, Multiparty Computation: no corresponding chapter.

Thu, 11 Dec 2008: NU course evaluations are being done online this semester. You should already have received info on this, but if not, here is the info I have.

Wed, 09 Dec 2008: I will have to cancel my office hours today. To compensate, I will hold two hours of office hours tomorrow (wednesday) afternoon, 16h00-18h00.

Wed, 03 Dec 2008: Homework 8 is out. Due next Tuesday.

Wed, 03 Dec 2008: Lecture notes (revised) for last night has been posted. Homework 8 should be coming up very soon...

Thu, 27 Nov 2008: Happy Thanksgiving, everyone. I'd like to have our final on the Tuesday following our last lecture, which would be December 16th, during the scheduled class time, 18h00-20h00, or possibly 19h00-21h00. Two hours will be enough, that's the time allotted to finals generally. It should not conflict with your schedule, especially if you can make it to lecture in general. An alternative is to schedule it one evening the week before, after the last lecture.

Wed, 26 Nov 2008: Lecture notes for last night have been posted, as well as some links to papers and surveys.

Wed, 19 Nov 2008: A variant of last night's lecture notes have been posted.

Tue, 18 Nov 2008: Homework 7 is out, due next Tuesday the 25th in class.

Sun, 16 Nov 2008: I have re-uploaded the grades to Blackboard. Please double check to make sure I got them right. Also, I have been getting reports about people grumbling about the grading. I am fully behind Jeff in his grading: I tell him how to grade and what to look for. Most of the grumbling is about proofs, and how they are graded. First, an example is not a proof. If I ask you to prove something, showing that it's true on an example should barely give you half the points, and that's on a day when I'm in a particularly good mood. "Prove that the sum of any two numbers is positive: well, I tried it on 2+3=5, and 4+6=10, so yes, it's true." Sigh. Second, if you have to prove that something is true for all natural numbers, then you want a proof by induction. I expect you've done a reasonable undergraduate program, and any reasonable undergraduate program will have taught you proofs by induction. If you have forgotten, review it. Here is a primer to refresh your memory. Of course, I will not ask you to prove something explicitly by induction - you are supposed to recognize it. If you don't, but you have a reasonable general argument (not an example, a general argument), you usually get most of your points, minus a few.

Thu, 13 Nov 2008: Just received this from the University: " Late today (Wednesday November 12 th ) we were informed by Blackboard Inc that the Northeastern University Blackboard environment they host has a corrupted database which must be repaired immediately. [...] Since correcting the problem will cause all changes made since approximately 3am on Monday November 10 th to be lost, we are suspending access to the system immediately (before 6pm, Nov 12 th). Blackboard projects that the repair may take up to 24 hours although we will return the system to service as soon as possible once it's repaired by Blackboard staff and tested by Information Services personnel." All that to say that the midterm grades may not be available until I re-enter them this weekend.

Tue, 11 Nov 2008: I got a question by email about Homework 6, question 2, and here was my answer. Might as well share it with everyone: "I want you to think of a scenario where if an access structure is non-monotone, it is very easy to make something bad happen. (E.g., start WWIII, or some such, in the context of the generals/nuclear arsenal scenario.) That should be the case independently of how the secret is actually shared - the problem should just come out of the non-monotonicity of the access structure."

Tue, 11 Nov 2008: I've uploaded all your grades (at least, all those I have) to the Blackboard course page. You can check out your midterm grades there. I will be out of town until the weekend, just so you know.

Mon, 10 Nov 2008: Just to remind you that there is no lecture tomorrow, for Veterans' Day. See you all next week.

Mon, 10 Nov 2008: The midterms are graded, but I will not have time to enter the grades online (I will post them through Blackboard) until late afternoon.

Tue, 04 Nov 2008: Secret sharing lecture is posted below, and homework 6 is out - see link below - due November 12th.

Mon, 03 Nov 2008: I am trying out an RSS feed for announcements. If all goes well, you should see an RSS link up in your browser. If not, then click on the RSS square above.

Nov 3: For homework 5, question 1: don't find a and k by cycling through all possibilities. (That's solving an instance of the discrete log, which you are not allowed to do.) Cf p. 291-292. You may need something like the following because you cannot use the equation at the top of p.291 directly, because the appropriate gcd's are not 1. So you have to think a little bit.

Oct 27: Important: The midterm tomorrow will be held at class time, 18h00, in Dodge 150. Remember, it is open notes, so bring books and your class notes if you so desire. No computers, or anything with an internet connection, please.

Oct 21: Homework 5 is out. Due dute of November 4th, in two weeks. Next week, midterm, in class. I will post the room in which we will be holding the midterm by this weekend. Check this website again on Monday.

Oct 21: Homework 4 submission: I want a hardcopy in lecture tonight (or tomorrow at my office if you can't bring one tonight.) I will not accept email-only submissions.

Oct 15: Lecture notes for hashing are up, as is homework 4.

Oct 9: Lecture notes for public key cryptography are up, as is homework 3. (I gave the questions in class, but did not have time to write it up until now. I do not have the book with me right now, so I cannot type up question 1, so if you do not have the book (shame, shame), you'll have to wait until tomorrow...)

Oct 6: I had a few question about whether you could submit Homework 2 online somehow, given that it is source code. Sure. Email me your code tonight (say, by midnight), with subject "CSG 252 Homework 2". Just the source code, please, no executables. Also, please provide some sample input and output traces, at least showing that when you decrypt what you encrypted, you get the plaintext you started with.

Oct 2: Question asked about homework 2: what should we use as S-boxes for DES? Answer: the S-boxes that the DES standard requires. Read this first for an overview, and then this for the actual details of the permutations used and the S-boxes, as well as the key schedule.

Oct 1: Lecture 3 on block ciphers is up.

Oct 1: Our TA Jeff tells me that I got his office number wrong below. It's really 460 WVH. It's been corrected.

Sep 30: Homework 2 is out, due October 7th. I will most likely ask you to submit code online as well, and I will post instructions here accordingly in the next few days. I will post tonight's lecture notes as well, as soon as I come up with a printable version. Some readings for block ciphers are included in the schedule below, for your edification.

Sep 24: Added lecture notes for second lecture, the slides that I used, plus a "printable" version with white background. (Printable slides from the first lecture added as well.)

Sep 23: Homework 1 is out. Due September 30th. Covers the first two lectures. See below for the text of the ciphertexts in question 2.

Sep 17: Slides from the first lecture are up. See the schedule below. I've also added a link to Poe's short story The Gold Bug which contains a celebrated instance of a statistical cryptanalysis. Read it. (Plus it's a good short story, a classic of American literature.)

Course Information

Time and Location: Tuesdays 18h00-21h00 in 130 Forsythn (#55)

Instructor: Riccardo Pucella, 328 West Village H (#23H)

Office hours: Tuesdays 15h00-17h00

Teaching Assistant: Jeff Satterley, Office hours: Wednesdays 15h00-17h00 (460 WVH)

Course Web Site: http://www.ccs.neu.edu/home/riccardo/csg252

Prerequisites: CSG 113 or CSG 713 (can be taken concurrently)

Grading: Grading will be based on homeworks (about one a week), a midterm, and either a final exam or a final project:

• Homeworks: 50%
• Midterm: 25%
• Final exam or project: 25%

Textbooks: The textbook for the course is:

• Cryptography Theory and Practice (3rd ed), by Stinson. (There is an updated errata.)

You may also find the following book useful, but it is not required:

• Applied Cryptography (2nd ed), by Schneier.

Schedule Outline and Lecture Notes

This schedule is subject to change without warning. Readings will be assigned to supplement lectures, and posted here.

Homeworks

Removed