Boîtes de substitutions : courbes hyperelliptiques et algorithmes de minimalisation
Institution:
Université Joseph Fourier (Grenoble)Disciplines:
Directors:
Abstract EN:
Ln this thesis, the airn is the optimisation ofkey tools usually used in blocks cyphers: substitution boxes. The goal is the optimization of their linear and differential resistance and their protection against algebraic attacks, developped by ! N. Courtois and 1. Pieprzyk, which are a potential weakness of the AES (Advanced Encryption System). Various means of optimization are studied. First, the generalisation of elliptic substitution boxes developped by R. Gillard and F. Leprevost to hyperelliptic curves leads to similar results, but increased the space of research. Secondly, we develop minirnalisation algorithms of substitution boxes, relatively to linear and differential resistance. A greedy heuristic and clever choices of permutations leads to results close to the substitution box of the AES.
Abstract FR:
Les travaux effectués au cours de cette thèse portent sur l'optimisation de boîtes de substitutions vis à vis de la cryptanalyse linéaire et différentielle. Parallèlement à ceci, le but est de les rendre résistantes aux attaques algébriql ! telles que celles proposées par N. Courtois et 1. Pieprzyk, et ainsi de combler une faiblesse potentielle de l'AES. Pour cela, on explore diverses pistes. Dans un premier temps, la généralisation des boîtes de substitution elliptiques proposées par R. Gillard et F. Leprevost aux courbes hyperelliptiques permet d'augmenter sensiblement l'espace de recherche de boîtes de substitutions satisfaisantes et conduit à des résultats similaires. Dans un second temps, des algorithmes de minimalisation de boîtes de substitutions vis à vis des paramètres de résistance linéaire et différentielle permettent, à l'aide de stratégies gloutonnes et de permutations judicieusement choisies, d'obtenir des résultats qui s'approchent de la boîte de substitution de l'AES.