Etude sur les corps finis

Conception de générateurs aléatoires

Un générateur de nombre aléatoire ou RNG(Random Number Generator) est un dispositif capable de produire une séquence dont on ne peut pas prédire la sortie.On dit qu’un tel générateur est idéal s’il est une construction mathématique générant des nombres aléatoires indépendants et uniformément répartis.

CONCEPTION DE GÉNÉRATEURS ALÉATOIRES

Il existe depuis longtemps des méthodes pour obtenir de tels nombres mais néanmoins de nombreux progrès ont été réalisés.
On distingue ainsi deux types de générateurs de nombres aléatoires avec une possibilité d’hybridation entre eux :
• les générateurs de nombres réellement aléatoires ou TRNG(Random True Number Generator) et
• les générateurs de nombres pseudo-aléatoires ou PRNG(Pseudo Random Number Generator)
Cependant leur critère de classification coincide avec celui des sources d’aléa (d’entropie).

Définition source d’entropie

Une source d’entropie est une source constituée généralement de certaines quantités physiques ou non.
Ainsi on note l’existence de deux types de sources d’entropie.

Source d’entropie non physique

Une source d’entropie non physique est une source qui essaie d’imiter le comportement des sources naturelles , mais avec moins de robustesse. Elle provient également des algorithmes mathématiques et est de nature séquentielle.
Exemple 2.3.1. le mouvement d’une souris , les jeux de dés…

Source d’entropie physique

Une source d’entropie physique est une source due aux caractéristiques intrinsèques des systèmes physiques.
Exemple 2.3.2. le vidéo projecteur , le bruit thermique… ∗ Ainsi nous pouvons dire que le niveau de non-prédictibilité sur les sources d’entropie physiques est trés élevé et ne dépend que de la source d’aléa utilisée sur les générateurs aléatoires.
En effet pour choisir un générateur de nombres aléatoires on se base principalement sur deux caractéristiques à savoir son débit de bits aléatoires mais également la qualité de l’aléa produit.
Ce qui nous permettra tout juste après d’introduire la structure des générateurs aléatoires.

CONCEPTION DE GÉNÉRATEURS ALÉATOIRES

Structure des générateurs de nombres aléatoires

Générateurs de nombres réellement aléatoires (TRNG)

Définition 2.3.1. Un générateur de nombre réellement aléatoire est un composant générant des valeurs issues d’une source dont le niveau de non-prédictibilité est très élevé.
Exemple 2.3.3. Des photons envoyés contre un miroir semi-transparent , l’horloge système d’un ordinateur , le mouvement d’une souris , les jeux de hasard ,le vidéo projecteur ….
Propriété 2.3.1. Les propriétés fondamentales qu’un TRNG doit satisfaire sont les suivantes :
• posséder une distribution statistique uniforme.
• mais également contenir une source d’entropie responsable de la caractéristique aléatoire.
Et suivant la source utilisée on distingue deux types de générateurs de nombres réellement aléatoires :

TRNG non Physique

Ce sont des générateurs dont la source d’aléa n’est pas un phénoméne physique. Mais aussi ce sont des composants stockant d’autres information du systéme.

TRNG Physique

Contrairement au TRNG non physique les TRNG dits physiques sont des dispositifs dédiés uniquement à la génération de nombres aléatoires.
L’architecture suivante nous permet de mieux illustrer ces propos.
Pour les générateurs aléatoires si le signal de bruit est en défaillance, alors se sera le rôle du numériseur de s’assurer que la sortie ne soit pas perturber par cette faille. Cependant si le numériseur n’est pas capable de rééquilibrer cette disparité,alors un correcteur d’entropie également appelé post-traitement sera ajouté à la sortie.

Post-traitement

Un post-traitement est un traitement effectué sur les données avant leur utilisation.
Ils existent deux types de correcteurs d’entropie :
• les post-traitements arithmétiques : la méthode de Neumann ,le Correcteur XOR , les LFSR
• les post-traitements cryptographiques :la fonction de hachage , ceux basés sur le chiffrement par bloc , et ceux sur la théorie des nombres.
En dessous on note l’architecture des TRNG après correction.

Générateurs de nombres aléatoires déterministes (DRNG)

Définition 2.3.2. Un générateur de nombres aléatoires déterministes est un générateur qui produit des nombres qui ont de très bonnes propriétés statistiques mais théoriquement prévisibles

CONCEPTION DE GÉNÉRATEURS ALÉATOIRES

Propriété 2.3.2. Les propriétés fondamentales qu’un DRNG doit satisfaire sont les suivantes :
• une bonne propriété statistique et d’uniformité : on veut obtenir une séquence de nombres qui passe avec succés la plupart des tests statistiques mais à un temps raisonnable
• une longue période : la période des valeurs produites doit être beaucoup plus grande que celle des valeurs aléatoires pour une simulation
• l’efficacité : le temps de calcul pour produire les valeurs doit être le plus petit que possible que le temps de simulation
• la répétabilité : L’utilisateur doit être capable de reproduire la même séquence de nombres facilement ce qui est important pour la vérification de programmes
• la facilité d’implémentation et la séparabilité : on doit pouvoir exécuter le générateur sur tous les types d’ordinateurs standards ; mais également ce générateur doit être capable de quitter une valeur (Un) vers une autre valeur (Un+k) à un temps suffisamment grand.
Ainsi on note l’existence de deux types de DRNG :
? les PRNG également appelé générateur de nombres pseudo-aléatoire
? et les PRNG probabilistes

Générateurs de nombres pseudo-aléatoires

Définition 2.3.3. Un générateur pseudo-aléatoire est un procédé qui à partir d’une initialisation de taille fixée appelée graine ou germe engendre de manière déterministe une suite de très grande longueur de séquences binaires dite aléatoire. Méthodologie de génération de nombres pseudo-aléatoires On définie un générateur de nombres pseudo-aléatoires(PRNG) comme étant une fonction :

Exemples de générateurs de nombres pseudo-aléatoires(PRNG)

Générateurs basés sur les registres à décalage à rétroaction linéaire (LFSR) Un LFSR est un générateur qui permet de décrire l’évolution du système, sa périodicité et sa complexité. Son principe repose sur des mécanismes d’algébres linéaires.
Cependant, il faut être prudent avec leur utilisation car leur comportement complexe peut masquer une faible entropie en entrée et ceci est dangereux car ces structures sont très prévisibles.
Principe 2.3.1. Le principe de base d’un registre de n bits à base de fonction de rétroaction linéaire(XOR) initialisée avec (b1, b2, b3, …., bn−1) est le suivant :
• le 1ier top d’horloge est rempli par le résultat d’une fonction linéaire qui prend en compte l’état d’un ou de plusieurs étages.
•arriver au (n − 1) ier top d’horloge l’état du registre est identique à son état initial. On dit alors que le LFSR est de période (n − 1).

Générateurs de nombres pseudo-aléatoires probabilistes

Définition 2.3.6. Un générateur de nombres pseudo-aléatoires probabilistes est un algorithme déterministe qui produit un résultat à partir d’une chaine aléatoire r ∈ {0, 1}
∗ dans l’ensemble des valeurs possibles.
Cet algorithme se comporte différemment lorsqu’il est appelé deux fois avec les mêmes paramétres.
• Ainsi pour résumer nous pouvons dire qu’il existe deux types de générateurs de nombres aléatoires : les générateurs de nombres pseudo-aléatoires et les générateurs de nombres réellement aléatoires.
Cependant la manière de les classer coincide avec celui des sources d’entropie et pour mieux illustrer cela nous avons proposé tout juste après une architecture résumant la structure de ces générateurs.

Générateurs Cryptographiques Sûrs

Définition

Un générateur aléatoire est dit cryptographiquement sûr si sa sécurité se repose sur un protocole (problème) mathématique connu difficile (NP-Complet). Un générateur cryptographiquement sûr a également une preuve de sécurité bien définie.
Parmi ces protocoles mathématiques nous pouvons en citer quelques uns :
F le Décodage par Syndrome
F le Problème de la Factorisation
F le Problème du résidu quadratique multi-varié etc…..
Cependant pour faire la preuve de sécurité illustrée ci-dessous nous nous baserons sur le problème de la Factorisation.

Exemple

Comme exemple nous avons prit le générateur de RSA et en dessous on note le résultat du test effectué sur ce générateur.

Preuve de Sécurité

Pour faire cette preuve nous allons d’abord définir la théorie de la complexité qui est un élément central de la notion de fonction à sens unique, ensuite nous donnerons le principe et enfin nous terminerons avec la preuve de sécurité accompagnée d’un exemple plus détaillé.

Définition de la Théorie de la Complexité des Algorithmes

C’est le domaine des mathématiques et plus précisément de l’informatique théorique qui étudie formellement la quantité des ressources temporelles mais aussi spatiales (en mémoire) dont a besoin un algorithme pour résoudre un problème algorithmique.
Cette théorie est un élément central de la notion de fonction à sens unique car elle donne un sens mathématique à la notion floue de difficulté à trouver un antécédent.

Algorithmes

• Etant donné A un algorithme efficace de la famille des fonctions à sens unique qui à partir d’un indice i ∈ I génére un élément x ∈ Di.
Cet algorithme est composé de deux étapes :
S1 : Pour tout n ∈ N, il existe un algorithme probabiliste efficace S1 qui prend en paramètre n et génére un élément i.
S2 : Pour tout x ∈ Di , il existe un algorithme probabiliste efficace S2 qui à partir de l’indice i ∈ I génére l’élément x.
• Soit B un algorithme efficace qui à partir de tout élément i ∈ I et de tout élément x ∈ Di , calcule la valeur fi(x).
• Soit C un algorithme efficace qui inverse les fonctions fi sur une entrée de longueur i . Cependant la probabilité de trouver un antécédent de taille i de y = fi(x) est négligeable. Le schéma donné ci-dessous, nous permet de mieux comprendre le principe de la preuve.

Conclusion

Les générateurs pseudo-aléatoires possèdent de très bonnes propriétés statistiques, mais la plupart d’entre eux ne répondent pas à l’attente des applications de transmission. Ces générateurs ne peuvent également pas générer de séquence à l’abri de toute analyse statistique.
Mais on note une exception vis-à-vis des générateurs pseudo-aléatoires à base de registres filtres et pour illustrer cela nous avons décider de parler d’eux dans le chapitre qui suit.