Research On Finite Fields Arithmetic For Elliptic Curve Cryptography

The Elliptic Curve Cryptosystem (ECC) has played an important role in the public-key cryptosystem. It is shown that ECC has advantages over other cryptosystems in both performance and security. The efficiency of the ECC actually depends on the point addition and scalar multiplication of an elliptic curve, which is defined over a finite field. However, the two operations relay on the arithmetic of the corresponding finite field. The construction of an elliptic curve usually focus on three types of finite fields, i.e., prime field GF(p), GF(2~m) with m some positive integer, GF(p~m) with p>2 a prime and m some positive integer. Although a lot of work has focused the high performance of the finite field arithmetic, there are still some further works can be done. Whereas, in this thesis, we make further research on the above areas, mainly focus on the arithmetic of the field GF(p~m) (p>2) and GF(2~m), propose some efficient solutions and obtain several research achievements. The main research contents in this thesis include four aspects, which are described as follows:Firstly, we do research on the implementation of multiplication in GF(p~m), mainly focus on the optimization using Chinese remainder theorem (CRT). By utilizing the simplicity of modular operation with respect to binomials, we proposed an alternative representation for GF(p~m), namely, binomial residue representation (BR). Based on this representation, an efficient Montgomery multiplication is developed. Meanwhile, a new type of irreducible polynomials using the BR representation is constructed. The distribution about this type of polynomials is evaluated and an efficient multiplication modulo such polynomial is also proposed. Moreover, Fast Fourier Transform (FFT) approach is applied to improve the modular multiplication further. The corresponding tricks can be used for the optimization of NTRU. Secondly, we study the inversion computation in GF(pm). A new inversion algorithm using BR representation is developed. It is derived from the Extended Euclidean Algorithm and can obtain the field inverse without any transformation between polynomial basis (PB) representation and the BR representation. We also show that the multiplication modulo binomial can be improved using the BR representation. Under this precondition, the inversion based on Frobenius mapping is also investigated. Thirdly, we propose three types of bit-parallel GF(2~m) multipliers. All these multipliers utilize the Karatsuba-Offman algorithm. The first multiplier is a modification of classic Karatsuba algorithm for trinomials. The time delay is reduced by slight increase of space complexity. The other multipliers are designed for two kinds of irreducible trinomials. The mainly technique is based on the combination of Shifted Polynomial Basis (SPB) and Karatsuba algorithm. These two multipliers outperform others if the time and space complexity are both considered.Finally, we propose three inversion algorithms for GF(2~m) which is based on Fermat's little theorem. One is an improvement of Itoh-Tsujii (IT) algorithm using fast forth power operation. The other two are extended from the Takagi-Yoshiki-Takagi (TYT) algorithm. The first multiplier has less time complexity while the other two multipliers have less space complexities without increasing the time complexity.The innovation works in this thesis mainly have:1. Propose an alternative field representation named BR representation using binomial residue arithmetic. Under this representation, an efficient Montgomery multiplication is proposed. This algorithm roughly costs sub-quadratic number of operations in p, for best cases, the number equals O(m1.5). For the inversion, we investigate a variant of the extended Euclidean algorithm, where the inputs are in the BR representation.2. A new type of irreducible polynomials is proposed in order to extend the application of optimal extension fields. The proposed polynomial takes advantages of binomial residue arithmetic and achieve high performance for field multiplication which costs O(m1.5) operations in p. Extensive simulation results demonstrate that these polynomials roughly outperform irreducible binomials by 20% in some fields of medium prime characteristic. 3. Proposed a variant of Karatsuba-Offman algorithm which aims to speed up the classic multiplier for trinomials. This multiplier outperforms the previous Karatsuba based multipliers except for those based on equal-space trinomial or all-one polynomial. On the other hand, it still maintains a smaller number of logic gates than the fastest known multipliers. Furthermore, two types of multiplier for specific irreducible trinomials are also developed. These two multipliers cost about 66% and 62% circuit gates of the best known multiplier, respectively. While the time delay about these multipliers matches the best result which is preferable to other multiplier if the space and time complexity are both considered.4. A fast forth power operation is developed for an improvement of the IT algorithm in polynomial basis (PB). The proposed algorithm for inversion achieves even faster performance, roughly improves the delay by m/2 TX, at the cost of slight increase in the space complexity compared with the standard version. To the best of our knowledge, this is the first work that proposes the use of forth power in computation of multiplicative inverse and shows that it can be efficient.5. We proposed two versions of improvement of the TYT inversion algorithm. One is an extension of the TYT algorithm using PB representation. It is argued that, when the field is generated with an irreducible trinomial, our proposal shows almost the same practical complexity as the original algorithm. Another reduces the number of required multiplication by reusing intermediate computation values. Extensive simulation shows that, for a large number of GF(2m), the new algorithm achieves the lower bound of the inversion algorithm based on Fermat little theorem.