| 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 optional 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/.
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 MF 6 (except for 12 Dec, when it's in PAV M23) and Thursdays 13:45 - 17:30 in Laplace 1.05. There is a holiday break between Christmas and New year so that there are no lectures between 23 Dec and 08 Jan. All courses will be given in their allocated slots, hence there will be no lectures in the repetition week.
It is not necessary to purchase a book to follow the course.
For some background on algebra see
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. To make sure that you get used to crypto I require
solutions to be sent encrypted with GPG/PGP. Each participant must
have communicated with me at least once using GPG/PGP.
My key can be found
here.
There will be an exam on 23 January 2017, 13:30 - 16:30 (with a retake on
April 20, 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.
The first exam takes place in matrix atelier 1.
Here is a test exam. Note that the CRT exercise would have somewhat smaller keys for the exam.
14 Nov 2016
Substitution cipher, Caesar cipher, Viginere, one-time pad,
Playfair system. Some statements about the number
of possible keys for these schemes.
Pictures of white boards are here.
17 Nov 2016
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. We discussed how to break the Hill cipher given some plaintext-ciphertext pairs and in particular repeated the extended Euclidean algorithm.
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.
I wanted to show an Enigma animation but it didn't work in the browsers
I tried. Justin Szanto tweaked a few things and made it work again.
You can play with it at
his copy
of the page. Have fun!
We discussed a bit about rotor machines and cryptanalysis.
One-time pad with bits, and problems with reuse. Try the 4th challenge
in the old Mystery Twister to see the reusse problems. Finally, we discussed
stream ciphers.
Pictures of black boards are here.
21 Nov 2016
Feedback shift registers and how to use them for encryption;
k-th order feedback sequence (=a sequence with k coefficients),
period, pre-period, ultimately periodic sequences,
Linear feedback shift registers (LFSRs), want c0=1, can run backwards,
is periodic, max period is 2^n-1, relation to matrix multiplication.
characteristic polynomial of the matrix.
Pictures of black board are here.
I was too fast in erasing the board at some point. Take a look at the pictures
from last year's lecture.
24 Nov 2016
Here is the
exercise sheet for block 5 and 6: exercise-2.pdf.
We summarized the results of exercise 1 to derive some conjectures on the
periods and factorization patterns.
If you solve the second one, note that for the Fibonacci
squence you need to use minus signs to get the characteristic polynomial
and that there was a sign error when we derived the result (we need
(-1)k and (-1)k-1 on the terms.
Defintion of irreducible polynomials, order/period of a polynomial, Rabin's
irreducibility test, period of an irreducible polynomial of degree n
divides 2n-1. Order of C matches period of its characteristic
polynomial.
Order of a polynomial and why it is defined; some examples using the
characterisitc polynomials from the exercises; this order matches the
order of the matrix C -- because f is C's characteristic polynomial;
if f is irreducible of degree n its order.
We tried to prove that for irreducible characteristic
polynomials the period of the polynomial equals the maximum least
period of the LFSR. The proof uses generating functions and I got stuck
in the order of summation. I stated without proof that if F and G are
the characteristic polynomials of
(si) and (ti) then
(si)+(ti) has characteristic polynomial
lcm(F,G).
Further reading on finite fields and LFSRs, including the missing proof,
is in Lidl/Niederreiter (see literature section).
Pictures of black boards
are here.
28 Nov 2016
Lecture given by Andreas Hülsing.
Concept of public-key cryptography: key generation, producing a keypair (sk,pk); encryption, using pk; and decryption, using sk. Similar set up for signatures.
Signatures are used e.g. in your browser.
Recap of number theory background: multiplicative group modulo n,
Euler-phi function (examples + general formula), Lagrange's
theorem).
RSA cryptosystem: public key for RSA is (n,e), private key is (n,d), where n=pq
for two different primes p and q, φ(n)=(p-1)(q-1) and d is the
inverse of e modulo φ(n); encryption, decryption, sign,
verify. Attention, this is schoolbook RSA, do not use
this in practice. For functionality (and security) we want to sign h(m)
and not m. Some examples of how bad schoolbook RSA will come on Thursday.
Security notions of public-key cryptography: semantic security as game
between attacker and challenger; the attacker should not have higher
probability than guessing in deciding which of two messages m0 and m1 was
encrypted, given the messages and one ciphertext.
Thanks to Andreas for taking
pictures of the black boards.
01 Dec 2016
Lecture given by Christine van Vredendaal.
Here is the exercise sheet for block 5 and 6: exercise-3.pdf
Exponentiation by square and multiply and how many operations this
takes, examples; can choose small e but d must be large/random.
More on security notions.
Attack on RSA using gcd computation.
First problem with schoolbook multiplication: we can recover a message that is sent to multiple people, if they all use the same small exponent. More issues with schoolbook RSA: can decrypt linearly related messages; RSA is homomorphic; schoolbook RSA is not CCA-II secure; RSA OAEP.
The first homework is due on December 08, 2016 at 13:45. Here is the first homework sheet.
Please remember to submit your homework by encrypted, signed email.
Don't forget to include your public key for me to reply.
05 Dec 2016
I couldn't really write, so I showed some slides.
The slides are
here.
Pictures of black boards are here.
08 Dec 2016
Here is the exercise sheet for block 5 and 6: exercise-4.pdf
Diffie-Hellman key exchange in different groups,
including some insecure ones.
A good choice is to use the intergers modulo a
large prime or elliptic curve crypto (not covered in this class).
CDHP, DDHP, DLP, relations between
these problems. Problem with active man-in-the-middle attacks,
authenticated DH needs long-term keys.
Semi-static DH,
ElGamal encryption, encryption is homomorphic -- asking for
(r,2c) can be used to decrypt (r,c). ElGamal signatures
and why these systems work.
Baby-Step Giant-Step algorithm: any system based on DLP has at most
squareroot of the group oder hardness of the DLP.
I wrote slides because I still
couldn't write on the board.
12 Dec 2016
Needham-Schroeder authentication protocol and why it doesn't actually
proof to B that he is talking to A. Shamir secret sharing: allows to share a secret in a
t-out-of-n fashion so that any set of t people can recover it; works
by simple Lagrange interpolation.
There is an error on the board for the Lagrange coefficient:
the numerator in the product is ji, not jl
Note that the secret never needs to
be re-computed -- for applications in RSA or DH the shares can be
applied individually and then only the per-message secrets be
combined. Also note that there is no need to ever have the secret --
it can be generated from t shares; these shares are then re-shared in
a t-out-of-n fashion.
Block cipers. ECB (electronic code book) mode encrypts each block
separately, this means that identical blocks encrypt the same way. A
famous example of how weak this is is the ECB
penguin. More modes on Thursday; we quickly covered CBC mode.
Some details on DES, 56 bits for the key is not secure enough! Key schedule
take k of 56 bits and turns it into 16 round keys. Rough description of
DES and the 16 rounds and why this can encrypt and decrypt with the
same circiutry. I still need to explain how the boxes taking ki are
instantiated.
The black board pictures are here.
15 Dec 2016
Here is the exercise sheet for block 5 and 6: exercise-5.pdf
More details on DES. S-box is non-linear part and designed to avoid
differential attacks. In the exercises we saw that small changes in
the input lead to big changes in the output. Quick comment on
PRESENT
and that it uses a single S-box
and on the current standard AES.
Discussion of brute force attacks on DES. Only 2^56 trials for complete
key search. 2-DES is only marginally harder to break
than DES, taking 2^57 with a divide-and-conquer approach.
Still common use is 3-DES with k1=k3 and use k2 with decryption instead of
encryption. This needs 2^112 steps to break.
Modes of operations: CBC, OFB, CTR; the exercises mentioned issues
with CBC used in the POODLE attack; would like to achieve local
encryption and decryption and parallelization; CRT has these
features; but need large enough counter.
Pictures of black boards are here.
19 Dec 2016
Short discussion of key schedule for DES and exercises 5-7 from sheet 5.
Cryptographic hash functions need to provide preimage
resistance, second preimage resistance, and collision resistance. If
the output of the hash function has n bits then finding a collision
takes on average 2n/2 trials (use the birthday paradox to
see this) and finding a preimage or second preimage takes on average
2n trials.
Collisions are problems e.g. for signatures, because the signature is
on h(m) instead of on m.
Short summary of hash functions: MD4 is completely broken; for MD5 it's esasy to find collisions, we expect to see SHA-1 collisions any day now. SHA-256, SHA-512 and SHA-3 (and the other SHA-3 finalists) are likely to be OK.
Encryption with stream ciphers is malleable -- changing a bit in the ciphertext leads to a decryption in which the same bit is changed. Need extra checksum to achieve integrity. Also want to achieve authenticy.
Message Authentication Codes (MACs): easiest version is to use a hash function to compute cryptographic checksum. Want to have checksum on the ciphertext for easy and quick rejection of forged packets = Encrypt, then MAC. Some namedropping of HMAC, GCM, and Poly1305.
I briefly explained how RC4 works. There will be much more on this in the lecture and exercises on Thursday.
Pictures of black boards are here.
22 Dec 2016
Here is the exercise sheet for block 5 and 6: exercise-6.pdf.
The second homework is due on January 12, 2017, 13:45.
Here is the second homework sheet.
Please remember to submit your homework by encrypted, signed email
and that this time the other team member should submit. If you're in a
team of three have the third person send me some additional encrypted
email.
Pictures of black boards are here.
09 Jan 2017
Missing details of LFSRs: generating function S(x) satisfies
S(x)=F(x)/f*(x), where * gives the reciprocal, f is the
characteristic polynomial and F(x) is a polynomial of degree less than
deg(f). The characteristic polynomial is the polynomial of smallest
degree with this property. The characteristic polynomial of the sequence
{si+ti} is the lcm of the characteristic polynomials of the two sequences.
An irreducible polynomial generates a sequence with period equal to its
order.
Short summary of factorization of polyomials. Most important part: this is a fast process -- taking polynomial time. Steps are
Pictures of black boards are here.
12 Jan 2017
We spent all hours on the old exams and questions about them.
Email me if you have questions or think you have solutions to old exams
(= send me scans of your solutions and I'll send comments back).
This course was given for the first time in Q2 of 2014. Here are the exams so far
