Exchange of private information over a public medium must incorporate a method for data protection against unauthorized access. Elliptic curve cryptography (ECC) has become widely accepted as an efficient mechanism to secure private data using public-key protocols. Scalar multiplication (which translates into a sequence of point operations each involving several modular arithmetic operations) is the main ECC computation, where the scalar value is secret and must be secured. In this dissertation, we consider ECC over five standard prime finite fields recommended by the National Institute of Standard and Technology (NIST), with the corresponding prime sizes of 192, 224, 256, 384, and 521 bits. This dissertation presents our general hardware-software approach and technical details of our novel hardware processor design, aimed at accelerating scalar multiplications with flexible security-performance tradeoffs. To enhance performance, our processor exploits parallelism by pipelining modular arithmetic computations and associated input/output data transfers. To enhance security, modular arithmetic computations and associated data transfers are grouped into atomically executed computational blocks, in order to make curve point operations indistinguishable and thus mask the scalar value. The flexibility of our processor is achieved through the software-controlled hardware programmability, which allows for different scenarios of computing atomic block sequences. Each scenario is characterized by a certain trade-off between the processor’s security and performance. As the best trade-off scenario is specific to the user and/or application requirements, our approach allows for such a scenario to be chosen dynamically by the system software, thus facilitating system adaptation to dynamically changing requirements. Since modular multiplications are the most critical low-level operation in ECC computations, we also propose a novel modular multiplier specifically optimized to take full advantage of the fast reduction algorithms associated with the five NIST primes. The proposed architecture has been prototyped on a Xilinx Virtex-6 FPGA and takes between 0.30 ms and 3.91 ms to perform a typical scalar multiplication. Such performance figures demonstrate both flexibility and efficiency of our proposed design and compares favourably against other systems reported in the literature. / Graduate

Elliptic Curve Cryptography (ECC), independently proposed by Miller [Mil86] and Koblitz [Kob87] in mid 80’s, is finding momentum to consolidate its status as the public-key system of choice in a wide range of applications and to further expand this position to settings traditionally occupied by RSA and DL-based systems. The non-existence of known subexponential attacks on this cryptosystem directly translates to shorter keylengths for a given security level and, consequently, has led to implementations with better bandwidth usage, reduced power and memory requirements, and higher speeds. Moreover, the dramatic entry of pairing-based cryptosystems defined on elliptic curves at the beginning of the new millennium has opened the possibility of a plethora of innovative applications, solving in some cases longstanding problems in cryptography. Nevertheless, public-key cryptography (PKC) is still relatively expensive in comparison with its symmetric-key counterpart and it remains an open challenge to reduce further the computing cost of the most time-consuming PKC primitives to guarantee their adoption for secure communication in commercial and Internet-based applications. The latter is especially true for pairing computations. Thus, it is of paramount importance to research methods which permit the efficient realization of Elliptic Curve and Pairing-based Cryptography on the several new platforms and applications. This thesis deals with efficient methods and explicit formulas for computing elliptic curve scalar multiplication and pairings over fields of large prime characteristic with the objective of enabling the realization of software implementations at very high speeds. To achieve this main goal in the case of elliptic curves, we accomplish the following tasks: identify the elliptic curve settings with the fastest arithmetic; accelerate the precomputation stage in the scalar multiplication; study number representations and scalar multiplication algorithms for speeding up the evaluation stage; identify most efficient field arithmetic algorithms and optimize them; analyze the architecture of the targeted platforms for maximizing the performance of ECC operations; identify most efficient coordinate systems and optimize explicit formulas; and realize implementations on x86-64 processors with an optimal algorithmic selection among all studied cases. In the case of pairings, the following tasks are accomplished: accelerate tower and curve arithmetic; identify most efficient tower and field arithmetic algorithms and optimize them; identify the curve setting with the fastest arithmetic and optimize it; identify state-of-the-art techniques for the Miller loop and final exponentiation; and realize an implementation on x86-64 processors with optimal algorithmic selection. The most outstanding contributions that have been achieved with the methodologies above in this thesis can be summarized as follows: • Two novel precomputation schemes are introduced and shown to achieve the lowest costs in the literature for different curve forms and scalar multiplication primitives. The detailed cost formulas of the schemes are derived for most relevant scenarios. • A new methodology based on the operation cost per bit to devise highly optimized and compact multibase algorithms is proposed. Derived multibase chains using bases {2,3} and {2,3,5} are shown to achieve the lowest theoretical costs for scalar multiplication on certain curve forms and for scenarios with and without precomputations. In addition, the zero and nonzero density formulas of the original (width-w) multibase NAF method are derived by using Markov chains. The application of “fractional” windows to the multibase method is described together with the derivation of the corresponding density formulas. • Incomplete reduction and branchless arithmetic techniques are optimally combined for devising high-performance field arithmetic. Efficient algorithms for “small” modular operations using suitably chosen pseudo-Mersenne primes are carefully analyzed and optimized for incomplete reduction. • Data dependencies between contiguous field operations are discovered to be a source of performance degradation on x86-64 processors. Three techniques for reducing the number of potential pipeline stalls due to these dependencies are proposed: field arithmetic scheduling, merging of point operations and merging of field operations. • Explicit formulas for two relevant cases, namely Weierstrass and Twisted Edwards curves over and , are carefully optimized employing incomplete reduction, minimal number of operations and reduced number of data dependencies between contiguous field operations. • Best algorithms for the field, point and scalar arithmetic, studied or proposed in this thesis, are brought together to realize four high-speed implementations on x86-64 processors at the 128-bit security level. Presented results set new speed records for elliptic curve scalar multiplication and introduce up to 34% of cost reduction in comparison with the best previous results in the literature. • A generalized lazy reduction technique that enables the elimination of up to 32% of modular reductions in the pairing computation is proposed. Further, a methodology that keeps intermediate results under Montgomery reduction boundaries maximizing operations without carry checks is introduced. Optimized formulas for the popular tower are explicitly stated and a detailed operation count that permits to determine the theoretical cost improvement attainable with the proposed method is carried out for the case of an optimal ate pairing on a Barreto-Naehrig (BN) curve at the 128-bit security level. • Best algorithms for the different stages of the pairing computation, including the proposed techniques and optimizations, are brought together to realize a high-speed implementation at the 128-bit security level. Presented results on x86-64 processors set new speed records for pairings, introducing up to 34% of cost reduction in comparison with the best published result. From a general viewpoint, the proposed methods and optimized formulas have a practical impact in the performance of cryptographic protocols based on elliptic curves and pairings in a wide range of applications. In particular, the introduced implementations represent a direct and significant improvement that may be exploited in performance-dominated applications such as high-demand Web servers in which millions of secure transactions need to be generated.

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» φακέλους αρχείων και κατ΄ επέκταση σκληρούς δίσκους / -

This dissertation emphasizes the security aspects of real-time media. The problems of existing real-time media protections are identified in this research, and viable solutions are proposed. First, the security of real-time media depends on the Secure Real-time Transport Protocol (SRTP) mechanism. We identified drawbacks of the existing SRTP Systems, which use symmetric key encryption schemes, which can be exploited by attackers. Elliptic Curve Cryptography (ECC), an asymmetric key cryptography scheme, is proposed to resolve these problems. Second, the ECC encryption scheme is based on elliptic curves. This dissertation explores the weaknesses of a widely used elliptic curve in terms of security and describes a more secure elliptic curve suitable for real-time media protection. Eighteen elliptic curves had been tested in a real-time video transmission system, and fifteen elliptic curves had been tested in a real-time audio transmission system. Based on the performance, X9.62 standard 256-bit prime curve, NIST-recommended 256-bit prime curves, and Brainpool 256-bit prime curves were found to be suitable for real-time audio encryption. Again, X9.62 standard 256-bit prime and 272-bit binary curves, and NIST-recommended 256-bit prime curves were found to be suitable for real-time video encryption.The weaknesses of NIST-recommended elliptic curves are discussed and a more secure new elliptic curve is proposed which can be used for real-time media encryption. The proposed curve has fulfilled all relevant security criteria, but the corresponding NIST curve could not fulfill two such criteria. The research is applicable to strengthen the security of the Internet of Things (IoT) devices, especially VoIP cameras. IoT devices have resource constraints and thus need lightweight encryption schemes for security. ECC could be a better option for these devices. VoIP cameras use a similar methodology to traditional real-time video transmission, so this research could be useful to find a better security solution for these devices.

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.

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.