Prime Field Modular Arithmetic Algorithm And Hardware Architecture Optimization And Its Cryptographic Application

Modular arithmetic is the basic operations of elliptic curve cryptography. Elliptic curve cryptography (ECC) is a public-key cryptography based on the algebraic structure of elliptic curves over finite fields; its security depends on the problems of elliptic curve discrete logarithm. Compared to the famous RSA algorithm, the ECC algorithm adopts a smaller key and achieves a higher level of security. In 2007, Chen G., Bai G. Q. and Chen H. Y. presented an efficient modular division algorithm for prime field with its systolic array implementation (IEEE Transactions on Computers,2007,56(2):282-286), based on which and affine coordinates an ECC processor is realized. Their study introduces the idea of ECC implementation based on affine coordinates and fast modular division algorithm.This paper inherits this idea to do research in algorithm and hardware implementation optimization for fast elliptic curve cryptosystems over prime field. First, based on the improvement of two basic ECC arithmetic algorithms, modular division algorithm and a fast unified modular division and Montgomery multiplication algorithm are proposed. Second, the optimized hardware implementation of fast unified modular division and Montgomery multiplication algorithm has reduced the critical path delay by arranging the sequence of four full adders in the systolic array in the hardware implementation of improved modular division algorithm, therefore, the speed of calculating the modular division and Montgomery multiplication has been accelerated. Last, only one modular division and Montgomery multiplication arithmetic systolic unit is needed to realize an ECC processor.The main contributions of this paper are three improvements of modular arithmetic algorithms.First, a fast modular division algorithm suitable for systolic array implementation is proposed, by arranging the sequence of four full adders in the systolic array in the hardware implementation, the critical path has been reduced, and the speed of calculating the modular division has been accelerated. Modular division is the most complex calculation in ECC algorithm. The fast modular division algorithm uses a new while-loop exit condition and a better updating method of a control variable to reduce the average of iteration numbers by about 15 percent compared to the algorithm proposed by Chen G. Bai G. Q. and Chen H. Y. Based on the fast modular division algorithm, this paper proposes a fast systolic hardware modular divider. With an optimized core calculation cell, the fast systolic architecture reduces the critical path delay by about 18 percent and the algorithm reduces the iteration numbers by 15 percent, the total computational time for one modular division has been reduced by almost 30 percent.Secondly, a fast unified modular division and Montgomery multiplication algorithm is proposed. This unified algorithm has the same calculation process as the improved modular division algorithm, and has the same exit condition suitable for hardware implementation for modular division and Montgomery multiplication. By the addition of only one flag signal and three logic basic gates, the proposed modular division systolic architecture can be the implementation of the fast unified modular division and Montgomery multiplication algorithm, and a fast unified modular divider/multiplier is realized. Therefore, modular division and Montgomery multiplication shares almost all hardware resources.Lastly, three improved modular division algorithm based on adder and a scalable modular division processor are introduced. The algorithms gain a less while-loop iteration numbers by controlling the swap of two variables at the specific condition in the algorithms. These three algorithms are suitable for different hardware resources and performance requirements. The scalable modular division processor is used to calculate huge size modular division.Based on only one unified systolic modular division and Montgomery multiplication arithmetic unit, the hardware implementation of the ECC system uses affine coordinates to achieve a fast computational speed, and three stages pipeline reduces the computational time of point operation furthermore. Compared to the existing result, the modular division algorithm reduces iteration numbers by about 15 percent, the Montgomery multiplication algorithm has the same iteration numbers, because the critical path delay has been reduced by 18 percent, the computational time of modular division and Montgomery multiplication have been reduced about 30 percent and 18 percent respectively, therefore, based on the unified systolic modular divider/multiplier, the ECC processor reduces computational time about 19 percent.