CS402 Cryptography (2017-18)

Lecturer: Graham Ellis

Module Description:

This is an introduction to cryptography suitable for students who have taken at least one module in linear algebra and who are willing to play with a computer. The module aims to cover enough of the textbook Cryptography, An Introduction (Third Edition) by Nigel Smart to provide students with the mathematical basis, and hopefully the motivation, to continue studying the book on their own. Material from the textbook is supplemented by Python programming problems, though no previous experience of programming is required, as a couple of lectures are devoted to the relevant elementary Python programming techniques.

In preparation for the module students should:
        # File: Hello.py
        print "Hello World!"

        and that you know how to run this file in Python. See here for details on how to do this.

Module coordinates:

Lectures take place
There are no tutorials scheduled since some lectures will take the form of tutorials.

Module Assessment:

There will be an end of semester 2-hour exam worth 70%, and there will be three homeworks each worth 10%.

The end of semester exam will be based on THIS WORK SHEET. You should be able to figure out how to answer the work sheet questions from the lectures (slides of which are given below). The exam template is available here.

The online homeworks are available here.

Some Python material:

Some Python code relevant to this module can be found here.


My lecturing technique will be very old-fashioned: I'll write out everything on acetate projector sheets, and after the lecture I'll place a photocopy of the sheets below. Some student feedback on the module can be found here.

Lecture summary
Introduced the Ceaser Cipher used by Julius Caser, the Enigma cipher used by the Germans in World War II, and the secure key two factor authentication used by HSBC online banking. Explained the general model for cryptosystems and Kerckhoff's Principle: "the enemy knows everything about the system, except for the choice of enciphering/deciphering key"
Explained that a cryptosystem consists of five components: 1) an alphabet, 2) an enciphering function, 3) a deciphering function, 4) an enciphering key, 5) a deciphering key. By Kerckhoff's Principle we assume that the adversary knows everything about (1), (2) and (3). In symmetric cryptosystems a knowledge of the enciphering key is, by definition, essentially equivalent to a knowledge of the deciphering key and so in such systems we assume that (4) and (5) are known only to the intended users. In public key cryptography a knowledge of the enciphering key does not yield a knowledge of the deciphering key; in such systems (4) is public knowledge and only (5) is kep secret. Talked more about the Caeser Cipher, HSBC secure key and Enigma Cipher. Introduced the affine cipher. Explained how to use the affine cipher in the Python file cs402.py .
Explained that an affine cipher system on single letter message units is insecure because its enciphering key space is too small. Gave a Python demonstration to show how to break such a cipher using this ciphertext. Then considered a permutation cipher on single letter message units. It has an enormous key space, but even so it is insecure because frequency analysis can be used to break it. Gave a Python demonstration to show how to break such as cipher using this ciphertext.. Ended up talking about the Vigenère Cipher.
Gave a computer tutorial on how to use Python.
Demonstrated on the computer how frequency analysis can be used to easily crack the Vigenère cipher. Described the Hill Cipher. Described the Affine Cipher on blocks of length d and showed how to use the implementation of this in the file cs402.py .
Explained the terms "computationally secure cryptosystem" and "perfectly secure cryptosystem". Gave a theorem of Shannon for establishing that certain cryptosystems are perfectly secure. Ended with a simple (and impractical) example of a perfectly secure cryptosystem.
Recalled the definition of a block cipher. Then I introduced the idea of a stream cipher. Ended with the notion of an L-bit linear feedback shift register (LFSR), its representation as a connection polynomial, and how it is used to generate an infinite (pseudo-random?) binary sequence. I gave a computer demonstration of how to convert between a sequence of decimal integers and a sequence of L-bit binary integers. Also demonstrated a Python function LFSR(K,S) which inputes a list K of the positions of the non-zero coefficients in the connection polynomial, and a list S of L-bit binary integers; it outputs a list of L-bit binary integers.
Went through a detailed example in which I calculated the transition graph of a 3-bit LFSR. Discussed the problem of periodicity in a pseudo-random sequence generated by an L-bit LFSR. I observed that at best the sequence will be periodic of period 2L-1, but the period could be much worse than this if a poor connection polynomial is chosen. I kept going on about the primitive element that generates the multiplicative group of a finite field -- just to let those students who chose not to take the finite fields module realize that that was a poor choice on their part!.
Defined the notion of an L-bit linear feedback shift register whose connection polynomial is primitive. Stated (without proof) the theorem: for each L> 0 there exists an L-bit LFSR with primitive connection polynomial. Gave a computer demonstration which showed that for the 4-bit LFSR with connection polynomial C(X)=1+X+X3, this polynomial C(X) is not primitive. In this example the associated pseudo-random binary sequences are not necessarily purely periodic, though they are of course eventually periodic. Explained that from 2L terms of a pseudo-random sequence produced from an LSFR on can probably quickly compute the connection polynomial of the LFSR. Thus such a sequence would not be a good enciphering key for a stream cipher. Ended up with an explanation of how one can combine, in a non-linear fashion, several LFSRs.
Began with the notion of an information theoretically secure binary function. Then talked about "clocking shift registers". Ended with a description of the A5/1 stream cipher which is used to provide over-the-air communication privacy in the GSM cellular telephone standard.
Watched a video on the history of cryptography.
Introduced the notion of public key cryptography and explained the mechanics of the RSA public key cipher.
Lecture cancelled due to red weather alert.
Lecture cancelled due to red weather alert. This weather problem meant that this year I'll have to skip talking about Feistel Ciphers and DES.
Started with a computer demonstration explaining how to encode/decode using the RSA implementation in the cs402.py file. Also explained how to choose random 100-digit primes in Python. Then recalled/introduced the notion of a group, a subgroup, a coset. Ended with a statement and proof of Lagrange's Theorem: If H is a subgroup of a finite group G then the order |G| is a multiple of the order |H|.
Used Lagrange's Theorem to prove Euler's Totient Theorem, and used the latter to prove:

If N=pq is a product of distinct primes, and if a is in the range 1,2,...,N with gcd(a,N)=1, and if d = e-1 mod (p-1)(q-1) then (ae)d = 1 mod N.

Then discussed the Prime Number Theorem and how it underlies the basic strategy for finding randon prime numbers: choose a random integer m and while m is not prime set m=m+1; output m. This strategy requires an efficient method for testing if an integers is prime. Ended with a discussion of trial division as a method.
Defined a pseudo-prime to the base b and a Carmichael number. Noted that Fermat's Little Theorem is a special case of Euler's Totient Theorem. Described the Fermat test for an integer: a composite non-Carmichael number n passes k applications of the test with probability < (1/2)k. Mentioned that Carmichael numbers are very rare, though Pomerance et al. proved in 1992 that there are infinitely many such numbers.
Started with an algorithm for modular exponentiation. Then talked about: the discrete logarithm problem (DLP); the Diffie-Hellman problem (DHP); the Diffie-Hellman key exchange procedure; the man in the middle attack; digital signatures.
Introduced the abelian group associated to an elliptic curve. Mentioned the NSA Suite B list of elliptic curve cryptography algorithms.
Described Lenstra's elliptic curve algorithm for finding a factor d of a large integer N. Then described Pollard's rho algorithm for finding a factor d of a large integer N.