Research On The Fast Implementation Of The Basic Algorithm Of Elliptic Curve Over Finite Fields

In order to improve the efficiency of elliptic curve arithmetic operations over finite fields,this thesis studies the squaring in binary extension fields, inversion in finite fields, and scalar multiplication on elliptic curve. For these three different operations, it proposes fast computation algorithms. The main work and research achievements are as follows:A fast algorithm is proposed to calculate the squaring in binary extension fields. The algorithm requires construct a two-dimensional table, and then it uses the table to calculate the square of elements in binary extension fields. In this way, it speeds up the squaring operation in binary extension fields. Because of the special nature of the elements in binary extension fields,there is no need to update the lookup table and the lookup table can also be fixed in memory or written directly into hardware devices. In this paper, it writes the two-dimensional look-up table to the memory directly and makes the content to be queried as an index subscript to improve the efficiency of searching. In addition, the algorithm is more suitable for parallel computing because of that each byte to be counted among the elements has no relevance, and then the squaring in binary extension field can be further improved.Two security outsourcing algorithms for inversion in finite fields are proposed. This paper also gives the formal definition of security and the security model of outsourcing computation. It proposes a secure outsourcing computation algorithm for inversion of a specific single element which meets the security on the basis of the definitions. In order to reduce the cost of cloud, it proposes a secure algorithm for inversion of multiple elements combined with the joint inversion algorithm. Finally, the security proofs of the proposed algorithms are made, and the efficiency is analyzed and the comparison is given.This paper researches the scalar multiplication on the elliptic curve and proposes an algorithm for elliptic curve scalar multiplication with a window look-up table. The algorithm requires calculate some simple scalar multiplications according to the size of the window and stores the results to construct a two-dimensional look-up table. In subsequent calculations, for the same value to calculate, what it needs to do is to look up the look-up table to replace the recalculation to improve the efficiency of scalar multiplication. When the bit length of scalar is relatively large, the algorithm is more suitable.