Codes de Reed-Muller et cryptanalyse du registre filtré.

Accueil || Parcours || Recherche || S'enregistrer || Mon Compte || Contacts || Aide || Langues

Didier, Frédéric (2007) Codes de Reed-Muller et cryptanalyse du registre filtré. Doctorat INRIA Rocquencourt - projet SECRET, INRIA Rocquencourt - projet SECRET, EP/X p.175.

Autres Localisations: http://www.imprimerie.polytechnique.fr/Theses/Files/Didier.pdf

Résumé

Les travaux de cette thèse portent sur la cryptanalyse d'un système
de chiffrement simple, mais important : le registre filtré. Ils
concernent les deux principales familles d'attaques que sont les
attaques algébriques et les attaques probabilistes.

Pour les attaques algébriques, il est important de pouvoir calculer
efficacement l'immunité algèbrique de la fonction booléenne par
laquelle le registre est filtré. Cette quantité est intimement liée
au comportement des codes de Reed-Muller sur le canal à effacements
et son étude a permis la découverte de plusieurs résultats qui
s'expriment naturellement dans le cadre de la théorie des codes
correcteurs. Nous avons ainsi construit une nouvelle borne sur la
probabilité de pouvoir compenser un nombre d'effacements fixé. Cette
borne montre que l'immunité algébrique d'une fonction booléenne
aléatoire est presque toujours maximale. Nous avons également
explicité une méthode de décodage fondée sur des algorithmes
d'algèbre linéaire creuse (comme l'algorithme de Wiedemann) qui
donne un des algorithmes les plus efficace pour calculer l'immunité
algébrique.

Pour les attaques probabilistes, un outil très important est de
parvenir à trouver efficacement de nombreux multiples de poids
faible du registre à décalage du système. Un nouvel algorithme
fondé sur les logarithmes discrets à été proposé. Il est
particulièrement interessant pour les multiples de poids 4,
améliorant dans de nombreux cas pratiques le meilleur algorithme
connu. Ce travail s'est poursuivi par une nouvelle cryptanalyse
probabiliste du registre filtré qui utilise ces multiples de poids
faible pour reconnaître les entrées nulles de la fonction de
filtrage. Cette attaque est l'une des plus efficaces connue à
l'heure actuelle.

Table des Matières

Remerciements 7
Aperçu de la thèse 9
1 Introduction 11
1.1 Une introduction aux codes correcteurs - 11
1.2 Une introduction 'a la cryptographie - 13
1.3 Les chiffrements 'a flot - 15
1.4 G´en´erateur pseudo-al´eatoire - 17
2 R´ecurrence lin´eaire sur les corps finis 21
2.1 Les corps finis - 21
2.2 Les LFSR - 23
2.3 Quelques remarques - 27
3 Les fonctions bool´eennes 31
3.1 Un mot sur les ´el´ements de Fm
2 - 31
3.2 D´efinitions et repr´esentations - 32
3.3 La transform´ee de Walsh - 35
3.4 Les fonctions bool´eennes cryptographiques - 37
4 Cryptanalyses du registre filtr´e 41
4.1 Le registre filtr´e - 41
4.2 Recherche exhaustive et compromis temps-m´emoire - 43
4.3 Attaques par corr´elation - 45
4.4 Autres attaques - 46
5 Calcul des multiples de poids faible 49
5.1 Pr´esentation du probl'eme - 49
5.2 Algorithme de Chose Joux Mitton - 51
5.3 Utilisation des logarithmes discrets - 52
5.4 Calcul des logarithmes discrets - 55
5.5 R´esum´e - 56
6 Une nouvelle attaque sur le registre filtr´e 57
6.1 Pr´esentation de l’attaque - 57
6.2 Calcul du biais - 60
6.3 Complexit´e de l’attaque - 63
6.4 R´esum´e et performances - 65
7 Complexit´e lin´eaire 67
7.1 L’algorithme de Berlekamp-Massey - 67
7.2 Complexit´e lin´eaire du registre filtr´e - 70
7.3 L’attaque de Rønjom et Helleseth - 72
7.4 R´esum´e - 74
8 Les attaques alg´ebriques sur le registre filtr´e 77
8.1 Une id´ee qui date de Shannon - 77
8.2 L’attaque alg´ebrique standard - 79
8.3 L’attaque alg´ebrique rapide - 81
8.4 Aspect algorithmique de l’attaque rapide - 83
8.5 R´esum´e - 84
9 Les codes de Reed-Muller 85
9.1 D´efinition et premi'eres propri´et´es - 85
9.2 Autres propri´et´es - 88
9.3 Quelques algorithmes utiles - 90
10 Immunit´e alg´ebrique et code de Reed-Muller 95
10.1 Le canal 'a effacements - 95
10.2 Lien avec l’immunit´e alg´ebrique - 97
10.3 Fonctions d’immunit´e alg´ebrique maximale - 98
10.4 R´esum´e - 101
11 Probabilit´e d’erreur sur le canal 'a effacements 103
11.1 R´esultats exp´erimentaux - 103
11.2 Bornes standards de la th´eorie des codes - 106
11.3 Utilisation des distances g´en´eralis´ees - 108
11.4 Les codes 'a rendement coh´erent - 113
11.5 Application aux Reed-Muller et 'a l’immunit´e alg´ebrique . . . 117
11.6 R´esum´e - 118
12 Calcul de l’immunit´e alg´ebrique 121
12.1 Utilisation de l’alg'ebre lin´eaire - 121
12.2 Cas des attaques alg´ebriques rapides - 123
12.3 ´Etat de l’art - 125
13 V´erifier efficacement l’immunit´e alg´ebrique 129
13.1 Un premier algorithme - 130
13.2 Calcul th´eorique de la complexit´e - 134
13.3 Une version pratique - 137
13.4 Cas de l’attaque alg´ebrique rapide - 141
13.5 R´esum´e et performances - 142
14 Alg'ebre lin´eaire creuse et canal 'a effacements 145
14.1 L’algorithme de Wiedemann - 146
14.2 Conditionnement pour les matrices non carr´ees - 148
14.3 Application aux Reed-Muller et 'a l’immunit´e alg´ebrique . . . 149
14.4 R´esum´e et performances - 151
Conclusion et perspectives 155
A Transform´ee de M¨obius et de Walsh rapide 159
B Quelques r´esultats sur la loi binomiale 161
Bibliographie 165

Statistiques de consultation

Administrateurs de l'archive uniquement : éditer cet enregistrement