Pierrick Gaudry
Cryptographic methods can be divided in two large classes: symmetric systems where the same key is used to cipher and to decipher, and asymmetric systems (a.k.a. public key cryptosystems) where the key used to encipher is different from the one used to decipher, the latter being impossible to deduce from the former.
Both have advantages and disadvantages. Depending on the context, one or the other will be used, and sometimes both together, mixed in complicated protocols.
Mathematical tools involved in symmetric algorithms include information theory, statistics, boolean functions. On the other hand, most of the cryptosystems used in public key cryptography rely on problems coming from number theory. The most famous, RSA, should be safe as long as we do not have efficient algorithms for factoring integers. Others rely on the difficulty of the discrete logarithm problem in a finite abelian group.
Optimizing and implementing the algorithms involved in these systems have become crucial. Some of them are highly non-trivial and make heavy use of tools coming from computer algebra or computational algebraic number theory.
After a short history, we shall explain which are the criterion for a modern cryptosystem. The distinction between symmetric and asymmetric systems will be explained, together with their main characteristics. We shall list some tasks that can be achieved satisfactorily with today's state of the art.
We shall make a survey of the currently available public key cryptosystems with an emphasis on RSA and elliptic curves which are the most popular systems. For these two systems we shall give more details on the algorithmic problems that are involved and a rough idea of the state of the art.
As an example of a non-trivial algorithmic problem, we shall explain how the point counting problem has switched in 15 years from almost infeasible in a reasonable amount of time, to easily tackled even in a constraint environment like a PDA. This was made possible by using deep theoretical results and efficient algorithms from computer algebra.