Σε αυτή τη Μεταπτυχιακή Διπλωματική Εργασία γίνεται μία προσπάθεια κατασκευής ασφαλέστερων block ciphers (Κεφ.1). Αρχικώς παρουσιάζουμε αναλυτικά το θεωρητικό υπόβαθρο της Γραμμικής Κρυπτανάλυσης (Κεφ.2) και της Διαφορικής Κρυπτανάλυσης (Κεφ.3). Στη συνέχεια, προχωρούμε σε μια εφαρμογή της Γραμμικής και Διαφορικής Κρυπτανάλυσης στον αλγόριθμο CAST-128 (Κεφ.4), που είναι ένας σύγχρονος block cipher αλγόριθμος. Στο Κεφ.5 αναφερόμαστε στις σχεδιαστικές παραμέτρους ενός block cipher (S-box Design, Framework Κρυπτογραφήματος, Key Schedule και Round Function). Η συμβολή μας συνίσταται στην κατασκευή κρυπτογραφικά ασφαλών S-boxes με τη χρήση Bent συναρτήσεων και συναρτήσεων Maiorana και η μελέτη της μη γραμμικότητας του προκύπτοντος κρυπτοσυστήματος (Κεφ.6). Στο τελευταίο κεφάλαιο (Κεφ.7) αναφερόμαστε στις μελλοντικές προεκτάσεις και στο ερευνητικό πλάνο που έχουμε θέσει με αφετηρία αυτή τη Μεταπτυχιακή Διπλωματική Εργασία. Στο Παράρτημα Α παραθέτουμε τον Κώδικα Υλοποίησης της κατασκευής των S-boxes. / In this Master Thesis we make an attempt to construct secure block ciphers (Chap.1). First of all, we present in details the theoretical background of Linear Cryptanalysis (Chap.2) and Differential Cryptanalysis (Chap.3). Then we apply Linear and Differential Cryptanalysis in CAST-128 algorithm (Chap.4), which is a modern block cipher algorithm. In Chap.5 we present the design parameters of a block cipher (S-box Design, Feistel Framework, Key Schedule and Round Function). Our contribution is the construction of cryptographically secure S-boxes using Bent Functions and Maiorana Functions and also we study the non-linearity of the constructed cryptosystem (Chap.6). In the last Chapter (Chap.7) we present our future research plan, based on this Master Thesis. The Source Code of the S-boxes construction can be found in Appendix A.

Le but de cette thèse est l'étude des Automates Cellulaires (AC) dans la perspective des fonctions booléennes et des dessins combinatoires. Au-delà de son intérêt théorique, cette recherche est motivée par ses applications à la cryptographie, puisque les fonctions booléennes et les dessins combinatoires sont utilisés pour construire des générateurs de nombres pseudo aléatoires (Pseudorandom Number Generators, PRNG) et des schémas de partage de secret (Secret Sharing Schemes, SSS). Les résultats présentés dans la thèse ont été développés sur trois lignes de recherche, organisées comme suit. La première ligne porte sur l'utilisation des algorithmes d'optimisation heuristique pour chercher des fonctions booléennes ayant des bonnes propriétés cryptographiques, à utiliser comme des règles locales dans des PRNG basés sur les AC. La motivation principale est l'amélioration du générateur de Wolfram basé sur la règle 30, qui a été montré être vulnérable vis à vis de deux attaques cryptanalytiques. La deuxième ligne s'occupe des fonctions booléennes vectorielles engendrées par les règles globales des AC. La première contribution considère la période des pré-images des configurations spatialement périodiques dans les AC surjectifs, et l'analyse des propriétés cryptographiques des règles globales des AC. La troisième ligne se concentre sur les dessins combinatoires engendrés par les AC, en considérant les Carrés Latins Orthogonaux (Orthogonal Latin Squares, OLS), qui sont équivalents aux SSS. En particulier, on donne une caractérisation algébrique des OLS engendrés par les AC linéaires, et on utilise des algorithmes heuristiques pour construire des OLS basés sur des AC non linéaires. / The goal of this thesis is the investigation of Cellular Automata (CA) from the perspective of Boolean functions and combinatorial designs. Beside its theoretical interest, this research finds its motivation in cryptography, since Boolean functions and combinatorial designs are used to construct Pseudorandom Number Generators (PRNG) and Secret Sharing Schemes (SSS). The results presented in the thesis are developed along three research lines, organized as follows. The first line considers the use of heuristic optimization algorithms to search for Boolean functions with good cryptographic properties, to be used as local rules in CA-based PRNG. The main motivation is to improve Wolfram's generator based on rule 30, which has been shown to be vulnerable against two cryptanalytic attacks. The second line deals with vectorial Boolean functions induced by CA global rules. The first contribution considers the period of preimages of spatially periodic configurations in surjective CA, and analyze the cryptographic properties of CA global rules. The third line focuses on the combinatorial designs generated by CA, specifically considering Orthogonal Latin Squares (OLS), which are equivalent to SSS. In particular, an algebraic characterization of OLS generated by linear CA is given, and heuristic algorithms are used to build OLS based on nonlinear CA.

Block and stream ciphers are widely used to protect the privacy of digital information. A variety of attacks against block and stream ciphers exist; the most recent being the algebraic attacks. These attacks reduce the cipher to a simple algebraic system which can be solved by known algebraic techniques. These attacks have been very successful against a variety of stream ciphers and major efforts (for example eSTREAM project) are underway to design and analyze new stream ciphers. These attacks have also raised some concerns about the security of popular block ciphers. In this thesis, apart from designing new stream ciphers, we focus on analyzing popular nonlinear transformations (Boolean functions and S-boxes) used in block and stream ciphers for various cryptographic properties, in particular their resistance against algebraic attacks. The main contribution of this work is the design of two new stream ciphers and a thorough analysis of the algebraic immunity of Boolean functions and S-boxes based on power mappings. First we present WG, a family of new stream ciphers designed to obtain a keystream with guaranteed randomness properties. We show how to obtain a mathematical description of a WG stream cipher for the desired randomness properties and security level, and then how to translate this description into a practical hardware design. Next we describe the design of a new RC4-like stream cipher suitable for high speed software applications. The design is compared with original RC4 stream cipher for both security and speed. The second part of this thesis closely examines the algebraic immunity of Boolean functions and S-boxes based on power mappings. We derive meaningful upper bounds on the algebraic immunity of cryptographically significant Boolean power functions and show that for large input sizes these functions have very low algebraic immunity. To analyze the algebraic immunity of S-boxes based on power mappings, we focus on calculating the bi-affine and quadratic equations they satisfy. We present two very efficient algorithms for this purpose and give new S-box constructions that guarantee zero bi-affine and quadratic equations. We also examine these S-boxes for their resistance against linear and differential attacks and provide a list of S-boxes based on power mappings that offer high resistance against linear, differential, and algebraic attacks. Finally we investigate the algebraic structure of S-boxes used in AES and DES by deriving their equivalent algebraic descriptions.

Block and stream ciphers are widely used to protect the privacy of digital information. A variety of attacks against block and stream ciphers exist; the most recent being the algebraic attacks. These attacks reduce the cipher to a simple algebraic system which can be solved by known algebraic techniques. These attacks have been very successful against a variety of stream ciphers and major efforts (for example eSTREAM project) are underway to design and analyze new stream ciphers. These attacks have also raised some concerns about the security of popular block ciphers. In this thesis, apart from designing new stream ciphers, we focus on analyzing popular nonlinear transformations (Boolean functions and S-boxes) used in block and stream ciphers for various cryptographic properties, in particular their resistance against algebraic attacks. The main contribution of this work is the design of two new stream ciphers and a thorough analysis of the algebraic immunity of Boolean functions and S-boxes based on power mappings. First we present WG, a family of new stream ciphers designed to obtain a keystream with guaranteed randomness properties. We show how to obtain a mathematical description of a WG stream cipher for the desired randomness properties and security level, and then how to translate this description into a practical hardware design. Next we describe the design of a new RC4-like stream cipher suitable for high speed software applications. The design is compared with original RC4 stream cipher for both security and speed. The second part of this thesis closely examines the algebraic immunity of Boolean functions and S-boxes based on power mappings. We derive meaningful upper bounds on the algebraic immunity of cryptographically significant Boolean power functions and show that for large input sizes these functions have very low algebraic immunity. To analyze the algebraic immunity of S-boxes based on power mappings, we focus on calculating the bi-affine and quadratic equations they satisfy. We present two very efficient algorithms for this purpose and give new S-box constructions that guarantee zero bi-affine and quadratic equations. We also examine these S-boxes for their resistance against linear and differential attacks and provide a list of S-boxes based on power mappings that offer high resistance against linear, differential, and algebraic attacks. Finally we investigate the algebraic structure of S-boxes used in AES and DES by deriving their equivalent algebraic descriptions.

Boolean functions are an important area of study for cryptography. These functions, consisting merely of one's and zero's, are the heart of numerous cryptographic systems and their ability to provide secure communication. Boolean functions have application in a variety of such systems, including block ciphers, stream ciphers and hash functions. The continued study of Boolean functions for cryptography is therefore fundamental to the provision of secure communication in the future. This thesis presents an investigation into the analysis of Boolean functions and in particular, analysis of affine transformations with respect to both the design and application of Boolean functions for cryptography. Past research has often been limited by the difficulties arising from the magnitude of the search space. The research presented in this thesis will be shown to provide an important step towards overcoming such restrictions and hence forms the basis for a new analysis methodology. The new perspective allows a reduced view of the Boolean space in which all Boolean functions are grouped into connected equivalence classes so that only one function from each class need be established. This approach is a significant development in Boolean function research with many applications, including class distinguishing, class structures, self mapping analysis and finite field based s-box analysis. The thesis will begin with a brief overview of Boolean function theory; including an introduction to the main theme of the research, namely the affine transformation. This will be followed by the presentation of a fundamental new theorem describing the connectivity that exists between equivalence classes. The theorem of connectivity will form the foundation for the remainder of the research presented in this thesis. A discussion of efficient algorithms for the manipulation of Boolean functions will then be presented. The ability of Boolean function research to achieve new levels of analysis and understanding is centered on the availability of computer based programs that can perform various manipulations. The development and optimisation of efficient algorithms specifically for execution on a computer will be shown to have a considerable advantage compared to those constructed using a more traditional approach to algorithm optimisation. The theorem of connectivety will be shown to be fundamental in the provision many avenues of new analysis and application. These applications include the first non-exhaustive test for determining equivalent Boolean functions, a visual representation of the connected equivalence class structure to aid in the understanding of the Boolean space and a self mapping constant that enables enumeration of the functions in each equivalence class. A detailed survey of the classes with six inputs is also presented, providing valuable insight into their range and structure. This theme is then continued in the application Boolean function construction. Two important new methodologies are presented; the first to yield bent functions and the second to yield the best currently known balanced functions of eight inputs with respect to nonlinearity. The implementation of these constructions is extremely efficient. The first construction yields bent functions of a variety of algebraic order and inputs sizes. The second construction provides better results than previously proposed heuristic techniques. Each construction is then analysed with respect to its ability to produce functions from a variety of equivalence classes. Finally, in a further application of affine equivalence analysis, the impact to both s-box design and construction will be considered. The effect of linear redundancy in finite field based s-boxes will be examined and in particular it will be shown that the AES s-box possesses complete linear redundancy. The effect of such analysis will be discussed and an alternative construction to s-box design that ensures removal of all linear redundancy will be presented in addition to the best known example of such an s-box.

Nous avons développé un cryptosystème à clé symétrique hautement sécuritaire qui est basé sur un réseau de substitutions et de permutations. Il possède deux particularités importantes. Tout d'abord, il utilise de très grandes S-Boxes incompressibles dont la taille peut varier entre 256 Kb et 32 Gb bits d'entrée et qui sont générées aléatoirement. De plus, la phase de permutation est effectuée par un ensemble de fonctions linéaires choisies aléatoirement parmi toutes les fonctions linéaires possibles. Chaque fonction linéaire est appliquée sur tous les bits du bloc de message. Notre protocole possède donc une structure simple qui garantit l'absence de portes dérobées. Nous allons expliquer que notre cryptosystème résiste aux attaques actuellement connues telles que la cryptanalyse linéaire et la cryptanalyse différentielle. Il est également résistant à toute forme d'attaque basée sur un biais en faveur d'une fonction simple des S-Boxes. / We developed a new symmetric-key algorithm that is highly secure. Our algorithm is SPN-like but with two main particularities. First of all, we use very large random incompressible s-boxes. The input size of our s-boxes vary between 256 Kb and 32 Gb.Secondly, for the permutation part of the algorithm, we use a set of random linear functions chosen uniformly and randomly between every possible fonctions. The input of these functions is all the bits of the block of messages to encode. Our system has a very simple structure that guarantees that there are no trap doors in it. We will explain how our algorithm is resistant to the known attacks, such as linear and differential cryptanalysis. It is also resistant to any attack based on a bias of the s-boxes to a simple function.