Actuellement, la technologie RFID (Radio Frequency Identification) est utilisée dans plusieurs domaines d'applications allant de l'identification dans les chaines d'approvisionnement à l'authentification dans les applications les plus sensibles telles que: les titres de transport, la médicine, les systèmes de surveillance, les cartes de crédit ou encore le passeport biométrique. Cependant, la nature sans-fil des données échangées rend cette technologie vulnérable à un certain nombre d'attaques et de nouvelles menaces. Ceci, engendre deux principaux problèmes à savoir; celui lié à la sécurité des informations échangées et celui lié à l'atteinte à la vie privée du propriétaire de l'étiquette. Par conséquent, cette technologie nécessite l'emploi de mécanismes de sécurité pour lutter contre tout type d'attaque et menace, ce qui peut se donner par le service authentification. Néanmoins, il se trouve que les étiquettes RFID imposent de fortes contraintes en termes de ressources matérielles telles que le temps de calcul, l'espace de stockage et l'énergie consommée et communication, ainsi, les primitives cryptographiques classiques telles que l'AES (Advanced Encryption Standard), le RSA (Rivest, Shamir and Adleman), etc. ne peuvent plus être employées. C'est pourquoi, dans la plupart des applications RFID, que nous retrouvons sur le marché, adoptent la cryptographie légère ou ultralégère (à faible coût) qui s'avère la principale solution pour résoudre le problème de capacité limitée, mais son limitation réside dans son niveau de sécurité. Ainsi, avec les moyens de calcul que nous disposons aujourd'hui, ces systèmes deviennent de plus en plus vulnérables à un nombre important d'attaques, d'où la nécessité de chercher des primitives cryptographiques qui soient à la fois robustes et sûres envers tout type d'attaques et en conformités avec contraintes imposées par les étiquettes RFID. Par conséquent, l'étude et l'exploitation des applications RFID est d'intérêt primordial afin de mieux comprendre et maitriser les menaces et les risques de cette technologie. A travers les travaux de recherche présentés dans cette thèse, nous nous sommes inscrits dans cette compétition qui consiste à chercher des solutions permettant de résoudre les problèmes liés à la sécurité de systèmes RFID, allant de l'authentification ultralégère à celle adoptant les courbes elliptiques (ECC) pour les étiquettes actives ou encore à la génération de clés de chiffrement pour les crypto-systèmes ECC. Parmi les tâches développées au cours de ces travaux de thèse, nous avons proposé de nouveaux protocoles d'authentification RFID en utilisant les concepts des courbes elliptiques qui présentent plus d'efficacité, de sécurité et de robustesse. Dans part, nous avons cryptanalyé, développé et proposé des protocoles d'authentification légers et ultralégers convenables aux étiquettes à faible coût. Plus loin, une autre contribution importante qui rentre dans le cadre de la génération aléatoire des clés de chiffrement, nous avons proposé un nouveau générateur pseudo aléatoire (PRNG) construit à base de plusieurs courbes elliptiques auto-sélectionnées convenable aux applications de type sécurisation des systèmes embarqués, la sécurité et simulations informatiques ou plus encore pour les systèmes miniaturisés à base des ECC tels que les cartes à puces et les étiquettes RFID. / The deployment and use of radio-frequency identification (RFID) technology is growing rapidly in different aspects of our daily life. This technology is used not only in traditional applications such as access control and container identification but also in security services such as in biometric passports, medicine, RFID-embedded cards. However, the main drawback of exchanging data wirelessly is the security issue. These systems are especially vulnerable to different attacks such as, eavesdropping attack, tracking attack, active attacks. For these reasons, the security and privacy of the RFID systems are to be addressed seriously and considered as a crucial matter before deploying this technology. These security mechanisms may be given by the authentication service. However, it turns out that RFID tags impose challenging constraints in terms of storage requirements, computing power, bandwidth and computational cost, thus, it is hard for them to implement or to adapt the existing custom cryptographic primitives and protocols or modern ciphers, such as AES (Advanced Encryption standard), RSA (Rivest, Shamir and Adleman), etc., which require a huge computational workload and storage space. Hence only lightweight cryptographic primitives can be implemented. Therefore, with the development of the calculation means, these systems are becoming increasingly vulnerable to a significant number of attacks. Consequently, the need for strong and secure cryptographic primitives compliant with the tag's challenging constraints must be addressed seriously. In addition, the study and the exploitation of the RFID applications is paramount interest in order to understand and master the threats and risks of this technology. Through the research presented in this thesis, we entered in this competition which consists to find solutions and solving problems related to the RFID systems security, ranging from the use of the lightweight authentication to those adopting elliptic curves cryptography. Among the tasks developed in the thesis works, we have proposed new RFID authentication protocols using the elliptic curves concepts that present more efficiency, security and robustness. In the other hand, we have cryptanalyzed, developed and proposed efficient lightweight and ultra-lightweight authentication protocols suitable for low cost RFID tags. Further, another important contribution which comes within the framework of the random generation of encryption keys, we have proposed a new pseudo-random generator (PRNG) constructed by randomly selecting points from elliptic curves, suitable for applications such as security systems, computer physic simulations, cryptographic applications and control coding.

Elliptic curve cryptosystems offer security comparable to that of traditional asymmetric cryptosystems, such as those based on the RSA encryption and digital signature algorithms, with smaller keys and computationally more efficient algorithms. The ability to use smaller keys and computationally more efficient algorithms than traditional asymmetric cryptographic algorithms are two of the main reasons why elliptic curve cryptography has become popular. As the popularity of elliptic curve cryptography increases, the need for efficient hardware solutions that accelerate the computation of elliptic curve point multiplications also increases. This dissertation introduces elliptic curve processor architectures suitable for the computation of point multiplications for curves defined over fields GF(2^m) and curves defined over fields GF(p). Each of the processor architectures presented here allows designers to tailor the performance and hardware requirements according to their performance and cost goals. Moreover, these architectures are well suited for implementation in modern field programmable gate arrays (FPGAs). This point was proved with prototyped implementations. The fastest prototyped GF(2^m) processor can compute an arbitrary point multiplication for curves defined over fields GF(2^167) in 0.21 milliseconds and the prototyped processor for the field GF(2^192-2^64-1) is capable of computing a point multiplication in about 3.6 milliseconds. The most critical component of an elliptic curve processor is its arithmetic unit. A typical arithmetic unit includes an adder/subtractor, a multiplier, and possibly a squarer. Some of the architectures presented in this work are based on multiplier and squarer architectures developed as part of the work presented in this dissertation. The GF(2^m) least significant bit super-serial multiplier architecture, the GF(2^m) most significant bit super-serial multiplier architecture, and a new GF(p) Montgomery multiplier architecture were developed as part of this work together with a new squaring architecture for GF(2^m).

"Elliptic Curve Cryptosystems (ECCs) are utilized as an alternative to traditional public-key cryptosystems, and are more suitable for resource limited environments due to smaller parameter size. In this dissertation we carry out a thorough investigation of side-channel attack aware ECC implementations over finite fields of prime characteristic including the recently introduced Edwards formulation of elliptic curves, which have built-in resiliency against simple side-channel attacks. We implement Joye's highly regular add-always scalar multiplication algorithm both with the Weierstrass and Edwards formulation of elliptic curves. We also propose a technique to apply non-adjacent form (NAF) scalar multiplication algorithm with side-channel security using the Edwards formulation. Our results show that the Edwards formulation allows increased area-time performance with projective coordinates. However, the Weierstrass formulation with affine coordinates results in the simplest architecture, and therefore has the best area-time performance as long as an efficient modular divider is available."

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 et la problématique de la sécurité informatique deviennent des sujets de plus en plus prépondérants dans un monde hyper connecté et souvent embarqué. La cryptographie est un domaine dont l'objectif principal est de ''protéger'' l'information, de la rendre inintelligible à ceux ou à celles à qui elle n'est pas destinée. La cryptographie repose sur des algorithmes solides qui s'appuient eux-mêmes sur des problèmes mathématiques réputés difficiles (logarithme discret, factorisation des grands nombres etc). Bien qu'il soit complexe, sur papier, d'attaquer ces systèmes de protection, l'implantation matérielle ou logicielle, si elle est négligée (non protégée contre les attaques physiques), peut apporter à des entités malveillantes des renseignements complémentaires (temps d’exécution, consommation d'énergie etc) : on parle de canaux cachés ou de canaux auxiliaires. Nous avons, dans cette thèse, étudié deux aspects. Le premier est l'apport de nouvelles idées algorithmiques pour le calcul dans les corps finis binaires GF(2^m) utilisés dans le cadre de la cryptographie sur courbes elliptiques. Nous avons proposé deux nouvelles représentations des éléments du corps : la base normale permutée et le Phi-RNS. Ces deux nouveautés algorithmiques ont fait l'objet d'implémentations matérielles en FPGA dans laquelle nous montrons que ces premières, sous certaines conditions, apportent un meilleur compromis temps-surface. Le deuxième aspect est la protection d'un crypto-processeur face à une attaque par canaux cachés (dite attaque par «templates»). Nous avons implémenté, en VHDL, un crypto-processeur complet et nous y avons exécuté, en parallèle, des algorithmes de «double-and-add» et «halve-and-add» afin d'accélérer le calcul de la multiplication scalaire et de rendre, de par ce même parallélisme, notre crypto-processeur moins vulnérable face à certaines attaques par canaux auxiliaires. Nous montrons que le parallélisme seul des calculs ne suffira pas et qu'il faudra marier le parallélisme à des méthodes plus conventionnelles pour assurer, à l'implémentation, une sécurité raisonnable. / Cryptography and security market is growing up at an annual rate of 17 % according to some recent studies. Cryptography is known to be the science of secret. It is based on mathematical hard problems as integers factorization, the well-known discrete logarithm problem. Although those problems are trusted, software or hardware implementations of cryptographic algorithms can suffer from inherent weaknesses. Execution time, power consumption (...) can differ depending on secret informations such as the secret key. Because of that, some malicious attacks could be used to exploit these weak points and therefore can be used to break the whole crypto-system. In this thesis, we are interested in protecting our physical device from the so called side channel attacks as well as interested in proposing new GF(2^m) multiplication algorithms used over elliptic curves cryptography. As a protection, we first thought that parallel scalar multiplication (using halve-and-add and double-and-add algorithms both executed at the same time) would be a great countermeasure against template attacks. We showed that it was not the case and that parallelism could not be used as protection by itself : it had to be combined with more conventional countermeasures. We also proposed two new GF(2^m) representations we respectively named permuted normal basis (PNB) and Phi-RNS. Those two representations, under some requirements, can offer a great time-area trade-off on FPGAs.

<p>This thesis makes a survey of converse theorems for Dirichlet series. A converse theo-rem gives sufficient conditions for a Dirichlet series to be the Dirichlet series attachedto a modular form. Such Dirichlet series have special properties, such as a functionalequation and an Euler product. Sometimes these properties characterize the modularform completely, i.e. they are sufficient to prove the proper transformation behaviourunder some discrete group. The problem dates back to Hecke and Weil, and has morerecently been treated by Conrey et.al. The articles surveyed are:</p><ul><li>"An extension of Hecke's converse theorem", by B. Conrey and D. Farmer</li><li>"Converse theorems assuming a partial Euler product", by D. Farmer and K.Wilson</li><li>"A converse theorem for ¡0(13)", by B. Conrey, D. Farmer, B. Odgers and N.Snaith</li></ul><p>The results and the proofs are described. The second article is found to contain anerror. Finally an alternative proof strategy is proposed.</p>

This thesis makes a survey of converse theorems for Dirichlet series. A converse theo-rem gives sufficient conditions for a Dirichlet series to be the Dirichlet series attachedto a modular form. Such Dirichlet series have special properties, such as a functionalequation and an Euler product. Sometimes these properties characterize the modularform completely, i.e. they are sufficient to prove the proper transformation behaviourunder some discrete group. The problem dates back to Hecke and Weil, and has morerecently been treated by Conrey et.al. The articles surveyed are: "An extension of Hecke's converse theorem", by B. Conrey and D. Farmer "Converse theorems assuming a partial Euler product", by D. Farmer and K.Wilson "A converse theorem for ¡0(13)", by B. Conrey, D. Farmer, B. Odgers and N.Snaith The results and the proofs are described. The second article is found to contain anerror. Finally an alternative proof strategy is proposed.

In 2001, Boneh, Lynn, and Shacham presented a pairing-based signature scheme known as the BLS signature scheme. In 2003, Boneh, Gentry, Lynn, and Shacham presented the first aggregate signature scheme called the BGLS aggregate signature scheme. The BGLS scheme allows for N users with N signatures to combine their signatures into a single signature. The size of the resulting signature is independent of N. The BGLS signature scheme enjoys roughly the same level of security as the BLS scheme. In 2005, Waters presented a pairing-based signature scheme which does not assume the existence of random oracles. In 2007, Lu, Ostrovsky, Sahai, Shacham, and Waters presented the LOSSW aggregate signature scheme which does not assume the existence of random oracles. The BLS, BGLS, Waters, and LOSSW authors each chose to work with a restricted class of pairings. In each scheme, it is clear that the scheme extend to arbitrary pairings. We present the schemes in their full generality, explore variations of the schemes, and discuss optimizations that can be made when using specific pairings. Each of the schemes we discuss is secure assuming that the computational Diffie-Hellman (CDH) assumption holds. We improve on the security reduction for a variation of the BGLS signature scheme which allows for some restrictions of the BGLS signature scheme can be dropped and provides a stronger guarantee of security. We show that the BGLS scheme can be modified to reduce public-key size in presence of a certifying authority, when a certain type of pairing is used. We show that patient-free bit-compression can be applied to each of the scheme with a few modifications.

In 2001, Boneh, Lynn, and Shacham presented a pairing-based signature scheme known as the BLS signature scheme. In 2003, Boneh, Gentry, Lynn, and Shacham presented the first aggregate signature scheme called the BGLS aggregate signature scheme. The BGLS scheme allows for N users with N signatures to combine their signatures into a single signature. The size of the resulting signature is independent of N. The BGLS signature scheme enjoys roughly the same level of security as the BLS scheme. In 2005, Waters presented a pairing-based signature scheme which does not assume the existence of random oracles. In 2007, Lu, Ostrovsky, Sahai, Shacham, and Waters presented the LOSSW aggregate signature scheme which does not assume the existence of random oracles. The BLS, BGLS, Waters, and LOSSW authors each chose to work with a restricted class of pairings. In each scheme, it is clear that the scheme extend to arbitrary pairings. We present the schemes in their full generality, explore variations of the schemes, and discuss optimizations that can be made when using specific pairings. Each of the schemes we discuss is secure assuming that the computational Diffie-Hellman (CDH) assumption holds. We improve on the security reduction for a variation of the BGLS signature scheme which allows for some restrictions of the BGLS signature scheme can be dropped and provides a stronger guarantee of security. We show that the BGLS scheme can be modified to reduce public-key size in presence of a certifying authority, when a certain type of pairing is used. We show that patient-free bit-compression can be applied to each of the scheme with a few modifications.

Elliptic curve cryptography has gained much popularity in the past decade and has been challenging the dominant RSA/DSA systems today. This is mainly due to elliptic curves offer cryptographic systems with higher speed, less memory and smaller key sizes than older ones. Among the various arithmetic operations required in implementing public key cryptographic algorithms based on elliptic curves, the elliptic curve scalar multiplication has probably received the maximum attention from the research community in the past a few years. Many methods for efficient and secure implementation of scalar multiplication have been proposed by many researchers. In this thesis, many scalar multiplication methods are studied in terms of their mathematical, computational and implementational points.