Cryptography

Duration

Four Weeks

Lecturer

David Kohel (University of Sydney)

Assessment

80% Final exam (Friday 9 Feb 14–16h in Carslaw Room 351), 20% assignments.

Consultation Hours:

Thursdays 14–15h Carslaw Room 625.

Assumed Knowledge

We will assume a basic background of abstract algebra: (primarily abelian) groups, rings, and fields. Students with some background on elementary number theory, or modular arithmetic (the ring Z/NZ) should be able to pick up the relevant concepts along the way.

Background Material

Any standard textbook on abstract algebra (e.g. Fraleigh’s ”A first course in abstract algebra”, Herstein’s ”Abstract algebra”, or chapter one of Lidl and Niederreiter’s ”Finite Fields”) would be useful, but relevant material will be summarised with appendices to the lectures notes. The popular book ”The Codebook” by Simon Singh is recommended as entertaining background reading on the subject.

Resources

Lecture notes and other resources are posted at http://echidna.maths.usyd.edu.au/~kohel/tch/Crypto/.

Course Outline

We begin with an overview of cryptography, including the fundamental concepts of encryption, material on classical ciphers and their cryptanalysis, and distinction between symmetric key and asymmetric (or public) key cryptography. Material on symmetric key cryptography will cover standard block cipher constructions, together with their modes of use, followed by stream ciphers. For the subject of public key cryptography, we recall the construction of the quotient rings Z/NZ and introduce finite fields of any prime power. The main cryptosystems RSA and ElGamal will be introduced, together with the main algorithms for their construction (finding large primality and proving primality) and their cryptanalysis (factoring and discrete logarithm algorithms). We conclude with more “exotic” generalisations of ElGamal cryptosystems to groups of elliptic curves.

Throughout we emphasize an algorithmic approach, and demonstrate the principles with computer experiments and exercises. This will allow us to provide nontrivial examples and discuss algorithmic approaches to construction of large prime numbers, factorization, and ”discrete logarithms”.