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

Alternative Locations: http://www.imprimerie.polytechnique.fr/Theses/Files/Didier.pdf

Abstract

This thesis deals with the cryptanalysis of a simple but important
stream cipher: the filter generator.

A first approach to break such cipher is to use algebraic attacks.
For these attacks, it is important to compute efficiently the
algebraic immunity of the Boolean function used as a filter. This
quantity is closely related to the behavior of Reed-Muller codes
over the erasure channel. Using this relation, we discovered new
results that are best stated in the error correcting codes
framework. We thus build a new bound on the probability to be able
to correct a fixed number of erasures. This bound implies that the
algebraic immunity of a random function is optimal or close from it.
We also detail a new decoding method based on sparse linear algebra
algorithm like Wiedemann's one. It leads to one of the most
efficient algorithm to compute the algebraic immunity of a given
function.

A second approach is to use probabilistic attacks. For most of them,
we need to compute small weight multiples of the LFSR. We propose a
new algorithm that use discrete logarithm and is particularly
efficient for multiples of weight 4. We then describe a new attack
that use these multiples to detect the time positions for which the
inputs of the filter are all zero. At the time being, this attack is
one of the most efficient.

Table of content

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

Repository Staff Only: edit this item