Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Les travaux de recherche de cette thèse s’inscrivent dans le cadre de la sécurité par chaos des réseaux locaux sans fil, en particulier les réseaux de capteurs sans fil. L’originalité de cette thèse consiste à proposer des cryptosystèmes à base de chaos plus adaptés aux réseaux de capteurs, en termes de consommation d’énergie, que les algorithmes conventionnels et à réaliser une implémentation sur une plateforme réelle. Nous présentons en premier lieu un état de l’art des réseaux, les menaces, les contraintes limitant le processus de sécurité des informations ainsi que les principales techniques de cryptographie. Nous donnons un aperçu sur la théorie de chaos et nous validons l’aspect aléatoire de plusieurs suites chaotiques par les tests statistiques du NIST. Nous proposons ensuite des nouvelles méthodes de construction de S-Box chaotiques tout en prouvant leur robustesse contre les attaques traditionnelles. Nous proposons enfin un nouvel algorithme de cryptage d’image dédié au réseau de capteurs sans fil. La validation de nos contributions est effectuée par simulation et par des mesures expérimentales sur une plateforme de réseaux de capteurs réels (SensLab). / The security of wireless sensor network is a growing field of research hampered by limited battery life time and computing constraints. The originality of this thesis is to provide Low Power chaotic cryptosystems for sensor networks more suitable than conventional algorithms and achieve an implementation on a real platform.. We present first a state of the art of wireless networks, threats and constraints of the security process as well as conventional cryptographic techniques. We give an overview of the chaos theory and we validate the randomness of several chaotic maps by the NIST statistical tests. Then, we propose new methods of chaotic S-Box construction, while demonstrating their robustness against traditional attacks. Finally, we propose a new image encryption algorithm dedicated to wireless sensor network. Validation of our contributions is performed by simulation and experimental measurements on a platform of real sensor networks (SensLab).

La démocratisation des ordinateurs, des téléphones portables et surtout de l'Internet a considérablement révolutionné le monde de la communication. Les besoins en matière de cryptographie sont donc plus nombreux et la nécessité de vérifier la sûreté des algorithmes de chiffrement est vitale. Cette thèse s'intéresse à l'étude d'une nouvelle cryptanalyse, appelée cryptanalyse logique, qui repose sur l'utilisation de la logique propositionnelle - à travers le problème de satisfaisabilité - pour exprimer et résoudre des problèmes cryptographiques. Plus particulièrement, les travaux présentés ici portent sur une certaine catégorie de chiffrements utilisés dans les protocoles d'authentification et d'intégrité de données qu'on appelle fonctions de hachage cryptographiques. Un premier point concerne l'aspect modélisation d'un problème cryptographique en un problème de satisfaisabilité et sa simplification logique. Sont ensuite présentées plusieurs façons pour utiliser cette modélisation fine, dont un raisonnement probabiliste sur les données du problème qui permet, entres autres, d'améliorer les deux principaux points d'une attaque par cryptanalyse logique, à savoir la modélisation et la résolution. Un second point traite des attaques menées en pratique. Dans ce cadre, la recherche de pré-Image pour les fonctions de hachage les plus couramment utilisées mènent à repousser les limites de la résistance de ces fonctions à la cryptanalyse logique. À cela s'ajoute plusieurs attaques pour la recherche de collisions dans le cadre de la logique propositionnelle. / Democratization of increasingly high-Performance digital technologies and especially the Internet has considerably changed the world of communication. Consequently, needs in cryptography are more and more numerous and the necessity of verifying the security of cipher algorithms is essential.This thesis deals with a new cryptanalysis, called logical cryptanalysis, which is based on the use of logical formalism to express and solve cryptographic problems. More precisely, works presented here focuses on a particular category of ciphers, called cryptographic hash functions, used in authentication and data integrity protocols.Logical cryptanalysis is a specific algebraic cryptanalysis where the expression of the cryptographic problem is done through the satisfiabilty problem, fluently called sat problem. It consists in a combinatorial problem of decision which is central in complexity theory. In the past years, works led by the scientific community have allowed to develop efficient solvers for industrial and academical problems.Works presented in this thesis are the fruit of an exploration between satisfiability and cryptanalysis, and have enabled to display new results and innovative methods to weaken cryptographic functions.The first contribution is the modeling of a cryptographic problem as a sat problem. For this, we present some rules that lead to describe easily basic operations involved in cipher algorithms. Then, a section is dedicated to logical reasoning in order to simplify the produced sat formulas and show how satisfiability can help to enrich a knowledge on a studied problem. Furthermore, we also present many points of view to use our smooth modeling to apply a probabilistic reasoning on all the data associated with the generated sat formulas. This has then allowed to improve both the modeling and the solving of the problem and underlined a weakness about the use of round constants.Second, a section is devoted to practical attacks. Within this framework, we tackled preimages of the most popular cryptographic hash functions. Moreover, the collision problem is also approached in different ways, and particularly, the one-Bloc collision attack of Stevens on MD5 was translated within a logical context. It's interesting to remark that in both cases, logical cryptanalysis takes a new look on the considered problems.

La cryptologie est une des disciplines des mathématiques, elle est composée de deux sous-ensembles: la cryptographie et la cryptanalyse. Tandis que la cryptographie s'intéresse aux algorithmes permettant de modifier une information afin de la rendre inintelligible sans la connaissance d'un secret, la seconde s'intéresse aux méthodes mathématiques permettant de recouvrer l'information originale à partir de la seule connaissance de l'élément chiffré.La cryptographie se subdivise elle-même en deux sous-ensembles: la cryptographie symétrique et la cryptographie asymétrique. La première utilise une clef identique pour les opérations de chiffrement et de déchiffrement, tandis que la deuxième utilise une clef pour le chiffrement et une autre clef, différente de la précédente, pour le déchiffrement. Enfin, la cryptographie symétrique travaille soit sur des blocs d'information soit sur des flux continus d'information. Ce sont les algorithmes de chiffrement par blocs qui nous intéressent ici.L'objectif de la cryptanalyse est de retrouver l'information initiale sans connaissance de la clef de chiffrement et ceci dans un temps plus court que l'attaque par force brute. Il existe de nombreuses méthodes de cryptanalyse comme la cryptanalyse fréquentielle, la cryptanalyse différentielle, la cryptanalyse intégrale, la cryptanalyse linéaire...Beaucoup de ces méthodes sont maintenues en échec par les algorithmes de chiffrement modernes. En effet, dans un jeu de la lance et du bouclier, les cryptographes développent des algorithmes de chiffrement de plus en plus efficaces pour protéger l'information chiffrée d'une attaque par cryptanalyse. C'est le cas notamment de l'Advanced Encryption Standard (AES). Cet algorithme de chiffrement par blocs a été conçu par Joan Daemen et Vincent Rijmen et transformé en standard par le National Institute of Standards and Technology (NIST) en 2001. Afin de contrer les méthodes de cryptanalyse usuelles les concepteurs de l'AES lui ont donné une forte structure algébrique.Ce choix élimine brillamment toute possibilité d'attaque statistique, cependant, de récents travaux tendent à montrer, que ce qui est censé faire la robustesse de l'AES, pourrait se révéler être son point faible. En effet, selon ces études, cryptanalyser l'AES se ``résume'' à résoudre un système d'équations quadratiques symbolisant la structure du chiffrement de l'AES. Malheureusement, la taille du système d'équations obtenu et le manque d'algorithmes de résolution efficaces font qu'il est impossible, à l'heure actuelle, de résoudre de tels systèmes dans un temps raisonnable.L'enjeu de cette thèse est, à partir de la structure algébrique de l'AES, de décrire son algorithme de chiffrement et de déchiffrement sous la forme d'un nouveau système d'équations booléennes. Puis, en s'appuyant sur une représentation spécifique de ces équations, d'en réaliser une analyse combinatoire afin d'y détecter d'éventuels biais statistiques. / Cryptology is one of the mathematical fields, it is composed of two subsets: cryptography and cryptanalysis. While cryptography focuses on algorithms to modify an information by making it unintelligible without knowledge of a secret, the second focuses on mathematical methods to recover the original information from the only knowledge of the encrypted element.Cryptography itself is subdivided into two subsets: symmetric cryptography and asymmetric cryptography. The first uses the same key for encryption and decryption operations, while the second uses one key for encryption and another key, different from the previous one, for decryption. Finally, symmetric cryptography is working either on blocks of information either on continuous flow of information. These are algorithms block cipher that interests us here.The aim of cryptanalysis is to recover the original information without knowing the encryption key and this, into a shorter time than the brute-force attack. There are many methods of cryptanalysis as frequency cryptanalysis, differential cryptanalysis, integral cryptanalysis, linear cryptanalysis...Many of these methods are defeated by modern encryption algorithms. Indeed, in a game of spear and shield, cryptographers develop encryption algorithms more efficient to protect the encrypted information from an attack by cryptanalysis. This is the case of the Advanced Encryption Standard (AES). This block cipher algorithm was designed by Joan Daemen and Vincent Rijmen and transformed into standard by the National Institute of Standards and Technology (NIST) in 2001. To counter the usual methods of cryptanalysis of AES designers have given it a strong algebraic structure.This choice eliminates brilliantly any possibility of statistical attack, however, recent work suggests that what is supposed to be the strength of the AES, could prove to be his weak point. According to these studies, the AES cryptanalysis comes down to ``solve'' a quadratic equations symbolizing the structure of the AES encryption. Unfortunately, the size of the system of equations obtained and the lack of efficient resolution algorithms make it impossible, at this time, to solve such systems in a reasonable time.The challenge of this thesis is, from the algebraic structure of the AES, to describe its encryption and decryption processes in the form of a new Boolean equations system. Then, based on a specific representation of these equations, to achieve a combinatorial analysis to detect potential statistical biases.

Depuis 1980, l'idée d'utiliser des systèmes chaotiques pour la conception d'algorithmes de chiffrement/déchiffrement attire de plus en plus l'attention des chercheurs. La riche dynamique des systèmes chaotiques, telle que la sensibilité aux conditions initiales et aux paramètres de contrôle, l'imprédictibilité à long terme et à large spectre, permet d'avoir de fortes propriétés telles que la "confusion" et la "diffusion". La découverte de la possibilité d'une synchronisation du chaos en 1990, a ouvert les portes d'investigation aux chiffrements chaotiques. Par ailleurs, deux approches possibles coexistes pour la conception des cryptosystèmes basés chaos : les approches analogique et numérique. Les techniques de chiffrement analogiques sont basées principalement sur la recherche d'une synchronisation des signaux chaotiques générés analogiquement. Tandis que, les techniques numériques de chiffrement chaotique ne dépendent pas d'une synchronisation chaotique et peuvent être mis en ?uvre soit sous forme logicielle ou matérielle. Plusieurs contributions ont été proposées pour la réalisation de cryptosystèmes numériques. Cependant, la plupart d'entre elles sont vulnérables et cryptanalysées. Afin de concevoir des chiffrements numériques chaotiques plus robustes et répondant aux besoins de sécurité dans les systèmes embarqués, des mécanismes originaux doivent soigneusement être considérés au cours d'une conception. Toutefois, le problème de la dégradation dynamique d'une numérisation lors de la conception des systèmes chaotiques n'a pas été sérieusement considéré par la plupart des concepteurs d'algorithmes de chiffrements numériques. D'autre part, la quasi-totalité des cryptosystèmes numériques basés chaos proposés ne traitent l'aspect pas sécurité-embarquabilité. Cette thèse se concentre sur la conception et l'implantation numérique d'un nouveau cryptosystème basé chaos, dédié aux applications embarquées temps réel. Parmi les tâches développées au cours de ces travam de thèse, on trouve les solutions adaptées et performantes de résolution de ces deux principaux inconvénients, notamment pour les applications embarquées sécurisées. Nos principales contributions sont, premièrement la conception et l'implantation sur FPGA de nouveaux générateurs de clés pseudo-aléatoires basés sur des systèmes chaotiques (continus et discrets). Deuxièmement, l'analyse statistique détaillée de la sécurité de ces générateurs. Troisièmement, la conception d'un nouveau générateur de clés de chiffrement adéquat par comparaison et son intégration dans un cryptosystème symétrique par flot, tout en y incluant la résolution du problème de la synchronisation entre un émetteur et un récepteur. Quatrièmement, la mise en ?uvre matérielle du cryptosystème proposé pour des applications réelles de cryptage/décryptage. Plus précisément, le chiffrement/déchiffrement en temps réel de données audio, image et vidéo. De plus, une évaluation des performances et une comparaison avec d'autres algorithmes basés chaos sont réalisées afin d'extraire les points faibles et forts de l'approche proposée et dont le but d'en tirer des perspectives de travaux futurs / Since 1980, the idea of using dynamic systems with chaotic behaviour for the design of encryption/decryption algorithms has attracted increasing: attention from researchers. The strong dynamics of chaotic systems such as sensitivity to initial conditions and control parameters, the unpredictability in the long term and broad-spectrum can provide important properties such as confusion and diffusion usually meet in standard cryptography. In addition, there are two possible approaches for designing chaos-based cryptosystems: analog and digital. Analog encryption techniques are primarily based on chaos-synchronization, while the chaotic digital encryption approaches do not depend on the chaos-synchronization and can be implemented either in software or hardware. This thesis focuses on the digital design and implementation of a new cryptosystem based on chaos-synchronization. The discovery of the possibility of chaos synchronization in 1990 opens the door to investigation digital chaos-based encryption. Indeed, many contributions are made for many promising achievements of digital cryptosystems. However, a number of recently proposed digital chaotic ciphers have been shown that they are not secure enough and they are cryptanalyzed. In addition, in order to design more secure digital chaotic ciphers and meet the security requirements in embedded systems, rules and new mechanisms must be carefully considered to make up the flaws in the design flow. However, the problem of the degradation dynamics of chaotic systems has not been seriously considered by most designers of digital chaotic ciphers. Furthermore, most all the digital chaos-based cryptosystems proposed in the literature does not address the issue of real-time embedded applications. Consequently, the tasks of these thesis works focus on the design solutions providing the real secure suitable for embedded applications. Our contributions in this thesis are, firstly the design and hardware implementation on reconfigurable FPGA technology of a pseudo-random key generator based on chaotic systems (continuous and discrete). Secondly, the statistical analysis detailed security of the proposed generators. Thirdly, the development, the conception and the integration of a new chaotic generator in a symmetric stream cipher, includes the resolution problem of the chaos synchronization between the transmitter (encryption) and receiver (decryption). Fourthly, the hardware implementation of the proposed cryptosystem on real encryption applications. i.e. the encryption/decryption of real-time audio, image and video data. In addition, a performance evaluation and comparisons with previous conventional and chaos-based ciphers is performed in order to extract these weaknesses and strengths and define future work prospects

De nos jours, l'emploi de la cryptographie est largement répandu et les circuits intègrent des primitives cryptographiques pour répondre à des besoins d'identification, de confidentialité, ... dans de nombreux domaines comme la communication, la PayTV, ...La sécurisation de ces circuits est donc un enjeu majeur. Les attaques par canaux cachés consistent à espionner ces circuits par différents biais comme le temps de calcul, la consommation en courant ou les émanations électromagnétiques pour obtenir des informations sur les calculs effectués et retrouver des secrets comme les clefs de chiffrement. Ces attaques ont l'avantage d'être indétectables, peu couteuses et ont fait l'objet des nombreuses études. Dans le cadre des attaques par analyse de la consommation en courant ou des émanations électromagnétiques l'acquisition de bonnes courbes est un point crucial. Malgré la forte utilisation de techniques de prétraitement dans la littérature, personne n'a tenté d'établir un modèle de fuite dans le domaine fréquentiel. Les travaux effectués durant cette thèse se concentrent donc sur cet aspect avec pour intérêt d'améliorer l'efficacité des attaques. De plus, de nouvelles attaques dans le domaine fréquentiel sont proposées, sujet peu étudié malgré l'intérêt de pouvoir exploiter plus efficacement la fuite éparpillée dans le temps. / Nowadays, the use of cryptography is widely spread, and a lot of devices provide cryptographic functions to satisfy needs such as identification, confidentiality, ... in several fields like communication, PayTV, ...Security of these devices is thus a major issue.Side Channel Attacks consist in spying a circuit through different means like the computation time, power consumption or electromagnetic emissions to get information on the performed calculus and discover secrets such as the cipher keys.These attacks have the advantage to be cheap and undetectable, and have been studied a lot.In the context of attacks analysing the power consumption or the electromagnetic emissions, the acquisition of good traces is a crucial point.Despite the high use of preprocessing techniques in the literature, nobody has attempted to model the leakage in the frequency domain.The works performed during this thesis are focusing on this topic with the motivation of improving the efficiency of attacks.What's more, new frequency domain attacks are proposed, subject poorly studied despite the advantage of better exploiting the leakage spread in time.

Cette thèse est composée de deux axes principaux, le premier portant sur le chiffrement homomorphe et le second sur l’algèbre linéaire creuse sur corps finis. Avec l’essor des technologies de communication et en particulier d’internet, de nouveaux protocoles de chiffrement sont développés. En particulier, le besoin de systèmes de chiffrement permettant de manipuler les données chiffrées tout en assurant leur sécurité. C’est dans ce contexte que des systèmes de chiffrement homomorphe sont développés, ces protocoles permettent d’effectuer des calculs avec des données chiffrées. La sécurité de ce type système repose sur l’ajout de bruit aux messages à chiffrer. Ce bruit augmente avec chaque opération effectuée, mais il ne doit pas dépasser un certain seuil. Pour contourner ce problème, une technique nommée bootstrapping est utilisée permettant de réduire le bruit d’un chiffré. Les bootstrappings sont le goulot d’étranglement lors des calculs sur des données chiffrées, il est important d’en faire le moins possible. Or la quantité de bootstrappings à faire est déterminée par la nature des calculs à effectuer ainsi que du protocole de chiffrement utilisé.C’est dans ce contexte que notre travail intervient, nous proposons une méthode effective pour réduire le nombre bootstrappings basé sur la programmation linéaire en nombre entier. Cette méthode s’adapte à un grand nombre de protocoles de chiffrement. De plus, nous effectuons une analyse de la complexité de ce problème en montrant qu’il est APX-complet et nous fournissons un algorithme d’approximation.La résolution de système linéaire sur corps finis est une brique de calcul essentielle dans de nombreux problèmes de calcul formel. En particulier, beaucoup de problèmes produisent des matrices comprenant un grand nombre de zéros, on dit qu’elles sont creuses. Les meilleurs algorithmes permettant de résoudre ce type de système linéaire creux sont des algorithmes dits itératifs. L’opération fondamentale de ces algorithmes itératifs est la multiplication de la matrice par un vecteur ou une matrice dense. Afin d’obtenir les meilleures performances, il est important de tenir compte des propriétés (SIMD, multicoeurs, hiérarchie des caches ....) des processus modernes .C’est dans ce contexte que notre travail intervient, nous étudions la meilleure façon d’implanter efficacement cette opération sur les processeurs récents.Nous proposons un nouveau format permettant de tenir compte du grand nombre de +- 1 présents dans une matrice.Nous proposons une implantation parallèle basée sur le paradigme du vol de tâche offrant un meilleur passage à l’échelle que le parallélisme par threads.Nous montrons comment exploiter au mieux les instructions SIMD des processeurs dans les différentes opérations.Finalement, nous proposons une méthode efficace permettant d’effectuer cette opération lorsque le corps finis est multiprécision (les éléments sont stockés sur plusieurs mots machine) en ayant recours au système de représentation RNS. / This thesis is composed of two independent parts.The first one is related to homomorphic encryption and the second part deal with sparse linear algebra on finite fields.Homomorphic encryption extends traditional encryption in the sense that it becomes feasible to perform operations on ciphertexts, without the knowledge of the secret decryption key. As such, it enables someone to delegate heavy computations on his sensitive data to an untrusted third party, in a secure way. More precisely, with such a system, one user can encrypt his sensitive data such that the third party can evaluate a function on the encrypted data, without learning any information on the underlying plain data. Getting back the encrypted result, the user can use his secret key to decrypt it and obtain, in clear, the result of the evaluation of the function on his sensitive plain data. For a cloud user, the applications are numerous, and reconcile both a rich user experience and a strong privacy protection.The first fully homomorphic encryption (FHE) scheme, able to handle an arbitrary number of additions and multiplications on ciphertexts, has been proposed by Gentry in 2009.In homomorphic encryption schemes, the executed function is typically represented as an arithmetic circuit. In practice, any circuit can be described as a set of successive operation gates, each one being either a sum or a product performed over some ring.In Gentry’s construction, based on lattices, each ciphertext is associated with some noise, which grows at each operation (addition or multiplication) done throughout the evaluation of the function. When this noise reaches a certain limit, decryption is not possible anymore.To overcome this limitation, closely related to the number of operations that the HE.Eval procedure can handle, Gentry proposed in a technique of noise refreshment called“bootstrapping”.The main idea behind this bootstrapping procedure is to homomorphically run the decryptionprocedure of the scheme on the ciphertext, using an encrypted version of the secret key. In this context, our contribution is twofold. We first prove that the lmax-minimizing bootstrapping problem is APX-complete and NP-complete for lmax ≥ 3. We then propose a new method to determine the minimal number of bootstrappings needed for a given FHE scheme and a given circuit.We use linear programming to find the best outcome for our problem. The main advantage of our method over the previous one is that it is highly flexible and can be adapted for numerous types of homomorphic encryption schemes and circuits.Computing a kernel element of a matrix is a fundamental kernel in many computer algebra and cryptography algorithms. Especially, many applications produces matrices with many matrix elements equals to 0.Those matrices are named sparse matrices. Sparse linear algebra is fundamentally relying on iterative approaches such as Wiedemann or Lanczos. The main idea is to replace the direct manipulation of a sparse matrix with its Krylov subspace. In such approach, the cost is therefore dominated by the computation of the Krylov subspace, which is done by successive product of a matrix by a vector or a dense matrix.Modern processor unit characteristics (SIMD, multicores, caches hierarchy, ...) greatly influence algorithm design.In this context our work deal with the best approach to design efficient implementation of sparse matrix vector product for modern processors.We propose a new sparse matrix format dealing with the many +-1 matrix elements to improve performance.We propose a parallel implementation based on the work stealing paradigm that provide a good scaling on multicores architectures.We study the impact of SIMD instructions on sparse matrix operations.Finally, we provide a modular arithmetic implementation based on residue number system to deal with sparse matrix vector product over multiprecision finite fields.

Le problème du calcul d'isogénies est apparu dans l'algorithme SEA de comptage de points de courbes elliptiques définies sur des corps finis. L'apparition de nouvelles applications du calcul d'isogénies (crypto système à trappe, fonction de hachage, accélération de la multiplication scalaire, crypto système post quantique) ont motivé par ailleurs la recherche d'algorithmes plus rapides en dehors du contexte SEA. L'algorithme de Couveignes (1996), malgré ses améliorations par De Feo (2011), présente la meilleure complexité en le degré de l'isogénie mais ne peut s'appliquer dans le cas de grande caractéristique.L'objectif de cette thèse est donc de présenter une modification de l'algorithme de Couveignes (1996) utilisable en toute caractéristique avec une complexité en le degré de l'isogénie similaire à celui de Couveignes (1996).L'amélioration de l'algorithme de Couveignes (1996) se fait à travers deux axes: la construction de tours d'extensions de degré $ell$ efficaces pour rendre les opérations plus rapides, à l'image des travaux de De Feo (2011), et la détermination d'ensemble de points d'ordre $ell^k$ stables sous l'action d'isogénies.L'apport majeur de cette thèse est fait sur le second axe pour lequel nous étudions les graphes d'isogénies dans lesquels les points représentent les courbes elliptiques et les arrêtes représentent les isogénies. Nous utilisons pour notre travail les résultats précédents de Kohel (1996), Fouquet et Morain (2001), Miret emph{et al.} (2005,2006,2008), Ionica et Joux (2001). Nous présentons donc dans cette thèse, à l'aide d'une étude de l'action du Frobenius sur les points d'ordre $ell^k$, un nouveau moyen de déterminer les directions dans le graphe (volcan) d'isogénies. / Isogeny computation problem appeared in the SEA algorithm to count the number of points on an elliptic curve defined over a finite field. Algorithms using ideas of Elkies (1998) solved this problem with satisfying results in this context. The appearance of new applications of the isogeny computation problem (trapdoor crypto system, hash function, scalar multiplication acceleration, post quantic crypto system) motivated the search for a faster algorithm outside the SEA context. Couveignes's algorithm (1996) offers the best complexity in the degree of the isogeny but, despite improvements by DeFeo (2011), it proves being unpractical with great characteristic.The aim of this work is to present a modified version of Couveignes's algorithm (1996) that maintains the same complexity in the degree of the isogeny but is practical with any characteristic.Two approaches contribute to the improvement of Couveignes's algorithm (1996) : firstly, the construction of towers of degree $ell$ extensions which are efficient for faster arithmetic operations, as used in the work of De Feo (2011), and secondly, the specification of sets of points of order $ell^k$ that are stable under the action of isogenies.The main contribution of this document is done following the second approach. Our work uses the graph of isogeny where the vertices are elliptic curves and the edges are isogenies. We based our work on the previous results of David Kohel (1996), Fouquet and Morain (2001), Miret emph{& al.} (2005,2006,2008), Ionica and Joux (2001). We therefore present in this document, through the study of the action of the Frobenius endomorphism on points of order $ell^k$, a new way to specify directions in the isogeny graph (volcano).

La cryptographie ADN est un domaine nouveau et prometteur pour la sécurité de l'information. C'est une combinaison des solutions classiques de cryptographie avec les avantages du matériel génétique. En effet, il est possible de bénéficier des avantages des systèmes cryptographiques classiques et de les rendre plus efficaces sur certaines méthodes grâce à l’utilisation de l'ADN. Il y a différentes façons d'utiliser l'ADN pour sécuriser le contenu de l'information. Cette thèse propose deux solutions différentes pour utiliser l'ADN dans la cryptographie : sous sa forme biologique ou alors sous forme numérique. D ‘une part, l'ADN biologique peut être utilisé pour le stockage et pour cacher des données à l'intérieur de celui-ci. L'information secrète est placée dans une molécule de l'ADN et caché parmi d'autres molécules d'ADN. D’autre part, les nombres aléatoires peuvent être générés à partir de séquences numériques d'ADN. Ils représentent une solution pour la génération et la transmission des clés OTP (One-Time-Pad) symétriques. La transmission d'une très longue clé de cryptage n'est pas nécessaire, car chaque séquence possède un numéro d'identification unique dans la base de données. Ce numéro, ou une combinaison de ces numéros, peut alors être transmis. Enfin, la sécurité et la compression sont très importantes lors de la transmission et du stockage des données informatiques. Cependant, la plupart des systèmes de cryptage peuvent augmenter la taille des données, ou encore augmenter la complexité calcul. Ces inconvénients peuvent être résolus en combinant la compression de données avec le cryptage dans un seul processus ou en effectuant le cryptage sélectif des données. / DNA cryptography is a new and promising field in information security. It combines classical solutions in cryptography with the strength of the genetic material. By introducing DNA into the common symmetric key cryptography, it is possible to benefit from the advantages of the classical cryptosystems and solve some of its limitations. There are different ways how DNA can be used to secure information content. It is about using the biological medium of DNA for storing and hiding data. Secret information can be placed in microscopic size of DNA and hidden among a great amount of other DNA structures. Biomolecular computation is possible with specially designed DNA structures. Random numbers can be generated from DNA sequences which can be found in genetic databases in digital form. Genetic databases represent a feasible solution to the One-Time-Pad (OTP) symmetric key generation and transmission problem. The one-time use is ensured due to the great variety of the publicly available, very long (thousands of bases) sequences. Transmission of a very long key is not required because each sequence has a unique identification number in the database and this number can be sent instead. Compression along with information security have always been topics of interest because, as technology advances, the amount of data that is desired to be transmitted, stored, or used in real time applications is becoming greater. Some of the encryption schemes can increase the size of the data, or bring unwanted additional computations. These drawbacks can be solved by several techniques to combine compression with encryption in one process or by performing a selective encryption of the data.