Lorenzo Grassi
Coding Theory and Cryptology group
Department of Mathematics and Computer Science
Eindhoven University of Technology
MetaForum, room 5.071A
E-mail: l.grassi (at) tue.nl
This page belongs to course 2MBD60 - Introduction to cryptology.
This course is offered at TU/e as part of the bachelor's elective
package
Security
and used to be called 2WF80 - Introduction to Cryptology. For the 2025/26
edition there is no difference between the courses.
Contents
- Introduction to symmetric cryptography, public-key cryptography, and digital signature schemes
- Classical ciphers (Caesar cipher, Vigenère, Playfair, rotor machines, ...)
- Shift Register Sequences and RC4
- Block cipher DES and mode of operations (ECB, CBC, ...)
- Hash functions and Message Authentication Code (MAC)
- RSA encryption and signature
- Diffie-Hellman key exchange
- ElGamal encryption and signature
- Cryptanalysis by using statistics, factorization, ...
- Secret sharing
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.
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 on Monday (block 3 and 4)
and on Thursday (block 7 and 8).
Instruction sessions take place on Thursday (block 5 and 6).
I really recommend doing the instruction sessions and
attending them live if you can fit them in your agenda. They are more important
than the lecture, and thus get the prime spot. We'll have enough instructors in
the rooms so that you can ask your questions and check the answers to your
exercises with them. We will not hand out solutions.
The teaching assistants/instructors for this course are the following 6 people:
- Sebastiano Boscardin,
s.boscardin (at) tue.nl, PGP key
- Emanuele Di Giandomenico,
e.di.giandomenico (at) tue.nl, PGP key
- Matthias Meijers,
teaching (at) mmeijers.com,
PGP key
- Berenika Richterová,
b.richterova (at) tue.nl,
PGP key
- Abishanka Saha,
a.saha1 (at) tue.nl, PGP key
- Tianxin Tang,
t.tang2 (at) tue.nl , PGP key
Note: there will be no lecture on Monday January 5, 2026. We will have lecture on Monday January 12, 2026.
Literature and Software
It is not necessary to purchase any 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
-
Jean-Philippe Aumasson
"Serious Cryptography", No Starch Press, 2017.
-
Johannes Buchmann "Introduction to Cryptography", Springer, 2004.
-
Neal Koblitz "A course in Number Theory and Cryptography",
Springer, 1994.
-
Rudolf Lidl and Harald Niederreiter "Introduction to Finite Fields and
their Applications", Cambridge University Press, 1994.
-
Christof Paar and Jan Pelzl "Understanding Cryptography", Springer, 2010.
-
Doug Stinson "Cryptography: Theory and Practice", CRC Press, 1995.
-
Henk van Tilborg "Fundamentals
of Cryptology" Kluwer academic Publishers, Boston, 2000.
For easy prototyping of crypto implementations, I suggest 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). See this video for a demonstration on how to use Sage https://www.sagemath.org/ (by Prof. Tanja Lange - it also covers basics of finite fields and
elliptic curves). Prof. Tanja Lange also wrote a short ``cheat sheet'' with commands for Sage,
see here.
Videos and Slides
For 2022 and 2023 the lectures were recorded
and posted at
TU/e's
Yuja site. Search for course code 2WF80 (the old name of this course) to
see the recordings. Courses from Prof. Tanja Lange are the 2022/23 and 2023/24 versions, not the 2018/19
version which for some reason laods with preview. Click on the three vertical
dots on the right end of the course to select "open" and get to the videos.
For the 2020 and 2021 editions of the course, Prof. Tanja Lange recorded a lot of short videos
which you can find on the YouTube
Channel which are better for self study or if you want a more direct way to
look up a subject.
The
course page for 2021 has short descriptions of all videos, slides,
and no-cookie links to the YouTube videos.
Homeworks
Any exercise and homework module will have the corresponding files released on Canvas at appropriate times. That is, 30
minutes before the corresponding instruction for the exercises, and 30
minutes after the instruction for the homeworks.
Homework deadlines are at the start of an instruction, starting November 20 at 13:30. (And will be released 30 minutes after the preceding instruction
ends.)
Homework assignments should be completed and submitted in groups of 4. Please, use Canvas to form a group.
We require you to:
-
submit your solutions via Canvas (without encrypting them), and
-
send them encrypted and signed to all 6 teaching assistants via e-mail.
Please always inlcude all 6 teaching assistants when you send in your homeworks - and make
sure that you encrypt to all 6 of them and to your team mates. (Please, do not send your homeworks to Prof. Lorenzo Grassi.) All email
systems that I know of will do this automatically if you have all keys in your
address book and the people in the To or Cc field your email.
The teaching assistants from 2023 wrote
this
guide to homework submission for this course.
For encrypting your homeworks you should use GPG/PGP. If you're
running Linux then GNU uPG 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, the command-line linux version works for sure).
Thunderbird has good integration and I hear that also outlook can
work well with the plugins.
If absolutely not possible otherwise, we are OK with having only the attachment being
encrypted and signed, but prefer proper encryption of the whole email. If you
end up going for file encryption only you must ensure that all receipients can
decrypt and you're missing out on the support that the email system offers you.
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 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.
Date of the Exam (TBC): Monday January 26, 2026 (9am-12pm).
Old Exams
This course was given for the first time in Q2 of 2014. Old exams are listed here.
-
Exam from April 2025 here.
-
Exam from 03 February 2025: here.
-
Exam from April 2024 here.
-
Exam from 22 January 2024: here.
-
Exam from April 2023 here.
-
Exam from 23 January 2023: here.
-
Exam from April 2022: here.
-
Exam from 24 January 2022: here.
Printing from Ans deleted the pictures. Here are
the PCBC MAC and
two examples of modes
CFB|CBC
and
CBC|CBC.
-
Exam from April 2021: here.
Printing from Ans deleted the pictures. Here are
the simple MAC and
two examples of modes
CRT|CBC
and
OFB|CBC.
-
Exam from 25 January 2021: here.
Printing from Ans deleted the pictures. Here are
the LFSR schematic and the
MAC from exercise .
-
Exam from 27 January 2020: here.
-
Exam from 22 January 2018: here.
Note that in the text of exercise 6 the equation for S_1 should use O_1, not O_i.
-
Exam from 19 January 2017: here.
-
Exam from 18 January 2016: here.
-
Exam from 19 January 2015: here.
-
Practice exam 2014/2015: here.
Note: the exercise about breaking RSA when all recipients have
the same exponent and get the same message has too large numbers
for your calculator.
Class Notes
This section is extended through the course with notes of what
happened in class.
-
10 Nov 2025: Introduction to symmetric-key cryptography (and Kerchkoff's principle).
Main goals of cryptography: Confidentiality, Authenticity, Integrity, Non-Repudiation.
Cryptanalysis of symmetric-key schemes.
#Type of attacks:
- key-recovery;
- plaintext-recovery;
- recovery some bits of the plaintext -> secret-key distinguishers (distinguishing between a Pseudo-Random Permutation (PRP) and a cipher instantiated via a secret key - see also here).
#Attack scenario:
Introduction to public-key cryptography (difference between public-key and secret-key: impossibility to derive the sk from the pk).
Cryptanalysis of public-key schemes.
#Type of attacks:
Additional material (slides by prof. Tanja Lange):
-
13 Nov 2025: Definition of digital signature schemes.
#Type of attacks:
- (secret-)key-recovery;
- universal forgery (ability to forge a signature for *any new* message);
- existential forgery (ability to forge a signature for *some new* messages).
Historical ciphers:
- Caesar cipher (one-to-one relation between alphabet and integers modulo 26);
- Vigenere cipher;
- Substitution cipher: frequency analysis + example of secret-key distinguisher;
- Playfair cipher;
- ADFGX cipher (= substitution + column transposition);
- Hill cipher (see example about inverse matrix).
Additional material (slides by prof. Tanja Lange):
Slides about E.S.H.A. Trojan.
-
17 Nov 2025: Shannon's Principle (Confusion + Diffusion).
Enigma: details and size of the key = number of combinations equal to 3! * 26^3 * 26!/(14! * 2^6 * 6!) approx 2^53.3 (see explanation for plugboard with 10 cables).
One-time pad (or Vernam cipher) as example of *stream cipher*.
Pseudo-Random Number Generator (PRNG):
- crypto scenario: relation with Vernam cipher
- example of PRNG in C/C++: x_{i+1} = a * x_i + b mod q, where q = 2^32, a = 1103515245, b = 12345 (and x_0 being the seed).
How to instantatiate a PRNG? (Linear) Feedback-Shift Register ((L)FSR):
- Definition, and possible settings (for simplicity, we omit the initial value IV in the lecture):
- Updating function F = secret, and initial state s_0, s_1, ..., s_{n-1} = public (for example, IV instantiates the initial state), or
- Updating function F = public, and initial state s_0, s_1, ..., s_{n-1} = secret (it is possible to reserve part of the initial state to the IV).
- Example over Z_2: F(x_0, x_1, x_2) = x_0 + x_1 * x_2 + 1 mod 2. Possible periods: 1 (if initial state is 111), 2 if initial state is (101), and 5 if initial state is (001). Not surprising, as there at most 2^3 = 8 states, and 1+2+5=8.
- How to draw a LFSR defined by F(x_0, x_1, ..., x_{n-1}) = sum_{i=0}^{n-1} c_i * x_i over Z_2 (for c_i in {0,1}).
- Definition of period and divisibility property.
- The periods depend both on the details of F and on the initial state: what is the longest possible period? Answer (and more examples) in the next lectures!
Additional material (slides by prof. Tanja Lange):
-
20 Nov 2025: Additional examples: s_{i+3} <- s_i + s_{i+2} (periods: 1 and 7) and s_{i+3} <- s_i + s_{i+1} + s_{i+2} (periods: 1, 1, 2, and 4).
LFSRs are *not* secure for cryptographic purposes! E.g., it is simple to recover F even if it is secret. Non-Linear FSRs (NLFSRs) are required. Still, in this course, we will mainly study LFSRs, and transfer our analysis to NLFSRs later on (whenever possible).
Matrix representation C of LFSRs and order of a matrix (defined as smallest k > 1 s.t. C^k = I).
Theorem (with proof): Let Ord(C)=k for C being the state update matrix of an LFSR. The longest period generated by this LFSR is k. State (0, 0, ..., 0, 1) is a starting state of maximal period. All (sub-)periods divide k (Proof for this last part: let y be a state with period q < k, hence, y = y * C^q. By assumption, y = y * C^k. Let k = q * s + r for 0 <= r < q. Hence, y = y * C^{q * s + r} = (y * C^{q * s}) * C^{r} = y * C^r. As q is the order of y, it follows that r = 0, that is, k is a multiple of q.)
@Note: there was a *mistake* in the proof given during the lecture. The correct proof proceeds as following:
- Assume by contradiction that 0 < r < k is the period of [0,0,...,0,1];
- As we saw in the class, we have S_{n,n} = S_{n,n} * C^r, which implies C^r = I;
- It follows that the order of C is r < k, which contradicts the assumption (Ord(C) = k). Hence, the claim.
(Note that you can find the proof also in the slides of prof. Tanja Lange.)
Characteristic polynomial defined as P(x) = det(x * I - C), and equal to P(x) = x^n - sum_{i=0}^{n-1} c_i * x^i (note that + and - are the same modulo 2). Ord(P) defined as smallest k > 1 s.t. x^k = 1 mod P(x).
Ord(P) >= deg(P). As Ord(P) = Ord(C), we will use the polynomial P instead of C as it is easier to handle.
Based on "Rabin's Irreducible Test", if P irreducible, then Ord(P) divides 2^n - 1 (where n = deg(P)). It follows that if P is irreducible and 2^n - 1 is prime, then Ord(P) = 2^n - 1 (which implies the periods are only 1 or 2^n-1).
Additional material (slides by prof. Tanja Lange):
-
24 Nov 2025: Theorem (with proof): If P irreducible, then all non-zero starting states have the same period.
Sum of LFSRs:
- sum of two LFSRs with period p and r -> period lcm(p,r).
- gcd(p,r) sequences of period lcm(p,r) + sequences of period p, r, 1.
Definition of reciprocal polynomial F^\star(x): if F(0)!=0 -> deg(F)=deg(F^\star), (F*G)^\star = F^\star * G^\star, F irreducible <-> F^\star irreducible, lcm(F^\star, G^\star) = (lcm(F, G))^\star.
Definition of generating function S(x): 2^n generating functions for an LFSR of state size n; if period r: S(x) = (sum_{i=0}^{r-1} s_i * x^i) / (x^r + 1).
Proposition (with proof): let S(x) be the generating function of an LFSR with characteristic polynomial P(x) = x^n + sum_{i=0}^{n-1} c_i * x^i. Then: deg(S(x) * P^\star(x)) < n.
Proposition (no proof): let F(x) be a function of degree striclty less than n. Let P(x) be P(x) = x^n + sum_{i=0}^{n-1} c_i * x^i. Then, S(x) = F(x)/P^\star(x) is the generating function of an LFSR of period n satisfying s_{j+n} <- sum_{i=0}^{n-1} c_i * s_{j+i}.
Theorem (proof in progress): Let {s_i}_i and {t_i}_i be two output sequences of two LFSRs with characterestic polynomials P(x) and Q(x). Then, there exists an LFSR with output matching {s_i + t_i}_i and characterestic polynomials lcm{P(x), Q(x)}.
@Note: on the blackboard, I wrote R(x) = A(x) * F(x) = B(x) * G(x). This is wrong.
Correct one is: R^\star(x) = A(x) * P^\star(x) = B(x) * Q ^\star(x).
Indeed: F(x)/P^\star(x) -> F(x)/P^\star(x) * lcm{P^\star(x), Q^\star(x)}/lcm{P^\star(x), Q^\star(x)} = A(x) * F(x) / lcm{...}.
Additional material (slides by prof. Tanja Lange):
-
27 Nov 2025: Proof of Theorem about sum of LFSRs (from previous lecture).
Re-visiting the "odd" example where we added two sequences and got a period that was shorter than the input.
Summary on how to analyze a generic LFSR: (1) decompose its polynomial characterestic P(x) = prod_i (P_i(x))^{e_i} so that P_i are irreducible; (2) analyze (P_i(x))^{e_i} (compute periods); (3) combine periods, taking care of offsets to get all periods. See e.g. here (end of the page - f(x)=(1+x+x^2)*(1+x+x^3)*(1+x+x^4)^2) for a concrete example (many results in this webpage are not part of the course, and are not requested during the exam - just look at the example, where you can brute force the sequences/periods of (1+x+x^4)^2).
Three stream ciphers (based on non-linear FSRs) for telecommunication:
- A5/1 and A5/2. Both broken (links for more details in the slide);
- SNOW-3G.
One extra stream cipher: RC4. Attack/Distinguisher on the 2nd output byte. Additional observations on RC4.
Just for your knowledge: better stream ciphers exist! See the final portfolio from the eSTREAM competition (example: Salsa20).
Additional material (slides by prof. Tanja Lange):
-
1 Dec 2025: Problem: stream ciphers do not provide authentication and integrity!
Solution: Message Authentication Codes (MACs).
In order to instantiate a MAC, we need a hash function, that is, a hash function that takes inputs of arbitray size, and returns outputs of fixed size, such that it is easy/fast to compute, but hard to invert. In particular, a hash function should guarantee:
- pre-image and second pre-image resistance;
- collision resistance.
A hash function that returns n bits can guarantee at most 2^n bits of security for (second) pre-image resistance and 2^{n/2} bits of security for collision resistance (due to the birthday paradox).
Merkle-Damgaard construction for setting up secure hash functions. (Public) Compression function {0,1}^{2n} -> {0,1}^n set up via e.g.:
Importance of the padding 10^* (see here for details).
Short summary of hash functions:
- MD4 (completely broken) and MD5 (easy to find collisions);
- SHA-1 (first collisions computed in 2017);
- SHA-2 (including SHA-256 and SHA-512);
- SHA-3.
How to set up the MAC?
- MAC(x, k_{aut}) := H(k_{aut}, x) (if H = Merkle-Damgaard construction, then it is trivial to generate a MAC. Indeed, let y = H(k_{aut},x). Then, MAC(x | x' , k_{aut}) = H(y, x') computed without knowning k_{aut}, just y);
- MAC(x, k_{aut}) := H(x, k_{aut}) (if H = Merkle-Damgaard construction, it is sufficient to find x and x' such that H(x) = H(x') (no key involved!) in order to find a collision in the MAC);
- MAC(x, k_{aut}) := H(k_{aut}, x, k_{aut}) (still weak);
- HMAC:= H(k_{aut}, H(k_{aut}, x)).
See the LATEX package (by Luka Bijma) for drawing Linear Feedback Shift Registers (LFSRs) in TikZ.
Additional material (slides by prof. Tanja Lange):
-
4 Dec 2025: (to appear!)
Additional material (slides by prof. Tanja Lange):
