Search

This thesis adresses two different aspects of cryptology: the design of new ciphers and the cryptanalysis of existing systems. The first part deals with permutation polynomials. We first introduce the basic properties of those objects before presenting the different known classes of such polynomials. We will also consider the problem of the repartition of those polynomials Finally we will review different situations where those polynomials occur in cryptology. We will especially detail the link with APN functions. The second part deals with the cryptanalysis of a classic cipher design: combined registers. After presenting the necessary theoretical and the existing cryptanalysis, we will present our results. Attacking those system is usually done in two phases: an offline precalculus followed by the active attack. We will propose improvements for each of those two phases.; Cette thèse se décompose en deux parties qui correspondent à deux aspect de la cryptologie avec d'une part la conception de nouvelles méthodes de chiffrement et d'autre part la cryptanalyse des systèmes existants. La première partie est consacrée à l'étude des polynômes de permutation. Après avoir introduit les propriétés élémentaires de ces objets mathématiques, nous tenterons de donner un aperçu aussi large que possible des différentes familles connues. Nous verrons aussi quelle est la répartition des polynômes de permutation. Nous détaillerons ensuite plusieurs situations où ces polynômes interviennent en cryptologie. En particulier, nous développerons le lien avec les fonctions APN. La seconde partie traite de la cryptanalyse d'un système de chiffrement classique: le générateur par combinaison. Après avoir rappelé les bases théoriques nécessaires à l'étude de ces systèmes ainsi que les techniques de cryptanalyse existante, nous présenterons nos résultats. L'attaque de ces systèmes se décompose en deux phases: une phase de précalcul, puis la phase active de l'attaque. Nous proposerons pour chacune de ces deux étapes des améliorations.

This thesis adresses two different aspects of cryptology: the design of new ciphers and the cryptanalysis of existing systems. The first part deals with permutation polynomials. We first introduce the basic properties of those objects before presenting the different known classes of such polynomials. We will also consider the problem of the repartition of those polynomials Finally we will review different situations where those polynomials occur in cryptology. We will especially detail the link with APN functions. The second part deals with the cryptanalysis of a classic cipher design: combined registers. After presenting the necessary theoretical and the existing cryptanalysis, we will present our results. Attacking those system is usually done in two phases: an offline precalculus followed by the active attack. We will propose improvements for each of those two phases.; Cette thèse se décompose en deux parties qui correspondent à deux aspect de la cryptologie avec d'une part la conception de nouvelles méthodes de chiffrement et d'autre part la cryptanalyse des systèmes existants. La première partie est consacrée à l'étude des polynômes de permutation. Après avoir introduit les propriétés élémentaires de ces objets mathématiques, nous tenterons de donner un aperçu aussi large que possible des différentes familles connues. Nous verrons aussi quelle est la répartition des polynômes de permutation. Nous détaillerons ensuite plusieurs situations où ces polynômes interviennent en cryptologie. En particulier, nous développerons le lien avec les fonctions APN. La seconde partie traite de la cryptanalyse d'un système de chiffrement classique: le générateur par combinaison. Après avoir rappelé les bases théoriques nécessaires à l'étude de ces systèmes ainsi que les techniques de cryptanalyse existante, nous présenterons nos résultats. L'attaque de ces systèmes se décompose en deux phases: une phase de précalcul, puis la phase active de l'attaque. Nous proposerons pour chacune de ces deux étapes des améliorations.

We present one of the most efficient attacks against the combination generator. This attack is inherent to this system as its only assumption is that the filtering function has a good autocorrelation. This is usually the case if the system is designed to be resistant to other kinds of attacks. We use only classical tools, namely vectorial correlation, weight 4 multiples and Walsh transform.

Finding low-weight multiples of a binary polynomial is a difficult problem arising in the context of stream ciphers cryptanalysis. The classical algorithm to solve this problem is based on a time memory trade-off. We will present an improvement to this approach using discrete logarithm rather than a direct representation of the involved polynomials. This gives an algorithm which improves the theoretical complexity, and is also very flexible in practice.

We investigate some open problems on Almost Perfect Nonlinear (APN) functions over a finite field of characteristic $2$. We provide new characterizations of APN functions and of APN permutations by means of their component functions. We generalize some results of Nyberg (1994) and strengthen a conjecture on the upper bound of nonlinearity of APN functions. We also focus on the case of quadratic functions. We contribute to the current works on APN quadratic functions, by proving that a large class of quadratic functions cannot be APN.