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.

- Johannes Buchmann "Introduction to Cryptography", Springer
- Neal Koblitz "A Course in Elementary Number Theory and Cryptography", Springer.
- Tanja Lange "Number Theory and Algebra" (Chapter of draft book "Discrete Mathematics")
- 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 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
**F*** _{p}* one sees that a finite field has

Pictures are here.

Possible topics for projects are here.

**29 Oct 2010**

*(a+b) ^{p}=a^{p}+b^{p}* and

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 **F**_{17} and
**F**_{11}; index calculus attack in
**F**_{107}; complexity of index calculus; index calculus
attacks in **F**_{2n}.

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: