Cryptosystems are used to provide security in communications and data transmissions. Stream ciphers are private key systems that are often used to transform large volumn data. In order to have security, key streams used in stream ciphers must be fully analyzed so that they do not contain specific patterns, statistical infomation and structures with which attackers are able to quickly recover the entire key streams and then break down the systems. Based on different schemes to generate sequences and different ways to represent them, there are a variety of stream cipher analyses. The most important one is the linear analysis based on linear feedback shift registers (LFSRs) which have been extensively studied since the 1960's. Every sequence over a finite field has a well defined linear complexity. If a sequence has small linear complexity, it can be efficiently recoverd by Berlekamp-Messay algorithm. Therefore, key streams must have large linear complexities. A lot of work have been done to generate and analyze sequences that have large linear complexities. In the early 1990's, Klapper and Goresky discovered feedback with carry shift registers over Z/(p) (p-FCSRS), p is prime. Based on p-FCSRs, they developed a stream cipher analysis that has similar properties to linear analysis. For instance, every sequence over Z/(p) has a well defined p-adic complexity and key streams of small p-adic complexity are not secure for use in stream ciphers. This disstation focuses on stream cipher analysis based on feedback with carry shift registers. The first objective is to develop a stream cipher analysis based on feedback with carry shift registers over Z/(N) (N-FCSRs), N is any integer greater than 1, not necessary prime. The core of the analysis is a new rational approximation algorithm that can be used to efficiently compute rational representations of eventually periodic N-adic sequences. This algorithm is different from that used in $p$-adic sequence analysis which was given by Klapper and Goresky. Their algorithm is a modification of De Weger's rational approximation algorithm. The second objective is to generalize feedback with carry shift register architecture to more general algebraic settings which are called algebraic feedback shift registers (AFSRs). By using algebraic operations and structures on certain rings, we are able to not only construct feedback with carry shift registers, but also develop rational approximation algorithms which create new analyses of stream ciphers. The cryptographic implication of the current work is that any sequences used in stream ciphers must have large N-adic complexities and large AFSR-based complexities as well as large linear complexities.

Les travaux réalisés au cours de cette thèse se situent au carrefour de la cryptographie symétrique et du monde des environnements contraints. Le but de cette cryptographie, dite cryptographie à bas coût, est de fournir et d'évaluer des algorithmes symétriques pouvant être implémentés sur des systèmes très limités en ressources. Les contributions de cette thèse portent d'une part sur l'évaluation de la sécurité des registres à décalage à rétroaction avec retenue (FCSR) face à de nouvelles attaques et d'autre part sur une vision unifiée des différents schémas de Feistel généralisés (GFN) qui permet de mieux cerner leurs propriétés cryptographiques. Ces études ont donné lieu à deux nouveaux algorithmes à bas coût~; d'une part GLUON une fonction de hachage à base de FCSR et d'autre part le chiffrement LILLIPUT basé sur une famille étendant plus avant la notion de GFN. Enfin, une méthode générique permettant de réaliser des attaques différentielles en fautes sur des GFN est esquissée. / The work done during this Ph.D. lies at the crossroads of symmetric cryptography and constraints environments. The goal of such cryptography, called lightweight cryptography, is to propose and evaluate symmetric algorithms that can be implemented on very ressource limited devices. The contributions of this thesis are first on the security evaluations of feedback with carry shift registers (FCSR) to some new attacks and second on a unified vision of generalized Feistel networks (GFNs) that allows to better understand their cryptographic properties. These studies gave rise to two new lightweight algorithms: first GLUON a hash function based upon FCSRs and second the cipher LILLIPUT based on a family further extanding the notion of generalized Feistel network. Finally, a generic method for carrying out a differential fault attack on GFNs is outlined.