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

III.4 Sécurité du générateur Blum-Blum-Shub 

III.4.1 Problème de la résiduosité quadratique

Le problème de la résiduosité quadratique est comme suit : étant donné un nombre il faut déterminer si est un carré modulo ou non.

Lorsque un premier, le problème sera résolu en temps polynomial en la taille de par le calcule du symbole de Legendre Puisqu'on sait que est un résidu quadratique modulo si et seulement si son symbole de Legendre est 1.

Lorsque est un nombre composé dont on ne connait pas la factorisation, aucun algorithme polynomial en la taille de sera disponible pour résoudre le problème de la résiduosité quadratique.

Supposons que où et deux premiers distincts. Si la factorisation de est connue alors le problème de la résiduosité quadratique se résout en temps polynomial en cherchant tout simplement si et sont des résidus quadratiques par le calcul de leurs symboles de Legendre. Mais lorsqu'on ne connait pas la factorisation de ,il sera impossible de résoudre le problème en temps polynomial.

Un autre problème s'oppose à savoir l'extraction d'une racine carrée modulaire : sachant qu'un nombre est un résidu quadratique , comment déterminer un nombre tel que

Nota

Soit un entier de Blum, un élément de symbole de Jacobi 1 et son carré modulo On sait que , et possède 4 racines carrées dont deux ont pour symbole de Jacobi 1 : et . Une et une des deux valeurs et est dans En outre et ont des parités différentes. Autrement dit, si on disposait d'un algorithme capable de déterminer avec une probabilité de succès non négligeable, à partir de quelle est la parité de la racine carrée qui est elle-même un carré, on pourrait déterminer avec la même probabilité de succès si est un carré ou non.

III.4.2 Détails sur la sécurité du générateur Blum-Blum-Shub

On va noter l'ensemble des entiers de symbole de Jacobi valant 1.

Les nombres d'éléments de est donné par :

Et aussi alors

Comme est un entier de Blum, par conséquent l'application de dans lui-même définie par est une bijection.

Soit la taille de l'entier qui servira de paramètre de sécurité. On dispose d'un algorithme probabiliste polynomial en qui étant donné en entrée le paramètre de sécurité construit au hasard un environnement de travail, c'est-à-dire un entier de Blum de taille (pour notre cas). Soit la fonction d'élévation au carrée modulo On note l'ensemble des environnements possibles.

Soit un algorithme probabiliste polynomial en dont l'entrée est le paramètre de sécurité le nombre et un élément de et la sortie un bit dont on souhaite qu'il détermine avec succès si est un élément de ou non.

Considérons les expériences :

L'avantage de l'attaquant est définie par :

Le problème de la résiduosité quadratique est sûr par l'hypothèse de la difficulté de la résiduosité quadratique, c'est-à-dire que pour tout attaquant polynomial et pour tout entier Autrement dit tout attaquant polynomial a un avantage qui est une fonction négligeable du paramètre de sécurité .

Les algorithmes d'extrapolation

Soit le paramètre de sécurité, un entier de Blum de taille et le générateur des nombres pseudo-aléatoire définie par :

, où pour tout le calcul de se fait de la façon suivante :

1. La bijection de dans lui-même définie par permet de calculer

2. Chaque donne un bit

3.

Lemme

Soit et un algorithme probabiliste polynomial qui étant donnés les bits prédit le bit avec un avantage non négligeable. Alors on fournit en entrée de cet algorithme probabiliste polynomial, les bits d'un , il prédit le bit avec le même avantage non négligeable.

Preuve

Du fait est une bijection, la loi de probabilité du terme calculé est la même que la loi de probabilité du terme tiré au sort dans qui sert de germe

Pour prouver que le générateur BBS est sûr, on montrera que s'il existe un extrapoleur probabiliste polynomial qui prédit le bit avec un avantage non négligeable, alors, il existe un algorithme probabiliste polynomial qui possède un avantage non négligeable pour résoudre le problème de la résiduosité quadratique.

Soit un algorithme polynomial probabiliste, dont les entrées sont et dont l'avantage de prédiction du bit n'est pas une fonction négligeable de . Construisons l'algorithme dont les entrées sont ( où et sort un bit.

Par le nota précédent, on voit que l'algorithme ainsi construit, a un avantage non négligeable pour le problème de la résiduosité quadratique. En tenant compte de la difficulté de la résiduosité quadratique, on conclut que le générateur Blum-Blum-Shub est sûr.