Research On Elliptic Curve Point Multiplication

In this thesis, we research on the multiplication of points in ECC over F_p and F_2ⁿ in differentaspects, which is the core operation in ECC implementations. The main work and results obtained are as follows:1. We take the research in three aspects, that is arithmetic over finite fields, the basic operation of points on elliptic curves, and various optimizations over k when calculating kP . Besides summarizing known algorithms, we also present new improved ones.2. Two modified Montgomery modular inverse algorithms are proposed for software applications. The radix-4 algorithm can reduce the upper limit of the number of iterationsfrom 2n to 7/6n on average, and the average number of iterations from 1.4n to 0.82n accordingly. The software experiment shows about 11% speedup, and the iterations are about 41.5% less in experiment. As for the radix-8 one, it can reduce the upper limit of number of25iterations to 25/24n, and the average number of iterations to 0.73n. But there are more complicated branches in the algorithm, which makes it only suitable for very large numbers. For example, for numbers larger than 2048 bits, the speedup can be 13%-18%.3. "Thribble-splited" algorithm is proposed, which is improved from JSF algorithm. At the cost of precomputing 9 more points, the speedup is about 26%. And further we present the binary tree algorithm for parallel implementation, which can achieve higher speed by less parallel units. And the architecture is also suitable for pipelining in hardware implementation. For the flexibility in the algorithm architecture, hardware implementation can get compromised between efficiency and cost.4. During the research we have developed by ourselves an ECC software library over F_p. Thedevelopment and application of the library deepens our understanding of ECC. By a few modifications, the library can be used in business as a support library for software crypto-module.