CRYPTOGRAPHY FOUNDATION

In this course we introduce the mathematical basis and related applications of mathematical cryptography.

The students should know the fundamental mathematical tecniques of mathematical cryptography.

Basics of Discrete Mathematics

1. What is a group. Cryptography in a Group. Polynomial and Exponential Time.

2. Arithmetics of Integers: Division and Ideals. GCD. Complexity of Euclidean algorithm. GCD and Matrices. Modular Arithmetics: Fermat, Wilson and Euler. Chinese remainder Theorem.

3. The Fast Powering Algorithm. The Discrete Logarithm Problem (DLP). Shanks's Babystep-Giantstep Algorithm. Pohlig-Hellman Algorithm. The Elgamal Public Key Cryptosystem. RSA public key cryptosystem.

4. Solovay-Strassen Probabilistic Test of Primality. Polynomial Deterministic Test of Primality: The AKS algorithm. Probabilistic encryption and the Goldwasser-Micali cryptosystem.

5. The geometry of cubics. Weierstrass Normal Form of cubic curves. Singular cubics. Elliptic curves. The group operation. Algorithm for the group law in an elliptic curve. Elliptic curves on rational numbers Q, real numbers R, complex numbers C and finite fields.

6. Diffie-Hellman Key Exchange (DHP) and The Elgamal Public Key Cryptosystem over Elliptic Curves. The elliptic curve discrete logarithm problem (ECDLP).

7. Factorisation Algorithms: Pollard Algorithm. Lenstra's elliptic curve factorization algorithm. Factorization via difference of squares (Fermat and beyond). Pomerance Quadratic Sieve. Number Field Sieve.

A. Salibra. Slides of the course. 2018.
M.W. Baldoni, C. Ciliberto, G.M. Piacentini Cattaneo: Elementary Number Theory, Cryptography and Codes, Springer-Verlag, 2009.
J.H. Silverman, J. T. Tate: Rational Points on Elliptic Curves, Springer-Verlag, 2015.
J. Hoffstein, J. Pipher, J. H. Silverman: An Introduction to Mathematical Cryptography, Springer-Verlag, 2008.

Exercise and written exams in the classroom

Digital and traditional blackboard.

English

oral