Design And Implementation Of Digit Serial Multiplication Based On Polynomial Basis

With the development of network technology and 1024-bit RSA algorithm is cracked,the elliptic curve encryption algorithm gradually replaces the RSA algorithm to become the mainstream encryption technology.Elliptic curve encryption algorithm is often implemented in the prime field and the binary expansion.binary expansion field has no carry chain,so it has been widely studied and applied.In the binary expansion field,the most time-consuming operation of the elliptic curve encryption is the point multiplication,which needs frequent calls of addition and multiplication.Among them the addition operation can use XOR operation to solve,so designing a high efficiency low area complexity multiplier is crucial.There are two main factors that determine the efficiency of multiplication.The one is basis for the feild element represents,and another one is the structure of the multiplier.The two most commonly used basis are polynomial basis(PB),gaussian normal basis(GNB).In this paper,we chooses the polynomial basis as a field element representation,which is easy to understand and partition.And In order to be able to achieve the balance of time and space complexity,this paper selected the digit serial structure as a multiplier structure.In this paper,a new polynomial basis MPB is redefined based on polynomial basis and irreducible trinomial.The double basis multiplication is defined by polynomial basis and MPB.So that double-base multiplication can be converted into the Toeplitz matrix vector product form.According to the properties of Toeplitz matrix and k-way TMVP method,this paper designs a digit serial multiplier architecture with low space complexity.Although the multiplier designed in this paper is slightly larger in computation time than other existing multipliers,it has significant advantages in area and space complexity.Especially when the number of segments is 4,6,it can achieve the balance of time complexity and space complexity,which is more conducive to the realization of modern embedded mobile devices.Using Verilog HDL to write the corresponding two-way TMVP method of the multiplier architecture,and using Model Sim to verify the correctness of the multiplication method.At the same time,Xilinx ISE was used to evaluate the hardware resource utilization and the maximum frequency.The Spartan-6 series FPGA development board used a serial port to communicate with the host computer to achieve 256-bit point multiplication.