CS 6750   Fall 2009
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  

Fri, 11 Dec 2009: The slides from the second day of presentations are up. Thanks to all the presenters, and thanks to everyone for a nice semester. Remember that the final paper is due this coming Monday -- the 14th.

Thu, 10 Dec 2009: The slides for the first day of presentation are up.

Wed, 09 Dec 2009: Slight revision to the presentation schedule.

Mon, 07 Dec 2009: The preliminary presentation schedule can be found here.

Thu, 03 Dec 2009: Slides for the lecture on secure multiparty computations are up.

Thu, 19 Nov 2009: Slides for the lecture on zero knowledge protocols are up, including a couple of corrections following class discussions. My plan is to send you all papers for your projects on Friday night. Stay tuned.

Thu, 12 Nov 2009: Slides for the lecture on key establishment protocols are up. Homework 7 is out, due next Thursday. Also remember that I'd like to see your proposal about what you would like to investigate for your final project by November 15.

Tue, 10 Nov 2009: You can find a small writeup about the final project here. I would like to see your proposal about what you would like to investigate for your final project by November 15. An email will do fine.

Thu, 05 Nov 2009: Slides for the lecture on security protocols are up, including those I skipped over, on protocols with public-key cryptography and Kerberos. Homework 6 is out, due next Thursday.

Thu, 05 Nov 2009: Some of you had a question about question 2 of homework 4, about how to get the value of a. If you follow the technique in the book, you end up with an equation to solve that doesn't seem to be easily solvable. In particular, you want to solve ax = b (mod n) for x, provided you know gcd(a,n) divides b -- in which case you know there's a solution.

The trick is to reduce this equation to an equation of the form a'x = b' (mod n') with gcd(a',n') = 1, because for that you can find a solution easily.

One approach is to take d=gcd(a,n), and take a'=a/d, b'=b/d, and n'=n/d. You then solve a'x = b' (mod n'). Note that gcd(a',n')=1.

You get a solution, call it s, but that's a solution mod n'. The trick then is to convert this s to a solution of the original equation, mod n. I'll leave you to figure out how to do that. Hint: think about what values (mod n) give you s (mod n'). Another hint: there are d=gcd(a,n) of them.

Thu, 29 Oct 2009: Slides for the lecture on secret sharing are up. Homework 5 is out, due next Thursday. Reading assignment for next class: chapter 13, sections 1 and 2. Stay tuned tomorrow night for a list of ideas for the end of term project.

Wed, 21 Oct 2009: Blackboard is giving me grief, and somehow does not always consistently show all grades that I have entered. I believe (big caveat) that I have corrected the problem, and that you should see all the grades that I have for you. If you believe this is mistaken and that I am missing something, let me know.

Tue, 20 Oct 2009: Lei points out that in the list of chapters/sections I gave earlier, I included the subsection about the ECDSA signature scheme, the version of DSA based on elliptic curves. You do not have to know/read that one, since after all I had you skip the section on elliptic curves cryptography. (I do not know exactly what subsection it is, but I believe it's one of those in 7.3 or 7.4.)

Sat, 17 Oct 2009: Grades for all homeworks (except for one or two that I still need to get to because of printing problems) can be found on Blackboard. Grades are on a per-question basis (each out of 10). Graded homeworks have been put outside my office door, but not those that were submitted online and containing source code. If you have any question as to your grade on a question and you do not have a hardcopy of the homework, feel free to shoot me an email. I will try to print out an explanatory sheet for every homework that was submitted online that I will add to the pile of graded homeworks come Monday.

Fri, 16 Oct 2009: The midterm next week will be in class, and will be open notes and open books. No computers or smartphones. But you can bring a calculator if you really want to. The midterm will cover all the lectures we have seen until yesterday, including signature schemes. In the textbook, you will be responsible for the following chapters/sections:
Chapter 1 [sections 1.1, 1.2 (only 1.2.1-1.2.3)]
Chapter 2 [sections 2.1-2.7]
Chapter 3 [sections 3.1-3.2, 3.5-3.7]
Chapter 4 [sections 4.1, 4.2 (only 4.2.1), 4.3 (only 4.3.1), 4.4]
Chapter 5 [sections 5.1-5.3]
Chapter 6 [section 6.1]
Chapter 7 [sections 7.1-7.4]

Fri, 16 Oct 2009: Slides for the lecture on signature schemes are up. Homework 4 is out, due next Thursday. Reading assignment for next class: reach chapter 7 in Stinson. Note that next Thursday is the midterm; I will post some more information about the midterm later tonight, including chapters/sections of the textbook to study.

Fri, 09 Oct 2009: Slides for the lecture on hash functions are up. Extension for homework 3 has been granted until Sunday night. Reading assignment for next class: read chapter 4 in Stinson.

Thu, 01 Oct 2009: Slides for the lecture on public-key cryptosystems are up. Homework 3 is out, due next Thursday. Reading assignment for next class: read chapters 5 and 6.

Thu, 01 Oct 2009: If you need an extension for homework 2, I am happy to give you an extension until the end of the weekend, that is, until Sunday night. Send me an email to let me know.

Thu, 01 Oct 2009: For homework 2 submissions, please send me an email containing your source code packaged in either a zip file or a tar/gz file, and sample executions.

Mon, 28 Sep 2009: I completely forgot to update this website with my office hours, sorry about that. They're Thursday 16h00-18h00 (before class, then), and my office is 328 WVH.

Thu, 24 Sep 2009: Slides for the lecture on block ciphers are up. Homework 2 is out, due next Thursday. Finally, reading assignment for next class: read chapter 3. I will try to put up some sample plaintexts and ciphertexts to check your DES code for homework 2.

Mon, 21 Sep 2009: Slides for the second lecture are up. They have a colored background unfortunately, so I recommend not printing them unless you want to kill your printer. It's not that easy to make a non-colored copy from those, so I won't even bother. Besides, everything is contained in Chapter 2 of Stinson anyways, in some form or another. I also posted the first homework, due next lecture. I also added links to two text files with the content of the ciphertexts for question 2, in case you want to attempt decryption using a program you wrote.

Thu, 10 Sep 2009: Slides for the first lecture are up. The link is in the schedule below. I've also put a pointer to the short story I mentioned in class, Poe's "The Gold Bug". Reading assignment for next week: chapter 1 of Stinson.

Mon, 07 Sep 2009: Setting up the RSS feed for the course. You should see an RSS link up in your browser.

Course Information

Time and Location: Thursdays 18h00-21h00 in 011 Kariotis Hall (#35)

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

Office hours: Thursday 16h00-18h00

Teaching Assistant: None

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

Prerequisites: CS 5800 or CS 7800 (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%

This scheme is subject to change until the first lecture.

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.

• Homework 1: Due Sep 24 (Ciphertexts for question 2, part (a) and part (b))
• Homework 2: Due Oct 1
• Homework 3: Due Oct 7
• Homework 4: Due Oct 22
• Homework 5: Due Nov 5
• Homework 6: Due Nov 12
• Homework 7: Due Nov 19

Writeup about the final project