Cryptography
Corresponding entry in Aachen Campus, Bonn University (Lecture, Tutorial).
First meeting: Monday, 26 October 2009, 13^{00}, bit bitmax.
Lecture
Tutorial
Time & Place
 Monday, 13^{00}14^{30}, bit bitmax.
 Thursday, 13^{00}14^{30}, bit bitmax.
 Tutorial 1: Monday, 14^{45}16^{15}, bit bitmax.
 Tutorial 2: Tuesday, 11^{30}13^{00}, bit 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.
Contents
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 ecommerce 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.3016.30
 at the bitmax, bit.
You were invited to join us after the exam for an "Apfelschorle" at the Bönnsch.
Results are available at bit 1.22.
Students who took, but failed the final exam may register until March 22nd 2010 for the makeup exam
 on Monday, 29 March 2010, 13.3016.30
 at the Marschallsaal, bit.
Certificates will be available for pickup at bit 1.26.
The lecture's mailing list
Students are encouraged to ask and answer any questions related to the course on the mailinglist:
Establishing secure communication
Students are advised to exchange PGP keys with the tutor.
 Install Mozilla Thunderbird
 Install GnuPG
 Install the ThunderbirdAddOn 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 nonempty 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 selfexplanatory. 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_{28} (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 rhomethod and polynomialtime reductions (due December 3rd) pdf
 Assignment 6: DiffieHellman key exchange and a derived publickey 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 rsafe 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 038721156X (hardcover), 0387207562. Erratum.
 Alfred J. Menezes, Paul C. van Oorschot & Scott A. Vanstone (1997). Handbook of Applied Cryptography. CRC Press, Boca Raton FL. ISBN 0849385237. 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. McGrawHill. ISBN 0077099877. This first edition is out of print, but a second edition is available online.
Links
 A visualisation of AES flows (needs Java). Each "wire" carries one byte encoded as a color.
 A Stick Figure Guide to the Advanced Encryption Standard (AES) by Jeff Moser.
 Alexander Sotirov, Marc Stevens, Jacob Appelbaum, Arjen Lenstra, David Molnar, Dag Arne Osvik, Benne de Weger, MD5 considered harmful today