Number Theory and Cryptology - Fall 2010

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 211, from 14:15 - 17:00 except for November 26 when it takes place in Minnaertbuilding, room 012.
The first meeting is on September 10, 2010. There will be no lectures on October 22, 2010.
The semester consists of 14 weeks of lectures, the dates are Sep 10, Sep 17, Sep 24, Oct 01, Oct 08, Oct 15, Oct 29, Nov 05, Nov 12, Nov 19, Nov 26 (different room!), Dec 03, Dec 10, and Dec 17. Changes to this plan will be announced here.

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.


Attention: My teaching in Eindhoven ends at 12:30, I try to make it on time for 14:15.
To get feedback on your project send me your draft (preferably a link to your sandbox on wikipedia) before January 12. I plan to go through the drafts on the 12th, so the cut-off is very early in the morning on that day. Deadline for the final version is January 26.


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 or 3 people.

Class notes

To come after classes.

10 Sep 2010
General introduction to cryptography; concepts public key and symmetric key cryptography, Caesar encryption, Vigenere sytem, one-time pad. 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.
Please read up on groups, rings, fields and vectorspaces if you don't know these concepts.
Here are the slides in pdf for the perfect code system. I took pictures of all black boards before erasing them. They are here.

17 Sep 2010
Elementary number theory: division, modular reduction, extended Euclidean algorithm. The worked out example for the Euclidean algorithm is here. We then studied (and broke) the m-RSA system, which is another example from the Fellow-Koblitz paper.
Pictures of the black boards are here.
You can now find a skript for abstract algebra in the course material section.

24 Sep 2010
Chinese remainder theorem, including non-coprime moduli, multiplicative group modulo n, Euler phi-function, computation, and proof, Lagrange's theorem, Fermat's little theorem, Euler's theorem, RSA cryptosystem (schoolbook version).
Pictures of the black boards are here.

01 Oct 2010
RSA as signature scheme, homomorphic property to attack encryption or signature scheme using a single call to an oracle and asking for a different message to be decrypted or signed, square-and-multiply method for exponentiation, small public keys for efficient encryption/signature verification, CRT-RSA for efficient decryption/signature generation, problems with small public exponents if the same message is sent to multiple users or if there is a linear (or more general) dependence between messages. All these problems are avoided using randomization and fixed formatting as in RSA-OAEP
Pictures are here.

08 Oct 2010
Cyclic groups, how to find elements of fixed order, Diffie-Hellman key exchange, discrete logarithm problem, some examples of bad groups for DH key exchange, one good group.
Pictures are here.

15 Oct 2010
An excursion into finite fields with explorations of the additive and multiplicative structure. The characteristic of a finite field is prime. By considering the field as a vectorspace over Fp one sees that a finite field has pn elements for some prime n and positive integer n. The multiplicative group is cyclic. Each of these representations facilitates one of the field operations but not both. One needs to store tables of αij for 0<=i,j < n or (gi+1) for 0<i< pn-1.
Pictures are here.
Possible topics for projects are here.

29 Oct 2010
(a+b)p=ap+bp and (a+b)pn=apn+bpn; number of primitive elements; Zech's logarithm; explicit construction of F8; representation of finite fields via polynomials modulo irreducible polynomials.
Pictures are here.

5 Nov 2010
Some more bits about finite fields. Baby-step giant-step attack, start of Pollard's rho method.
Pictures are here.
At this moment I have found teams for all the English Wikipedia pages stated in the projects.txt file. There are still lots of Dutch pages open and we can find other topics.

12 Nov 2010
Number of elements of certain orders in finite fields. Pollard's rho method, parallel Pollard's rho method, Pohlig-Hellman attack (computing the DL modulo factors of the group order and combining them via CRT).
Pictures are here.

19 Nov 2010
Examples for Pohlig-Hellman attack in F17 and F11; index calculus attack in F107; complexity of index calculus; index calculus attacks in F2n.
Pictures are here.

26 Nov 2010
Summary of index calculus attacks, factorbasis for small characteristic. The clock group, Edwards curves, for which d exist points (x,x)?, pictures.
Pictures are here.

03 Dec 2010
Edwards curves, elliptic curves in Weierstrass form; affine coordinates, projective coordinates.
Pictures are here.

10 Dec 2010
Elliptic curves in Weierstrass form, maps between Edwards and Weierstrass curves, exceptional points and their order. Factorization of integers.
Pictures are here.

17 Dec 2010
Lecture was given by Christiane Peters
p-1 method for factorization, factorization with elliptic curves. Primality and compositeness proofs. Christiane provided her notes as scans: