Soutenance mémoire
L’aléa ou l’observation du phénomène aléatoire était utilisé dans le cadre de nombreuses applications et cela depuis plusieurs siècles déjà. En effet autrefois l’aléa était utilisé pour départager les hommes de manière incontestable et c’est pour cette raison qu’il était considéré comme l’élément le plus important dans les jeux de hasard. Il était également utilisé dans les processus de gestions publiques car dans l’antique démocratie athénienne certaines fonctions politiques étaient confiées à des citoyens choisis aléatoirement. Mais à partir du 20iem siècle on note l’apparition de nouvelles méthodes dites de Monte-Carlo qui à l’aide de processus aléatoire permettaient de calculer la valeur numérique d’une intégrale dont le calcul formel est quasi-impossible.
De nos jours avec les besoins de sécuriser l’information ces techniques ne sont plus utilisées et c’est dans ce contexte que Auguste Kerckhoffs proposa une règle fondamentale de la cryptographie moderne qui va marquer le début des générateurs pseudo-aléatoires. Actuellement dans un grand nombre de ces applications cryptographiques, il serait très commode mais également souhaitable que le générateur soit aussi simple que possible. Cependant les postulats de Golomb résument les propriétés de bases exigées sur une telle construction et toute séquence possédant ces propriétés est appelée une séquence pseudo-aléatoire. En effet les générateurs pseudo-aléatoires doivent passer d’autre tests statistiques comme ceux du NIST dont la base repose sur ces trois postulats.
Rappels sur Les Corps Finis
Les corps finis interviennent dans divers domaines des mathématiques et en particulier dans la théorie de Galois sur la résolution des équations algébriques. Ils sont également utilisés dans la plupart des méthodes de construction des séquences pseudoaléatoires. Ces corps sont aussi présents dans d’autres applications telles que les algorithmes de cryptographie , les codes correcteurs d’erreurs , les codes compresseurs etc….
Etude sur les corps finis
Structures Algébriques
Groupes
Définition 2.1.1. Un groupe est un ensemble non vide G muni d’une opération ◦ :
G × G −→ G
(x, y) 7−→ x ◦ y
telle que :
• ◦ est associative
∀ x , y , z ∈ G : x ◦ (y ◦ z) = (x ◦ y) ◦ z
• il existe un unique élément neutre e ∈ G tel que :
x ◦ e = e ◦ x = x , ∀ x ∈ G.
• Tout élément x ∈ G a un unique inverse x−1 ∈ G tel que :
x ◦ x−1 = x−1 ◦ x = e
Remarque. De plus le groupe (G, ◦) est dit abélien si l’opération ◦ est commutative :
x ◦ y = y ◦ x , pour tout x , y ∈ G.
Anneaux
Définition 2.1.2. Un anneau est un ensemble A muni de deux opérations + , ◦ :
A × A → A
Corps
Un corps est un anneau unitaire (K, +, ◦) tel que si on note K∗ = K\{0} , alors (K∗, ◦) est un groupe. Si (K, +, ◦) est un corps , un sous-corps de K est un sous-anneau K1 de K tel que pour tout élément non nul x ∈ K1 on a x −1 ∈ K1 ; donc (K1, +, ◦) est aussi un corps. On dit qu’un corps K est fini si son cardinal est fini.
Applications des Suites Récurrentes Linéaires
Définition 2.2.1. Une suite (Un)n d’ordre k est dite récurrente linéaire dans Fq s’il existe a0, a1, …., ak−1 , b ∈ Fq tels que pour tout entier n , on a :
Un+k = ak−1Un + …….. + a0Un+k−1 + b, ∀n ≥ 0
Exemple 2.2.1. Soit (Un)n une suite récurrente linéaire dans F2 d’ordre 4 et 2 définie par :
Un+4 = Un+1 + Un + b
ou
Un+2 = Un+1 + Un + b
avec b ∈ F2.
Remarque. Pour la définition ci-dessus on constate que :
❖ si b = 0 la relation est dite homogène et dans le cas contraire elle est dite non homogène.
❖ U0, U1, …., Uk−1 détermine l’état initial de la suite.
Exemple et Remarque
Exemple
Dans cette partie nous avions proposé un exemple expliquant les deux sous-sections élaborées tout juste au haut. En effet soit (Un)n une suite récurrente linéaire dans F2 d’ordre 4 et 2 définie par :
Un+4 = Un+1 + Un + b
ou
Un+2 = Un+1 + Un + b
avec b ∈ F2.
Leurs polynômes caractéristiques sont respectivement :
f1(x) = x4 + x + 1
f2(x) = x2 + x + 1
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.
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.
Source d’entropie physique
Une source d’entropie physique est une source due aux caractéristiques intrinsèques des systèmes physiques.
|
Table des matières
1 Introduction Générale
2 Rappels sur Les Corps Finis
2.1 Etude sur les corps finis
2.2 Applications des Suites Récurrentes Linéaires
2.3 Conception de générateurs aléatoires
3 Générateurs Pseudo-Aléatoires à Base De Registres Filtrés
3.1 Régistre à Décalage à Rétroaction Linéaire
3.2 LFSR et Cryptographie
3.3 Régistres Combinés ou Filtrés
4 Tests de Génération de Nombres Pseudo-aléatoires
4.1 Les Critères de Golomb et Test d’Hypothèse
4.2 Tests de Génération de Nombres Pseudo-Aléatoires
5 Simulation
5.1 Test de fréquence Monobit
5.2 Test de fréquence par Bloc
5.3 Test de Run
5.4 Test de Run par Bloc
5.5 Test de Rang d’une Matrice Binaire
5.6 Test de Somme Cumulative
6 Conclusion Générale
