| 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 potentiaal 9.05. There is a holiday break between Christmas and New year so that there are no lectures between Dec 19 and Jan 4. 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. My key can be found
here.
There was an exam on January 19, 13:30 - 16:30 (with a retake on
April 13, 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.
10 Nov 2014
Substitution cipher, Caesar cipher, Viginere, one-time pad,
Playfair system, Hill cipher. Some thoughts on strenghts and
cryptanalysis of these schemes.
Pictures of white boards are here.
13 Nov 2014
Here is the exercise sheet for block 5 and 6
(now with fixed exercses, sorry): exercise-1.pdf.
In the lecture part we had Benne de Weger do a show
and tell about his
Hagelin BC-38.
I showed some pages about the Enigma by Tony
sale. Lots of pages are linked from here,
including a simulator
for the Enigma. Unfortunately the page only seems to work in Internet
Explorer.
Scytale, extended Euclidean algorithm, one time pad with
bits, problems with reuse.
Pictures of black boards are here.
17 Nov 2014
Feedback shift registers and how to use them for encryption;
n-th order feedback sequence,
period, pre-period, ultimately periodic sequences, least period.
Linear feedback shift registers (LFSRs), want c0=1, can run backwards,
is periodic, max period is 2^n-1, relation to matrix multiplication,
order of matrix is divisible by least period,
characteristic polynomial of the matrix, characteristic polynomial
of the LFSR; factors of the characteristic polynomial.
Further reading can be Lidl/Niederreiter or van Tilborg.
Pictures of white boards are here.
20 Nov 2014
Here is the
exercise sheet for block 5 and 6: exercise-2.pdf.
The results are included on the blackboard pictures, it's
the only white board in the set. Note that for the Fibonacci
squence uses minus signs (check with the way we derived the
polynomial from C).
The lecture had a quick tour through finite fields, defining fields,
characteristic, irreducible polynomials, (a+b)p=ap+
bp in characteristic p, how to generate extension fields,
Fp[x]/f is a field with pn elements if f is irreducible
and of degree n; compute inversion in this field Fpn
by using XGCD with f.
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.
24 Nov 2014
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).
RC4: some history, description, example of key setup. Note the output
is S[(S[i]+S[j])] and not S[i]+S[j] as I wrote on the board.
Pictures of white boards are here.
The first homework is due on December 4, 13:30.
Here is the first homework sheet.
27 Nov 2014
Here is the exercise sheet for block 5 and 6: exercise-3.pdf.
We used some of the lecture time to present the results from the
exercises. RC4 has a strong bias towards 0 in the second byte. This is
explained in exercise two: if the third byte of the state equals 0
then the seecond byte is 0, no matter what value the other cells
have.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. The slides on more biases of RC4 that I showed are by
Daniel J. Bernstein and 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
Chacha12. 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. 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.
There was a lot of namedropping today; please check out the detailed
descriptions online and remember the big picture of what the respective
functions are used for.
Pictures of black boards are here.
01 Dec 2014
Details on DES, Feistel cipher, how to en- and decrypt,
56 bits for the key is not secure enough; confusion and
diffusion and how 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. 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.
Pictures of white boards are here.
04 Dec 2014
Here is the exercise sheet for block 5 and 6: exercise-4.pdf.
Modes of operations: CBC, OFB, CTR, mention of GCM. Want to precompute
stream and to access blocks without computing decryptions of all
preceding blocks.
Message Authentication Codes (MACs): use hash function to compute
cryptographic checksum. Want to have checksum on the ciphertext for
easy and quick rejection of forged packets; H(k||m) vs. H(m||k).
I forgot to mention that H(k||m) allows message extension attacks --
if a is a valid authenticator for message m them by the iterative
nature of cryptographic hash functions H(a||x) is a valid authenticator
for m||x. Please look up HMAC and GCM.
Pictures of black boards are here.
08 Dec 2014
Lecture given by Jens Bauch.
Concept of public-key cryptography, some recap of number theory
background (multiplicative group modulo n, Euler-phi function, Euler's
theorem), public key for RSA is (e,n), private key is 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. First
problem with schoolbook multiplication: we can recover a message that
is sent to multiple people, if they all use the same small exponent.
Jens scanned his class prep for you
instead of pictures.
11 Dec 2014
Here is the exercise sheet for block 5 and 6: exercise-5.pdf.
More issues with schoolbook RSA: can decrypt linearly related
messages; RSA is homomorphic; security notions, schoolbook RSA is not
CCA-II secure; RSA OAEP.
Jens scanned his class prep for you
instead of pictures.
The second homework is due on December 23, 12:00. Here is the first homework sheet.
Additional comments: I've tweaked the description of 1 and 1b to make
things clearer of what is and what is not possible and included a part
with concrete numbers. Please state in detail one XGCD computation in
2 and the XGCD computation in 3.
15 Dec 2014
RSA-OAEP and why it protects against attacks using the homomorphic
properties of RSA; n has at least 1024 bits, so no shortage of space
for message, randomness, and padding. Use of RSA in TLS (example of
DigID ciphersuite). Security relies on strength of the used encryption
systems and on the security of the certificate (cryptographic strength
and operational security).
Diffie-Hellman key exchange, use in TLS, example of google.com for use
of DH for encryption, ephemeral vs. static DH, ephemeral can mean
time-based or mean connection-based, two bad choices for g and the
operation; a good choice is to use the intergers modulo a large prime.
Pictures of white boards are here.
18 Dec 2014
Here is the exercise sheet for block 5 and 6: exercise-6.pdf.
Some hints on exams; there will be a test exam ready by Jan 5. For
now you can try the old exams for the masters course Crypto I
but note that those students know more tools and can use books during
the exam.
Computational and Decisional Diffie-Hellman problem (CDHP/DDHP),
Discrete Logarithm problem, relations between these problems.
ElGamal encryption, DSA signatures (as example of ElGamal signatures)
and why these systems work, typical sizes for primes and group orders,
Baby-Step Giant-Step algorithm, any system based on DLP has at most
squareroot of the group oder hardness of the DLP. Problems with
ElGamal encryption -- e.g. (r*g, c*H
Pictures of black boards are here.
05 Jan 2015
Repetition of some background on DLP
systems. 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.
Undeinable signatures and disavowal protocol based on Chaum and
van Antwerp, with example.
Pictures of white boards are here.
08 Jan 2015
Lecture given by Jens Bauch.
For the exercise part please do exercise-6 from last week or work
on the test exam.
Repetition of finite fields and whatever the students want more
explanations on. This is the last lecture.
12 and 15 Jan 2015
No lectures.
This course was given for the first time in Q2 of 2014. Here are the exams so far
