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.

Etude des propriétés de symétrie des solutions de quelques problèmes aux limites de type elliptique. / Doctorat en sciences, Spécialisation mathématiques / info:eu-repo/semantics/nonPublished

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

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.

Cette thèse est composée de deux parties indépendantes. Dans la première, on s'intéresse à la résolution de certaines équations diophantiennes par la méthode modulaire. On traite plus particulièrement le cas des équations de Fermat de type (5,5,p) ainsi que celui des équations de la forme F(x,y)=z^p où p est un nombre premier et F une cubique rationnelle. La deuxième partie est consacrée à l'arithmétique des courbes elliptiques. Dans le cas d'une courbe définie sur une extension finie de Q_2 ayant mauvaise réduction additive avec potentiellement bonne réduction, on s'intéresse à la détermination de son défaut de semi-stabilité. On énonce un résultat partiel valable pour toute extension finie de Q_2. Dans le cas des extensions quadratiques ramifiées de Q_2, on obtient un résultat complet. Par ailleurs, si E est une courbe elliptique définie sur un corps de nombres K, on s'intéresse, dans le dernier chapitre, à l'ensemble des nombres premiers p pour lesquels l'action du groupe de Galois absolu de K sur le sous-groupe des points de p-torsion de E est réductible. Lorsque cet ensemble est fini, on obtient un critère permettant en pratique de le déterminer explicitement.

Les galaxies de type précoce présentent un large éventail de structures photométriques et dynamiques. Ces structures sont autant de signatures fossiles des processus de formation et d'évolution de ces galaxies. Leur étude nous permet de remonter à l'histoire de leur formation et de leur évolution. Dans le but de comprendre les structures observées, des modèles reproduisant des observations sont construits. La méthode développée est une généralisation de celle introduite par Syer & Tremaine (1996), consistant en un N-corps dont le poids des particules varie au cours du temps. Le code présenté est adapté à des données de spectroscopie intégrale de champ, et est à-même de reproduire la photométrie ainsi que la dynamique des galaxies observées. Ces modèles sont basés sur des données SAURON obtenues sur des galaxies de type précoce. Des modèles préliminaires ont été obtenus pour les galaxies M 87 et NGC 3377. Une annexe présente en outre des observations menées sur NGC 936.

Nombres d'intersection arithmétiques et opérateurs de Hecke sur les courbes modulaires<br /><br />Cette thèse s'inscrit dans l'étude des opérateurs de Hecke en tant que correspondances sur les courbes modulaires X_0(N). D'une part, nous étudions la relation entre l'algèbre de Hecke et la théorie d'Arakelov; d'autre part, nous entreprenons un début d'étude de la dynamique de l'action des opérateurs de Hecke sur l'ensemble des courbes elliptiques supersingulières. <br /><br />On considère la courbe modulaire X_0(N) munie de la métrique de Poincaré (métrique hyperbolique). Cette métrique présente des singularités aux points elliptiques et pointes. On suppose que N est sans facteurs carrés. On note XN le modèle entier de cette courbe donné par l'interprétation modulaire étudiée par Deligne et Rapoport. On définit un groupe de Chow arihmétique généralisé CH(N) tel que ses éléments sont représentés par des couples (D,g) avec D un diviseur de Weil sur XN et g un courant de Green admissible pour la métrique de Poincaré. J.-B. Bost et U. Kühn ont développé, de manière indépendante, des généralisations de la théorie d'intersection arithmétique d'Arakelov qui fournissent une forme bilinéaire à valeurs réelles sur CH(N) x CH(N) dans ce cadre où la métrique est singulière. On étudie aussi une version à coefficients réels et à équivalence numérique près de CH(N), que l'on note CH(N)*.<br /><br />Nous montrons dans cette thèse que les correspondances de Hecke agissent sur CH(N) et que cette action est autoadjointe par rapport à la forme bilinéaire de Bost-Kühn. Ceci permet de diagonaliser cette action sur CH(N)* et de définir ses sous-espaces propres. Ensuite nous étudions le faisceau dualisant relatif, considéré comme un élément de CH(N)*, ainsi que sa décomposition selon les sous-espaces propres. Nous calculons l'auto-intersection de la composante propre correspondante à la pointe à l'infini en utilisant des résultats d'Ulf Kühn.<br /><br /> L'action des opérateurs de Hecke sur les fibres spéciales de XN définit une dynamique qui preserve les points supersinguliers. Nous nous intéressons à étudier cette action sur les points supersinguliers des fibres de bonne réduction et nous calculons, à l'aide des résultats de Deuring et Eichler, la fréquence asymptotique avec laquelle un point supersingulier donné visite un autre point du même type.