| 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 Systems and Information
Department of Mathematics and Computer Science
Room MF 6.103
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/.
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 in AUD 5 (except for Nov 13
Jan 16 where it is
in Flux 1.02)
and Thu block 7 and 8 in AUD 2 (except for Nov 23 when it is in
AUD 7).
We have two locations for the instruction sessions (Thu block 5 and 6),
namely Luna 1.240, and Altas 4.215 (except for Nov 16 when it is Atlas -1.820);
please join the room that's emptier. These rooms are still subject to change.
In 2020 and 2021 the course has been
running online with short videos – one video per topic,
so several videos per unit.
This year the course will be streamed and recorded.
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.
The teaching assistants for this course are:
It is not necessary to purchase a book to follow the course.
For some background on algebra see
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).
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.
GPG4win; if
you're using MAC-OS you can use GPG
Suite (though I'm getting reports that they changed their system and now
charge for the full version.
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.
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 3 or 4. 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 22 January 2024, 13:30 - 16:30; the rooms are TBD. The retake is scheduled for April 8, 18:00 - 21:00, the rooms are TBD. The exam accounts for the remaining 70% of the grade.
For 2023 the lectures will be recorded and streamed.
In 2022, the in-person lectures were recorded and posted 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.
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.
13 Nov 2023
This is our first day of lectures. More to come here after the lecture.
The frist lecture was be given by
Monika Trimoska.
Monika presented 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. Then, presented an introduction to public-key cryptography and
signatures and ended with security notions.
These three sets of slides:
16 Nov 2023
Note that we have excerises in block 5 &6, lectures in block 7 & 8.
Here is the exercise sheet for block 5 and 6: exercise-1.pdf. See also the raw data if paste fails.
This year exercise 1 and 2 are combined and 3 is omitted.
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.
The first homework is due on 23 November 2023 at 13:30. Here is the first homework sheet.
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.
Please remember to submit your homework by encrypted, signed email to
all the TAs.
Don't forget to include your public key and those of your team mates.
This second lecture was be given by
Monika Trimoska.
Monika 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
she used
She then covered column transposition as another historical cipher. The Playfair and
Hill ciphers were covered in the instruction session, see the exercise sheet.
These are the 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 Monika 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 are
here
20 Nov 2023
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. Note that this is very much simplifying
things and LFSRs alone are really bad stream ciphers as you can recover the
state update from the IV and just n more ooutput bits. However, LFSRs are used
in bigger constructions because we can reason well about the periods they
geerate (without having to try everything).
We have seen that depending on the
function the output sequence can have a very short period. For LFSRs we have
established that the output sequence is periodic (not just ultimately periodic)
if c0=1 and that the period divides the order of the state-update materix.
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 for LFSRs 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 thess examples.
Finally we showed that the characteristic polynomail of the state update matrix
is x^n -cn-1xn-1
-cn-2x
Pictures of black boards are here.
If you are following the course remotely note that this lecture corresponds to the videos for 16 Nov 2020.
23 Nov 2023
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 used 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. On the practical side is 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 which do not have irreducible LFSRs and we got some ideas – and disproved some. See here for the slides that I showed of the sums.
Pictures of black boards are here.
The second homework is due on 30 November 2023 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.
27 Nov 2023
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 getting the indies right – next year I'll use a
cheat sheet.
For a clean version see the 'Math vs. Mystery' video (maybe with pauses and rewiding) and checking the slides. However, do check the blackboard/live recording to see the instructions of how to approach the analysis of LFSRs.
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.
30 Nov 2023
Here is the exercise sheet for block 5 and 6: exercise-3.pdf.
This course was given for the first time in Q2 of 2014. Here are my exams so far
