La fonction à sens unique

La clé publique repose sur une asymétrie mathématique : une opération facile dans un sens, hors de portée dans l'autre.

L'exemple central

Multiplier deux nombres premiers est instantané :

p = 6 700 417
q = 2 147 483 647
p × q = 14 388 460 000 000 000 (environ)

Retrouver p et q à partir du seul produit est très difficile. Sur des nombres de 300 chiffres chacun, aucun algorithme connu n'y parvient en un temps raisonnable, même avec tous les ordinateurs de la planète.

C'est le problème de la factorisation.

Ce qu'il faut bien comprendre

La difficulté n'est pas démontrée : on n'a pas prouvé que factoriser est impossible rapidement. On a seulement constaté que personne n'y arrive depuis des décennies d'efforts.

C'est une différence essentielle avec le masque jetable :

	Masque jetable	RSA
Sécurité	prouvée	supposée
Repose sur	l'information	la difficulté calculatoire
Tient face à	n'importe quelle puissance	les moyens connus aujourd'hui

Si quelqu'un trouvait demain un algorithme de factorisation rapide, RSA tomberait du jour au lendemain. C'est un risque accepté, pas un oubli.

La menace quantique

Ce n'est pas de la science-fiction : l'algorithme de Shor, publié en 1994, factorise efficacement… sur un ordinateur quantique. Les machines actuelles sont très loin de la taille nécessaire, mais le risque est identifié.

C'est pourquoi les organismes de normalisation préparent depuis plusieurs années la cryptographie post-quantique, fondée sur d'autres problèmes difficiles que la factorisation.