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

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

- 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 Tilburg "Fundamentals of Cryptology" Kluwer academic Publishers, Boston, 2000.

For encrypting your homeworks you should use GPG/PGP. If you're running linux then GnuPG is easy to install. If you're using windows I recommend using GPG4win; if you're using MAC-OS you can use GPG Suite. I'm OK with having only the attachment encrypted, but for proper encryption of your email you might want to look into Enigmail which works well with Thunderbird.

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 2^{n}-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
(s_{i}) and (t_{i}) then
(s_{i})+(t_{i}) 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 j_{i}, not j_{l}

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 2^{n/2} trials (use the birthday paradox to
see this) and finding a preimage or second preimage takes on average
2^{n} 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.

RC4 has a strong bias towards 0 in the second byte. We saw this experimentally and also gave the explanation. The first byte has a strong bias towards the first key byte unless the first key byte it zero. RC4 does not provide for refreshing the key stream, so one needs to remember the last values for j and i. WEP needs a place to put some per connection data and uses key bits for that, so we get the known biases plus known key bits plus known plaintext/ciphertext pairs. Aircrack uses these to break WEP encryption.

I mentioned slides on more biases of RC4 by Daniel J. Bernstein. They are available here.

History of stream cipher development; check out the cell phone ciphers A5/1 and A5/2. For good choices check out Salsa20, Trivium, and Chacha20.

Comparision of properties of MACs vs. signatures. The most important part is to whom A can prove that the message is from B -- to anybody for signatures and just to herself for MACs. Sometimes the latter is a desired property, see e.g. OTR.

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

- square-free factorization
- distinct-degree factorization
- equal-degree factorization, e.g. Cantor-Zassenhaus' algorithm

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