La cryptographie repose sur une idée paradoxale : un système peut sembler complètement aléatoire alors qu’il est en réalité pseudo-aléatoire. Ce caractère pseudo-aléatoire est au cœur de la cryptographie moderne et permet de concevoir des schémas de chiffrement qui demeurent sûrs même lorsqu’un adversaire observe l’ensemble des chiffrés produits.
Pour comprendre pourquoi le pseudo-aléatoire joue un rôle central, il est nécessaire de préciser ce que l’on entend par sécurité.
Certains schémas de chiffrement offrent une garantie exceptionnellement forte : ils restent sûrs même face à un adversaire disposant d’une puissance de calcul illimitée. Ces schémas sont dits informationnellement sûrs ou parfaitement sûrs.
Dans un schéma à secret parfait, le chiffré ne contient aucune information sur le message en clair tant que la clé secrète est inconnue. Formellement, l’observation du chiffré ne modifie pas la distribution de probabilité de l’adversaire sur l’ensemble des messages possibles.
L’exemple le plus connu est le masque jetable (one-time pad), qui atteint le secret parfait en utilisant une clé :
Le secret parfait ne repose sur aucune hypothèse computationnelle. Aucune quantité de puissance de calcul, aucun algorithme ingénieux ni aucune avancée technologique future ne permet de le compromettre. Sa sécurité est absolue.
Toutefois, cette force a un coût.
En pratique, il est impossible d’utiliser des clés aussi longues que les messages à chiffrer. Les systèmes cryptographiques réels emploient généralement des clés de longueur 128 ou 256 bits.
Pour justifier ces choix, la cryptographie s’appuie souvent sur des garanties de sécurité concrètes, c’est-à-dire des estimations numériques de la probabilité de succès d’une attaque.
Par exemple :
Sous cet angle, le choix d’une clé de 128 bits paraît offrir une sécurité écrasante. Mais une question fondamentale se pose alors :
Sûre contre qui ?
Suppose-t-on du matériel grand public ? Des GPU ou ASIC spécialisés ? Un attaquant isolé ou un État-nation ? Une attaque menée sur deux ans ou sur plusieurs siècles ?
Les garanties concrètes dépendent inévitablement d’hypothèses sur la puissance de calcul, l’efficacité algorithmique et le progrès technologique — hypothèses susceptibles d’évoluer ou de devenir obsolètes.
Afin de s’affranchir de ces incertitudes, la cryptographie moderne adopte une approche asymptotique, issue de la théorie de la complexité.
Plutôt que de fixer des valeurs numériques précises, la sécurité est définie à l’aide d’un paramètre de sécurité n. Le temps de calcul de l’adversaire et sa probabilité de succès sont alors considérés comme des fonctions de n.
Un schéma de chiffrement est jugé sûr si tout adversaire probabiliste en temps polynomial ne peut le compromettre qu’avec une probabilité négligeable, c’est-à-dire une probabilité qui décroît plus rapidement que l’inverse de tout polynôme en n.
Par exemple, pour un paramètre de sécurité n = 500, même un adversaire opérant pendant des centaines d’années ne réussirait qu’avec une probabilité inférieure à 2−500.
L’avantage essentiel de ce cadre est sa capacité d’adaptation : lorsque la puissance de calcul augmente ou que de nouveaux algorithmes apparaissent, il suffit d’augmenter la valeur du paramètre de sécurité.
Le secret parfait est incompatible avec le chiffrement d’un grand nombre de messages à l’aide d’une seule clé courte.
Étant donné un chiffré c, un adversaire non borné peut tester toutes les clés possibles et obtenir l’ensemble des messages compatibles avec c. Si l’espace des clés est plus petit que l’espace des messages, une fuite d’information est inévitable.
Plus encore, cette attaque s’exécute en temps polynomial, réussit avec une probabilité non nulle (environ 1/|K|) et ne peut être empêchée par aucun raffinement du schéma de chiffrement.
La sécurité est impossible sans restrictions sur l’adversaire.
La cryptographie moderne accepte donc deux assouplissements fondamentaux :
Dans ce cadre, le caractère pseudo-aléatoire devient pleinement exploitable : il est possible de concevoir des schémas dont les sorties sont computationnellement indiscernables du hasard véritable.
Le secret parfait représente un idéal — élégant, rigoureux, mais inatteignable à grande échelle. Le recours au pseudo-aléatoire et à l’approche asymptotique offre une alternative pragmatique : une sécurité non absolue, mais robuste, extensible et durable.
En déplaçant l’analyse des garanties concrètes vers le comportement asymptotique, la cryptographie s’affranchit d’hypothèses fragiles sur le matériel et la technologie. La sécurité devient alors une propriété mathématique plutôt qu’une cible mouvante — et c’est ce qui rend la cryptographie moderne possible.