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

• Tanja Lange "Number Theory and Algebra" ( Chapter of draft book "Discrete Mathematics").
• Tanja Lange "Finite Fields" (Chapter of draft book "Discrete Mathematics").

• 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.

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.

Old Exams

This course was given for the first time in Q2 of 2014. Old exams are listed here (solutions are not - and will not be - provided).

• Exam from 26 January 2026: 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:
  • ciphertext only attack;
  • known plaintexts/ciphertexts attack (example: car + car key);
  • chosen plaintexts (or ciphertexts) attack (CPA/CCA).
  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:
  • (secret-)key-recovery;
  • plaintext-recovery;
  • recovery some bits of the plaintext -> IND-CPA, IND-CCA1, IND-CCA2 distinguishers.
  
  Additional material (slides by prof. Tanja Lange):
  • Cryptology: Basic concepts and intro
  • Public-key and symmetric-key cryptology
  • Security notions for public-key cryptography
  
  
• 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):
  • Historical ciphers I
  • Historical ciphers II
  
  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):
• Stream ciphers: definition and IV
• Feedback shift registers
• Linear feedback shift registers


• 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):
  • LFSRs: matrix and characteristic polynomial
  • LFSRs: Mathematical properties
  
  
• 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):
  • Sums of LFSRs
  • LFSRs: Math vs. mystery
  
  
• 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):
  • Practical use of LFSRs
  • Stream ciphers: RC4 and others
  
  
• 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.:
  • truncated permutation Trun(P(.)), where Trunc: {0,1}^{2n} -> {0,1}^n returns half of the input bits;
  • cipher (see Davies-Meyer, Matyas-Meyer-Oseas, and Miyaguchi-Preneel).
  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):
  • Hash functions
  • Message authentication codes (MACs)
  
  
• 4 Dec 2025: Definition of block cipher.
  Details about Substitution-Permutation Network (SPN) construction. Example: PRESENT. How to choose the S-Box? We look for a non-linear function that maximizes the non-linearity. Given F : {0,1}^n -> {0,1}, the non-linearity of F is defined as NL(F) := 1 - max_{G linear} |{x \in {0,1}^n | F(x) = G(x)}| / 2^n. E.g., given F(x_0, x_1, x_2, x_3) = x_0 + x_1 (linear), then NL(F) = 0. Given F(x_0, x_1, x_2, x_3) = x_0 + x_0 * x_1 * x_2 * x_3 (almost linear), then NL(F) = 1/16.
  Feistel construction: invertible even if the round function is not invertible.
  Data Encryption Standard (DES): see here for more details. Broken: 3-DES as possible replacement. Match-in-the-Middle attack against 2-DES.
  Modes of operation (for encryption of large messages):
  • Electronic Codebook mode (ECB): *not* secure!
  • Cipher-Block-Chaining mode (CBC);
  • Output-FeedBack mode (OFB);
  • Counter mode (CTR).
  
  Additional material (slides by prof. Tanja Lange):
  • Block ciphers
  • Modes of operation
  
  
• 8 Dec 2025: Extended Euclidean algorithm (XGCD): how to find gcd(a,b); how to find x, y s.t. x * a + y * b = gcd(a,b). Note: x, y are not unique (x' = x - b/gcd(a,b)*i; y' = y + a/gcd(a,b)*i).
  Fermat's little theorem (with proof). Euler's theorem (where Euler's function phi(n) := n * prod_{p | n} (1 - 1/p)).
  Chinese Remainder Theorem (with sketch of the proof).
  Schoolbook RSA (encryption): key-generation, encryption, decryption. Invertibility of RSA. Sizes of n for several security levels.
  Right-to-left binary exponentiation.
  Signature via RSA: key-generation, signature, verification.
  
  Additional material (slides by prof. Tanja Lange):
  • Extended Euclidean algorithm (XGCD)
  • Chinese remainder theorem
  • Exponentiation
  • Schoolbook RSA
  
  
• 10 Dec 2025 (E.S.H.A. Trojan - not part of the course!): Differential attacks on DES and AES - see here for details.
  
  
• 11 Dec 2025: Problems with Schoolbook RSA:
  • small exponent: no modulo reduction! Choose e.g. e = 2^16 + 1;
  • if the attacker knows c_1 and c_2 where m2 = a * m1 + b for known a,b, it is possible to recover the message;
  • attack if the attacker knows encryption of same message under several secret key (but same exponent e);
  • RSA is deterministic and homomorphic (that is, Enc(m*m') = Enc(m) * Enc(m')): *not* IND-CPA/-CCA1/-CCA2 secure!
  • signature RSA: trivial to generate valid signatures (given s, the pair (m=s^e, s) corresponds to a valid signature, even if the attacker has no control on m). To avoid this problem:
    • pad the message as m|0^c for a certain c (where 0^c = 00...0 of length c). The probability that s^e satisfies this padding is 2^{-c}, so very low for e.g. c=128;
    • sign the hash of the message, that is, s := (H(x))^d. For the forgery, the attacker has to find m s.t. H(m) = s^e, that is, the attacker has to break the hash (which is infeasible!).
    (Important: always sign the hash value of the message H(m) rather than the full message!)
  Solutions: RSA PKCS#1 v1.5 and OAEP.
  
  Additional material (slides by prof. Tanja Lange):
  • Problems with Schoolbook RSA I
  • Problems with Schoolbook RSA II
  • Problems with Schoolbook RSA III
  
  
• 15 Dec 2025: Primality tests:
  • Fermat: a^{n-1} != 1 mod n for gcd(a,n)=1 -> n is not prime. Note: this is a necessary condition only! E.g., given n = 341 = 11 * 31, then 2^340 = 1 mod 341, but n is obviously not prime. Similar for n = 561;
  • Miller Rabin: let n = 1 + 2^s * d. n is said "strong probable prime" if a^d = 1 mod n, or if a^{2^r * d} = -1 mod n for some 0 <= r < s. Same considerations as before (check n = 221 = 13 * 17 = 1 + 2^2 * 55, with a = 174: 174^55 = 47, and 174^{2*55} = -1 mod 221).
  Cost of factorization: O(e^{(a * (log(n) * (loglog(n))^2)^{1/3}}) via General number field sieve -> size of n for security: e^{(a * (log(n) * (loglog(n))^2)^{1/3} >= 2^k for k-bit of security ( factorization challenges).
  p-1 Method: gcd(a^{p-1}-1, n) = p but p-1 is unknown. If p-1 has small factors, consider gcd(a^s,n) for s = lcm{1,2,...,B} for some B >= 2.
  Diffie-Hellman key-exchange. Let (Z_p, *) be a group with generator g (note: g^{p-1} = 1 mod p, and g^l != 1 mod p for each 0 < l < p-1). Alice chooses a, computes hA = g^a; Bob chooses b, computes hB = g^b. hA and hB are exchanged. Alice computes hBA = (hB)^a and Bob computes hAB = (hA)^b. Note that hAB = hBA. Set up the symmetric key as k = Hash(g, hA, hB, hAB).
  Security of Diffie-Hellman:
  • Decisional Diffie-Hellman problem (DDHP);
  • Computational Diffie-Hellman problem (CDHP);
  • Discrete Logarithm problem (DLP).
  Note: DLP -> CDHP -> DDHP.
  
  Additional material (slides by prof. Tanja Lange):
  • Attacks on RSA
  • Diffie-Hellman key exchange
  
  
• 18 Dec 2025: Cost of discrete-logarithm: O(e^{(a * (log(n) * (loglog(n))^2)^{1/3}}) via Coppersmith algorithm (similar to RSA).
  Baby-step giant-step attack: how to find the discrete logarithm in time O(n^{1/2}).
  Shamir secret sharing (n,k): splits a secret S into n parts, distributing them among n different participants, such that k of them are sufficient for recovering it. Idea:
  • let F(x) be a polynomial function of degree k-1 such that F(0) = S;
  • compute and distribute (i, F(i)) for n different integers i >= 1;
  • participants: use Lagrange interpolation polynomial to find F, and so S.
  ElGamal encryption: key-generation, encryption, and decryption.
  
  Additional material (slides by prof. Tanja Lange):
  • Baby-step giant-step attack
  • Example for BSGS
  • Shamir secret sharing
  • ElGamal encryption and signature
  
  
• 5 Jan 2026: NO LECTURE!
  
  
• 8 Jan 2026: ElGamal signature scheme: key-generation, signature, and verification. Security of ElGamal signature scheme.
  ElGamal in practice: let q | (p-1) be a prime of size 160 bits. Set up ElGamal encryption/signature via a generator g of order q.
  Decisional DHP (DDHP): given g, g^a, g^b, g^c, decide if g^{a*b} = g^c or not. If g has order p-1, we can solve it, by working with the parity of a, b, and c. Note that g^((p-1)/2) = - 1. And (g^a)^((p-1)/2) = 1 if a even, and -1 if a odd. Moreover, parity(a*b) = odd if a & b odd, and even otherwise. Finally, if c = a*b, then parity(c)=parity(a*b). Otherwise, Prob(parity(c)=parity(a*b))=1/2. By combining all these observations, it is possible to break DDHP.
  How to avoid this problem? If p = 2*p'+1 for p' prime, choose a generator g of ord(g)=(p-1)/2.
  How does it affect the security of ElGamal? If an attacker can break DDHP, then ElGamal is *not* IND-CPA. Indeed, note that c/m_0 = beta^l=g^{d*l} if b = 0, and beta^l * m_1/m_0 = g^{d*l} * m_1/m_0. Solve the DDHP given by (g, beta = g^d, r = g^l, c/m_0) to decide if b = 0 or not.
  Note: ElGamal is *not* IND-CCA2 as it is homomorphic. Indeed, given (r_1 = g^{l_1}, beta^{l_1} * m_1) and (r_2 = g^{l_2}, beta^{l_2} * m_2), then (r_1 * r_2 = g^{l_1+l_2}, beta^{l_1+l_2} * m_1 * m_2) is a valid ciphertext of m_1*m_2.
  
  Please, complete the survey: course evaluation.
  
  Additional material (slides by prof. Tanja Lange):
  • ElGamal encryption and signature
  • Hardness of DLP, DDHP, CDHP
  
  
• 12 Jan 2026 (last lecture): as we saw in the last lecture, ElGamal encryption is homomorphic. A possible way to destroy such property is by using a hash function: c = Hash(beta^l, beta, r) * m -> m = c / Hash(r^d, beta, r).
  KEM-DEM: Key Encapsulation Mechanism + Data Encapsulation Mechanism. Combination of public-key encryption (= KEM) and symmetric-key encryption (= DEM). Alice and Bob share a secret key K by using a PKC turned into a KEM. Then, they use a symmetric cipher (e.g., AES) instantiated with K to share the data in a confidential way.
  Problem: any public-key encryption scheme is vulnerable to a Man-in-the-Middle attack. Concrete example with Diffie-Hellman.
  The Needham-Schroeder authentication protocol provides a solution to this problem. A key ingredient is a server trusted by both parties. The Needham-Schroeder Symmetric Key Protocol is based on a symmetric encryption algorithm, and forms the basis for the Kerberos protocol. The Needham-Schroeder Public-Key Protocol is based on public-key cryptography, and it is intended to provide mutual authentication between two parties communicating on a network.
  
  Additional material (slides by prof. Tanja Lange):
  • KEM-DEM framework
  • Authenticated key agreement
  
  
• 15 Jan 2026 (13.30 - 15.30): TAs will answer any specific question about the course/previous exams - location: AUD02.