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.

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.

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

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.

- Johannes Buchmann "Introduction to Cryptography", Springer
- Neal Koblitz "A Course in Elementary Number Theory and Cryptography", Springer.
- Kenneth Ireland and Michael Rosen "A Classical Introduction to Modern Number Theory", Springer

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.

**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
*p ^{n}* for some prime

**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
*x ^{q}-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 *F*_{4007},
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.

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.

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.

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
http://www.mastermath.nl/registration/EvaluationForm.pdf/
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.