| 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
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.
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: Neal Koblitz "A Course in Elementary Number Theory and Cryptography", Springer. It is though not necessary to purchase the book 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 at most 2 people.
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.
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.