Number Theory and Cryptology

Pictures and slidesAnnouncements 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
Netherlands

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

The easiest ways to reach me where ever I am:
e-mail:tanja@hyperelliptic.org

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.

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

Announcements

Attention: Please contact me about projects if you haven't done that yet. I need to know by December 12 which group is doing what. Please send intermediate version late December/early January. Absolutely last day for handing in your project is January 20, 2009. More on pictures of December 5, 2008.

Literature

Literature: Neal Koblitz "A Course in Elementary Number Theory and Cryptography", Springer. It is though not necessary to purchase the book to follow the course.

Examination

Criterion is active participation in the course and exercise sessions and a final project. The final project can be done in groups of at most 2 people.

Class notes

12 Sep 2008
General introduction to cryptography; concepts public key and symmetric key cryptography, brief excursion into different security assumptions (known plaintext security vs. known ciphertext security). As an example 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 for the perfect code system.

19 Sep 2008
Summary of background material on groups to refresh it. We took pictures of all white boards before erasing them. They are here.

26 Sep 2008
Summary of background material on rings and modular reduction. We took pictures of all white boards before erasing them. They are here.

03 Oct 2008
Modular reduction, Euclidean algorithm, Bezout's theorem, kid-RSA, Euler phi-function. Pictures of the black- and white boards are here.
Here are the slides for the Kid-RSA system; another example from the Fellow-Koblitz paper.

10 Oct 2008
Euclidean rings, Chinese remainder theorem, proof of Euler-phi function, Pohlig-Hellman attack. Pictures of the black- and white boards are here.
Between imgp1451.jpg and imgp1452.jpg we had two stories as introduction to the CRT. The first one asked you to compute the number of camels (<60) that would satisfy the following description: when the camels are grouped in triples, 2 camels remain; when grouped in groups of 4 exactly 1 camel remained; when grouped in groups of 5 there were 4 camels remaining.
The second story is about a Chinese general who has a special way of "counting" the number of soldiers in his army of 1000 soldiers. Every morning he asks them to line up in lines of first 11, then 13 and then of 17 and counts only the number of remaining soldiers. One morning he counts and has the leftovers of 3, 4 and 9 respectively. The solution to this question is imgp1452.jpg.

17 Oct 2008
Lecture given by Michael Naehrig
Fermat's little theorem, Fields, subfields, vector spaces, dimension, extension degree.
New chapter: Finite Fields. Characteristic, characteristic of a field must be prime. Pictures of all blackboards are here.

24 Oct 2008
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. Pictures of all blackboards are here.

31 Oct 2008
Discussion of possible projects (see pictures); reminder of additive and multiplicative structure of finite fields; original Diffie-Hellman key exchange, overview of attacks (see slides below); index calculus attack in prime fields; polynomials over finite fields. Pictures of all blackboards are here. For the attack overview I re-used (with permission) slides by Daniel J. Bernstein made for a tutorial on elliptic curves.

07 Nov 2008
Detailed example of index calculus attack in F2003, solved using Pari GP . An alternative, also free software package is Sage (Sage can also be used with pari). We then discussed more properties of polynomials over finite fields (unique factorization, derivatives).
We distributed the topics. I prefer not to put the file here since the page is public. If you are a participant of this course and would like to know what we disucssed please contact me.
Pictures of all blackboards are here.

14 Nov 2008
Projects: Some details of the topics are visible on the pictures from October 31st.
Construction of general finite fields via irreducible polynomials, existence and uniqueness of finite fields; criterion for squarefreeness via gcd and derivatives; Rabin irreducibility test; binomials and trinomials; when do irreducible binomials exist. Please note that the comment about irreducible binomials over F2 applies only to the ground field F2 and not the extension field.
New chapter: Elliptic curves
Clock group; Edwards curves.
Pictures of all blackboards are here.

21 Nov 2008
Edwards curves, points of special order, completeness of addition law, explicit formulas for addition and doubling.
Pictures of all blackboards are here.

28 Nov 2008
Scalar multiplication methods; number of points over finite fields; Weierstrass curves.
Part of this lecture was given from slides. They are here.
Pictures of all blackboards are here.

05 Dec 2008
Attention: Please contact me about projects if you haven't done that yet. I need to know by December 12 which group is doing what. Please send intermediate version late December/early January. Absolutely last day for handing in your project is January 20, 2009. More on the first picture.
Legendre symbol; Quadratic reciprocity; Fermat's primality test Jacobi Symbol; Soloway-Strassen test
I didn't finish the proof for the Solovay-Strassen test in class. I typed up my classnotes for that part and also included the Miller-Rabin test which has a higher chance per round to detect composits. These notes are here.
Pictures of all blackboards are here.

12 Dec 2008
Lecture given by Peter Birkner
RSA, factorization methods: Pollard p-1 method, ECM.
Pictures of all blackboards are here.
Peter's maple worksheets are here: RSA and Pollard.