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