Week 1
We covered Chapter 1 of Stinson and the Cryptosystems note up to and including section 3.
Week 2
We covered first part of Stinson's chapter 2, on perfect security and Shannon's definition
of entropy and its properties. Next week, we finish Chapter 2
Exercises
2.4 (presented by group 1)
This one looks simple, but can be a bit tricky. Let p() be the probability distribution for which
perfect security is guaranteed, i.e., you know that p(y) = p(y|x) for any x,y.
Now let p'() be probabilities that you get if you change the plaintext distribution. Of course,
the choice of keys and the encryption function are not changed. Your goal is now to show that
p'(y) = p'(y|x). Hint: show that p'(y|x) = p(y|x] and that p'(y) = p(y).
2.14 (presented by group 2)
Hint: Theorem 2.10 is useful.
The hand-in exercise (Presented by group 3)
Suppose you get to play the following variant of the bonus round in the TV show
Wheel of Fortune (Lykkehjulet): you are shown N cards, each of which cover one letter.
Each letter has been independently chosen from the same distribution, and you are given
the distribution (p0, p1,..., p25). You get to choose one letter from the alphabet, say you choose
letter i. Now every position in the hidden string where letter i occurs (if any) are uncovered.
Your goal is to learn (on average) as much information as possible on the hidden string.
(Of course this is a very crude model of Wheel of Fortune since we only consider single letter
frequencies, but we want something that is feasible to analyze)
In the real-version of the game, people tend to choose the most frequent letter as their guesses. Let's
try to see what information theory has to say about this. Suppose we adopt the convention that Shannon
used when defining Entropy: if you know that some event occurs with probability p, and you learn that
this event did indeed occur, you have learnt log(1/p) bits of information.
Now, if your guess is letter nr. i, how many bits of information will you learn on average from
playing the game (as a function of pi and N)? Hint: note that for every position in the hidden
string you learn either that letter i occurred here, or that it did not occur.
What strategy does your result suggest for choosing your guess, given frequencies p0,..,p25
as in English? based on this, does it make sense that players in real life choose the most frequent
letter(s)? Would this be a good strategy no matter what the frequencies were?
Week 3
This week, we finish Stinson Chapter 2, and we also look at some background material from the
paper by Wolf on the web page. Next week we start with symmetric cryptosystems, using
Stinson chapter 3 and the Cryptosystems note.
Exercises
2.10 (presented by group 4)
To hand in: 2.12 (presented by group 5)
- you are free to choose to solve this one using the diagrams from the lectures, or the formulas.
2.15 (presented by group 6)
- you can use Thm 2.11 (or rather, the estimate following it), even though it actually only
gives a bound on the unicity distance.
Week 4
This week, we look at block ciphers and security definition for deterministic encryption,
also known as pseudorandom functions. If there is time we also include probabilistic systems, if not
that will have to wait until next week. We will use Stinson 3.1, 3.2, 3.5 and the cryptosystems note
section 4.
Exercises
3.2 (presented by group 7)
- note that a Feistel cipher is any cipher with the same high-level structure as DES, i.e., it works
as i Figure 3.6, and with no switch of block halves after the last round.
To hand in: 3.3 (presented by group 8)
- optional extra challenge: given a chosen plaintext attack, show that you can use the complementation
property to do exhaustive key search in about half the time it would normally take.
3.4 (presented by group 9)
- you should be a bit critical about the algorithm Stinson suggests in (b) and (c). I don't see
why you need to store two lists, one seems to be enough.
Week 5
This week, we will look at AES, Stinson chapter 3.6, and modes of operation 3.7.
We also cover security of these modes, CBC in particular, the cryptoystems note sec. 5.
Monday, I plan to do a short overview of Differential and Linear Cryptanalysis, hence not
so many exercises for Monday.
Exercises
Are all from the revised version of the Cryptosystems note (sec.5.3 with exercises
has been added).
To hand in: Exercise 1 (presented by group 10)
Exercise 2 (presented by group 11)
Exercise 3 is the challenge of the week - more about this at the lectures.
Week 6
This week, we start on public-key cryptography, using Chapter 5 in Stinson and Section 6 from
the Cryptosystems note.
Exercises
are all from Stinson chapter 5
5.7, presented by Group 1
To hand in: 5.10, presented by Group 2
5.13, presented by Group 3
There is no challenge of the week this week, but there will be next week..
Warning about the hand-in exercise: we prove in the lectures that RSA decryption
works, but only for input x in Zn*. Be careful that you correctly identify the x-vaules for which
this proof does not hold and argue that the result is still good for these x's.
Week 7
This week, we will cover generation of random primes and primality testing, (Stinson 5.4, 5.4.3)
and also definitions for security of 1-way trapdoor permutations and semantically secure public-key cryptosystems, section 6 from the cryptosystems note. If there is time, we also look at security of
single bits in RSA plaintexts, Stinson 5.9.
Exercises
5.16 (presented by group 4)
5.17 (presented by group 5)
To hand-in, the exercise below (presented by group 6)
Are there particular RSA ciphertexts that are "weak", that is, ciphertexts that the
adversary can very easily decrypt? There are certainly some, just think of the ciphertext 0.
But in this exercise, we will show that if RSA is any good at all, there cannot be *large*
sets of weak ciphertexts.
Let A be an algorithm that gets as input an RSA public key (n,e) and a ciphertext y. A
will either return the correct plaintext x, or will return "no answer". Suppose A is able
to decrypt if and and only if y is in some subset S of Zn*. Assume also that the size of
S is epsilon times (p-1)(q-1), for 0< epsilon <1.
Your task: construct a probabilistic algorithm B that uses A as a subrutine. B gets input
public key (n,e) and ciphertext z, where z can be any number in Zn. The demand to B is
that for ANY fixed z, B returns the correct plaintext for z with probability at least epsilon.
Hint: first show that if z is not in Zn*, you can decrypt it easily without using A, by
first computing the secret key. If z is in Zn*, you do need to use A. You will also need
to use the multiplicative property of RSA stated in Stinson exercise 5.14. Note that you cannot
just run A on input (n,e) and z. If z is not in S, A will always return "no answer" so then
your success probability is 0 and not epsilon as required.
[this is one of those exercise where you are stuck if you don't get the right idea, so
don't hesitate to come and ask me if you are in trouble..]
Week 8
Monday, we breifly looked at factoring algorithm. Thursday, we will look at why and how
to achieve chosen ciphertext security for public key cryptosystems, using the the last part
of the cryptosystems note, and we will then continue with public-key crypto based on the
discrete logarithm problem, using the note on this from the web page.
Exercises
To hand in:
Exercise 4 from the revised version of the Cryptosystems note (p.22),
presented by Group 7
and this one, presented by Group 8
Consider Cryptosystem 5.3 (p. 220) in Stinson. Prove that this system is not
CCA-secure. The function G, referred to as a random oracle, you can just assume is
any function from k bit to m bit strings. Optional: can you think of a way to modify
the system that might make it be CCA secure - or at least would seem to prevent the
attack you just found?
Week 9
This week, we cover most the rest of the note on discrete log based cryptosystems.
Exercises - are from the note on discrete log cryptosystems
To hand in: Exercise 1 presented by group 9
Exercise 2 presented by group 10
Week 10
This week, we start on Authentication using the note on this on the web page (recently revised), the section
on hash functions and in addition Sec. 4.3 from Stinson.
Exercises
to hand in: Stinson 4.9, presented by group 11
Stinson 4.10, presented by group 1
Exercise 1 from the authentication note, presented by group 2
Week 11
This week, we cover Message Authentication Codes and Public Key signatures, using
Sections 3,4, and 5 in the note on Authentication and section 7.3 in Stinson.
Exercises
To hand in: Exercise 2, p.12 in the Authentication note, presented by group 3
7.3 (a) presented by group 4.
Week 12
This week, we cover the last part of the authentication note, combination of hash function
and signatures, and existence of secure signature schemes. This is the last week with lectures,
next week is reserved for project work, and there are no classes.