2WF80 -- Introduction to cryptology - Winter 2017

Contents Announcements Exams Literature Pictures and slides Old exams

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

This page belongs to course 2WF80 - Introduction to cryptology. This course is offered at TU/e as part of the bachelor's elective package 'Security'. The official page is here.

Contents
Classical systems (Caesar cipher, Vigenère, Playfair, rotor machines), shift register sequences, DES, RC4, RSA, Diffie-Hellman key exchange, cryptanalysis by using statistics, factorization, attacks on WEP (aircrack).

Some words up front: Crypto is an exciting area of research. Learning crypto makes you more aware of the limitations of security and privacy which might make you feel less secure but that's just a more accurate impression of reality and it a good step to improve your security.
Here is a nice link collection of software to help you stay secure https://prism-break.org/en/ and private https://www.privacytools.io/.

Announcements

You should have participated in "2WF50 - Algebra" or "2WF90 - Algebra for security" before taking this course. If not you can find some material in the Literature section.

All lectures take place Mondays 10:45 - 12:30 in AUD 10 and Thursdays 13:45 - 17:30 in Flux 1.03. There is a holiday break between Christmas and New year so that there are no lectures between 22 Dec and 07 Jan.

Gustavo Banegas is the teaching assistant for this course.

Literature and software

It is not necessary to purchase a book to follow the course.

For some background on algebra see

Some nice books on crypto (but going beyond what we need for this course) are For easy prototyping of cryptoimplementations I like the computer algebra system Sage. It is based on python and you can use it online or install it on your computer (in a virtual box in case you're running windows).
For encrypting your homeworks you should use GPG/PGP. If you're running linux then GnuPG is easy to install. If you're using windows I recommend using GPG4win; if you're using MAC-OS you can use GPG Suite. We are OK with having only the attachment encrypted, but for proper encryption of your email you might want to look into Enigmail which works well with Thunderbird.

Examination

30% of the grade is determined by homeworks. There will be two sets of homework during the quarter. You may hand in your homework in groups of 2 or 3. To make sure that you get used to crypto we require solutions to be sent encrypted with GPG/PGP. Each participant must have communicated with me at least once using GPG/PGP. You can find my public key for tanja@hyperelliptic.org on the key servers and on my homepage here. For Gustavo use gustavo@cryptme.in as email address and check for fingerprint 83458248E2E3D43F.

There will be an exam on 22 January 2018, 13:30 - 16:30 (with a retake on April 16, 18:00 - 21:00) which accounts for the remaining 70% of the grade. You may use a simple (non-programmable) calculator but no cell-phones or other devices containing calculator applications. You may not use books or your class notes.

Here is a test exam. Note that the CRT exercise would have somewhat smaller keys for the exam.

Class notes

This section will fill in gradually after the lectures. I'll provide short summaries and links to pictures of the blackboards. The homeworks will be posted here as well.

13 Nov 2017
Substitution cipher, Caesar cipher, Viginere, Playfair system. Some statements about the number of possible keys for these schemes.
Pictures of black boards and videos are here.

16 Nov 2017
Here is the exercise sheet for block 5 and 6: exercise-1.pdf. See also the raw data if paste fails.

For most of the exercises the solution is obvious when you have it. There are many more pages on the web with tools for cryptanalysis of classical ciphers, e.g. https://www.guballa.de/vigenere-solver, http://www.braingle.com/brainteasers/codes/index.php, http://www.cryptool-online.org, http://axion.physics.ubc.ca/cbw.html.

In the lecture we discussed the column transposition cipher (see pictures). You can play with it in the C1.3 exercise of the old Mystery Twister if you have Flash Player installed.

We discussed a bit about rotor machines and cryptanalysis. Visit the exhibition of rotor machines from the Cryptomuseum that is currently on show in the MetaForum and take a look at their website (and museum if you get a chance).

We discussed how to break the Hill cipher given some plaintext-ciphertext pairs and in particular repeated the extended Euclidean algorithm.

One-time pad with bits, and problems with reuse. Try the 4th challenge in the old Mystery Twister to see the reuse problems.

Finally, we discussed stream ciphers. These are much more practical than the OTP in that the key is much shorter. To encrypt a message, expand the key into a stream of pseudo-random bits and xor those to the message, i.e., treat the stream-cipher output as the one-time pad. To encrypt multiple message it becomes necessary to remember how many bits have been used and either stay in that state or forward by that many positions the next time one uses the cipher. This is impractical. Initialization Vectors (IVs) deal with that problem in that they move the beginning of the stream to a random postion. The IV is then sent in clear along with the ciphertext, so that the receiving end can compute the same starting position. More on this on Monday.
Pictures of black boards and videos are here.

21 Nov 2017
Feedback shift registers and how to use them for encryption; k-th order feedback sequence (=a sequence with k coefficients), period, pre-period(=tail), ultimately periodic sequences, Linear feedback shift registers (LFSRs), want c0=1 (else there is just a delay in output); can run backwards, is periodic, max period is 2^n-1, relation to matrix multiplication. characteristic polynomial of the matrix.
Note that we did the last part only for characteristic 2, in general we need to pay attention to signs and P(x)=det(xI-C).
Pictures of black boards and videos are here.

23 Nov 2017
Here is the exercise sheet for block 5 and 6: exercise-2.pdf.

Old Exams

This course was given for the first time in Q2 of 2014. Here are the exams so far