Facile dans un sens, impossible dans l'autre

Qu'est-ce qu'une fonction à sens unique

Toute la cryptographie moderne repose sur une idée aussi simple qu'étonnante : certaines opérations sont faciles à faire mais pratiquement impossibles à défaire. On les appelle des fonctions à sens unique.

Une définition intuitive

Une fonction f est dite à sens unique lorsque :

calculer y = f(x) est rapide, même pour un ordinateur modeste ;
retrouver x à partir de y seul est infaisable en pratique, même avec des moyens considérables.

Le mot important est infaisable : il ne s'agit pas de « long » mais de « hors de portée » — des millions d'années de calcul pour les tailles utilisées en cryptographie.

Deux exemples fondateurs

La multiplication de deux grands nombres premiers. Multiplier p et q est instantané ; retrouver p et q à partir du seul produit n = p × q est le problème de la factorisation, pour lequel aucun algorithme rapide n'est connu.

        FACILE  ------------------->
   p, q                              n = p × q
        <-------------------  IMPOSSIBLE
              (factorisation)

L'exponentiation modulaire. Calculer y = g^x mod p est rapide. Retrouver l'exposant x à partir de y, g et p est le problème du logarithme discret, lui aussi réputé très difficile.

Deux analogies pour retenir

L'œuf cassé. Casser un œuf prend une seconde ; le reconstituer intact est impossible. Le sens direct est trivial, le sens inverse hors de portée.
La peinture mélangée. Mélanger deux pots de couleur est immédiat ; séparer à nouveau les pigments d'origine relève de l'impossible.

Ces images rendent tangible ce que veut dire « facile dans un sens, infaisable dans l'autre ».

Un point capital : rien n'est prouvé

Voici le paradoxe que tout étudiant doit comprendre : l'existence des fonctions à sens unique n'est pas démontrée. Personne n'a prouvé que factoriser est forcément lent — on a seulement constaté que, malgré des décennies d'efforts, personne n'y parvient rapidement.

Cette question est intimement liée au grand problème ouvert P vs NP de l'informatique théorique. Tant qu'il n'est pas tranché, la difficulté de ces problèmes reste une conjecture solide mais non prouvée.

Aspect	Fonction à sens unique
Sens direct	facile, rapide
Sens inverse	infaisable en pratique
Existence	conjecturée, non prouvée
Lien théorique	problème P vs NP

On bâtit donc la sécurité sur des problèmes que l'on croit durs, faute de certitude absolue. C'est un pari — mais un pari étayé par un immense effort de cryptanalyse.

En résumé