Lectures

Note: Section numbers in bold, written as §2.3, refer to the textbook unless otherwise noted. Likewise, N5 refers to page 5 of my number theory notes.

First, a quick overview of a few block cipher modes (slides). Next, I went through the exam problems from December 2009 (slides – in the newer version that I had intended to use).

An attempt to describe a wide overview of the whole course contents, focusing on cryptographic applications and building blocks and not so much on detail.

(This summary is a work in progress. The references are particularly incomplete for now.)

Example references to the book: Ch 2 and §2.3.
Example reference to the number theory notes: N6–7 for pages 6–7.
Example reference to the notes on symmetric cryptosystems: S.

– in chronological order

In this lecture, I got to talk about cryptography in general. (The word is derived from Greek κρυπτός, which means “hidden” or “secret”, I am told.) Some people take cryptography to mean the practice of using cryptographic techniques to protect secrets (and the many other uses that cryptography can be put to), while cryptanalysis refers to the attempted breaking of cryptosystems. And then cryptology refers to all of the above. Other people use the word cryptography to mean all of the above, however.

Anyhow, I tried to convey a big picture of the field, roughly split into classical cryptosystems, symmetric cryptosystems (in which the parties share a secret key) and asymmetric cryptosystems (also known as public-key systems). We will have much more to say about this in the future.

To kick off the discussion of classical cryptosystems, I discussed the Caesar cipher (§2.1) and how to break it. Hint: It's very easy. But a certain statistical method, though hardly worth the effort since a brute-force attack is so trivial, still illuminates the power of statistical techniques – in this case, based on letter frequencies.

I ended with a brief discussion of the rearrangement inequality, but messed up the proof a bit. I'll redo that much better on Thursday.

Finished my analysis of the Caesar cipher (and the rearrangement inequality, with slides), and then we look at the Vigenère cipher (§2.3). There are some extended notes including a Lisp program I wrote to break the Caesar and Vigenère ciphers, and showing its output.

Afterwards, we looked at the one-time pad (§2.9).

Number theory: We need to do a bit of number theory next. I follow my own notes on number theory for this, but of course there is a great deal of overlap with Ch. 2 of the textbook.

I covered the basics of modular arithmetic quite carefully, and in more details than the notes. In the notes, I got as far as Bézout's lemma (Lemma 1), but I did not quite finish the proof.

We continue with the notes: Inverses in modular arithmetic, primes and unique factorization, Euclid's algorithm. Perhaps there is time to get into modular exponentiation, too.

The Hill cipher, cryptanalysis. The Hill cipher is vulnerable to a known plaintext attack, and even more so to a chosen plaintext attack. (I also discussed the general notions of known ciphertext, known plaintext, chosen plaintext, chosen ciphertext attacks. Also a brief discussion of the notions of diffusion and confusion in a cipher.

In the end, a return to number theory, with a brief explanation of the computing of powers in modular arithmetic.

I started out saying a bit about periods in the exponential map \(x\mapsto a^x\bmod n\), then stated Fermat's little theorem without proof. Proceeded with brief introductions to Diffie–Hellman key exchange and the ElGamal cryptosystem, and noted that if you can break one, you can break the other. Ended with a quick look at the Chinese Remainder Theorem (CRT), with an almost complete proof.

Fermat's little theorem (FLT) and Euler's φ function, followed by an introduction to the RSA cryptosystem.

We will now put the number theory and related cryptographic aspects aside for a while and look at symmetric cryptosystems, including block ciphers such as AES. I started with a look at Feistel ciphers and DES, and then continued with a look at block cipher modes: ECB, CBC, CFB, and OFB. For the latter two, I followed the variants from Wikipedia, which are somewhat simpler than the variants given in the book, but still gets the main idea across. I used illustrations from the Wikipedia articles referenced.

More on symmetric cryptography, following Kristian Gjøsteen's note (also linked from the main page). We have already covered much of the material of that note, but it seems useful to repeat some of it in a systematic manner. The primary new material is hash functions and message authentication codes (MACs). I also covered SHA-1 (section 8.3 of the book) in moderate detail (slides).

A bit more on HMAC and other MACs, plus birthday attacks. I ended with a look at the famous padding oracle attack, showing the danger of leaking information.

A look at AES (slides). Then return to number theory: Primality testing (Fermat, Miller–Rabin).

There was no lecture on 29 September.

Safe primes, Sophie Germain primes and generators; Pocklington's theorem. Quadratic residues.

More quadratic residues, and factorization using the Fermat method.

Factoring: Quadratic sieve and Pollard's ρ.

The discrete log problem. The Pohlig–Hellman algorithm. Briefly on the Pedersen commitment scheme.

More on Pedersen commitment, as there was insufficient time last week. The discrete logarithm problem continued: The index calculus. (There was no time for coin tossing by telephone with quadratic residues. We'll return to that.)

Digital signatures (Ch 9). Slides.

Secret sharing (§12.1–12.2)

I walked through the Secure Remote Password protocol (SRP) and discussed its features and security (slides). See also the SRP homepage. See in particular the publications list on the site. My lecture was largely based on the two papers listed there.

Much summarizing, mainly of number theory, but also including some of the classical cryptosystem. I also covered the baby step – giant step algorithm (§7.2.2), which I had inadvertently skipped earlier.

No lecture today, activities in the computer lab instead. See the Exercises page.

More summaries …