Génération des clés pour cryptosystèmes symétriques basée sur les bits pseudo-aléatoires

III.2. Générateurs cryptographiquement sûrs

Du point de vue de la formalisation de la sécurité d'un générateur pseudo-aléatoire, il faut d'une part définir le problème de sécurité, d'autre part il faut définir ce qu'est l'attaque. Un attaquant est considéré comme un algorithme réalisable qui sort un résultat relatif au problème de sécurité posé. La notion d'algorithme réalisable est extrêmement importante car comme on travaille souvent sur des situations finies on peut décrire théoriquement des algorithmes qui cassent la sécurité des systèmes. Mais ces algorithmes ne sont pas réalisables en pratique à cause de la durée des calculs. On cherche donc à assurer la sécurité calculatoire.

Nous allons utiliser le générateur de Blum-Blum-Shub qui est cryptographiquement sûr.

Définition

Soit un paramètre, appelé paramètre de sécurité.

Définition

Soit une fonction en telle que Un générateur pseudo-aléatoire est une fonction calculable en temps polynomial en de dans .

Lorsque nous composons la distribution uniforme sur avec , nous obtenons une distribution sur appelée la distribution induite par .

Définition

Soit un générateur pseudo-aléatoire et . Un -distingueur pour est un algorithme probabiliste polynomial tel que

où signifie que les bits sont choisis selon la distribution induite par et qu'ils sont choisis selon la distribution uniforme.

Définition

Un générateur pseudo-aléatoire est dit cryptographiquement sûr s'il n'existe d' -distingueur pour que pour des fonctions négligeables (par rapport au paramètre

III.3. Extrapoleurs

Définition

Soit un générateur pseudo-aléatoire, un entier, et . On note des bits choisis suivant la distribution induite par sur . Un extrapoleur d'ordre pour d'avantage est un algorithme probabiliste polynomial calculant le bit en fonction des précédents avec probabilité .

Ainsi à partir d'un extrapoleur d'ordre et d'avantage pour , nous obtenons un -distingueur pour comme suit :

La probabilité que soit égal à vaut au moins lorsque est choisi selon la distribution induite par et vaut lorsque est choisi selon la distribution uniforme.

Théorème de Yao

Un générateur pseudo-aléatoire est sûr si et seulement si, pour chaque entier, il n'existe pas d'extrapoleur pour autres que d'avantage négligeable.

Preuve

D'après la construction de distingueur à partir d'un extrapoleur, ne peut être sûr que si tout extrapoleur n'est que d'avantage négligeable.

Inversement, supposons que ne soit pas sûr. Pour , notons la distribution sur selon laquelle les premiers bits sont produits par et les autres sont choisis uniformément au hasard. Ainsi, est la distribution uniforme et celle induite par . Par hypothèse, il existe un -distingueur pour telle que ne soit pas négligeable, c'est-à -dire

Donc il existe un et une fonction pas négligeable tels que

Considérons l'algorithme suivant :

Nous allons montrer que est un extrapoleur d'avantage pour

On a tout d'abord et

.

On a aussi donc

Pour alléger les notations, nous posons et . La probabilité que prévoie le bit correctement est donnée par