Cryptography

Corresponding entry in Aachen Campus, Bonn University (Lecture, Tutorial).

First meeting: Monday, 26 October 2009, 13⁰⁰, b-it bitmax.

Lecture

Prof. Joachim von zur Gathen

Tutorial

Konstantin Ziegler

Time & Place

Monday, 13⁰⁰-14³⁰, b-it bitmax.
Thursday, 13⁰⁰-14³⁰, b-it bitmax.
Tutorial 1: Monday, 14⁴⁵-16¹⁵, b-it bitmax.
Tutorial 2: Tuesday, 11³⁰-13⁰⁰, b-it Rheinsaal.

No lecture on Thursday, 7 January 2010.

Allocation

4+2 SWS, 8 credits. Optionally, 3+2 SWS, 6 credits.

Successful completion of the course yields 8 credit points. For students who only want 6 credit points, a breakpoint at about 3/4 of the teaching time will be defined, and only the course material up to that point will be relevant for their exams and grades. Students who wish to take the 6 credit version are required to indicate this until February 22nd by email to the tutor.

Media Informatics: Computer and Communication Technology.
Recommendation for University of Bonn - Computer Science: A or A1, respectively.

Prerequisites

None.

Cryptography deals with methods for secure data transfer. In earlier times this was the domain of military and intelligence agencies, but today modern cryptography has grown into a key technology, enabling e-commerce and secure internet communications. Its many applications range from credit and debit cards, mobile phones, tv decoders, and electronic money to unforgeable electronic signatures under orders and contracts in the internet. In the course, we first discuss two of the current standard tools, namely AES and RSA. Further topics are key exchange, including group cryptography and discrete logarithm, digital signatures and identification, and cryptographic hash functions.

Final Exam

The final exam took place

on Monday, 22 Febuary 2010, 13.30-16.30
at the bitmax, b-it.

You were invited to join us after the exam for an "Apfelschorle" at the Bönnsch.

Results are available at b-it 1.22.

Students who took, but failed the final exam may register until March 22nd 2010 for the make-up exam

on Monday, 29 March 2010, 13.30-16.30
at the Marschallsaal, b-it.

Certificates will be available for pickup at b-it 1.26.

The lecture's mailing list

Students are encouraged to ask and answer any questions related to the course on the mailinglist:

You can subscribe and unsubscribe to the mailing list using the information given on the list's Info page.

Establishing secure communication

Students are advised to exchange PGP keys with the tutor.

Install Mozilla Thunderbird
Install GnuPG
Install the Thunderbird-Add-On Enigmail
Call OpenPGP from the menu with the same name in Thunderbird.
Follow the assistant to generate your own PGP key.
Upload your PGP key to a key server using the appropriate option in the key management.
Send a signed email with subject "cryptography 2009/10" and non-empty body to the tutor.
Bring a fingerprint of your PGP key to the next lecture and give it to the tutor.
Ask if you have questions.

Submission guidelines

Solving the exercises is crucial for a good understanding of the course's content.

Note that to be admitted to the exam you need to earn at least 20% of the credits.
Students are encouraged to discuss the given exercises among each other.
Still, every student has to write up his/her solutions on his/her own.
Your solution has to be self-explanatory. Stating the final result is never enough.

You may submit your solutions either as a hardcopy or as attachment to an email. In any case put your name in the upper right corner of the first sheet.

If your submission is handwritten,

your handwritting must be legible, and
the sheets must be stapled.

If you submit by email, follow these steps:

The subject of the email should be "assignment ## by NN" where ## is the number of the assignment and NN is your name.
Your solution must consists of
- either: a single attached, printable file, best a PDF, (you may want to look for a "pdf printer" if your OS does not natively support pdf export)
- or: as text only in the mail body.
A printout of this single thing must contain your name. Your solution can only be graded if the name is on the printout readably.

(A zipped file is not printable and counts as many files!)

Please make sure that a printout is readable!
Sign the entire mail including attachments.
Do not encrypt.
Try to keep the size of your mail fairly below 5MB.

Assignments

Assignment 1: Arithmetic in F_2⁸ (due November 6th) pdf
Assignment 2: MixColumns, CRT and units in Z_N (due November 13th) pdf
Assignment 3: CRT for RSA, Orders, and Repeated Squaring (due November 19th) pdf
Assignment 4: RSA, expected value, Dixon's random squares and smooth numbers (due November 26th) pdf
Assignment 5: Pollard's rho-method and polynomial-time reductions (due December 3rd) pdf
Assignment 6: Diffie-Hellman key exchange and a derived public-key cryptosystem (due December 10th) pdf
Assignment 7: Index calculus, generators and cyclic subgroups (due December 17th) pdf
Assignment 8: Hashing and Discrete Logging (due January 14th) pdf
Assignment 9: The ElGamal Signature Scheme and the Schnorr Signature Scheme (due January 21th) pdf
Assignment 10: Security Reductions and r-safe Moduli (due January 28th) pdf
Assignment 11: Elliptic Curves (due February 4th) pdf

Literature

Mihir Bellare & Shafi Goldwasser (2001). Lecture Notes on Cryptography. PDF.
Johannes A. Buchmann (2004). Introduction to Cryptography. Birkhäuser Verlag, 2nd edition. ISBN 0-387-21156-X (hardcover), 0-387-20756-2. Erratum.
Alfred J. Menezes, Paul C. van Oorschot & Scott A. Vanstone (1997). Handbook of Applied Cryptography. CRC Press, Boca Raton FL. ISBN 0-8493-8523-7. Its homepage includes all chapteres available for free download.
Douglas R. Stinson (2005). Cryptography - Theory and Practice. Discrete Mathematics and its Applications. Chapman \& Hall / CRC Press, Boca Raton FL, 3rd edition. ISBN 1584885084, 600pp. Erratum. Parts of this text can be found online with GoogleBooks.
Nigel Smart (2002), Cryptography: An Introduction. McGraw-Hill. ISBN 0-077-09987-7. This first edition is out of print, but a second edition is available online.