Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Fonction à trappe
Résumé
vignette|Représentation d'une fonction à trappe. Il est facile d'évaluer la fonction mais son inversion est complexe sauf si la clé t est connue.
En cryptologie, une fonction à trappe ou TDF (pour l'anglais trapdoor function) est un modèle idéalisé permettant de raisonner à propos de systèmes cryptographiques. En première approche, il s'agit d'une fonction qu'il est facile d'évaluer en chaque point de son domaine, mais qu'il est difficile d'inverser à moins de disposer d'une information particulière, appelée « trappe ».
La notion de fonction à trappe a été introduite par les cryptologues américains Whitfield Diffie et Martin Hellman en 1979, comme une manière de résoudre le problème de la cryptographie à clé publique tel que posé par Ralph Merkle quelques années plus tôt. Étant donné une fonction à trappe, il est en effet immédiat de construire un algorithme de chiffrement ou de signature numérique. Cependant Diffie et Hellman ne proposent pas de telle fonction dans leur article.
La question de l'existence de fonctions à trappes a été difficile, le premier exemple pratique étant dû à Rivest, Shamir et Adleman en 1976 et reposant sur le problème RSA. C'est en partie pour ces travaux que les trois reçoivent en 2002 le prestigieux prix Turing. En 1979 Michael Rabin a proposé montrer comment construire une fonction à trappe reposant sur le problème de la factorisation. Dans les deux cas, RSA et Rabin, la trappe est donnée par un facteur d'un grand nombre composé.
Dans les années qui suivirent, les progrès en cryptologie (dus notamment à Lamport, Goldwasser-Micali-Rivest, Goldreich-Goldwasser-Micali, Goldreich, Naor-Yung, Rompel et d'autres) ont montré comment construire des algorithmes de signature simplement à partir de fonctions à sens unique, relativisant grandement l'intérêt des fonctions à trappes. Ainsi par exemple, les signatures ECDSA reposent sur le problème du logarithme discret, pour lequel aucune trappe n'est connue.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.