4.4.4 Improbabilité calculatoire

Afin de comprendre le problème d'improbabilité calculatoire auquel feront face d'éventuels cryptographes, mettons-nous à leur place. Nous connaissons le texte chiffré $x$ et la clé de chiffrement composée de $e$ et $n$ puisque celle-ci est publié dans un répertoire publique. Pour effectuer la fonction $d_{k}$, il nous faut connaître $d$. Nous savons que $d$ est l'inverse modulaire de $e$ dans la base $\phi (n)$. Nous savons aussi que le totient de $n$ se calcule à partir des valeurs de $p$ et de $q$ qui le composent, et nous savons que $p$ et $q$ sont des nombres premiers qui, multipliés ensembles, donnent $n$.

Nous avons donc besoin de $p$ et de $q$ afin de trouver $\phi (n)$, lequel nous servira à trouver $d$, lequel servira dans la fonction $d_{k}$. Le problème revient donc à trouver $p$ et $q$, ce qui constitue en fin de compte la factorisation de $n$. Il a été décrit à la section 4.4.2 l'immense puissance de calcul nécessaire à la factorisation d'un nombre. L'impasse dans laquelle nous nous trouvons est décrite par D. E. Denning: « Because $\phi (n)$ cannot be determined without knowing the prime factors $p$ and $q$, it is possible to keep $d$ secret even if $e$ and $n$ are made public. »¹³

C'est donc ici que s'arrête notre cryptographe, à moins qu'il ne possède une puissance de calcul énorme. Jusqu'à présent, aucun ordinateur n'a été assez puissant pour factoriser les nombres impliqués dans l'algorithme RSA. De plus, RSA est extensible. Il est effectivement beaucoup plus sécuritaire d'utiliser des grandes valeurs de $p$ et $q$. La sécurité calculatoire que l'on obtient avec RSA peut être aussi grande que l'on veut. Mais notons qu'il ne s'agira jamais de sécurité absolue.