Number Theory and Cryptology - Fall 2009

Pictures and slides Announcements Literature Course

Tanja Lange
Coding Theory and Cryptology
Eindhoven Institute for the Protection of Information
Department of Mathematics and Computer Science
Room HG 9.92
Technische Universiteit Eindhoven
P.O. Box 513
5600 MB Eindhoven

Phone: +31 (0) 40 247 4764
Fax.: +31 (0)40 243 5810

The easiest ways to reach me where ever I am:

This is an overview of the topics taught in the master math course Number Theory and Cryptology. Details are filled in as time permits. The official home page is here.
The course takes place Fridays at the University of Utrecht in Minnaertbuilding, room 208 (except in week 39, if applicable the room will be announced asap).
The semester consists of 14 weeks of lectures, the dates are Sep 11, Sep 18, Sep 25, Oct 02, Oct 09, Oct 16, Oct 23, Oct 30, Nov 06, Nov 13, Nov 20, Nov 27 (in room BBL471), Dec 04, and Dec 11. No lectures on Dec 18.

Number theory is a classical discipline in mathematics and has been studied already in ancient times. It is the study of relations among the integers. Cryptography is the art of secretly transmitting information and is as such as old as people trying to hide their secrets. In recent years cryptography has changed a lot -- away from a science that was mostly related to military and secret service to an omnipresent enabler of online banking, eCommerce, and secure email to mention just a few.
Cryptography is an exciting and motivating topic with a touch of a spy novel and thus a great background for math projects. A solid background in number theory is essential to understand the cryptography deployed e.g. in Internet browsers. Even though your future pupils will not be expected to build their own crypto algorithm they should be able to understand the framework in which they are operating, not the least to make valid decisions which services to trust. While this course cannot cover all topics of security it will give a solid background of the mathematics involved and show several examples, some of which have been tried in classes at school.
We will loosely follow Koblitz' "A Course in Elementary Number Theory and Cryptography". It is though not necessary to purchase the book to follow the course; relevant material will be presented at the blackboard.
Here is the rough schedule of the course:
We will review fundamental results such as the Euclidean Algorithm and the Chinese Remainder theorem and study algorithmic versions thereof together with an analysis of the runtime.
From modular arithmetic we can understand the RSA cryptosystem and the original version of Diffie-Hellman key exchange. The integers modulo a prime p form the simplest case of a finite field. Finite fields are an important building block of cryptography, in particular of public key cryptography. We consider general finite fields and study their use in elliptic curve cryptography.
We end the semester with a study of factorization algorithms and - if time permits - an overview of less standard public key cryptography.


On November 27 the course has to move to BBL471!
Final projects are due January 29, 2010. If you want feedback on a preliminary version, you need to submit this before January 11, 2010.
I have received preliminary versions but I am slow in giving feedback due to other responsibilities. The deadline for the final version is thus extended till February 15, 2010.

Attention: My teaching in Eindhoven ends at 12:30, depending on the trains I might arrive slightly past 14:00. In the first meeting we decided that classes will not start before September 11.


It is not necessary to purchase any of the books to follow the course.


Criterion is active participation in the course and exercise sessions and a final project. The final project can be done in groups of 2 people.
Deadline for the final projects is Jaunary 29, 2010.

Class notes

11 Sep 2009
General introduction to cryptography; concepts public key and symmetric key cryptography, brief excursion into Diffie-Hellman key exchange. As an example of public key cryptography we attacked the "Perfect Code Public Key System" by Fellows and Koblitz. Attention, this was never proposed for cryptography but only as a teaching tool.
Here are the slides in ps and in pdf for the perfect code system. I took pictures of all black boards before erasing them. They are here.

18 Sep 2009
Summary of background material on groups, rings and fields. Pictures of the black boards are here.
At the end of class I failed to give the proof of Lemma 1.12. I fixed that after you all left & took a final picture (imgp1694.jpg) with the correct proof.

25 Sep 2009
Lecture given by Peter Birkner.
Summary of background material on vector spaces. Elementary number theory: modular reduction, extended Euclidean algorithm, kid-RSA. Pictures of all black boards are here.
Peter kindly made his notes available: p1, p2, p3, p4, p5, p6, p7. Here are the slides for the Kid-RSA system; another example from the Fellow-Koblitz paper.

02 Oct 2009
Euler phi-function, multiplicative group of integers mod n, group orders and how to find generators in cyclic groups, RSA encryption and signatures, weaknesses of school book version of RSA, Chinese remainder theorem (start). Pictures of the black boards are here.

09 Oct 2009
Chinese remainder theorem (proof, details on use, algorithmic version, how to handle non-co-prime moduli, proof of Euler-phi function. Start of finite fields section. Pictures of the blackboards are here.

16 Oct 2009
Discussion about possible project topics; an initial list with some topics already taken is here. Please contact me by email to discuss further details.
Finite Fields, subfields as vector spaces, number of elements in a finite field must be pn for some prime p and some positive integer n; additive and multiplicative structure of finite fields, primitive elements. Pictures of all blackboards are here.

23 Oct 2009
Original Diffie-Hellman key exchange, Pohlig-Hellman attack, polynomials, roots, gcd(f,f')=1 means no multiple roots in f.
For the computations we used the computer algebra system PARI/GP which is freely available. Note that Mod(a,b) gives an element in Z/b congruent to a.
Pictures of most blackboards are here. I erased one black board too quickly; the missing part is on this picture.
Please contact me about projects!

30 Oct 2009
Lecture given by Michael Naehrig.
Construction of finite fields via polynomials, minimal polynomial, splitting field, existence and uniqueness of finite fields.
Pictures of all blackboards are here.

06 Nov 2009
Lecture given by Michael Naehrig.
Constuction of finte fields via irreducible polynomials; splitting of xq-x; number of irreducible polynomials. Generic attacks against the DLP: Baby-step giant-step attacks.
Pictures of all blackboards are here.

13 Nov 2009
Continuation of BSGS, Pollard's rho method, index calculus attacks. Detailed example of index calculus attack in F4007, solved using Pari GP . An alternative, also free software package is Sage (Sage can also be used with pari).
Pictures of all blackboards are here.

20 Nov 2009
Lecture given by Michael Naeh rig.
Generalization of index calculus attacks to other fields; comments on key sizes.
New chapter: Elliptic curves
Clock group; Edwards curves. Edwards curves, points of special order, completeness of addition law.
Pictures of all blackboards are here.

27 Nov 2009
Twisted Edwards curves; number of points on curves; Hasse-Weil theorem; scalar multiplication methods (double-and-add, NAF); explicit formulas for addition and doubling.
Weierstrass curves.
Pictures of all blackboards are here.

04 Dec 2009
Attention: Please contact me about projects if you haven't done that yet. Next week is the last lesson. If you would like to arrange for a meeting, please email me. Slot 13:40-start is already taken.
Elliptic curves in Weierstrass form, derivation of general addition law, example of addition in short form, birational equivalence with twisted Edwards curves, exceptional points of map (justifying P_infty as separate point). Factorization: trial division, Pollard rho, random squares, comment on quadratic sieve.
Pictures of all blackboards are here.

11 Dec 2009
Final projects are due January 29, 2010. If you want feedback on a preliminary version, you need to submit this before January 11, 2010.
I forgot to bring the printed evaluation forms. Please download your copy from and send your form to Greata Oliemeulen-Löw.
Factorization methods: Pollard p-1 method, ECM.
Compositeness tests and primality tests: Fermat test, Miller-Rabin test, Pocklington test, ECPP.
Pictures of all blackboards are here.