| 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 multimedia paviljoen zaal 1 and Thursdays 13:45 - 17:30 in flux 1.12. There is a holiday break between Christmas and New year so that there are no lectures between Dec 18 and Jan 3.
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. My key can be found
here.
There will be an exam on January 18, 13:30 - 16:30 (with a retake on
April 11, 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 classnotes.
Here is a test exam. Note that the CRT exercise would have somewhat smaller keys for the exam.
09 Nov 2015
Substitution cipher, Caesar cipher, Viginere, one-time pad,
Playfair system, Hill cipher. Some statements about the number
of possible keys for these schemes..
Pictures of white boards are here.
12 Nov 2015
Here is the exercise sheet for block 5 and 6: exercise-1.pdf. See also the raw data if paste fails.
I wanted to show an Enigma animation but it doesn't work in the browsers I tried. Please check whether http://www.codesandciphers.org.uk/enigma/emachines/enigmacn.htm works for you. It should show exactly the enigma and not a long page with lots of individual pictures. If it works, try clicking on things.
In last year's lecture part we had Benne de Weger do a show
and tell about his
Hagelin BC-38. He has it in his office; maybe we can manage
a viewing at some point.
In the lecture we covered the extended Euclidean algorithm for computing
modular inversion and did part of exercise 6b.
Other systems we covered: scytale, column transposition cipher, the
one-time pad with bits, and problems with reuse. Try the 4th challenge
in the old Mystery Twister to see the reusse problems.
Pictures of black boards are here.
16 Nov 2015
Feedback shift registers and how to use them for encryption;
n-th order feedback sequence,
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 white boards are here.
19 Nov 2015
Here is the
exercise sheet for block 5 and 6: exercise-2.pdf.
The results for the first round of exercises
are included on the blackboard pictures.
If you do the second one, note that for the Fibonacci
squence you need to use minus signs to get the characteristic polynomial.
(check with the way we derived the
polynomial from C).
Irreducible polynomials,
order of matrix is divisible by period, characteristic polynomial
of the LFSR; factors of the characteristic polynomial.
Further reading on finite fields in Lidl/Niederreiter or van Tilborg.
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 divides 2n-1.
Pictures of black boards are here.
23 Nov 2015
I was late, thanks to NS having a defect train and no plan of how long
it would take (or rather, optimistic ideas ...)
Proof that for irreducible characteristic polynomials the order of the polynomial equals the maximum least period. The proof uses generating functions and along the way we showed that if f and g are the characteristic polynomials of (si) and (ti) then (si)+(ti) has characteristic polynomial lcm(f,g).
I did not get around to giving details about RC4. Please read up on it.
I would have covered what is stated on the Wikipedia page under
Description;
we will cover the (in)security on Thursday.
(And next time tell me when we still have 13 min and the clock is off).
Pictures of white boards are here.
26 Nov 2015
Here is the exercise sheet for block 5 and 6: exercise-3.pdf.
The first homework is due on December 3, 13:30. Here is the first homework sheet. Please remember to use PGP.
Results from the eexercises:
Pictures of black boards are here.
30 Nov 2015
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.
Details on DES, 56 bits for the key is not secure enough! Three
levels of details on DES, general Feistel cipher, how to en- and
decrypt. Concepts of confusion and diffusion, The epansion and S-box
design of DES achieves these. 2-DES only marginally harder to break
than DES; use 3-DES with k1=k3 and use k2 with decryption instead of
encryption. Some discussion on brute force attacks on DES, and
meet-in-the middle attacks.
Pictures of white boards are here.
03 Dec 2015
Here is the exercise sheet for block 5 and 6: exercise-4.pdf.
Quick namedropping of AES and Present
Modes of operations: CBC, OFB, CTR; the exercises mentioned issues
with CBC used in the POODLE attack; would like to achieve local
encryption & decryption and parallelization; CRT has these
features; but need large enough counter.
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. A
message from B authenticated with a MAC can convince A but not C
that it really originated from B.
Please look up HMAC, GCM, and Poly1305.
There are several possible issues depending on how the hash function H
is designed. Many hash functions work in rounds using a compression
function which takes in blocks of the input in a way that means that
if H(m) and H(m') collide then H(m|x) and H(m'|x) collide for any x,
e.g. if H(m1|m2|m3)=H(H(m1|m2)|m3).
If E can find another ciphertext c' which collides with c and such
a hash function is used then E can use B's valid tag H(c|k) as a
tag for H(c'|k) even though she doesn't know k. If the unknown k
comes first then H(k) and H(k) trivially collide but put the hash
function in an unknown inital state, so havin a collision on H does
not break the system.
At the same time, for such a hash function the authenticator a=H(k||c)
can be used to compute a'=H(a|x) which is is a valid authenticator
for c||x.
Pictures of black boards are here.
07 Dec 2015
Concept of public-key cryptography, some recap of number theory
background (multiplicative group modulo n, Euler-phi function, Lagrange's
theorem), 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.
Exponentiation by square and multiply and how many operations this
takes, examples; can choose small e but d must be large/random.
Pictures of black boards are here.
10 Dec 2015
Note: no lectures on Dec 10. Please solve the exercises from
exercise-5.pdf and watch two of the
videos from PSC (once
they are onlie).
14 Dec 2015
Lecture given by Henry de Valence.
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; security notions, schoolbook RSA is not CCA-II secure; RSA OAEP.
Henry was so nice to make the photos available
online.
17 Dec 2015
Here is the exercise sheet for block 5 and 6: exercise-6.pdf.
Diffie-Hellman key exchange, CDHP, DDHP, DLP, relations between
these problems. Problem with active man-in-the-middle attacks,
authenticated DH via signatures or triple-DH, semi-static DH,
emphemeral DH (ephemeral can mean time-based or mean
connection-based), a good choice is to use the intergers modulo a
large prime or elliptic curve crypto (not covered in this class).
ElGamal encryption, encryption is homomorphic, DSA signatures (as
example of ElGamal signatures) and why these systems work. DSA is
completely broken if a nonce becomes public or is reused.
Baby-Step Giant-Step algorithm: any system based on DLP has at most
squareroot of the group oder hardness of the DLP.
Pictures of black boards are here.
The second homework is due on Januar 07, 2016 at 13:30. 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.
04 Jan 2016
Lecutre given by Gustavo Banegas.
Repetition of some background on DLP systems and the BSGS algorithm.
Not that taking m as floor or ceiling of the square-root of the group
order both work.
Needham-Schroeder authentication protocol and why it doesn't actually
prove 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. 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.
Factorization algorithms: Fermat factorization, p-1 method.
Gustavo was so nce to take pictures of the white boards here.
07 Jan 2016
This session (blocks 5-8) will be given jointly by Gustavo and Henry as a
'ask-me-anything session'. Please prepare questions and try to
solve the practice exam during this time or try the rest of the
exercises from sheet 6.
This is the last lecture, see you all on Jan 18!
11 and 14 Jan 2016
No lectures. Please watch YouTube video
and take a look at ECCHacks webpage
and slides
to learn a bit about elliptic curves. This will not be part of the test but
is good for you.
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
