Research On Arithmetic Unit And Key Technology In Residue Number System

Unlike the traditional way of increasing the parallelism by the use of hardware,RNS(Residue Number System) is a method of using parallel numerical representation systems to achieve natural parallelism. In recent years, RSA and ECC(Elliptic Curves Cipher) as the representative of the public key algorithm widely used RNS architecture to enhance the speed of encryption. With the increase of the length of the secret key,high bit-wide and high speed modular multiplier needs to study. In addition, the backward transformation is one of the bottlenecks of the RNS architecture, and the fast backward conversion algorithm under moduli set { 2~n -1.2~n +3 .2~n +1.2~n - 3 } is proposed. But this moduli set is rarely applied due to the performance of the modulo 2 n+3 multiplier. The latest advances in the application of RNS in cryptographic applications and fast backward transform are studied in this paper. The arithmetic units of the corresponding special residue radixs are studied in depth. By classifying the relevant references of a large number of modulo 2~n±1 multipliers, the architecture suitable for the design requirements of this paper is screened. In this paper, the modular multiplicant is divided into four types according to the different parts of the binary multiplier, and is named according to the order of execution of the data stream. They are modified type 1, modified type 2, modified type 3 and modified type 4. The main work of this paper is as follows:1. For the problem of low utilization of dynamic range, using the extension method derive the relevant formula of the modular reduction, reduce its constraint condition and simplify the required decision. The A lossless dynamic extension method is proposed for the application of the algorithm. By using this method, the modulus adder and multiplier are improved by 41.1% and 12.3%, respectively, on the efficiency of the"area × delay".2. A modified type 1 modulp 2~n-2~p-1 multiplier is proposed. After the formula is deduced, the uncorrected partial product and the correction term are separated reasonably, so that the uncorrected partial product can use the related circuit generated by the binary product of the binary Booth multiplier, and finally the regular partial product is obtained. This structure is reduced by 49.1% and 6.5%, respectively,over the average and average area of the conventional universal multiplication.3. Two different structures are proposed for the modified type 3 modulo 2~n -2~p -1 multiplier. In the Booth structure, the problem that the partial product represented by the 2~n -bit twos complement number is more difficult to fix to n bits is solved. It derives a uniform correction term independent of the input variable, and corrects the correction term to n bits by precomputing, and then obtains a unified structure independent of the value combination. In the TDM structure,the TDM algorithm is first introduced into the design of the modulo 2~n -2~p -1 multiplier. The partial product obtained after TDM compression is modified to derive a fast structure which is more compact than Booth coding. These two modulo 2~n -2~p -1 multipliers are 9.7% lower than the current modulo 2~n -2~p -1 multiplier on average delay.4. For the modified type 4 multiplier, we proposed two kinds of multiplier structures. In the modulo 2~n-2~p-1 multiplier, using a CSA on the critical path instead of the p-bit binary carry propagation adder, the delay of the critical path is shortened. In the modulo 2~n+3 multiplier, the "+9" and "-9" are generated when the partial volume is compressed by the modal product, saving the hardware resources required for the extra processing "-9". Reduces the critical path delay. The two structures are 12.4% and 9.0% higher than the same type of modulo multiplier in terms of "area×delay".At the end of this paper, it is convenient to design, implement and test several kinds of algorithm elements proposed in this paper. This paper constructs an automated processing platform and gives the conclusion of DC (Design Compiler) synthesis and comparative analysis.