Multiplier based on improved Montgomey's algorithm

Abstract

The invention belongs to the field of computer encryption / decryption, characterized in that: the mode multiplier uses two 7-stage pipelining 64-bit multipliers to resolve operation numbers so as to raise system clock frequency and uses precalculating unit to send the data inputted in advance into a multiplier under the control of an external state machine. And the stages are divided according to three clock cycles of waiting the calculated results in the stage of calculating the previous bit value in the operation number. From i=0, the invention starts the first stage of calculating, repeats the above steps until all the mode multiplication of ones place numbers in the operation number ends, thus solving the problem of pipeline stopping and improving system parallel property and reducing the needed clock number. The mode multiplier is 233-bit long, and based on SMIC 0.18 mum worst process and the maximum time delay of the key route is 3.8 nano ad 2 sq m. One mode multiplication need take 110 clock cycles. As compared with the other structures, the invention has the characters of small area and high speed, applied to ECC code system and RSA code system.

Description

technical field [0001] The rapid development of e-commerce, secure communication and other applications puts forward higher requirements for information security on the open network, so public key cryptosystems such as RSA and ECC are widely used in key transmission and digital signatures. The core operations of RSA and prime number field ECC are modular exponentiation operations, and in order to ensure a certain degree of security, the bit length of the RSA modulus and exponent needs to reach more than 1024 bits, and the bit length of the ECC modulus and exponent also needs to reach 233 bit above. However, it is very inefficient to use software for large-scale modular multiplication operations of this scale, and it will take up a lot of system resources. Therefore, various hardware for large-number modular exponentiation has emerged as the times require. The modular multiplier VLSI structure in this design belongs to this kind of encryption / decryption technical field. Back...

AI Technical Summary

Problems solved by technology

[0014] Another problem is that the multiplication and addition operations included in the original Montgomery algorithm are all large number operations. The hardware cost is very high when VLSI is implemented, and because the carry chain is too long, the critical path delay is very large, which restricts the clock frequency of the system.

The systolic array structure is one of the strategies to solve the problem of long carry chains, but the disadvantage of this type of strategy is that the calculation cycle is large and the VLSI implementation area is large, and the improved algorithm described below can effectively solve this problem

Images