Various approaches to the modular multiplication of multi-bit (large) numbers are analyzed. The advantages and disadvantages of these approaches are given. We consider a circuit solution that implements the algorithm for multiplying numbers modulo, where at each step of multiplication two bits of the multiplier are analyzed, which reduces the number of multiplication steps. The proposed multiplier modulo does not pre-calculations and all calculations do not go beyond the bit grid of the module.
In asymmetric cryptosystems, data encryption and decryption procedures are
performed by modular exponentiation of the number a to the power x modulo P (ax
modP), which can be implemented in hardware and/or software [
Approaches to the multiplication modulo Modular multiplication of numbers can be done in three ways. In the first method, the operation is divided into two stages. At the first stage, n-bit numbers A and B are multiplied and a 2n-bit number C is formed. At the second stage, the product C = A*B is reduced by the module P.
Nowadays, a great deal of experience has been gained in the development of
highspeed integer multipliers and devices for squaring. These include Brown, Wallace
multipliers, Dadda multipliers, systolic and vedic multipliers and quadrants, where the
computational complexity is О ( 2) bit operations. But these multipliers are very
effective in calculating "low-bit" numbers, which are widely used in the construction
of operating units of computers of various classes [
In cryptography for multiplication of multi-bit numbers, which allow to calculate
the required product faster than О ( 2) steps (bit operations), the Karatsuba method
[
The modular reduction operation, which is performed in the second stage, is the
receipt of the remainder of dividing the product C = A*B by the module P. In [
In the second modular multiplication method, using the Barrett or Montgomery algorithms [14, 15, 16], the process of multiplying large numbers by the module is accelerated. However, these algorithms require preliminary calculations associated with the need to use the algorithm for dividing large numbers, therefore representing the greatest complexity: – Barrett algorithm requires constant predictions = ⌊
⌋ 2 where d = 2k, k-size of a word in bits, m-number of words in module. The effectiveness of the Barrett algorithm depends entirely on how effectively the preliminary calculations will be performed, which are performed by dividing large numbers. – for the Montgomery algorithm, prediction of the constant “ 2( )”, is required, using division with remainder.
In the third method, the process of multiplying numbers modulo is performed in many steps, where at each step partial and intermediate remainders are calculated and the number of steps is determined by the bit number of the multiplier.
In such multipliers, depending on which bits of the multiplier the multiplication begins, a multiplier can be distinguished, where the multiplication begins with the analysis of the least and the highest significant bits. The multiplier of numbers modulo, where the multiplication begins with the analysis of the least significant bit of the multiplier was considered in [17].
In this paper, we consider a multiplier, where multiplication is carried out with the analysis of the two least significant bits of the multiplier, which leads to reduce in the number of multiplication steps [18-21].
In the process of multiplication, at each step of multiplication, the following actions are performed: the partial remainder = 4 −1 is calculated; bit вi+1 of the multiplier В is multiplied by 2 , and вi is multiplied by , з then they are summed and this sum is reduced modulo Р: ′ = (2 ∗ в +1 + ∗ в ) ; the intermediate remainder = ( ′ + 0) is calculated.
The number of such steps is determined by the number N/2, where N is the number of digits B. Since А and В < Р, it follows that r0=A, therefore R0 is determined by the formula 0 = (2 0 ∗ в1 + 0 ∗ в0) . 3
High-speed device for modular multiplication of numbers The block diagram of the considered multiplier is shown in Fig. 1. The device consists of four blocks: 1 - a block of registers Rg3Р, RgР and RgB, where during execution of operations the values of the tripled module - 3Р, module P and multiplier B are stored respectively; 2 - block of formers of partial remainders FPR.N/2-1, FPR.N/2-2, ..., FPR.2, FPR.1; 3 – block of multipliers modulo MMod.N/2-1, MMod.N/2-2, ..., MMod.1, MMod.0; 4 - block of adders of remainders modulo ARM.N/2-1, ARM.N/2-2, ..., ARM..2, ARM..1. The device also includes a delay element 5.
6 7 8 12
R 1 2 3 4 5
Reg3Р
3Р PRF. 2 − 1 MMod. 2 − 1 Р
+1 ARM. 2 − 1 +1 R2−2
RegР 2Р Р ... ... ... ... ... To the inputs of the FPR are supplied from the outputs of the registers of the modules 3Р, 2Р and Р. The value of 2Р is formed by shifting Р by one bit towards a higher order of bit positions. From the outputs of the register RgP, the value 2Р and Р are also fed to the inputs of the multipliers modulo MMod. Besides, from the RgB register outputs, a pair of bits starting from the low order bits (b1, b0), (b3, b2), ..., (bN-1, bN-2) are fed to the inputs of the multipliers MMod.0, MMod.1, ..., MMod.N/2-1. Signal “+1” is fed to the inputs FPR, MMod and ARM. The inputs for receiving the bits of the multiplicand A are connected to the inputs of Mod.0, FPR.1. At the inputs of MMod.0, bits A are fed without modifications, and to the inputs of FPR.1, they are fed with a shift by two bits towards a higher order. Further, the outputs of the FPR.i are fed to the inputs of the FPR.i+1 with a shift by two bits towards a higher order and without changes to the inputs of the MMod.i. The inputs ARM.i are connected with the outputs MMod.i and MMod.i-1, and the outputs ARM.i are connected to the inputs of the next ARM.i+1. The output of the device is the ARM.N/2-1 outputs.
A device for multiplying modulo numbers with the analysis of two digits of a multiplier per step works as follows. The values of 3P from input 6, P from input 7 and multiplier B from input 8 are received in registers Rg3P, RgP and RgB, and the multiplicand A from input 9 is fed to the inputs of FPR.1 with by a shift of two bits to the left and without a shift to the input of MMod.0 with the signal "Start", which is fed to the input 11. This signal is also fed to the input of the delay element 5, where it is delayed for the time of the formation of the final result R=(A*B)modP. After submitting the multiplier А=r0 by the MMod.0 circuit, the operation R0 = ((2*A*b1) + (А*b0))modР is performed, which is fed to the ARM.1 inputs. At the same time, the scheme of FPR.1 performs an operation to form a partial remainder r1=(4*A)modP. The partial remainder r1 from the outputs of the FPR.1 is fed to the inputs of the FPR.2 with a shift of two bits towards the higher order, i.e. 4r1. From the output of the former r1 without shift is also fed to the inputs of MMod.1, where the operation r1’ = ((2*r1*b3) + (r1*b2))modP is performed, which is fed to the inputs of ARM.1, where the intermediate remainder R1 = (r1’+R0)modP is formed and the value of R1 is fed to theARM.2 inputs.
Further, r1 from the outputs of the FPR.1 with a shift of two bits to the left is fed to the input of the FPR.2, where a partial remainder r2 = (4*r1)modP is formed. This remainder with a shift of two bits in the direction of the higher ones is fed to the inputs of the FPR.3 and without shift to the inputs of MMod.2. At the output of MMod.2, a partial remainder r2’ = ((2*r2*b5) + (r2*b4))modP is formed, which is transmitted to the ARM.2 inputs, where the intermediate remainder R2 = (r2’+R1)modP is calculated.
In the same way, R3, R4, …, RN/2-1 are formed. After the end of the calculation of RN/2-1 delayed signal "Start" on the delay element 5, the result is given to the output of device 12.
4Ri-1 3Р 2Р C3
Add3
C2
Add2
Add1
3 From this table, as well as from Fig. 2, it can be seen that when C3 = C2 = C1 and Sign3 = Sign2 = Sign1 = 0, the smallest positive result is determined by the difference 4ri-1 – 3Р, this difference is transmitted to the output of the circuit AND.4 by signal C3 = 1. At the same time, signals Sign3 = Sign2 = 0 block transmissions of codes from outputs Add2 and Add1 and the value 4ri-1 by circuits AND.1, AND.2 and AND.3. When the values of C3 = 0 and C2 = C1 = 1, positive differences are formed at the outputs of the adders Add2 and Add1. In this case, the outputs of the Add3 adder are blocked by the signal C3 = 0, and the signals Sign2 = Sign1 = 0 block the output of the adder Add1 and the submission of the value 4ri-1 to the outputs of the OR circuit and positive value of the ri is transmitted to the output of the FPR. When C3 = C2 = 0 and C1 = 1, the result ri is formed at the output of Add1. When C3 = C2 = C1 = 0, these signals block the outputs Add 3, Add2 and Add1 and by the signal Sign1 = 1, the value 4ri-1 is transmitted by the circuit AND.1 to the output of the FPR.
The functional diagram of the modular multiplier circuit (MMod) is shown in Fig. 3. The multiplier consists of the adder CM1 to the inputs of which are fed from the outputs of the blocks of circuits AND.1 and AND.2. The partial remainder ri and the bit bi+1 are fed to the inputs of the block of circuits AND.1, and the inputs of the block of the circuit AND.2 also supply ri and the bit bi from the register RgB. At the outputs of Add1, the sum ri(bi+1+bi) is formed, which is fed to the left inputs of the adder Add2 and Add3. The right-hand inputs of Add2 and Add3 are supplied with L(1) Р (2Р) and Р, respectively, and the signal “+1” is applied to the lowest order bit position.
Table 2 shows the conditions for the formation of the smallest positive remainder ri’, depending on the values of the carries C2 and C1 and the signs Sign2 and Sign1.
L(1)ri 1 bi+1
Add1 ri
bi 2
C2 Sign2 3
Add2 Fig. 3. Functional diagram MMod
L(1)Р +1 C3
Sign3 4 1 ri
Р Add3 +1 5 +1 Checking (А*B)modP = (37*39)mod77 = 57 = 1443mod77=57 modulo. Let А=3710, b1 b0 1 1
Thus, when multiplying modulo numbers, analyzing at each step of multiplying two bits of the multiplier, starting with the least significant bits, we can speed up the multiplication process twice.
The practical part of the work was implemented on FPGAs (Field Programmable Gate Arrays). FPGA is a device for implementing high-performance logic circuits. In our case, the Nexys 4 Artix-7 FPGA Trainer Board, which is a platform for developing digital logic circuits based on the Artix-7 FPGA from Xilinx, was taken as the basis. FPGA Artix-7 at its base has 101,440 logic cells and 126,800 CLB Flip-Flops. The complexity of the implemented logic circuits depends directly on the number of FPGA resources. In our case, the resources of Artix-7 are enough to implement the device of modular multiplication of numbers with the analysis of two bits of the multiplier. About 1- 5% of the FPGA board's resources are enough to implement the circuit of a device with 8, 10, ... 24 bits. This suggests that based on Artix-7 FPGAs, it is possible to implement devices that multiply numbers modulo with much more bit depth.
Below are the results of the studies in the form of a timing diagrams (waveforms) intended for the device based on the Artix-7 FPGA.
Figures 4, 5 show the diagrams of the operation of the devices of multiplication of numbers modulo with the analysis of two bits of the multiplier. In the diagram, the designation r corresponds to the formers of partial remainders (FPR), rr - multipliers modulo (Mmod), and R - adders of remainders modulo (ARM). Figure 4 shows the operation of the device for 8 bit numbers. Since the device analyzes two bits of the multiplier, the operating time is also reduced by two.
In Fig. 4, on the front edge of the clock pulse CP1, the least two bits (B1B0) of register B are read and based on them the value of the register rr (Mmod) and R (ARM) is formed, which are equal and have the value rr0 = R0 = 141. And the value of the register r0 (FPR) will be equal to the value of the register A = 181. After the supply of CP2, the value of the register r is formed, which is calculated as r 1 = (4 ∗ A) mod P = 61, the value of the module P will have one of three values. The values of the module P in our case are P1 = 221, P2 = 442, P3 = 663, which corresponds to the P and its doubled and tripled the values. In the case of register rr, the module P can have the same values as the FPR (register r). And at this moment in the register B the next two bits (B3B2) will be read, with the help of which the values of the registers rr1 and R1 will be formed. At this measure, the value of the rr1 and R1 registers will be different, and they will be calculated as 1 = ((2 ∗ 3 ∗ 1) + ( 2 ∗ 1)) = 122 and 1 = ( 1 + 0) = 42. The next step CP3 generates the value of the FPR in the register r2 = 23. After receiving the value of the FPR, the value of the registers rr2 and R2, which corresponds to the values calculated as 2 = ((2 ∗ 5 ∗ 2) + ( 4 ∗ 2)) = 23 and 2 = ( 2 + 1) = 66. In this measure, the values of the registers 2 and 2 are equal, because 5 4 = 012. From this it follows that the value obtained in the calculation is equal to the value of 2 itself, and it is currently less than the value of the module P. At the last fourth step (CP4), the register value 3 = 92 is also first generated, which is used to calculate the Mmod value and is recorded in register 3 = 184. The desired remainder from operations = ( ∗ ) is generated in the adders of remainders modulo (ARM) and displayed in register 3, which has a value of 28. Figure 5 shows a diagram of the operation of the device of modular multiplication of numbers with the analysis of two bits of the multiplier, but for working with 10-bit numbers. This time, the full cycle of calculations takes 5 cycles, which is two times less than the number itself. At the first clock cycle (CP1) the value of the registers 0, 0, 0 will have a value of 441, 656, 656, respectively. At CP2, the value of the FPR will be 〖r 1 = (4 ∗ A) mod P = 430, where register A = 441. The Mmod and ARM values will have the value 1 = ((2 ∗ 3 ∗ 2) + ( 2 ∗ 1)) = 193 and 1 = ( 1 + 0) = 182. The next clock pulse (CP3) generates the following values in the registers 2 = 386, 2 = 105 and 2 = 287. During CP4, the FPR has a value of 3 = 210, and the registers for storing Mmod and ARM data are 3 = 420 и 3 = 40. The last CP5 forms the remainder, which is obtained during the operation = ( ∗ ) = 213, where the value A = 441, B = 421 and P = 667.