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”.
