The art of cryptography: cryptanalytic world records

This course is listed in Aachen Campus as The art of cryptography: Cryptanalytic world records and in Bonn Basis as The art of cryptography: Cryptanalytic world records.

Responsible

Prof. Dr. Joachim von zur Gathen

Lecture

Daniel Loebenberger and Konstantin Ziegler

Time & Place

Monday, 13⁰⁰-14³⁰, b-it bitmax.

Thursday, 13⁰⁰-14³⁰, b-it bitmax.

Tutorial: Monday, 14⁴⁵-16¹⁵, b-it bitmax.

First meeting: Monday, 07 April 2014.

Exam

The exam dates have been fixed.

Exam: 24 July 2014, 13:00h - 16:00h, b-it, Rheinsaal

2nd Exam: 15 September 2014, 14:00h - 17:00h, b-it, b-itmax

Mailinglist

This lecture's mailing list can be reached under

Additional information will be posted there and students are encouraged to ask and answer any questions related to the course. Information on how to subscribe and unsubscribe can be found on the list's Info page.

Cryptanalysis is the art of breaking cryptographic systems. To attack for example the cryptosystem RSA, it is sufficient (though not necessary) to factor the underlying RSA modulus. Other algorithms, like ElGamal encryption or the DSA, can be broken by computing discrete logarithms in certain domains.

Many attacks on symmetric cryptosystems are based on differential or linear cryptanalysis. These techniques are applicable to block-ciphers as well as hash functions. We study them on a small-scale version of AES and learn their powers and limits.

The lecture's aim is to give a thorough understanding of the techniques that were used to actually set real-world cryptanalytic world records by providing the necessary background.

About handins, credits and boni

To be admitted to the exam you need to earn at least 50% of the credits. Experience shows that you should try all exercises and tutorials. 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.

Always hand in to .
Your solution must consists of
- either: a single attached, printable file, best a PDF,
- 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 readable.

Please make sure that also the printout is readable!
Only in the case code has to be written, an additional tar/zip file is allowed for handin that contains your code ONLY.
Try to keep the size of your mail fairly below 5MB.
Obvious: credits are awarded for solutions that arrive within the respective deadline. Any post-deadline submission may be ignored.

Slides

Brute force cryptanalysis (PDF, last updated 10 April 2014, 10:58).
Discrete logarithms (PDF, last updated 15 April 2014, 10:35).
World record on discrete logarithms (PDF, last updated 24 April 2014, 15:57).
Factoring integers (PDF, last updated 08 May 2014, 19:31).
World record on factoring integers (PDF, last updated 22 May 2014, 09:15).
The elliptic curve method (PDF, last updated 05 June 2014, 11:31).

Exercises

Exercise 0 (PDF, last updated 07 April 2014, 16:47).
Exercise 1 (PDF, last updated 07 April 2014, 16:49).
Exercise 2 (PDF, last updated 15 April 2014, 10:38).
Exercise 3 (PDF, last updated 22 April 2014, 08:17).
Exercise 4 (PDF, last updated 29 April 2014, 10:01).
Exercise 5 (PDF, last updated 06 May 2014, 09:39).
Exercise 6 (PDF, last updated 13 May 2014, 10:04).
Exercise 7 (PDF, last updated 27 May 2014, 12:42).
Exercise 8 (PDF, last updated 27 May 2014, 12:43).
Exercise 9 (PDF, last updated 03 June 2014, 19:38).
Exercise 10 (PDF, last updated 20 June 2014, 00:00).
Exercise 11 (PDF, last updated 26 June 2014, 14:41).
Exercise 12 (PDF, last updated 30 June 2014, 21:11).
Exercise 13 (PDF, last updated 09 July 2014, 00:02).

Additional files

NIST special publication 800-63 (pdf)
Diceware word list (asc)
Barbulescu et al. (2013), A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic (pdf)

Allocation

4+2 SWS.

Master in Media Informatics: Computer and Communication Technology.
8 ECTS credits.
Optionally, 3+2 SWS, 6 ECTS credits. On request 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.
Master in Computer Science at University of Bonn: MA-INF 1312.
9 CP.
Students have to register this course with POS/BASIS.
Recommendation for diploma students of University of Bonn - Computer Science: A or A1, respectively.