L'objectif de ce cours est de donner des définitions précises pour les propriétés que doivent vérifier des fonctions qui vont servir de brique élémentaire pour des protocoles cryptographiques. Il s'agit en particulier d'expliquer précisément ce qu'est une fonction à sens unique : intuitivement une fonction qui est facile à calculer mais dont l'inverse est difficile à calculer. Nous aborderons aussi la notion de fonction trappe et donnerons quelques exemples de bons candidats pour de telles fonctions. Afin de définir ces notions, il nous faudra revoir les bases de la théorie de la complexité, et nous montrerons au passage le lien entre l'existence d'une fonction trappe et la conjecture P \neq NP.
Nous expliquerons ensuite comment utiliser des fonctions à sens unique ou des fonctions trappe pour faire des générateurs pseudo-aléatoires et des systèmes de chiffrement ayant de bonnes propriétés cryptographiques. Nous illustrerons ces constructions par des exemples.