Elliptic curve cryptosystems were proposed in 1985 by Victor Miller and by Neal Koblitz independently. Since elliptic curve discrete logarithm problem is harder to solve than discrete logarithm problem in finite fields. If is believed that the key length of elliptic curve cryptosystems can be shorter then that of RSA with the same security strength. The most important work of using elliptic curve cryptosystem is constructing a group from a proper elliptic curve. The major work of constructing an elliptic curve is counting points on elliptic curves over finite fields. In 1985, Schoof published a deterministic polynomial time algorithm for computing the number of points on the elliptic curves over finite fields. We consult IEEE P1363 to implement pseudo random elliptic curve.

Security issues have started to play an important role in the wireless communication and computer networks due to the migration of commerce practices to the electronic medium. The deployment of security procedures requires the implementation of cryptographic algorithms. Performance has always been one of the most critical issues of a cryptographic function, which determines its effectiveness. Among those cryptographic algorithms are the elliptic curve cryptosystems which use the arithmetic of finite fields. Furthermore, fields of characteristic two are preferred since they provide carry-free arithmetic and at the same time a simple way to represent field elements on current processor architectures. Multiplication is a very crucial operation in finite field computations. In this contribution, we compare most of the multiplier architectures found in the literature to clarify the issue of choosing a suitable architecture for a specific application. The importance of the measuring the energy consumption in addition to the conventional measures for energy-critical applications is also emphasized. A new parallel-in serial-out multiplier based on all-one polynomials (AOP) using the shifted polynomial basis of representation is presented. The proposed multiplier is area efficient for hardware realization. Low hardware complexity is advantageous for implementation in constrained environments such as smart cards. Architecture of an elliptic curve coprocessor has been developed using the proposed multiplier. The instruction set architecture has been also designed. The coprocessor has been simulated using VHDL to very the functionality. The coprocessor is capable of performing the scalar multiplication operation over elliptic curves. Point doubling and addition procedures are hardwired inside the coprocessor to allow for faster operation.

Security issues have started to play an important role in the wireless communication and computer networks due to the migration of commerce practices to the electronic medium. The deployment of security procedures requires the implementation of cryptographic algorithms. Performance has always been one of the most critical issues of a cryptographic function, which determines its effectiveness. Among those cryptographic algorithms are the elliptic curve cryptosystems which use the arithmetic of finite fields. Furthermore, fields of characteristic two are preferred since they provide carry-free arithmetic and at the same time a simple way to represent field elements on current processor architectures. Multiplication is a very crucial operation in finite field computations. In this contribution, we compare most of the multiplier architectures found in the literature to clarify the issue of choosing a suitable architecture for a specific application. The importance of the measuring the energy consumption in addition to the conventional measures for energy-critical applications is also emphasized. A new parallel-in serial-out multiplier based on all-one polynomials (AOP) using the shifted polynomial basis of representation is presented. The proposed multiplier is area efficient for hardware realization. Low hardware complexity is advantageous for implementation in constrained environments such as smart cards. Architecture of an elliptic curve coprocessor has been developed using the proposed multiplier. The instruction set architecture has been also designed. The coprocessor has been simulated using VHDL to very the functionality. The coprocessor is capable of performing the scalar multiplication operation over elliptic curves. Point doubling and addition procedures are hardwired inside the coprocessor to allow for faster operation.

An important advantage of Elliptic Curve Cryptosystem (ECC) is the shorter key length in public key cryptographic systems. It can provide adequate security when the bit length over than 160 bits. Therefore, it has become a popular system in recent years. Scalar multiplication also called point multiplication is the core operation in ECC. In this thesis, we propose the ECC architectures of two different irreducible polynomial versions that are trinomial in GF(2167) and pentanomial in GF(2163). These architectures are based on Montgomery point multiplication with projective coordinate. We use polynomial basis representation for finite field arithmetic. All adopted multiplication, square and add operations over binary field can be completed within one clock cycle, and the critical path lies on multiplication. In addition, we use Itoh-Tsujii algorithm combined with addition chain, to execute binary inversion through using iterative binary square and multiplication. Because the double and add operations in point multiplication need to run many iterations, the execution time in overall design will be decreased if we can improve this partition. We propose two ways to improve the performance of point multiplication. The first way is Minus Cycle Version. In this version, we reschedule the double and add operations according to point multiplication algorithm. When the clock cycle time (i.e., critical path) of multiplication is longer than that of add and square, this method will be useful in improving performance. The second way is Pipeline Version. It speeds up the multiplication operations by executing them in pipeline, leading to shorter clock cycle time. For the hardware implementation, TSMC 0.13um library is employed and all modules are organized in a hierarchy structure. The implementation result shows that the proposed 167-bit Minus Cycle Version requires 156.4K gates, and the execution time of point multiplication is 2.34us and the maximum speed is 591.7Mhz. Moreover, we compare the Area x Time (AT) value of proposed architectures with other relative work. The results exhibit that proposed 167-bit Minus Cycle Version is the best one and it can save up to 38% A T value than traditional one.

In asymmetric cryptosystems, an important advantage of Elliptic Curve Cryptosystem (ECC) is the shorter key lengths than other cryptosystems. It can provide a level of security when the bit length over than 160 bits. So it has become a popular public key cryptographic system in recent year. Multiplier needs to run many times in scalar multiplication and it plays an essential role in ECC. Since the registers in multiplier are shifted every iteration, it will consume a lot of power in the computing process. So in this thesis, we propose five methods to save multiplication¡¦s energy consumption based on a scalable serial-parallel algorithm[1]. The first method is to design a low-power shift-register by modifying shift-register B to reduce the frequency of registers shifted. The second method is to use a frequency divider circuit. It can make registers to access a value every two clock cycles by modifying RA units. The third method is to introduce the gated clock circuit, and the clock signal of register will be disabled if its value is the same. The fourth method is to skip redundant operations and it can decrease the number of clock cycles for completing a multiplication operation. The last method raises multiplier¡¦s throughput by modifying RA units. The former three methods focus on low-power design, and the latter two methods emphasize on improving performance. Reducing power consumption and improving performance will save multiplication¡¦s energy consumption. Finally, we propose a Half Cycles schedule to raise scalar multiplication¡¦s performance. It is based on Montgomery scalar multiplication algorithm with projective coordinate[22][26]. For the hardware implementation, TSMC 0.13um library is employed and all modules are organized in a hierarchy structure. The implementation results show that the proposed multipliers have less energy consumption than traditional multiplier. It can get 5% ~ 24% energy saving. For Montgomery scalar multiplication, it can also reduce 12% ~ 47% energy consumption and is suitable for portable electronic products because its low area complexity and low energy.

Elliptic curves were first proposed as a basis for public key cryptography in the mid 1980's. They provide public key cryptosystems based on the difficulty of the elliptic curve discrete logarithm problem (ECDLP) , which is so called because of its similarity to the discrete logarithm problem (DLP) over the integers modulo a large prime. One benefit of elliptic curve cryptosystems (ECCs) is that they can use a much shorter key length than other public key cryptosystems to provide an equivalent level of security. For example, 160 bit ECCs are believed to provide about the same level of security as 1024 bit RSA. Also, the level of security provided by an ECC increases faster with key size than for integer based discrete logarithm (dl) or RSA cryptosystems. ECCs can also provide a faster implementation than RSA or dl systems, and use less bandwidth and power. These issues can be crucial in lightweight applications such as smart cards. In the last few years, ECCs have been included or proposed for inclusion in internationally recognized standards. Thus elliptic curve cryptography is set to become an integral part of lightweight applications in the immediate future. This thesis presents an analysis of several important issues for ECCs on lightweight devices. It begins with an introduction to elliptic curves and the algorithms required to implement an ECC. It then gives an analysis of the speed, code size and memory usage of various possible implementation options. Enough details are presented to enable an implementer to choose for implementation those algorithms which give the greatest speed whilst conforming to the code size and ram restrictions of a particular lightweight device. Recommendations are made for new functions to be included on coprocessors for lightweight devices to support ECC implementations Another issue of concern for implementers is the side-channel attacks that have recently been proposed. They obtain information about the cryptosystem by measuring side-channel information such as power consumption and processing time and the information is then used to break implementations that have not incorporated appropriate defences. A new method of defence to protect an implementation from the simple power analysis (spa) method of attack is presented in this thesis. It requires 44% fewer additions and 11% more doublings than the commonly recommended defence of performing a point addition in every loop of the binary scalar multiplication algorithm. The algorithm forms a contribution to the current range of possible spa defences which has a good speed but low memory usage. Another topic of paramount importance to ECCs for lightweight applications is whether the security of fixed curves is equivalent to that of random curves. Because of the inability of lightweight devices to generate secure random curves, fixed curves are used in such devices. These curves provide the additional advantage of requiring less bandwidth, code size and processing time. However, it is intuitively obvious that a large precomputation to aid in the breaking of the elliptic curve discrete logarithm problem (ECDLP) can be made for a fixed curve which would be unavailable for a random curve. Therefore, it would appear that fixed curves are less secure than random curves, but quantifying the loss of security is much more difficult. The thesis performs an examination of fixed curve security taking this observation into account, and includes a definition of equivalent security and an analysis of a variation of Pollard's rho method where computations from solutions of previous ECDLPs can be used to solve subsequent ECDLPs on the same curve. A lower bound on the expected time to solve such ECDLPs using this method is presented, as well as an approximation of the expected time remaining to solve an ECDLP when a given size of precomputation is available. It is concluded that adding a total of 11 bits to the size of a fixed curve provides an equivalent level of security compared to random curves. The final part of the thesis deals with proofs of security of key exchange protocols in the Canetti-Krawczyk proof model. This model has been used since it offers the advantage of a modular proof with reusable components. Firstly a password-based authentication mechanism and its security proof are discussed, followed by an analysis of the use of the authentication mechanism in key exchange protocols. The Canetti-Krawczyk model is then used to examine secure tripartite (three party) key exchange protocols. Tripartite key exchange protocols are particularly suited to ECCs because of the availability of bilinear mappings on elliptic curves, which allow more efficient tripartite key exchange protocols.