Fault analysis attacks represent a serious threat to a wide range of cryptosystems including those based on elliptic curves. With the variety and demonstrated practicality of these attacks, it is essential for cryptographic implementations to handle different types of errors properly and securely. In this work, we address some aspects of error detection and recovery in elliptic curve cryptosystems. In particular, we discuss the problem of wasteful computations performed between the occurrence of an error and its detection and propose solutions based on frequent validation to reduce that waste. We begin by presenting ways to select the validation frequency in order to minimize various performance criteria including the average and worst-case costs and the reliability threshold. We also provide solutions to reduce the sensitivity of the validation frequency to variations in the statistical error model and its parameters. Then, we present and discuss adaptive error recovery and illustrate its advantages in terms of low sensitivity to the error model and reduced variance of the resulting overhead especially in the presence of burst errors. Moreover, we use statistical inference to evaluate and fine-tune the selection of the adaptive policy. We also address the issue of validation testing cost and present a collection of coherency-based, cost-effective tests. We evaluate variations of these tests in terms of cost and error detection effectiveness and provide infective and reduced-cost, repeated-validation variants. Moreover, we use coherency-based tests to construct a combined-curve countermeasure that avoids the weaknesses of earlier related proposals and provides a flexible trade-off between cost and effectiveness.

Implementation of elliptic and hyperelliptic curve cryptographic algorithms has been the focus of a great deal of recent research directed at increasing efficiency. Elliptic curve cryptography (ECC) was introduced independently by Koblitz and Miller in the 1980s. Hyperelliptic curve cryptography (HECC), a generalization of the elliptic curve case, allows a decreasing field size as the genus increases. The work presented in this thesis examines the problems created by limited area, power, and computation time when elliptic and hyperelliptic curves are integrated into constrained devices such as wireless sensor network (WSN) and smart cards. The lack of a battery in wireless sensor network limits the processing power of these devices, but they still require security. It was widely believed that devices with such constrained resources cannot incorporate a strong HECC processor for performing cryptographic operations such as elliptic curve scalar multiplication (ECSM) or hyperelliptic curve divisor multiplication (HCDM). However, the work presented in this thesis has demonstrated the feasibility of integrating an HECC processor into such devices through the use of the proposed architecture synthesis and optimization techniques for several inversion-free algorithms. The goal of this work is to develop a hardware implementation of binary elliptic and hyperelliptic curves. The focus is on the modeling of three factors: register allocation, operation scheduling, and storage binding. These factors were then integrated into architecture synthesis and optimization techniques in order to determine the best overall implementation suitable for constrained devices. The main purpose of the optimization is to reduce the area and power. Through analysis of the architecture optimization techniques for both datapath and control unit synthesis, the number of registers was reduced by an average of 30%. The use of the proposed efficient explicit formula for the different algorithms also enabled a reduction in the number of read/write operations from/to the register file, which reduces the processing power consumption. As a result, an overall HECC processor requires from 1843 to 3595 slices for a Xilinix XC4VLX200 and the total computation time is limited to between 10.08 ms to 15.82 ms at a maximum frequency of 50 MHz for a varity of inversion-free coordinate systems in hyperelliptic curves. The value of the new model has been demonstrated with respect to its implementation in elliptic and hyperelliptic curve crypogrpahic algorithms, through both synthesis and simulations. In summary, a framework has been provided for consideration of interactions with synthesis and optimization through architecture modeling for constrained enviroments. Insights have also been presented with respect to improving the design process for cryptogrpahic algorithms through datapath and control unit analysis.

Στην παρούσα διπλωματική υλοποιήθηκε η σχεδίαση και υλοποίηση ασφαλούς υπηρεσίας με χρήση ελλειπτικής κρυπτογραφίας. Τα κρυπτογραφικά συστήματα που βασίζονται στις ελλειπτικές καμπύλες αποτελούν ένα πολύ σημαντικό κομμάτι της κρυπτογραφίας δημόσιου κλειδιού και τα τελευταία χρόνια όλο και περισσότεροι επιστήμονες ασχολούνται με τη μελέτη τους. Το πλεονέκτημα των συστημάτων αυτών σε σχέση με τα συμβατικά κρυπτογραφικά συστήματα είναι ότι χρησιμοποιούν μικρότερες παραμέτρους και κλειδιά, προσφέροντας τα ίδια επίπεδα ασφάλειας. Σχετικά με το πρόβλημα της προστασίας ευαίσθητων δεδομένων σκληρού δίσκου ή άλλου αποθηκευτικού μέσου διευθυνσιοδοτούμενου κατά τομείς (sector-adressed storage media), χρησιμοποιείται η τεχνική της κρυπτογράφησης δίσκου (disk encryption). Ορισμένα από τα υπεύθυνα για την υλοποίηση της κρυπτογράφησης λογισμικά (disk encryption software) χρησιμοποιούν την μέθοδο κρυπτογράφησης σε πραγματικό χρόνο (on-the-fly/real-time encryption). Ο όρος on-the-fly έγκειται στο γεγονός ότι τα αρχεία γίνονται προσβάσιμα αμέσως μόλις προσφερθεί το κλειδί κρυπτογράφησης (encryption key) όλο το διαμέρισμα (volume) «προσαρτάται» (mounted) σαν να ήταν ένας φυσικός δίσκος κάνοντας τα αρχεία να «φαίνονται» αποκρυπτογραφημένα. Στην πλαίσιο αυτό τοποθετείται ο σκοπός του ερευνητικού μέρους της παρούσας εργασίας, που εντοπίζεται το ερώτημα της προσαρμογής βιβλιοθηκών που υλοποιούν κρυπτογραφία ελλειπτικών καμπυλών σε λογισμικό ικανό να κρυπτογραφεί «on the fly» φακέλους αρχείων και κατ΄ επέκταση σκληρούς δίσκους / -

Digital signatures, which take the properties of classical signatures, are used to secure the actual content of documents, which can be modified during transmission over an insecure channel. The problems of security and protection of communicating participants are solved by cryptographic techniques. Identity verification, message integrity, credibility, the ownership of documents, and the secure transmission of information over an unsecured channel, are all dealt with in secure communications - Public Key Infrastructure, which uses digital signatures. Nowadays digital signatures are often used to secure data in communication over an unsecured channel. The aim of the following master’s thesis is to familiarize readers with the necessary technological aspects of digital signatures, as well as their advantages and disadvantages. By the time digital signatures are being used they will have to be improved and modified to be secure against more sophisticated attacks. In this paper, proposals of new efficient digital signature schemes and their comparison with current ones are described. Also are examined their implications for computationally weak devices, or deployment in low speed channel transmission systems. After an explanation of cryptography and a description of its basic subjects, digital signatures are introduced. The first chapter describes the possible formatting and architecture of the digital signature. The second part of this master’s thesis is about current digital signature schemes and their properties. Chapter 3 describes some proposals of new efficient digital signature schemes and their comparison to those currently in use. In the practical part, the implementations (in the environment .NET in C#) of two effective digital signature schemes as part of a client-server application are presented and described (Chapter 4). In the last chapter the comparison and analysis of the implemented signature schemes are provided.

La Cryptographie sur les Courbes Elliptiques (abréviée ECC de l'anglais Elliptic Curve Cryptography) est devenue très importante dans les cartes à puces car elle présente de meilleures performances en temps et en mémoire comparée à d'autres cryptosystèmes asymétriques comme RSA. ECC est présumé incassable dans le modèle dit « Boite Noire », où le cryptanalyste a uniquement accès aux entrées et aux sorties. Cependant, ce n'est pas suffisant si le cryptosystème est embarqué dans un appareil qui est physiquement accessible à de potentiels attaquants. En plus des entrés et des sorties, l'attaquant peut étudier le comportement physique de l'appareil. Ce nouveau type de cryptanalyse est appelé cryptanalyse physique. Cette thèse porte sur les attaques physiques sur ECC. La première partie fournit les pré-requis sur ECC. Du niveau le plus bas au plus élevé, ECC nécessite les outils suivants : l'arithmétique sur les corps finis, l'arithmétique sur courbes elliptiques, la multiplication scalaire sur courbes elliptiques et enfin les protocoles cryptographiques. La deuxième partie expose un état de l'art des différentes attaques physiques et contremesures sur ECC. Pour chaque attaque, nous donnons le contexte dans lequel elle est applicable. Pour chaque contremesure, nous estimons son coût en temps et en mémoire. Nous proposons de nouvelles attaques et de nouvelles contremesures. Ensuite, nous donnons une synthèse claire des attaques suivant le contexte. Cette synthèse est utile pendant la tâche du choix des contremesures. Enfin, une synthèse claire de l'efficacité de chaque contremesure sur les attaques est donnée. / Elliptic Curve Cryptography (ECC) has gained much importance in smart cards because of its higher speed and lower memory needs compared with other asymmetric cryptosystems such as RSA. ECC is believed to be unbreakable in the black box model, where the cryptanalyst has access to inputs and outputs only. However, it is not enough if the cryptosystem is embedded on a device that is physically accessible to potential attackers. In addition to inputs and outputs, the attacker can study the physical behaviour of the device. This new kind of cryptanalysis is called Physical Cryptanalysis. This thesis focuses on physical cryptanalysis of ECC. The first part gives the background on ECC. From the lowest to the highest level, ECC involves a hierarchy of tools: Finite Field Arithmetic, Elliptic Curve Arithmetic, Elliptic Curve Scalar Multiplication and Cryptographie Protocol. The second part exhibits a state-of-the-art of the different physical attacks and countermeasures on ECC.For each attack, the context on which it can be applied is given while, for each countermeasure, we estimate the lime and memory cost. We propose new attacks and new countermeasures. We then give a clear synthesis of the attacks depending on the context. This is useful during the task of selecting the countermeasures. Finally, we give a clear synthesis of the efficiency of each countermeasure against the attacks.

In this paper, we present a study of elliptic curves, focusing on theirunderlying mathematical concepts, properties and applications in numbertheory. We begin by introducing elliptic curves and their unique features,discussing their algebraic structure, and exploring their group law, pro-viding examples and geometric interpretations. The core of our studyfocuses on the Elliptic Curve Method (ECM) for integer factorization.We present the motivation behind ECM and compare it to Pollard’s (p-1) method. A discussion on pseudocurves and the choice of an ellipticcurve and bound B is provided. We also address the differences betweenECM and Pollard’s (p-1) method and propose optimization techniques forECM, including the calculation of the least common multiple (LCM) ofthe first B integers using the Sieve of Eratosthenes.

京都大学 / 新制・課程博士 / 博士(理学) / 甲第24389号 / 理博第4888号 / 新制||理||1699(附属図書館) / 京都大学大学院理学研究科数学・数理解析専攻 / (主査)教授 玉川 安騎男, 教授 並河 良典, 教授 望月 新一 / 学位規則第4条第1項該当 / Doctor of Science / Kyoto University / DGAM

[pt] Curvas elípticas são objeto de estudo pelos matemáticos há mais de 200 anos. Por si só, é uma teoria bastante interessante por estar relacionada com diversas áreas da matemática: álgebra, equações diofantinas e geometria algébrica, dentre outras. Recentemente, diversos pesquisadores sugeriram o uso de curvas elípticas para resolver problemas práticos; como exemplos, podemos citar a criptografia, algoritmos para fatoração de números inteiros e testes de primalidade. Uma curva elíptica é definida sobre um corpo (no sentido algébrico). Essa dissertação tem por objetivo apresentar os primeiros elementos da teoria das curvas elípticas sobre corpos finitos. Como veremos, o desenvolvimento do tema aborda diversos tópicos da educação básica. Para isso, iniciaremos o trabalho com uma introdução utilizando o corpo dos números reais e, em seguida, incluiremos a teoria mais geral sobre essas curvas algébricas. Concluiremos então com algumas propriedades e resultados de curvas elípticas sobre corpos finitos, incluindo alguns exemplos e a interpretação geométrica da soma de dois pontos de curvas sobre corpos finitos específicos. / [en] Elliptic curves have been studied by mathematicians for over 200 years. By itself, it is a remarkably interesting theory as it is related to several areas of mathematics: algebra, Diophantine equations and algebraic geometry, among others. Recently, several researchers have suggested the use of elliptic curves to solve practical problems; as examples, we can mention cryptography, integer factorization algorithms and primality tests. An elliptic curve is defined over a field (in algebraic sense). This dissertation aims to present the first elements in the theory of elliptic curves on finite fields. As we will see, the development of the subject addresses a number of topics covered in basic education. In order to accomplish this, we will start the work with an introduction using the field of real numbers and then we will include the more general theory about these algebraic curves. Finally, we will present some properties and results on elliptic curves over finite fields, including some examples and a geometric interpretation of the sum of two points over specific finite fields.

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.