Introduction to cryptology

2WF80 – Introduction to cryptology - Winter 2022

Contents Announcements Exams Literature Videos and slides Course notes and exercise sheets 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.

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

If you study mathematics, you should have participated in "2WF50 - Algebra" and "2WF70 - Algorithmic algebra and number theory".
If you study computer science or any other program you should have participated in "2DBI00 - Linear Algebra and Applications", "2IT50 or 2IT80 - Discrete structures", and "2WF90 - Algebra for security" before taking this course.
If not you can find some material in the Literature section but note that you are on your own for learning this.

Lectures take place Mon block 3 and 4 Helix 0.01 (except for Jan 16 where it is in Flux 1.02) and Thu block 7 and 8; the latter are in Flux 1.02 on 17 Nov and 19 Jan and in Aud 04 otherwise. We have four locations for the instruction sessions (Thu block 5 and 6), namely Gemini-zuid 3A.06, Gemini-zuid 3A.08, Luna 1.056, and Luna 1.240; please join the room that's emptier.
There will be no lectures on 22 December.
Lectures will be recorded and for the last two years the course has been running online with short videos – one video per topic, so several videos per unit. This means that you do not need to attend the in person lectures if you're concernd about your health. Please stay home and participate remotely if you are sick. If there is sufficient demand we will consider opening an exercise session online in the same time slot.

The teaching assistants for this course are:

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 crypto implementations 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).<,br> I recorded a video to demonstrate how to use Sage https://www.sagemath.org/, covering basics of finite fields and elliptic curves. The latter do not for this course so watch start till minute 10:50 and then again for about 2 minutes after 19:30.
I also wrote a short ``cheat sheet'' with commands for Sage, see here

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 being encrypted and signed, but prefer proper encryption of the whole email. Thunderbird has good integration and I hear that also outlook can work well with the plugins.

Examination

30% of the grade is determined by homeworks. There will be six sets of homework during the quarter. You should 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 and signed with GPG/PGP. Each participant must have communicated with the TAs at least once using GPG/PGP. You can find the keys for the TAs linked above or also on the key servers.
If for some reason you need to email me, you can find my public key for tanja@hyperelliptic.org on the key servers and on my homepage.

The exam will take place on 23 January 2023, 13:30 - 16:30. The retake is scheduled for April 17, 18:00 - 21:00. The exam accounts for the remaining 70% of the grade. The plan is to go back to the pre-Corona style of written exams without notebook support. So check out the exams from the 2019 edition and earlier (last exam Jan 2020) for examples.

Videos and slides

The in-person lectures will be recorded and should appear at videocollege.tue.nl.
For the 2020 and 2021 editions of the course I recorded a lot of short videos which you can find on the YouTube Channel.
The
course page for 2021 has short descriptions of all videos, slides, and no-cookie links to the YouTube videos. Watch them from there if you're on a low-cookie diet. For even fewer cookies, you can find the surfdrive. File names match the file names of the slides.

Class notes and exercise sheets

This section is extended through the course with notes of what happened in class and links to blackboard pictures. You can also find here the exercise sheets for the sessions on Thursdays.

14 Nov 2022
This was a full-on Murphy's law lecture with the system for the whole room failing, meaning that audio didn't work, I couldn't show slides (apart from the last 5 min of the second hour using a portable beamer), and the light for the blackboards was dimm. The person from AV support did a heroic effort to fix it but there was a remarkable level of things going wrong.

We covered the requirements that cryptography should achieve, namely to provide confidentiality, integrity, and authenticity, against attackers that have access to all messages sent and who may attempt to inject messages or to modify messages. We covered Caesar cipher (original and a keyed version), substitutionnn ciphers, the one-time pad, and Viginère cipher as well as how to break them and how big the keyspace is. Here are the slides that I tried to show.

Pictures of black boards are here.

17 Nov 2022
Here is the exercise sheet for block 5 and 6: exercise-1.pdf. See also the raw data if paste fails.
If you get stuck on the Hill cipher watch the 2021 video on XGCD under Math background on the 2021 course page.

For most of the exercises the solution is obvious when you have it. If you're not sure, please ask the TA in your room to check you solution. There are many more pages on the web with tools for cryptanalysis of classical ciphers, e.g. https://www.guballa.de/vigenere-solver, https://www.braingle.com/brainteasers/codes/index.php, http://www.cryptool-online.org, http://practicalcryptography.com/ciphers/, https://www.boxentriq.com/code-breaking.

We covered column transposition as another historical cipher. The Playfair and Hill ciphers were covered in the instruction session, see the exercise sheet. I commented briefly on rotor machines like the Enigma. I showed column transposition and a picture of the Enigma from these slides.
We had some rotor machines from the Cryptomuseum on show in the MetaForum. Currently we have Benne de Weger's Hagelin on display (near the elevator on floor 6 of the MetaForum) Check out the extensive website of the Cryptomuseum on crypto machines and spy craft.

As a second topic I covered stream ciphers as an example of symmetric-key encryption and as a more practical alternative to one-time pads. All security concerns of one-time pads apply – never use them twice – and additionally stream ciphers need to be checked whether they really produce random-looking outputs. Basic essentials to avoid the two-time pad issue is to use an IV (initialization vector) to make sure that the stream cipher has a fresh randomized starting point for each message and that the space for the IV is big enough to avoid repetitions.
The slides I used for the two--time-pad example are here

On a high level I explained the difference between symmetric-key cryptography and public-key cryptography and what public-key encryption and sigantures achieve along with the data flow. For submitting your homework you need to generate a keypair (a private and a public key). As the names suggest you should keep the private key private and can publish your public key. The latter is needed to encrypt messages to you and to verify signatures made by you, so that's what you need to send in along with your homework solution and that's also what your team mates need from you in order to communicate securely with you. You can find the keys of the TAs above under Announcements. I didn't want to wipe the board and used some slides for explaining the rest of public-key cryptography. You can find the slides here.

Pictures of black boards are here.

The first homework is due on 24 November 2022 at 13:30. Here is the first homework sheet. Please remember to submit your homework by encrypted, signed email to the TAs. Don't forget to include your public key and those of your team mates.

21 Nov 2022
We covered feedback-shift registers (FSRs), LFSRs and how to represent them via matrices.
(L)FSRs are examples of stream ciphers. The IV is used as the initial state and the key defines the feedback function. We have seen that depending on the function the output sequence can have a very short repeat. For LFSRs we have established that the output sequence is periodic (not just ultimately periodic) if c0=1. We also established that the all-zero state leads to the all-zero sequence of period 1 for any LFSR. We covered 2 complete examples with state-size 3 for and all states, one had periods 7 and 1, the other had 4,2,1,1. Note that there are 2^n different states, so the sum needs to match 2^n, so 8 in this example.
Finally we looked at the state update matrix and showed that its characteristic polynomail is x^n -cn-1xn-1 -cn-2x- .... - c1x - c0. Most of the time we consider sequences modulo 2 and the all the - turn into +. Note that the n is the state size and the ci are the update coefficients (being 1 for a closed wire and 0 for an open one).

Pictures of black boards are here. Somebody noticed that I made a mistake in the determinant computation. I have fixed this on the last picture (in pink), the c1 needed a minus sign.

24 Nov 2022
Here is the exercise sheet for block 5 and 6: exercise-2.pdf. You should really try to solve these exercises and make some conjectures about how orders, degrees, and periods fit together. You can call over the TAs for checking and I've put a quizz on Canvas so that you can check the numbers yourself -- and ask the TAs if you didn't get the right answer. I do expect that you use a computer for the larger examples.

In class we covered more details on LFSRs, in particular we took some of the conjectures on orders of C and f(x) that you should have found in the exercise session, turned them into theorems, and proved them. Now that they are proven, you can use them as facts, so proofs are useful. I mentioned Rabin's irreducibility test, you should know that from previous lectures and you should be able to recognize some irreducible polynomials of small degree namely x, x+1, x^2+x+1, x^3+x+1, and x^3+x^2+1 as factors of polynomials.

As a seccond topic we covered sums of LFSRs. This can be motivated by asking what we can build from given small hardware components, and in fact many designs are actually build from such pieces, but it is also a useful step in our quest to understand LFSRs and we got some ideas – and disproved some. See here for the slides that I showed of the sums (nicer drawings than I did on the board).

Pictures of black boards are here.

The second homework is due on 1 December 2022 at 13:30. Here is the second homework sheet. Please remember to submit your homework by encrypted, signed email to the TAs. Don't forget to include your public key and those of your team mates.

28 Nov 2022
This was another bout of Murphy's law. From what I understood from the person doing the recordings, the video for the second hour is likely messed up, too, in addition to the beamer being unkilleable, showing wrong colors, and me messing up a proof. If you're following remotely it likely makes more sense for this lecture to watch the 'Math vs. Mystery' video (maybe with pauses and rewiding) and checking the slides. In the live lecture I also resorted to using the slides when I was out of space where I could write.

At the end of the previous lecture we had found a counterexample to our hypotheses of what happens when we add two LFSRs. The main result of this lecture is that the characteristic polynomial of the LFSR that one obtains as the sum of two LFSRs equals the lcm of the characteristic polynomials of the LFSRs that are added up. We also proved that for an irreducible characteristic polynomial all non-zero output sequences have the same period length. Both of these results needed generating functions, which are very useful tools to know anyways. I got stuck in some pretty simple portion of the proof where I needed to rename the indices. In looking back, I think I had the result right in front of me without realizing it, because I somehow wanted to rename both rather than just one. I hope it's clearer on the picture or on the slides.

Further reading on finite fields and the mathematical theory of LFSRs is in Lidl/Niederreiter (see literature section), van Tilborg (see literature section), and David Kohel's lecture notes.

Pictures of black boards are here.


Old Exams

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