Cryptography

Notice:

* The final grade can be looked up through the Moodle server. If you have any claim or question about the grade or about my comments, please, let me know it by Tuesday 14th.

The planned syllabus is the following

Historical introduction. Motivation and examples. Elementary group theory and number theory. Finite fields. Simple encryption algorithms.
Discrete logarithm problem. Statement and examples. Basic attacks. Diffie-Hellman key exchange. The ElGamal cryptosystem.
The RSA cryptosystem. Algorithm, examples and cautions. Primality tests and factorization algorithms. Introduction to the number field sieve.
Elliptic curve cryptography. Elliptic curves and group law. Elliptic curves and factorization. The elliptic version of the discrete logarithm problem.
Complementary topics. Digital signatures. The algorithm DES. Knapsack cryptosystems. Lattices and cryptography.

This syllabus, the scope, aims and background are included in the proposal of the course. It was written long time ago and may suffer some (non substantial) changes.

This is the presentation of the course delivered the first day.

The schedule of the lectures is Tuesday and Thursday from 5:30 pm to 7:00 pm. The classroom is 320 in the Math Department "módulo 17" (formerly C-XV).

There is a web page for general reference about master courses in the Math Department. This is the Moodle server at Math Department.

Notes

There will be posted here short excerpts of the theory with some basic examples and some auxiliary material. Check also the links.

0. Using the computer
Basic Linux commands	The basics of compiling and running
Lecture 1 (Running on the console)
Lecture 2 (Crash course on Python) Python cheat sheet by M. Goerz)
Sage reference: number theory (by W. Stein)	Sage function description: p.46-53 of SAGE for Newbies by Ted Kosan
A home made scytale (/ˈskɪtəliː/): message gibberish Templates: helloworld.c, helloworld.py, example.sage, example3d.sage

Recall that Sage is free software system that runs under Linux. If you prefer not to install anything in your computer you can ask me for a live DVD (it is slow but works) or try Sage online through the official website.

Chapter 1

Elementary Number Theory

Simple encryption algorithms: Affine ciphers and Hill cipher (Sage: affine, hill )

Theoretical Cryptography (presentation 10 slides)

Chapter 2

Discrete logarithms (Sage: brute force and baby-step giant step)

The ElGamal cryptosystem (Sage: encryption, decryption)

Encoding Schemes and Finite Fields (Sage: num2text, text2num, ElGamalFF)

Chapter 3

RSA (Sage: rsa including key generation, encryption and decryption)

Primality tests (Sage: Miller-Rabin).

Factorization algorithms (Sage: fermat_factor, pollard_p_auto2)

Chapter 4

Group law (Sage: plot_g_l, plot_g_l.png, g_l )

Lenstra's factorization algorithm (Sage: fast_multp, lenstra, lenstra_stein )

Elliptic curve cryptography (Sage: ecdlp, mv_elgamal)

Complementary topics

Digital signatures: signature

Secret sharing: secret_sharing

Exercises and homework assignments

Home assignments
sheet 1	sheet 2
sheet 3	sheet 4

There are also challenges delivered in the lectures. Their statements may change for one student to another. The following table is a sample. Please do not use them in substituion of the challenges assigned to you.

Challenges
Challenges 1	Challenges 2
Challenges 3	Challenges 4

Grading

You can consult your grades in the Moodle server at Math Department using your email address and the password of your computer account.

1) Home assignments: 40%.

2) Final exam or challenges: 40%.

3) Quizzes, in-class exercises, participation: 20%

You have to get at least 50% to pass the course.

Examples: Suppose that there are 5 assignments sheets and 8 challenges along the course.
A student solving 4/5 of the exercises and one half of the challenges gets 40*4/5+40*1/2=52 plus the grade coming from 3).
Another student solving one half of the exercises and zero challenges accumulates 40*1/2+0=20 and (even with a high participation in class) should pass a final exam.

In other words, the final examination is not mandatory. It is reserved for students who did not get enough points from other sources.

Cryptography

Contents

Notes

Exercises and homework assignments

Grading

Links