| 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 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.
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:
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.
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.
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
αi*αj 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: