2MMC10 Cryptology - Fall 2017

Contents Announcements Exams Literature Pictures, videos, and slides

Tanja Lange
Coding Theory and Cryptology
Eindhoven Institute for the Protection of Information
Department of Mathematics and Computer Science
Room MF 6.104B
Technische Universiteit Eindhoven
P.O. Box 513
5600 MB Eindhoven
Netherlands

Phone: +31 (0) 40 247 4764

The easiest ways to reach me wherever I am:
e-mail:tanja@hyperelliptic.org

Some of the lectures will be given by Chloe Martindale.

Contents

Announcements

Note that one of the course requirements is algebra. I will not repeat basic background on groups, rings and fields in class. If you don't have the necessary background, take the summer and work through the "Number Theory and Algebra" script.

Literature

It is not necessary to purchase a book to follow the course. Previous versions of this course used Henk van Tilborg's "Fundamentals of Cryptology", Kluwer academic Publishers, Boston, 2000. But the book is out of print. A preliminary author's copy by Henk can be downloaded in pdf form here and as a mathematica worksheet here.
Other books you might find useful

Examination

The exam will be an open-book exam, meaning that you can use any book or notes that you have on paper. You may use a programmable calculator and I expect you to be able to use it for modular exponentiation and inversion.
I will also bring a laptop with access to the course page incl. blackboard pictures and scripts, but you may not use it to surf the internet. There will be a termnal to run GP-Pari; sage is not available on the laptop.

For 2MMC10, the first exam will take place October 31, 2017, 13:30 - 16:30. The retake exam will take place January 23, 2018, 18:00 - 21:00. Rooms will be announced. For Mastermath the exam will take place on January 8, 2018, 14:00 - 17:00. We plan to merge the retake with the 2MMC10 retake, this means that you need to come to TU/e on Jan 23.

For 2MMC10 you can earn up to 1P for the final mark through the homework. Please hand in your solutions in groups of 2 or 3, we do not have the capacity for individual corrections. Please make sure to register for the exam in time. For TRU/e students from Nijmegen, this means that you need to register at TU/e as well and get a student number etc.

For students from Mastermath, please register on their site.
You can earn up to 1P for the final mark through the homework. The bonus point only counts if the grade for the exam is at least 5.0, so even if you score a full bonus point in the homework but only a 4.5 in the test you do not pass. Please hand in your solutions in groups of 2 or 3, we do not have the capacity for individual corrections. Please submit your solution on time by email to the address below.

For all students: Gustavo Banegas and Manos Doulgerakis are the teaching assistants for this course. You can reach them at crypto.course (at) tue.nl.
Do not send me your homework but submit it on paper before the Thursday lectures. If there is a programming component to the exercises email the solution to the TAs.
If an assignment is unclear and you have questions about the homeworks, contact me in class or by email.

Class notes

The course notes will be filled in after each lecture. You will find a summary of the content of the lecture, links to further reading or slides, and pictures of the blackboard. The homework sheets will be posted along with the notes.

05 Sep 2017
General introduction to cryptography; concepts public key, symmetric key cryptography, and hash functions. Pictures of blackboards are here.
Videos will come as soon as I have better internet.
If you want to try your skills at some cryptosystems visit http://www.mysterytwisterc3.org/.
As an example we attacked the "Perfect Code Public Key System" by Fellows and Koblitz. Attention, this was never proposed for cryptography but only as a teaching tool.
Here are the slides in pdf for the perfect code system.

07 Sep 2017
Recap on Fermat's little theorem, Euler phi function and its computation, Lagrange's theorem, Chinese Remainder Theorem (CRT).
RSA encryption (KeyGen, Encrypt, Decrypt), exponentiation via square and multiply, use of RSA in hybrid encryption (use RSA to encrypt a key for symmetric crypto, use the latter to encrypt the message. choolbook RSA is homomorphic, avoid this structure by using a padding scheme; we covered RSA OAEP.
RSA signatures (KeyGen, Sign, Verify). Note that RSA is exceptional in that signing and encrypting are so closely related.
Faster decryption/signing via CRT-RSA incl. estimates on improvement (look up Karatsuba multiplication).
Pictures of blackboards and videos are here.
For 2MMC0, homework is due next Thursday, 14 Sep, at 10:45. To submit, please bring your homework on paper to the lecture on Thursday and hand it before the lecture to the lecturer.
For MasterMath, homework is due Thursday, 28 Sep, at 10:45 by email.
Please submit in groups of size 2 or 3; we do not have the correction capacity for handling singletons. The exercise sheet is here. For the RSA exercise you can assume a caclulator with very large precision, i.e. you should use the square-and-multiply method.

12 Sep 2017
Factorization techniques for integers: trial division, Pollard's rho method including explanation why it works when it works and Floyd's cycle-finding algorithm; Pollard's p-1 method including why it works.
Start of explanation of how to factore RSA numbers; e.g. how to factor if p and q ar too close.
Pictures of blackboards and videos are here.

14 Sep 2017
Factorization using Dixon's method/method of random squares. The initial example didn't work as well as I expected and I couldn't connect with my laptop. Thanks for helping out with laptop and typing!
We used the computer algebra system Pari-gp for the examples and I wrote some of the commands on the board (also at the beginning of the second lecture). See the beginning of the second lecture (= 4th picture) for a working example of factoring 323.
Q-sieve, quadratic sieve, some comments about the number-field sieve and running times. You can find examples and code snippets for these methods and those from the previous lecture on http://facthacks.cr.yp.to. The slides I used are here.
Primality testing methods: Fermat test and Carmichael numbers; Miller-Rabin test. These tests are 100% correct when they output 'not prime'; otherwise they say 'maybe prime'. If you want to be sure that a number is prime, you need to use a primality proof. Read up on Pocklington's test.
Pictures of blackboards and videos are here.

For 2MMC0, homework is due next Thursday, 21 Sep, at 10:45. To submit, please bring your homework on paper to the lecture on Thursday and hand it before the lecture to the lecturer.
For MasterMath, homework is due Thursday, 12 Oct, at 10:45 by email.
Please submit in groups of size 2 or 3; we do not have the correction capacity for handling singletons. The exercise sheet is here. Note that you do not need to write anything for exercise 6.

The next lectures will be given by Chloe Martindale and Joan Daemen. While I'm offline you can find photos and videos on Chloe's homepage.

Homework
The 3rd exercise sheet is here.

Old exams

Old exams by me:

Henk van Tilborg has agreed that I put up his old exams for you to practice: