Cette thèse a pour objectif d'étudier les applications cryptographiques des courbes elliptiques sur l'anneau Fp["], où Fp représente un corps fini d'ordre premier p et où " vérifie"2 = 0. Après avoir décrit ces courbes définies sur un anneau, nous en étudions l'aspect algorithmique en proposant des solutions concrètes d'implémentations des éléments et de la loi de groupe. Enfin, nous illustrons leur intérêt cryptographique, en proposant : une attaque du problème du logarithme discret elliptique (sur un corps fini) utilisant ces courbes ; un cryptosystème de type ElGamal sur ces courbes, dont nous étudions les propiétés de sécurité.

Cette thèse propose des améliorations aux problèmes de la multiplication et de la factorisation d’entier.L’algorithme de Schönhage-Strassen pour la multiplication d’entier, publié en 1971, fut le premier à atteindre une complexité de O(n log(n) log(log(n))) pour multiplier deux entiers de n bits, et reste parmi les plus rapides en pratique. Il réduit la multiplication d’entier à celle de polynôme sur un anneau fini, en utilisant la transformée de Fourier rapide pour calculer le produit de convolution. Dans un travail commun avec Gaudry et Zimmermann, nous décrivons une implantation efficace de cet algorithme, basée sur la bibliothèque GNU MP; par rapport aux travaux antérieurs, nous améliorons l’utilisation de la mémoire cache, la sélection des parameters et la longueur de convolution, ce qui donne un gain d’un facteur 2 environ.Les algorithmes P–1 et P+1 trouvent un facteur p d’un entier composé rapidement si p-1, respectivement p+1, ne contient pas de grand facteur premier. Ces algorithmes comportent deux phases : la première phase calcule une grande puissance g1 d’un élément g0 d’un groupe fini défini sur Fp, respectivement Fp^2 , la seconde phase cherche une collision entre puissances de g1, qui est trouvée de manière efficace par évaluation-interpolation de polynômes. Dans un travail avec Peter Lawrence Montgomery, nous proposons une amélioration de la seconde phase de ces algorithmes, avec une construction plus rapide des polynômes requis, et une consommation mémoire optimale, ce qui permet d’augmenter la limite pratique pour le plus grand facteur premier de p-1, resp. p + 1, d’un facteur 100 environ par rapport aux implantations antérieures.Le crible algébrique (NFS) est le meilleur algorithme connu pour factoriser des entiers dont les facteurs n’ont aucune propriété permettant de les trouver rapidement. En particulier, le module du système RSA de chiffrement est choisi de telle sorte, et sa factorisation casse le système. De nombreux efforts ont ainsi été consentis pour améliorer NFS, de façon à établir précisément la sécurité de RSA. Nous donnons un bref aperçu de NFS et de son historique. Lors de la phase de crible de NFS, de nombreux petits entiers doivent être factorisés. Nous présentons en detail une implantation de P–1, P+1, et de la méthode ECM basée sur les courbes elliptiques, qui est optimisée pour de tels petits entiers. Finalement, nous montrons comment les paramètres de ces algorithmes peuvent être choisis finement, en tenant compte de la distribution des facteurs premiers dans les entiers produits par NFS, et de la probabilité de trouver des facteurs premiers d’une taille donnée / This thesis explores improvements to well-known algorithms for integer multiplication and factorization.The Schönhage-Strassen algorithm for integer multiplication, published in 1971, was the firstto achieve complexity O(n log(n) log(log(n))) for multiplication of n-bit numbers and is stillamong the fastest in practice. It reduces integer multiplication to multiplication of polynomials over finite rings which allow the use of the Fast Fourier Transform for computing the convolution product. In joint work with Gaudry and Zimmermann, we describe an efficient implementation of the algorithm based on the GNU Multiple Precision arithmetic library, improving cache utilization, parameter selection and convolution length for the polynomial multiplication over previous implementations, resulting in nearly 2-fold speedup.The P–1 and P+1 factoring algorithms find a prime factor p of a composite number quickly if p-1, respectively p+1, contains no large prime factors. They work in two stages: the first step computes a high power g1 of an element g0 of a finite group defined over Fp, respectively Fp^2 , the second stage looks for a collision of powers of g1 which can be performed efficiently via polynomial multi-point evaluation. In joint work with Peter Lawrence Montgomery, we present an improved stage 2 for these algorithms with faster construction of the required polynomial and very memory-efficient evaluation, increasing the practical search limit for the largest permissible prime in p-1, resp. p+1, approximately 100-fold over previous implementations.The Number Field Sieve (NFS) is the fastest known factoring algorithm for “hard” integers where the factors have no properties that would make them easy to find. In particular, the modulus of the RSA encryption system is chosen to be a hard composite integer, and its factorization breaks the encryption. Great efforts are therefore made to improve NFS in order to assess the security of RSA accurately. We give a brief overview of the NFS and its history. In the sieving phase of NFS, a great many smaller integers must be factored. We present in detail an implementation of the P–1, P+1, and Elliptic Curve methods of factorization optimized for high-throughput factorization of small integers. Finally, we show how parameters for these algorithms can be chosen accurately, taking into account the distribution of prime factors in integers produced by NFS to obtain an accurate estimate of finding a prime factor with given parameters

Cette thèse est une étude des surfaces de type général dont le fibré cotangent est engendré par ses sections globales et dont l'irrégularité q est supérieure ou égale à 4.<br />L'objet et le moyen de cette étude est l'application cotangente qui est un morphisme du projectivisé du fibré cotangent dans l'espace projectif de dimension q-1. Nous étudions le degré de ce morphisme et le degré de son image.<br />Le fibré cotangent est ample si et seulement s'il n'existe pas de fibre de l'application cotangente de dimension strictement positive.<br />Si le fibré cotangent n'est pas ample, alors il existe une courbe C contenue dans la surface et il existe une section de C dans le projectivisé du fibré cotangent qui est contractée en un point par l'application cotangente. Une telle courbe C est qualifiée de courbe non-ample.<br />Nous donnons une classification des courbes non-amples de la surface suivant leur auto-intersection. Nous donnons ensuite une classification des surfaces possédant une infinité de courbes non-amples.<br />Un exemple pour lequel l'application cotangente intervient naturellement est celui des surfaces de Fano. Nous étudions le diviseur de ramification de leur application cotangente ainsi que leurs courbes non-amples.<br />Cette étude mène à la surface de Fano de la cubique de Fermat qui possède 30 courbes non-amples et dont nous détaillons les propriétés.

Cette these a pour theme la geometrie des courbes algebriques et de leur jacobienne (en caracteristique zero). Elle a, en particulier, pour objet l'etude du groupe engendre dans la jacobienne par les points de Weierstrass pour certaines courbes planes lisses de genre trois. Nous determinons ce groupe pour certaines familles de courbes de genre trois. Pour ce faire, nous procedons en deux etapes. Nous utilisons tout d'abord la geometrie de la courbe et de sa jacobienne pour restreindre le groupe cherche. Les restrictions obtenues par ces arguments geometriques s'avereront etre optimales. Pour demontrer cela, nous utilisons differentes techniques: dans la deuxieme partie, nous appliquons une descente explicite via une isogenie; dans la troisieme partie, nous utilisons des arguments de reduction modulo un nombre premier. Lorsque nous nous interessons a des familles, ces restrictions ``d'ordre geometrique'' s'obtiennent pour toute la famille. Par contre, les techniques mises en oeuvre lors de la seconde etape ne nous donnent le resultat que pour une courbe particuliere. Dans chaque cas, un argument de specialisation nous permet de conclure. De plus, nous determinons ce groupe pour la seule quartique, autre que le quartique de Fermat, possedant le nombre minimal de points de Weierstrass, a savoir douze; la encore, la geometrie de la jacobienne intervient dans la determination de ce groupe. Ces calculs nous permettent de donner des estimations sur le rang de ce groupe et sur la partie de torsion dans le cas d'une quartique generique, selon le nombre de points d'hyper-inflexion (c'est-a-dire de points de la courbe ou la tangente a multiplicite d'intersection quatre avec la courbe).

Dans l'esprit du théorème de Cassels, Ellison et Pfister qui démontre que le polynôme de Motzkin est une somme de 4 carrés et pas de 3 carrés de fractions dans R(X,Y), on construit des familles de polynômes de ce type de la forme Y^4+A(X)Y^2+B(X). La méthode est une extension de celle de Cassels, Ellison et Pfister : 2-descentes sur des courbes elliptiques.

Un tour d'horizon de plusieurs systèmes de numération "exotiques" et leurs applications en cryptographie est proposé.

Thèse (M.Sc.)--Université Laval, 2006. / Titre de l'écran-titre (visionné le 28 mars 2007). Dans le titre et le résumé, le "w" du symbole "w-NAF" s'apparente à la lettre grecque omega. Bibliogr.

Soit E une courbe elliptique sur un corps de valuation discrètecomplet K à corps résiduel algbriquement clos. Alors E a réduction semi-stable surune extension minimale L/K, galoisienne de groupe de Galois G. Soient O_{K} , O_{L} les anneaux de valuations respectives de K et L, et X , X' les modèles réguliers minimaux de E sur O_{K} et O_{L} respectivement.Premièrement nous montrons que pour tout entier naturel n, la fibre fermée infinitésimale X_{n} est déterminée par l'action du groupe G sur X'_{n+l} pour unentier naturel l assez grand (ne dépendant que du discriminant de L/K sile type de réduction de E n'est pas I*_{r} ). Deuxiémement, nous classifions àisomorphisme près la fibre fermée X_{0} en tant que courbe sur le corps résiduelde K, lorsque la caractéristique résiduelle est nulle ou au moins égale à 7. Cette classification est plus fine que la classification par le type à la Kodairaet Néron. / Suppose E is an elliptic curve over a complete discrete valuationfield K whose residue field k is algebraically closed. Then E has semi-stablereduction after a minimal field extension L/K, moreover L/K is Galois andlet G be the Galois group. Let O_{K} and O_{L} be the ring of integers of K andL respectively. Let X (resp. X ') be the minimal regular model of E over O_{K}(resp. O_{L} ). In the first part of thesis, we prove that for all natural integersn, the infinitesimal fiber X_{n} is determined by the G-action on O_{K}-schemeX'_{n+l} for some positive integer l (depending only on the discriminant of L/Kif the reduction type of E is not I*_{r} ). In the second part of thesis, we classifythe special fiber X_{0} up to isomorphisms as k-curves when Char(k) >= 7. This classification is finer than the classification by Kodaira and Néron.

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.

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).