fonction trappe

Imaginez une boîte aux lettres : chacun peut y glisser une enveloppe, mais seule la personne qui possède la clé peut la reprendre. Une fonction trappe transpose cette dissymétrie au calcul. Le trajet aller est rapide pour tous ; le retour est hors de portée en pratique sans une information secrète.

Cette information est la trappe. Elle ne change pas le résultat du calcul direct : elle fournit un raccourci pour retrouver l'entrée à partir du résultat.

Une fonction trappe est une fonction à sens unique munie d'une information secrète qui rend son inversion efficace. Le calcul direct transforme une entrée en une image en un temps raisonnable. Sans la trappe, retrouver un antécédent à partir de cette image est supposé computationnellement infaisable à l'échelle considérée ; avec elle, le calcul inverse redevient aisé.

La source présente une famille de bijections. Le paramètre secret est noté t, et la fonction qui lui correspond est notée f_t, du domaine fixé D_t vers le codomaine fixé C_t. La bijectivité garantit que chaque image de C_t possède un unique antécédent dans D_t. Pour une entrée x et son image y, la relation directe puis l'inversion s'écrivent : $y=f_t(x),x=f_t^{-1}(y)y=f\_t(x),\backslash qquad\; x=f\_t^\{-1\}(y)$. La seconde opération est efficace lorsque t est connu. L'exemple RSA de cette fiche prend pour domaine et codomaine les représentants 0 à 3232 des classes modulo 3233.

L'expression « infaisable » décrit une difficulté de calcul, non une impossibilité logique. Elle dépend du choix de la famille, de la taille des paramètres et des connaissances algorithmiques. Dans RSA, l'évaluation publique repose sur l'arithmétique modulaire ; l'information privée permet l'inversion, tandis que la factorisation du module est le problème difficile indiqué par la source.

La structure réunit quatre éléments. Un domaine contient les entrées possibles. Une fonction directe associe efficacement une image à chaque entrée. Une famille bijective fixe, pour chaque paramètre admis, une correspondance où chaque image a un unique antécédent. Enfin, une clé de trappe est l'information secrète qui fournit l'inversion efficace.

Le domaine et le paramètre déterminent quelle correspondance est utilisée. La trappe dépend de ce choix : une information secrète associée à une autre fonction ne suffit pas. Ces données permettent de calculer l'image publiquement et de reconstruire son antécédent avec la trappe. La manière de dessiner les ensembles ou les flèches n'appartient pas à la définition.

Considérons un exemple RSA volontairement minuscule, utile pour vérifier les calculs mais pas pour protéger une information. La fonction agit sur les représentants 0 à 3232 des classes modulo 3233. Le module vaut n = 3233, l'exposant public vaut e = 17, la trappe est l'exposant privé d = 2753 et l'entrée vaut x = 65.

1. La fonction directe élève l'entrée à la puissance publique, puis prend le reste modulo 3233 : $f(65)\equiv {65}^{17}\equiv 2790(\mathrm{m}\mathrm{o}\mathrm{d}3233)f(65)\backslash equiv65^\{17\}\backslash equiv2790\backslash pmod\{3233\}$. L'image obtenue est 2790.

2. Sans information secrète, le problème inverse part de 2790 et demande quel entier du domaine lui a donné naissance. La simple lecture du résultat ne révèle pas 65.

3. Avec la trappe 2753, on applique l'exposant privé au résultat : ${2790}^{2753}\equiv 65(\mathrm{m}\mathrm{o}\mathrm{d}3233)2790^\{2753\}\backslash equiv65\backslash pmod\{3233\}$. L'antécédent retrouvé est exactement 65.

4. Le contrôle consiste à refaire le calcul direct sur 65 : il redonne 2790 modulo 3233. Le trajet 65 → 2790 → 65 montre les deux vitesses de calcul, selon que la trappe est disponible ou non.

Dans un chiffrement à clé publique fondé sur ce principe, l'expéditeur effectue le calcul direct avec les données publiques. Le destinataire conserve la trappe qui rend possible l'opération inverse. Le critère observable est que le secret n'a pas à être communiqué pour effectuer le trajet aller.

Pour analyser un dispositif, on repère donc trois questions : qui peut calculer l'image, quelle information permet de l'inverser, et quel problème l'adversaire devrait résoudre sans cette information. Dans l'exemple RSA, le calcul direct est public ; connaître la factorisation du module permet de reconstruire l'exposant privé, sans que cela établisse une équivalence générale entre factorisation et inversion RSA.

Si les deux sens exigent le même secret partagé, le modèle n'est pas celui d'une fonction trappe publique. Si aucun retour n'est attendu, une fonction à sens unique non inversible en pratique peut suffire.

Fonction trappe et fonction à sens unique ordinaire. Toutes deux rendent l'inversion difficile sans aide, mais la fonction trappe possède une information secrète qui la rend efficace. Si aucun raccourci secret d'inversion n'est prévu, il manque la trappe.

Fonction trappe et fonction de hachage. La famille décrite par la source est bijective sur son domaine, donc chaque image y a un antécédent unique. Une transformation qui ramène de nombreuses entrées vers la même sortie ne satisfait pas ce critère.

Trappe et clé publique. La clé publique autorise le calcul direct ; la trappe reste secrète et autorise l'inversion efficace. Dans l'exemple, 17 est public tandis que 2753 joue le rôle de trappe.

Une bijection n'est pas automatiquement difficile à inverser. Le symptôme est l'existence d'un calcul inverse rapide sans information secrète. Il faut alors rejeter la famille comme fonction trappe, même si chaque image possède bien un unique antécédent.

La taille change la difficulté pratique. Le module 3233 de l'exemple vaut 61 × 53 et se factorise avec des moyens élémentaires. Ce cas sert à contrôler le trajet, pas à illustrer une sécurité réelle. Il faut augmenter les paramètres dans un dispositif cryptographique adapté.

Le domaine doit être fixé. La bijectivité se juge entre des ensembles précis. Dans l'exemple, 3233 et 0 représentent le même résidu modulo 3233 ; compter les deux comme des entrées distinctes crée une fausse collision. Il faut travailler avec un représentant par classe.

La difficulté reste une hypothèse computationnelle. « Infaisable » signifie qu'aucune méthode praticable n'est disponible dans le cadre retenu. Cela ne démontre pas l'impossibilité mathématique de l'inversion. Il faut préciser le problème et les paramètres plutôt que promettre une impossibilité absolue.

La fiche clé publique précise la partie diffusée d'un système où la trappe demeure privée.

Le glossaire Factorisation approfondit l'opération dont la difficulté sous-tend l'exemple RSA.

La fiche code RSA déroule le système cryptographique qui met en œuvre l'asymétrie entre calcul direct et inversion.