International Telemetering Conference Proceedings / October 20-23, 2003 / Riviera Hotel and Convention Center, Las Vegas, Nevada / SSL protocol is one industrial standard to protect data transferred securely on Internet. Firstly SSL is analyzed, according to its characteristics, one solution plan on mobile bank based on SSL is proposed and presented, in which GPRS technology is adopted and elliptic curve algorithm is used for the session key, finally several functional modules of mobile bank are designed in details and its security is analyzed.

Context. Digital counterparts of handwritten signatures are known as Digital Signatures. The Elliptic Curve Digital Signature Algorithm (ECDSA) is an Elliptic Curve Cryptography (ECC) primitive, which is used for generating and verifying digital signatures. The attacks that target an implementation of a cryptosystem are known as side-channel attacks. The Flush+Reload attack is a cache side-channel attack that relies on cache hits/misses to recover secret information from the target program execution. In elliptic curve cryptosystems, side-channel attacks are particularly targeted towards the point multiplication step. The Gallant-Lambert-Vanstone (GLV) method for point multiplication is a special method that speeds up the computation for elliptic curves with certain properties. Objectives. In this study, we investigate the applicability of the Flush+Reload attack on ECDSA signatures that employ the GLV method to protect point multiplication. Methods. We demonstrate the attack through an experiment using the curve secp256k1. We perform a pair of experiments to estimate both the applicability and the detection rate of the attack in capturing side-channel information. Results. Through our attack, we capture side-channel information about the decomposed GLV scalars. Conclusions. Based on an analysis of the results, we conclude that for certain implementation choices, the Flush+Reload attack is applicable on ECDSA signature generation process that employs the GLV method. The practitioner should be aware of the implementation choices which introduce vulnerabilities, and avoid the usage of such ECDSA implementations.

"Elliptic Curve Cryptosystems (ECCs) are utilized as an alternative to traditional public-key cryptosystems, and are more suitable for resource limited environments due to smaller parameter size. In this dissertation we carry out a thorough investigation of side-channel attack aware ECC implementations over finite fields of prime characteristic including the recently introduced Edwards formulation of elliptic curves, which have built-in resiliency against simple side-channel attacks. We implement Joye's highly regular add-always scalar multiplication algorithm both with the Weierstrass and Edwards formulation of elliptic curves. We also propose a technique to apply non-adjacent form (NAF) scalar multiplication algorithm with side-channel security using the Edwards formulation. Our results show that the Edwards formulation allows increased area-time performance with projective coordinates. However, the Weierstrass formulation with affine coordinates results in the simplest architecture, and therefore has the best area-time performance as long as an efficient modular divider is available."

For some applications, elliptic curve cryptography (ECC) is an attractive choice because it achieves the same level of security with a much smaller key size in comparison with other schemes such as those that are based on integer factorization or discrete logarithm. Unfortunately, cryptosystems including those based on elliptic curves have been subject to attacks. For example, fault-based attacks have been shown to be a real threat in today’s cryptographic implementations. In this thesis, we consider fault-based attacks and countermeasures for ECC. We propose a new fault-based attack against the Montgomery ladder elliptic curve scalar multiplication (ECSM) algorithm. For security reasons, especially to provide resistance against fault-based attacks, it is very important to verify the correctness of computations in ECC applications. We deal with protections to fault attacks against ECSM at two levels: module and algorithm. For protections at the module level, where the underlying scalar multiplication algorithm is not changed, a number of schemes and hardware structures are presented based on re-computation or parallel computation. It is shown that these structures can be used for detecting errors with a very high probability during the computation of ECSM. For protections at the algorithm level, we use the concepts of point verification (PV) and coherency check (CC). We investigate the error detection coverage of PV and CC for the Montgomery ladder ECSM algorithm. Additionally, we propose two algorithms based on the double-and-add-always method that are resistant to the safe error (SE) attack. We demonstrate that one of these algorithms also resists the sign change fault (SCF) attack.

For some applications, elliptic curve cryptography (ECC) is an attractive choice because it achieves the same level of security with a much smaller key size in comparison with other schemes such as those that are based on integer factorization or discrete logarithm. Unfortunately, cryptosystems including those based on elliptic curves have been subject to attacks. For example, fault-based attacks have been shown to be a real threat in today’s cryptographic implementations. In this thesis, we consider fault-based attacks and countermeasures for ECC. We propose a new fault-based attack against the Montgomery ladder elliptic curve scalar multiplication (ECSM) algorithm. For security reasons, especially to provide resistance against fault-based attacks, it is very important to verify the correctness of computations in ECC applications. We deal with protections to fault attacks against ECSM at two levels: module and algorithm. For protections at the module level, where the underlying scalar multiplication algorithm is not changed, a number of schemes and hardware structures are presented based on re-computation or parallel computation. It is shown that these structures can be used for detecting errors with a very high probability during the computation of ECSM. For protections at the algorithm level, we use the concepts of point verification (PV) and coherency check (CC). We investigate the error detection coverage of PV and CC for the Montgomery ladder ECSM algorithm. Additionally, we propose two algorithms based on the double-and-add-always method that are resistant to the safe error (SE) attack. We demonstrate that one of these algorithms also resists the sign change fault (SCF) attack.

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.

The objective of this research is focused on two of the most important privacy-preserving techniques: privacy-preserving element matching protocols and privacy-preserving credential authentication protocols, where an element represents the information generated by users themselves and a credential represents a group membership assigned from an independent central authority (CA). The former is also known as private set intersection (PSI) protocol and the latter is also known as secret handshake (SH) protocol. In this dissertation, I present a general framework for design of efficient and secure PSI and SH protocols based on similar message exchange and computing procedures to confirm “commonality” of their exchanged information, while protecting the information from each other when the commonalty test fails. I propose to use the homomorphic randomization function (HRF) to meet the privacy-preserving requirements, i.e., common element/credential can be computed efficiently based on homomorphism of the function and uncommon element/credential are difficult to derive because of the randomization of the same function. Based on the general framework two new PSI protocols with linear computing and communication cost are proposed. The first protocol uses full homomorphic randomization function as the cryptographic basis and the second one uses partial homomorphic randomization function. Both of them achieve element confidentiality and private set intersection. A new SH protocol is also designed based on the framework, which achieves unlinkability with a reusable pair of credential and pseudonym and least number of bilinear mapping operations. I also propose to interlock the proposed PSI protocols and SH protocol to design new protocols with new security properties. When a PSI protocol is executed first and the matched elements are associated with the credentials in a following SH protocol, authenticity is guaranteed on matched elements. When a SH protocol is executed first and the verified credentials is used in a following PSI protocol, detection resistance and impersonation attack resistance are guaranteed on matching elements. The proposed PSI and SH protocols are implemented to provide privacy-preserving inquiry matching service (PPIM) for social networking applications and privacy-preserving correlation service (PAC) of network security alerts. PPIM allows online social consumers to find partners with matched inquiries and verified group memberships without exposing any information to unmatched parties. PAC allows independent network alert sources to find the common alerts without unveiling their local network information to each other.

The representation of field elements has a great impact on the performance of the finite field arithmetic. In this thesis, we give modified version of redundant representation which works for any finite fields of arbitrary characteristics to design arithmetic circuits with small complexity. Using our modified redundant representation, we improve many of the complexity values. We then propose new representations as an alternative way to represent finite fields of characteristic two by using Charlier and Hermite polynomials. We show that multiplication in these representations can be achieved with subquadratic space complexity. Charlier and Hermite representations enable us to find binomial, trinomial or quadranomial irreducible polynomials which allows us faster modular reduction over binary fields when there is no desirable such low weight irreducible polynomial in other representations. These representations are very interesting for the NIST and SEC recommended binary fields GF(2^{283}) and GF(2^{571}) since there is no optimal normal basis (ONB) for the corresponding extensions. It is also shown that in some cases the proposed representations have better space complexity even if there exists an ONB for the corresponding extension.