Les fonctions à trappe (trapdoor)

Une fonction à sens unique interdit à tout le monde d'inverser l'opération — y compris à son propriétaire légitime. Or, pour chiffrer un message, il faut bien que quelqu'un puisse le déchiffrer. La solution s'appelle la fonction à trappe.

L'idée de la trappe

Une fonction à trappe (en anglais trapdoor function) est une fonction à sens unique munie d'un secret : sans ce secret, l'inversion reste infaisable ; avec lui, elle devient facile.

Le secret s'appelle la trappe (trapdoor). C'est une porte dérobée mathématique, connue du seul détenteur.

   x  --[ facile : clé publique ]-->  y = f(x)

   y  --[ infaisable sans trappe ]-->  x        (attaquant)
   y  --[ facile AVEC la trappe   ]-->  x        (propriétaire)

Le cœur de la clé publique

C'est exactement le mécanisme de la cryptographie à clé publique :

• Chiffrer correspond au sens facile de la fonction. N'importe qui peut le faire avec la clé publique.
• Déchiffrer correspond à l'inversion. Elle est infaisable pour un attaquant, mais facile pour qui détient la trappe, c'est-à-dire la clé privée.

La clé publique décrit la fonction ; la clé privée est la trappe. On diffuse la première au monde entier, on garde la seconde jalousement.

RSA : la factorisation comme trappe

RSA est l'exemple historique. Le module public n = p × q définit une fonction facile à calculer : c = m^e mod n. Inverser cette opération — retrouver m à partir de c — revient à savoir factoriser n.

Élément	Rôle
(n, e)	clé publique : décrit la fonction, permet de chiffrer
p, q	la trappe : la factorisation connue du seul propriétaire
d	clé privée : dérivée de la trappe, permet de déchiffrer

Celui qui a fabriqué la clé connaît p et q : pour lui, l'inversion est facile. L'attaquant ne voit que n et doit le factoriser — infaisable pour un n assez grand.

Sens unique n'est pas trappe

Attention à ne pas confondre les deux notions :

• une fonction à sens unique simple n'a aucun raccourci : personne ne peut l'inverser. Utile pour du hachage, pas pour du chiffrement réversible.
• une fonction à trappe est une fonction à sens unique avec un raccourci secret. C'est ce qui permet de déchiffrer.

Toute fonction à trappe est à sens unique ; l'inverse est faux. C'est cette nuance qui rend la clé publique possible.

En résumé

Une fonction à trappe est une fonction à sens unique dotée d'un secret qui rend l'inversion facile pour qui le connaît. Ce secret — la trappe — est la clé privée ; la clé publique décrit la fonction et sert à chiffrer. Dans RSA, la trappe est la factorisation n = p × q, connue du seul propriétaire.