Design Of Finite Field Polynomail Multiplier

Finite field multiplication is the basic arithmetic operation of many cryptosystem and coding theory. The performance of finite field multiplication is of utmost important which will influence the performance of the whole system. Time spend in cryptographic functions can be critical for the availability of services. Since the major work is to calculate a large quantity of finite field polynomial multiplication in some cryptographic systems, accelerating polynomial multiplication is valuable for these cryptographic systems.In this thesis, the design and FPGA implementation result of a finite field polynomial multiplier is presented, whose arithmetic architecture is based on the number theoretic transform. It includes system algorithm design, system architecture design, hardware architecture design, and hardware implementation and function verification. The multiplier, which has been implemented on target device: Xilinx Virtex-II series FPGA: xc2vl000-4fg256 , has the character of high accuracy, high speed and low complexity. It shows that once computation takes 65.4 μ s. Comparing to software solution, the processor provides up to 7 times speedup in the execution of the computation, meets the demand of the digital signature and authentication system. These works are presented in this thesis:1 , The multiplication-free Fermat number transform (FNT) with the cyclic convolution property is used for calculating the multiplication of two polynomials to improve speed and accuracy. 64 points FNT is used for calculating the multiplication of two polynomials whose degrees are both less than 32. Then by using iteration techniques, the multiplication of two polynomial multiplication which degrees are both less than 256 can be calculated. And Ping-Pong RAM structure is used to improve the efficiency of the computation and to gain pipeline structure.2, 4-based 64 points FNT which has the similar architecture with 4-based FFT is presented. The architecture may handle two group data in parallel.3 , New-coding scheme is utilized for FNT and multiplication. The data is transformed from general binary representation to new-coding representation. Then the computations are suitable for hardware implementation where a multiplication operation may be performed by cyclic shifting operations and additions/subtractions.4, Modular carried save adder (MCSA) is used to improve the computation speedof FNT and multiplication.5, The whole structure has been implemented on target device: Xilinx Virtex-II series FPGA: xc2vl000-4fg256. The maximum clock frequency can achieve lOOMHz, that means once computation takes 65.4 u s.