Given an elliptic curve E over Q, we can then consider E over the finite field Fp. If Np is the number of points on the curve over Fp, then we define ap(E) = p+1-Np. We say primes p for which ap(E) = 1 are anomalous. In this paper, we search for curves E so that this happens for only a finite number of primes. We call such curves finitely anomalous. This thesis deals with the frequency of their occurrence and finds several examples.

No description available.

The Internet of Things will include many resource-constrained lightweight wireless sensing devices, hungry for energy, bandwidth and compute cycles. The sheer amount of devices involved will require new solutions to handle issues such as identification and power provisioning. First, to simplify identity management, device identification is moving from symmetric-key solutions to public-key solutions. Second, to avoid the endless swapping of batteries, passively-powered energy harvesting solutions are preferred. In this contribution, we analyze some of the feasible solutions from this challenging design space. We have built an autonomous, energy-harvesting sensor node which includes a micro-controller, RF-unit, and energy harvester. We use it to analyze the computation and communication energy requirements for Elliptic Curve Digital Signature Algorithm (ECDSA) with different security levels. The implementation of Elliptic Curve Cryptography (ECC) on small microcontrollers is challenging. Most of the earlier literature has considered optimizing the performance of ECC (with respect to cycle count and software footprint) on a given architecture. This thesis addresses a different aspect of the resource-constrained ECC implementation wherein the most suitable architecture parameters are identified for any given application profile. At the high level, an application profile for an ECC-based lightweight device, such as wireless sensor node or RFID tag, is defined by the required security level, signature generation latency and the available energy/power budget. The target architecture parameters of interest include core-voltage, core-frequency, and/or the need for hardware acceleration. We present a methodology to derive and optimize the architecture parameters starting from the application requirements. We demonstrate our methodology on a MSP430F5438A microcontroller, and present the energy/architecture design space for 80-bit and 128-bit security-levels, for prime field curves secp160r1 and nistp256. Our results show that energy cost per authentication is minimized if a microcontroller is operated at the maximum possible frequency. This is because the energy consumed by leakage (i.e., static power dissipation) becomes proportionally less important as the runtime of the application decreases. Hence, in a given energy harvesting method, it is always better to wait as long as possible before initiating ECC computations which are completed at the highest frequency when sufficient energy is available. / Master of Science

Most isogeny-based cryptosystems ultimately rely, for their security, on l- IsoPath, i.e. the problem of finding a secret l-smooth isogeny between two elliptic curves. As cryptographic applications usually employ weaker variants of l-IsoPath for practical reasons, it is natural to ask whether these variants are equally hard from a computational perspective. For example, what happens if the endomorphism ring of one of the curves is known? Does the existence of suitable pairings affect the hardness of l-IsoPath? What happens if some non-trivial endomorphisms of the domain and codomain curves are known? These kinds of questions lead to different problems, some of which are considered throughout this thesis. To prevent anyone from knowing the endomorphism ring of a supersingular elliptic curve, we would need a method to hash in the supersingular isogeny graph, i.e. the graph whose vertices are supersingular elliptic curves (up to isomorphism) and whose edges are isogenies of fixed degree. We give examples of cryptographic protocols that could benefit from this and survey some known methods. Since none of them is at the same time efficient and cryptographically secure, we also point out a few alternative approaches. Later on, we leverage the classic Deuring correspondence between supersingular elliptic curves and quaternion orders to study a weaker version of l-IsoPath, inspired by the study of CM theory from the previous part. We then focus on the construction of pairings of elliptic curves, showing that, in the general case, finding distinct pairings compatible with a secret isogeny is no easier than retrieving the isogeny itself. In the presence of an orientation, on the other hand, we show that the existence of suitable self-pairings, together with a recent attack on the isogeny-based key-exchange SIDH, does lead to efficiently solving l- IsoPath for some class-group-action-based protocols. In particular, we completely characterize the cases in which these selfpairings exist. Finally, we introduce a different graph of elliptic curves, which has not been considered before in isogeny-based cryptography and which does not arise, in fact, from isogenies: the Hessian graph. We give a (still partial) account of its remarkable regularity and discuss potential cryptographic applications.

Alors qu'initialement utilisés pour résoudre le Problème du Logarithme Discret (DLP) dans le groupe de points d'une courbe elliptique, les couplages sont très à la mode en cryptographie ces années car ils permettent de construire de nouveaux protocoles cryptographiques. Cependant, le calcul efficace du couplage dépend de l'arithmétique du modèle de courbe elliptique choisi et du corps sur lequel cette courbe est définie. Dans cette thèse, nous calculons le couplage sur deux modèles de Jacobi de courbes elliptiques puis nous introduisons et étudions l'arithmétique d'un nouveau modèle d'Ewards de courbe elliptique défini en toutes caractéristiques. Plus précisément, Nous utilisons l'interprétation géométrique de la loi de groupe sur l'intersection des quadriques de Jacobi pour obtenir pour la première fois dans la littérature, les formules explicites de la fonction de Miller pour le calcul du couplage de Tate sur cette courbe. Pour un calcul de couplage avec un degré de plongement pair, nous définissons la tordue quadratique pour obtenir des étapes de doublement et d'addition efficaces dans l'algorithme de Miller. Ensuite nous utilisons un isomorphisme entre la quartique spéciale de Jacobi Ed: Y²=dX⁴+Z⁴ et le modèle de Weierstrass pour obtenir la fonction de Miller nécessaire au calcul du couplage de Tate. Pour un degré de plongement divisible par 4, nous définissons la tordue d'ordre 4 de cette courbe pour obtenir un résultat meilleur du calcul du couplage de Tate par rapport aux courbes elliptiques sous forme de Weierstrass. Notre résultat améliore en même temps les derniers résultats obtenus sur cette courbe. Ce résultat est donc le meilleur connu à ce jour, à notre connaissance, pour le calcul du couplage de Tate sur les courbes possédant des tordues d'ordre 4. En 2006, Hess et al. introduisent le couplage Ate, qui est une version améliorée du couplage de Tate. Nous calculons ce couplage et ses variantes sur la même quartique. Nous y obtenons encore des résultats meilleurs. Notre troisième contribution est l'introduction d'un nouveau modèle d'Edwards de courbe elliptique d'équation 1+x²+y²+x²y²=Xxy. Ce modèle est ordinaire sur les corps de caractéristique 2 et nous montrons qu'il est birationnellement équivalent au modèle original d'Edwards x²+y²=c²(1+x²y²) en caractéristique différente de 2. Pour ce faire, nous utilisons la théorie des fonctions thêta et un modèle intermédiaire que nous appelons modèle thêta de niveau 4. Nous utilisons les relations de Riemann des fonctions thêta pour étudier l'arithmétique de ces deux courbes. Nous obtenons d'une part une loi de groupe complète, unifiée et en particulier compétitive en caractéristique 2 et d'autre part nous présentons les meilleures formules d'addition différentielle sur le modèle thêta de niveau 4. / While first used to solve the Discrete Logarithm Problem (DLP) in the group of points of elliptic curves, bilinear pairings are now useful to construct many public key protocols. The efficiency of pairings computation depends on the arithmetic of the model chosen for the elliptic curve and of the base field where the curve is defined. In this thesis, we compute and implement pairings on elliptic curves of Jacobi forms and we study the arithmetic of a new Edwards model for elliptic curves defined over any finite field. More precisely, We use the geometric interpretation of the group law of Jacobi intersection curves to obtain the first explicit formulas for the Miller function in Tate pairing computation in this case. For pairing computation with even embedding degree, we define and use the quadratic twist of this curve to obtain efficient formulas in the doubling and addition stages in Miller's algorithm. Moreover, for pairing computation with embedding degree divisible by 4 on the special Jacobi quartic elliptic curve Ed :Y²=dX⁴+Z⁴, we define and use its quartic twist to obtain a best result with respect to Weierstrass curves. Our result is at the same time an improvement of a result recently obtained on this curve, and is therefore, to our knowledge, the best result to date on Tate pairing computation among all curves with quartic twists. In 2006, Hess et al. introduced the concept of Ate pairing which is an improving version of the Tate pairing. We extend the computation of this pairing and its variations to the curve E_d. Again our theoretical results show that this curve offers the best performances comparatively to other curves with quartic twists, especially Weiertrass curves. As a third contribution, we introduce a new Edwards model for elliptic curves with equation 1+x²+y²+x²y²=\lambda xy. This model is ordinary over binary fields and we show that it is birationally equivalent to the well known Edwards model x²+y²=c²(1+x²y²) over non-binary fields. For this, we use the theory of theta functions to obtain an intermediate model that we call the level 4 theta model. We study the arithmetic of these curves, using Riemann relations of theta functions. The group laws are complete, unified, efficient and are particularly competitive in characteristic 2. Our formulas for differential addition on the level four theta model over binary fields are the best to date among well known models of elliptic curves.

Un réseau de capteurs sans fil (RCSF) est constitué d’un grand nombre de nœuds capteurs autonomes qui collaborent ensemble pour la surveillance d’une zone, d’une machine, d’une personne etc.. Dans certaines applications,les données critiques doivent être protégées contre toute utilisation frauduleuse et être accessibles en temps réel. Le besoin d’apporter une solution de sécurité fiable et adaptée paraît donc essentiel. Les solutions de sécurité utilisées dans les réseaux traditionnels ne sont pas directement applicables dans les RCSFs, car développer des primitives de sécurité en utilisant de faibles ressources devient un véritable défi. Dans cette thèse, nous proposons des solutions nouvelles peu gourmandes en ressources qui tiennent compte des faibles capacités de défense d’un réseau autonome. Dans cette optique nous appliquons des mécanismes cryptographiques bas´es sur les fonctions de hachage et les courbes elliptiques. Un focus sur différents mécanismes de sécurité peu gourmands en ressources nous permet la mise en évidence des rapports de forces entre les RCSFs et leurs vulnérabilités. Notre première contribution vise `a améliorer la sécurité et les performances en termes d’´énergie sur des protocoles d’authentification existants tout en utilisant les mêmes mécanismes. Dans la deuxième contribution, on utilise le concept de probabilité de risque afin de déterminer la consommation énergétique dans différentes architectures de déploiement. Dans la troisième contribution nous présentons un nouveau mécanisme d’accélération de la multiplication scalaire sur les courbes elliptiques définies dans des corps finis premiers. Ce mécanisme bas´e sur l’opposé et l’ordre d’un point, réduit le nombre d’opérations de points dans un intervalle donné, et présente en plus l’avantage de pouvoir être combiné avec les techniques existantes. Enfin dans notre dernière contribution, nous nous sommes intéressés à l’accélération du calcul des points résultants du partitionnement du scalaire qui introduisent des coûts additionnels de calcul et de stockage mémoire. Nous comparons différentes formules de points existantes en mettant en évidence leur efficacité. / A Wireless Sensor Network (WSN) consists of a large number of sensor nodes which collaborate so as tomonitor environnement. For various WSNs’ applications, the collected data should be protected by preventingunauthorized users from gaining the information. The need to find a reliable and adaptive security solution isvery important. Most current standard security protocols designed for traditional networks cannot be applieddirectly in WSN. For this reason, providing a variety of security functions with limited resources is a realchallenge. Our research work seeks to find secure efficient solutions that take into account the rather weakdefense of an autonomous network. In this way, we apply lightweight cryptography mechanisms based on hashfunction and elliptic curves. A focus on different security mechanisms and lightweight security algorithms canhighlight the strength ratio between WSNs and their vulnerabilities. Our first contribution is on a secure energyefficient solution, it uses the same mechanism and aims to enhance the security weaknesses of existing solutions.The second contribution uses the concept of probability risk analysis to show to which level the proposedsolution justifies the better energy consumption for a given network architecture. In the third contribution, wepresent a new technique to accelerate scalar multiplication on elliptic curves cryptography over prime field forlight-weight embedded devices like sensor nodes. Our method reduces the computation of scalar multiplicationby an equivalent representation of points based on point order in a given interval and can also act as a supportfor most existing methods. Finally our last contribution presents a fast pre-computation algorithm in a parallelscalar multiplication to avoid the storage of pre-computation points which requires extra memory. We alsoprovide a comparison of different formulas so as to find out their efficiency.

Orientador: Henrique Lazari / Banca: Jaime Edmundo Apaza Rodriguez / Banca: Carina Alves / Resumo: Com o crescimento da comunicação nos dias atuais, a segurança na troca de informa- ções tem se tornado cada vez mais importante o que tem dado destaque a Criptografia. A criptografia consiste de técnicas baseadas em conceitos matemáticos que tem por objetivo transmitir informações sigilosas forma segura através de canais monitorados por terceiros. Um ramo da Criptografia que vem crescendo está ligado ao estudo de curvas elípticas, que é uma das áreas mais ricas da matemática. O nome curvas elípticas é de certa forma enganoso, pois diferente do sentido literal da palavra, que leva a pensar em elipses, se trata de equações relacionadas a um determinado tipo de curva algébrica. Neste trabalho, as curvas elípticas serão estudadas do ponto de vista da álgebra e da teoria dos números com o objetivo de conhecer a Criptografia de Curvas Elípticas que é uma variação do Problema do Logaritmo Discreto / Abstract: With the growth of communication these days, security in exchange for information has become increasingly important what has given prominence to Cryptography. Encryption techniques is based on concepts mathematical aims to transmit sensitive information securely through channels monitored by third parties. A branch of cryptography that has growing up is connected to the study of elliptic curves, which is one of the most rich mathematics. The name elliptic curves is somewhat misleading, as di erent from the literal sense of the word, which makes one think of ellipses if equations is related to a certain type of algebraic curve. in this work, elliptic curves are studied from the viewpoint of algebra and of number theory in order to know the Curve Cryptography Elliptic is a variation of the discrete logarithm problem / Mestre

This thesis presents the Weil pairing on elliptic curves as a tool to implement a tripartite Diffie-Helman key exchange. Elliptic curves are introduced, as well as the addition operation that creates a group structure on its points. In leading to the definition of the Weil pairing, divisors of rational functions are studied, as well as the Weierstrass }-function, which shows the complex lattice as isomorphic to elliptic curves. Several important qualities of the Weil pairing are proved, and Miller's algorithm for quick calculation is shown. Next, the bipartite Diffie-Helman key exchange is discussed over finite fields and elliptic curves. Finally an example of a modifed Weil pairing is defined, which leads to the tripartite Diffie-Helman key exchange.

A digital signature is the electronic counterpart to the hand written signature. It can prove the source and integrity of any digital data, and is a tool that is becoming increasingly important as more and more information is handled electronically. Digital signature schemes use a pair of keys. One key is secret and allows the owner to sign some data, and the other is public and allows anyone to verify the signature. Assuming that the keys are large enough, and that a secure scheme is used, it is impossible to find the private key given only the public key. Since a signature is valid for the signed message only, this also means that it is impossible to forge a digital signature. The most well-used scheme for constructing digital signatures today is RSA, which is based on the hard mathematical problem of integer factorization. There are, however, other mathematical problems that are considered even harder, which in practice means that the keys can be made shorter, resulting in a smaller memory footprint and faster computations. One such alternative approach is using elliptic curves. The underlying mathematical problem of elliptic curve cryptography is different to that of RSA, however some structure is shared. The purpose of this thesis was to evaluate the performance of elliptic curves compared to RSA, on a system designed to efficiently perform the operations associated with RSA. The discovered results are that the elliptic curve approach offers some great advantages, even when using RSA hardware, and that these advantages increase significantly if special hardware is used. Some usage cases of digital signatures may, for a few more years, still be in favor of the RSA approach when it comes to speed. For most cases, however, an elliptic curve system is the clear winner, and will likely be dominant within a near future. / En digital signatur är den elektroniska motsvarigheten till en handskriven signatur. Den kan bevisa källa och integritet för valfri data, och är ett verktyg som blir allt viktigare i takt med att mer och mer information hanteras digitalt. Digitala signaturer använder sig av två nycklar. Den ena nyckeln är hemlig och tillåter ägaren att signera data, och den andra är offentlig och tillåter vem som helst att verifiera signaturen. Det är, under förutsättning att nycklarna är tillräck- ligt stora och att det valda systemet är säkert, omöjligt att hitta den hemliga nyckeln utifrån den offentliga. Eftersom en signatur endast är giltig för datan som signerades innebär detta också att det är omöjligt att förfalska en digital signatur. Den mest välanvända konstruktionen för att skapa digitala signaturer idag är RSA, som baseras på det svåra matematiska problemet att faktorisera heltal. Det finns dock andra matematiska problem som anses vara ännu svårare, vilket i praktiken innebär att nycklarna kan göras kortare, vilket i sin tur leder till att mindre minne behövs och att beräkningarna går snabbare. Ett sådant alternativ är att använda elliptiska kurvor. Det underliggande matematiska problemet för kryptering baserad på elliptiska kurvor skiljer sig från det som RSA bygger på, men de har en viss struktur gemensam. Syftet med detta examensarbete var att utvärdera hur elliptiska kurvor presterar jämfört med RSA, på ett system som är designat för att effektivt utföra RSA. De funna resultaten är att metoden med elliptiska kurvor ger stora fördelar, även om man nyttjar hårdvara avsedd för RSA, och att dessa fördelar ökar mångfaldigt om speciell hårdvara används. För några användarfall av digitala signaturer kan, under några år framöver, RSA fortfarande vara fördelaktigt om man bara tittar på hastigheten. För de flesta fall vinner dock elliptiska kurvor, och kommer troligen vara dominant inom kort.

Με την αύξηση της χρήσης του διαδικτύου σε εφαρμογές από απλή μεταφορά δεδομένων μέχρι ηλεκτρονικό εμπόριο, υπάρχει ανάγκη για ασφάλεια, η οποία έχει δώσει ώθηση στην έρευνα για κρυπτογραφικά πρωτόκολλα. Σήμερα είναι απαραίτητα πλέον τα πρωτόκολλα ασφαλείας σε όλες σχεδόν τις σημαντικές συναλλαγές, είτε είναι πρόσβαση σε κάποιο δίκτυο είτε για ηλεκτρονικό εμπόριο ή επικοινωνίες. Η κρυπτογραφία ελλειπτικών καμπυλών προσφέρει μια εναλλακτική λύση με εμφανή πλεονεκτήματα έναντι των παραδοσιακών συστημάτων ασφαλείας. Το βασικό τους πλεονέκτημα είναι ότι απαιτούν μικρότερο μήκος κλειδιού για επίτευξη ίδιου επιπέδου ασφαλείας με πιο παραδοσιακά κρυπτογραφικά συστήματα (όπως το RSA). Αυτή ακριβώς η ιδιότητα καθιστά τα κρυπτογραφικά συστήματα ελλειπτικών καμπυλών ιδιαίτερα ελκυστικά για εφαρμογή σε ενσωματωμένα συστήματα τα οποία εξορισμού έχουν περιορισμένους πόρους. Η παρούσα διπλωματική εργασία παρουσιάζει την μεταφορά μιας βιβλιοθήκης ελλειπτικών καμπυλών σε ένα ενσωματωμένο σύστημα. Ιδιαίτερο βάρος δόθηκε στην δημιουργία ελλειπτικών καμπυλών κατάλληλων για χρήση σε κρυπτογραφικά συστήματα. Η κατασκευή των ελλειπτικών καμπυλών οι οποίες θεωρούνται ασφαλείς γίνονται με την μέθοδο του μιγαδικού πολλαπλασιασμού, Παρουσιάζεται η διαδικασία μεταφοράς, τα προβλήματα καθώς και τα πειραματικά αποτελέσματα. Επίσης παρουσιάζεται μια εφαρμογή η οποία επιδεικνύει τις δυνατότητες δημιουργίας ασφαλούς ελλειπτικής καμπύλης καθώς και την χρήση της καμπύλης αυτής για ασφαλή μετάδοση δεδομένων. Έτσι έχουμε ένα ενσωματωμένο σύστημα, με περιορισμένες δυνατότητες, το οποίο όχι μόνο υλοποιεί τα κατάλληλα πρωτόκολλα ελλειπτικών καμπυλών, αλλά έχει την δυνατότητα να δημιουργεί ασφαλείς ελλειπτικές καμπύλες κατάλληλες για χρήση από άλλες συσκευές. / Over the last years there has been a rapid growth in Internet use and its benefits. Applications depending on connectivity range from simple networks to e-commerce and e-banking. Furthermore the nature of the hardware used in these transactions has been altered significally. Instead of high-end desktop computers laptops, PDAs and cell phones are widely used both in wired and wireless networks. In an environment as open as the Internet users may be in danger and their transactions may be compromised. There is an immediate need for safe cryptographic systems even for devices that meet hardware restrictions (i.e. processing power or memory and space limitations) without compromising the security levels required. Elliptic curve cryptography offers an interesting alternative in this direction instead of more traditional public key cryptosystem such as RSA. The main reason for this is the mathematical problems on which Elliptic Curve Cryptography (ECC) is based. ECC is based on the elliptic Curve Discrete Logarithm Problem (ECDLP). ECDLP is the ECC equivalent to DLP which is used in most public key cryptosystems and was introduced by Koblitz and Miller in 1985. So far the best algorithms for attacking the ECDLP take exponential time while for the DLP the time required is sub-exponential. This means that an ECC system can use smaller key size than traditional cryptosystems to achieve the same results. As an example, an ECC system with a key size of 160 bits is roughly equivalent to an RSA system with a key size of 1024 bits. Since the key size is significally smaller, so are requirements in space and memory, making ECC an excellent candidate for implementation in devices with limited resources. In this thesis we present an ECC library (ECC-LIB) in an embedded device with hardware limitations. ECC-LIB was developed by Elisavet Konstantinou, Yiannis Stamatiou, and Christos Zaroliagis as a tool to provide users with a modular library that allows development of various cryptographic protocols. We decided to use this library not on a desktop computer but on an embedded device to try and address any problems that might occur in such a limited environment. The device we selected is the AT76C520 chip, which can be used either as a wireless Access Point or as a network processor, with a microprocessor capable of running ucLinux, which is a Linux distribution for embedded devices. Our effort was focused on importing the library without changing the source code to ensure portability. We focused on the implementation of Complex Multiplication method for generating secure elliptic curves, which is not supported by most of the other implementations in embedded systems. Our experimental results demonstrate such an implementation is feasible and can produce efficiently elliptic curves suitable for use in cryptographic systems. Also, our implementation is highly portable. It can be used as is, or with minor changes, on practically any embedded system, since it is written exclusively in standard ANSI C, and there are no device specific optimizations (like assembly). We also implemented an application to support a working scenario. In this scenario our device is used as server from which other devices (wired or wireless, embedded or high end systems) can request an elliptic curve to use in order to achieve security in their communication. The client can request an elliptic curve of specific security level and our application can generate a suitable curve (using the Complex Multiplication method) and distribute it. This means that in a suitable environment plethora of devices can communicate safely, with devices types ranging from desktop computers to mobile phones and PDAs.