Aléatoire et Pseudo-aléatoire

L'aléatoire est l'essence même de la cryptographie — les clés, les nonces et les défis doivent être imprévisibles — et la pseudo-aléatoire permet d'étendre une courte graine véritablement aléatoire en de longues séquences indiscernables de l'aléatoire pour tout adversaire efficace.

Definition

La pseudo-aléatoire est la propriété d'être indiscernable de l'aléatoire véritable d'un point de vue calculatoire ; un générateur pseudo-aléatoire étend de manière déterministe une courte graine aléatoire en une sortie plus longue qu'aucun algorithme efficace ne peut distinguer de l'aléatoire.

Scope

Ce sujet aborde le rôle de l'aléatoire en cryptographie : les exigences relatives aux sources d'entropie et aux générateurs de nombres véritablement aléatoires, les définitions et constructions de générateurs pseudo-aléatoires et de fonctions pseudo-aléatoires cryptographiquement sûrs, ainsi que les conséquences catastrophiques d'une aléatoire faible ou réutilisée. Il examine comment les objets pseudo-aléatoires formalisent les primitives symétriques. Il exclut les chiffrements spécifiques et les hypothèses de difficulté, traités dans des sujets connexes.

Core questions

• Pourquoi la cryptographie exige-t-elle une aléatoire imprévisible, et qu'est-ce qui ne va pas sans elle ?
• Qu'est-ce qui distingue un générateur cryptographiquement sûr d'un générateur statistique ?
• Comment une courte graine véritablement aléatoire peut-elle être étendue en une longue sortie pseudo-aléatoire ?
• Que sont les fonctions et permutations pseudo-aléatoires, et comment modélisent-elles les chiffrements ?
• Comment l'entropie de haute qualité est-elle collectée et conditionnée dans les systèmes réels ?

Key concepts

• entropie et aléatoire véritable
• générateurs de nombres aléatoires
• générateur pseudo-aléatoire (PRG)
• fonction pseudo-aléatoire (PRF)
• permutation pseudo-aléatoire (PRP)
• indiscernabilité calculatoire
• dérivation de graine et de clé
• défaillances dues à la réutilisation de l'aléatoire
• conditionnement de l'entropie

Key theories

Générateurs pseudo-aléatoires

Un générateur pseudo-aléatoire étend une courte graine en une chaîne plus longue indiscernable d'une aléatoire uniforme pour tout discriminateur efficace ; de tels générateurs existent si et seulement si des fonctions à sens unique existent, reliant la pseudo-aléatoire aux fondements de la cryptographie.

Fonctions et permutations pseudo-aléatoires

Une famille de fonctions pseudo-aléatoires, constructible à partir de n'importe quel générateur pseudo-aléatoire, est indiscernable d'une fonction véritablement aléatoire pour un adversaire l'interrogeant ; cet objet sous-tend la modélisation de la sécurité des chiffrements par blocs et des codes d'authentification de message.

Mechanisms

Un générateur de nombres véritablement aléatoires collecte l'entropie physique (bruit thermique, gigue de synchronisation), qui est conditionnée et utilisée pour amorcer un générateur pseudo-aléatoire cryptographiquement sûr qui produit de manière déterministe tous les bits d'apparence aléatoire dont un système a besoin. Les fonctions pseudo-aléatoires sont construites à partir de générateurs (la construction GGM) et modélisent les primitives à clé ; un chiffrement par bloc est traité comme une permutation pseudo-aléatoire. Les définitions de sécurité exigent qu'aucun adversaire efficace, étant donné les sorties, ne puisse prédire les bits futurs ou les distinguer de l'aléatoire.

Clinical relevance

Les défaillances de l'aléatoire sont une source récurrente de brèches catastrophiques dans le monde réel : le bug OpenSSL de Debian en 2008 a paralysé la génération de clés, des nonces ECDSA prévisibles ont divulgué des clés privées (Sony PlayStation 3, certains portefeuilles Bitcoin), et une faible entropie des dispositifs embarqués a produit des clés devinables à grande échelle. Une aléatoire robuste — une collecte d'entropie appropriée et des générateurs pseudo-aléatoires validés — est donc essentielle à chaque déploiement cryptographique.

Evidence & guidelines

Les normes NIST SP 800-90A/B/C spécifient les générateurs de bits aléatoires déterministes approuvés, la validation des sources d'entropie et les directives de construction. La bonne pratique consiste à utiliser le générateur de nombres aléatoires cryptographique (RNG) validé du système d'exploitation (plutôt que de développer le sien), à s'assurer d'une entropie suffisante avant de générer des clés, et à ne jamais réutiliser les nonces. Les suites de tests statistiques aident à détecter les défauts majeurs mais ne peuvent pas établir la force cryptographique.

History

La théorie calculatoire de la pseudo-aléatoire a été fondée par Blum et Micali et par Yao vers 1982, définissant l'imprévisibilité et l'indiscernabilité. Goldreich, Goldwasser et Micali ont montré comment construire des fonctions pseudo-aléatoires à partir de générateurs en 1986, et Hastad, Impagliazzo, Levin et Luby ont prouvé plus tard que les générateurs pseudo-aléatoires existent si les fonctions à sens unique existent. Les désastres pratiques répétés dus à une aléatoire faible ont maintenu la qualité de l'entropie et des RNG comme une préoccupation d'ingénierie centrale.

Key figures

• Oded Goldreich
• Shafi Goldwasser
• Silvio Micali
• Manuel Blum
• Andrew Yao

Seminal works

• goldreich1986
• goldreich2001
• katz2020

Frequently asked questions

Pourquoi ne puis-je pas utiliser une fonction aléatoire normale comme rand() pour la cryptographie ?

Les générateurs de nombres aléatoires ordinaires sont conçus pour l'uniformité statistique et la vitesse, et non pour l'imprévisibilité ; leur sortie peut être prédite à partir de quelques échantillons. La cryptographie a besoin de générateurs dont la sortie future est infaisable à prédire même en connaissant la sortie passée, ce qui nécessite un RNG cryptographiquement sûr amorcé avec de l'entropie réelle.

Quelle est la différence entre l'aléatoire véritable et la pseudo-aléatoire ?

L'aléatoire véritable provient d'une source physique et imprévisible et est limitée en quantité. La pseudo-aléatoire est générée de manière déterministe à partir d'une courte graine véritablement aléatoire et peut être produite en grande quantité ; elle n'a besoin d'être indiscernable de l'aléatoire véritable pour aucun adversaire efficace, ce qui est suffisant pour un usage cryptographique.