CMSC456 Cryptology, Fall 2003
Instructor: Aravind Srinivasan
Class Venue and Time: CSI 1121, TuTh 2 - 3:15 PM
Outline |
Final Exam |
Announcements |
General Information |
Staff |
Course Material
Course Outline
This course serves as the introduction to cryptography for advanced undergraduates and graduate
students. The focus is on definitions, theoretical foundations, and rigorous proofs of security.
This course is cross-listed with the mathematics department, so it will have a significant
mathematical component. This course complements Computer and Network Security (CMSC 414) which
focuses more on "high-level" issues; in this class, we will actually look "under the hood" and attempt
to understand various cryptographic protocols and algorithms. This course and CMSC 414 may be taken in
either order.
We will begin with a brief discussion of "classical" cryptography and its limitations. Following this,
we will define a notion of "perfect" security and see what can and cannot be achieved in this sense.
This will lead us naturally to the modern, complexity-theoretic approach to cryptography in which
security is based on the assumed computational hardness of various problems. In this vein, we
will study pseudo-randomness, private-key (i.e., shared key) encryption and message authentication,
block ciphers, authentication, public-key encryption, and digital signatures. Advanced topics will be
covered as time permits.
No advanced mathematics background is assumed, but students are expected to possess "mathematical
maturity" since many of the concepts will be abstract and rigorous proofs will be given occasionally
throughout the semester. Discrete mathematics (probability theory, modular arithmetic) and complexity
theory are also helpful, but the necessary prerequisites will be discussed in class.
The textbook for the course is "Cryptography: Theory and Practice, 2nd edition" by Stinson. The
second edition is very different from the first edition; please do not use the older version of the
book. Additional readings will be listed on the course homepage.
Important Information Regarding the Final Exam
The final exam for CMSC 456 is scheduled by the University to be on Thursday December 18th from
10:30-12:30. However, due to a work-related conflict of the professor, it is requested that the final
exam be on Thursday December 11th, either from 2-4 PM (the regularly scheduled class is from 2-3:15pm)
or else from 6-8 PM. It is requested that students confirm, via an email to the professor, whether or
not they have any objections to this; additionally, if there are questions/concerns, they may be sent to
the professor and/or also be addressed to the Undergraduate Program Coordinator (James Maybury,
jmaybury@cs.umd.edu).
Note added on Oct 2, 2003: The final exam times are
confirmed now, to be on Dec 11th and Dec 12th; please see announcement
a few lines below.
Note added on Oct 19, 2003: The final exam times and
venues are confirmed now, to be on Dec 11th and Dec 12th; please see
announcement dated Oct 19, a few lines below.
Announcements
- [Posted 9/23/2003]:
The mid-term exam
will be held in class 2-3:15 PM on Tuesday, October 28, 2003.
It will include all material
covered up to and including the class of October 21.
- [Posted 10/01/2003]:
The mid-term will be closed-book, closed-notes. However, you
can bring one 8.5 x 11 sheet with anything written on it. As
announced before, the mid-term will be in class on Tue, 10/28.
The material included is as follows: (a) all material covered
up to and including the class of Oct. 21; and (b) anything that
you were asked to read as part of the homework assignments.
- [Posted 10/01/2003]:
The time-slots for the final are confirmed now. They will be
offered on Thu, Dec. 11 at: (i) 2-4 PM, (ii) 6-8 PM, and (iii) 7-9 PM.
You can choose any of these slots. (Also, one of you will take it on
Fri, Dec 12, 9-11 AM.) The exams will be sufficiently different, but
you will also be asked to not discuss them with anyone for a day after
you take the exam. I will announce the venues soon after they are
confirmed.
- [Posted 10/01/2003]:
A link to errors in the book has been added below. I thank
Walid Gomaa, Richard Gopaul, and Christine Smit for pointing
out the errors in the description of the Euclidean Algorithm.
- [Posted 10/19/2003]:
The venues and time-slots for the final are confirmed now. The exam
will be offered on Thu, Dec. 11 at: (i) 2-4 PM in Room 0119 of the Armory,
(ii) 6-8 PM in CSI 2117, and (iii) 7-9 PM in CSI 2117.
You can choose any of these slots. (Also, one of you will take it on
Fri, Dec 12, 9-11 AM, in my office, A.V.Williams 3227.)
- [Posted 11/06/2003]:
Aravind's office hours today are canceled. Please email him some
possible time-slots for you in the next few days, if you had planned
on coming to the office hours today.
- [Posted 11/12/2003]:
Problem 1 in HW 5 has now been corrected: the number of repetitions is
k^3, instead of (ln k)^3. My apologies for this error --Aravind.
- [Posted 11/17/2003]:
Due to the requests of some of you, the deadline for
submission of HW6 has been postponed
to the beginning of class on Tuesday, Nov 25.
- [Posted 11/18/2003]:
Walid Gomaa has pointed out that the repeated-squaring pseudocode
presented in class is incorrect, and has provided this
corrected
version. Thanks to Walid for this.
- [Posted 12/01/2003]:
As pointed out by Sun Kim, there is a typo in HW 7. In problem 2,
what we want is an x such that f(x) = y; this has been fixed now.
Thanks to Sun for this.
- [Posted 12/08/2003]:
The final exam will be closed-book, closed-notes. However, you
can bring one 8.5 x 11 sheet with anything written on it.
The material included is as follows: (a) all material covered
in class; and (b) anything that
you were asked to read as part of the homework assignments.
- [Posted 12/08/2003]:
Jonathan Katz's midterm and final from Fall 2002 are posted
below.
- [Posted 12/09/2003]:
The review session by Charles Clancy will be in CSI 1121
at 7PM on Wednesday, Dec. 10.
General Information
- Grading will be based on 6-7 homeworks assigned throughout the course (40%), a midterm
(25%), and a final exam (35%).
- Graduate students taking the course (both Masters and PhD students) will be required to do
additional problems for homework. Their grades will also be curved independently of those of
the undergraduate students.
- Homework:
- You may collaborate on the homeworks with at most one other student in the class. Each
student must independently write up their own solutions, and include the name of their
collaborator, if any.
- You may consult outside references when doing the homework, as long as these sources
are properly referenced, you write up the solution yourself, and you understand the
answer.
- Course Philosophy:
The more interactive the class is, the better it will be for all of us: we can get better
insights into the material, and enjoy the process better. Students are strongly encouraged to
participate actively in class. All of us hesitate occasionally in asking questions; the
instructor will do his very best to encourage questions. Doing the homework to the best of your
ability, comparing your solutions to the handed-out ones, and seeing if you can do better, is
the best way of understanding the course material.
- Check the course homepage frequently since all handouts will be distributed via the web and an
updated syllabus will be maintained on this page.
Staff
Professor: |
Aravind Srinivasan (srin AT cs)
Office: 3227 A.V. Williams Building, Phone 405-2695.
Office hours: Tuesday, Thursday 1-2 PM. |
Teaching Asst: |
T. Charles Clancy (clancy AT cs)
Office hours: Monday, Wednesday 11AM - 12 noon, held in room 1112, A.V. Williams Building. |
Course Material
- Suggested Readings (mostly the same
as in Jonathan Katz's 456 class from Fall 2002)
- Lecture Schedule
- Book Errata
- Fall 2002 Mid-Term
- Fall 2002 Mid-Term Solutions
- Fall 2002 Final
- Handouts
Posted | Document | Download |
Description |
8 September |
Algebra & Number Theory Notes |
PS |
PDF |
Notes from the Fall 2002 course. |
8 September |
Discrete Probability Notes |
PS |
PDF |
Notes from the Fall 2002 course. |
- Assignments
Posted | Document | Assignment |
Solution | Due | Ugrad Avg/Max | Grad Avg/Max |
8 September |
Homework 1 |
PS |
PDF |
PS |
PDF |
23 September |
16.5 / 23 | 29.5 / 33 |
23 September |
Homework 2 |
PS |
PDF |
PS |
PDF |
2 October |
14.8 / 18 | 23.5 / 30 |
5 October |
Homework 3 |
PS |
PDF |
PS |
PDF |
14 October |
13.6 / 20 | 25.3 / 28 |
14 October |
Homework 4 |
PS |
PDF |
PS |
PDF |
23 October |
13.0 / 18 | 22.3 / 28 |
28 October |
Exam 1 |
PS |
PDF |
PS |
PDF |
28 October |
18.9 / 25 | 31.7 / 35 |
4 November |
Homework 5 |
PS |
PDF |
PS |
PDF |
13 November |
15.5 / 20 | 19.3 / 25 |
13 November |
Homework 6 |
PS |
PDF |
PS |
PDF |
25 November |
9.1 / 10 | 15 / 15 |
26 November |
Homework 7 |
PS |
PDF |
PS |
PDF |
9 December |
12.5 / 15 | 18.7 / 23 |
Average scores do not reflect extra credit,
which will only be considered at the end of the semester.