Today, three types of encryptors are most widely used for data encryption: hardware, software/hardware, and software. Their main difference is not only in the way encryption is implemented and the degree of data protection reliability but also in the price, which often becomes a determining factor for users. While the price of hardware encryptors is much higher than that of software encryptors, the price difference is not comparable to a significant increase in the quality of information security. Hardware encryption has several strong advantages over software encryption, one of which is faster performance. Hardware implementation guarantees the integrity of the encryption process. At the same time, the generation and storage of keys, as well as encryption, is carried out in the encryption board itself, and not in the computer's operating memory. In this regard, the development of high-performance hardware processor operating units for asymmetric encryption, despite their high cost, is an urgent scientific and applied task. This paper analyzes modern approaches to modular multiplication, highlighting their strengths and weaknesses. An algorithm for multiplication with stepwise formation of partial and intermediate remainders is investigated, which, in turn, does not require preliminary calculations, and all calculations do not exceed the range of the module's bit grid. As a result, a synchronous matrix multiplier containing n blocks of AND circuits, n - 1 FPRs, and a single FIR with an intermediate remainder register has been developed, which will be useful for cryptographic transformations in systems with increased requirements for performance and information security (for example, in critical information infrastructure).
The vast majority of modern cryptographic systems perform transformations with integers. Large integers (not necessarily primes) act as keys to perform cryptographic transforxmations. To achieve the desired level of security, depending on the cryptosystem, integers range from several hundred to several thousand bits. Over time, to maintain the desired level of security, the size should increase. To work with integers in binary representation, the following arithmetic operations are widely used: addition, subtraction, left and right shifts, multiplication, squaring, modular multiplication, and division.
Specifically, in asymmetric cryptosystems, the
data encryption and decryption procedure are
carried out by raising the number a to a degree x
by modular Р (a x modP), which can be realized
by software, hardware, and software and hardware
means [
Hardware encryption has several significant
advantages over software encryption, one of
which (and probably the most significant) is faster
performance [
Today, operating
the units development of
high-speed
of
hardware
processors
for
asymmetric encryption, despite their high cost, is
an urgent scientific and applied task [
Given the above, the main goal of the paper is the development of a modular matrix multiplier for cryptographic transformations.
The multiplication operation takes a leading
place among the operations in rings and number
fields, which form the basis for cryptographic
transformations with public keys. At the same time,
multiplication is a pretty time-consuming operation [
Modular multiplication can be done in two ways. In the first case, the operation is divided into two stages. At the first stage, n-bit numbers A and B are multiplied and form a 2n-bit number C. In the second stage, the product C = A*B is reduced modulo P.
To date, a lot of experience has been accumulated in the development of high-speed integer multipliers and tools for squaring.
Among them are: Brown’s multiplier,
Wallace’s multiplier, Dadd’s multipliers, systolic and
vedic multipliers, and quadratus, where the
complexity of the calculation is O ( 2) bit operations.
However, these multipliers are very effective in
calculating “low-bit” numbers, which are widely
used in the construction of processing units of all
kinds of computers [
Today, the following integer multiplication methods are known and used in cryptography: ▪ ▪ ▪ ▪ ▪ ▪
Führer (development of the Schönhage
In cryptography, the Karatsuba method [
) steps (bit operations). The
SchönhageStrassen algorithm [
The modulo reduction operation performed in
the second step is to obtain the rest of the result of
dividing C = A*B by the modulo P. Paper [
High-performance matrix and conveyor devices for modular multiplication can be easily implemented based on partial remainder formers [14–
In the second method, modular multiplication is
performed by using an algorithm for dividing large
numbers. For example, the Barrett algorithm [
⌋ 2 where
= 2 , k is word size in bits, m is the number of words in the module N. The effectiveness of the Barrett algorithm depends entirely on how efficiently the preliminary calculations are performed by the distribution of large numbers.
Montgomery’s algorithm requires the
preliminary calculation of the constant 2(mod ), using
division with remainder [
In the third method, the process of modular multiplication is performed in a large number of steps, where the number of steps is determined by the bit depth of the multiplier.
This paper describes the modular multiplication of numbers, where multiplication begins with the analysis of the lowest bits. In such a multiplier, the following steps are performed at each step of the multiplication:
1. Partial remainder FPRi calculates the partial remainder ri for which the previous partial remainder ri – 1, shifted by one digit toward the higher digit, by modulo P, i.e., ri=2ri–1modP. When forming the first partial remainder ri, A is taken as the previous partial remainder, i.e., ri = A1.
2. The partial remainder ri is logically multiplied by the i-bit of the multiplier B by the logic circuit block Ii.
3. The intermediate residual Ri is calculated by adding up the partial remainder ri with the previous intermediate remainder Ri–1 by module Р, that is Ri = (ri + Ri–1) modP.
After performing n multiplication steps, the result is formed R – Rn–1=(rn–1 + Rn–2) modP.
In work [
The functional scheme of a synchronous multiplier with a matrix structure is shown in Fig. 1. The multiplier consists of the n-bit multiplier register RgB, the multiple registers RgA, and the module register RgP, the synchronization block SYNCHRO unit that generates level signals for the block of schemes І0 ÷ Іn–1. At the entrance SYNCHRO unit is supplied to the START signal, clock signals CLOCK and a binary code to the signal for the number of multiplier digits n. Following the START signal, the RECEPTION signal vibrates, after which the discharge of multiplier B is received into the RgP register through circuit block 3'.
«"ПRрeиcеeмiv"ing» «S"taПrуtс»к"
Clock n
SYNCБHлR.СOИuНnХit
The SYNCHRO unit consists of a binary counter and a decoder. The state of the counter is decoded on their outputs generating signal levels for І0 ÷ Іn–1. With the START signal, the binary code of the number n is also written to the binary counter and permits the clock signal Clock to pass to the counter input.
The multiplier also includes partial remainder generators FPR.1÷FPR.n–1 and circuits І0 ÷ Іn–1, circuit OR1, and intermediate remainder generator FIR with intermediate remainder register.
The results output of multiplication І4' after receiving the clock signal un–1 from the SYNCHRO unit through the delay element EZ.
The value of the modulus P̅ from the inverted output RgP is delivered to the inputs of all FPR.1 ÷ FPR.n–1 and FIR. On the RECEIVE signal, the multiplier A is delivered to the inputs of the I2' circuit block with a shift of one bit toward the high bit to the FPR.1 input. The other inputs of the I0 block receive the value of the lowest bit of the RgB – b0 register and the control level u0 from the SYNCHRO unit output.
The output of I0 is connected to the FIR register. The output FPR.1 is connected to the input of the circuit block I1. The other inputs of the I1 are connected to the outputs of the RgB and SYNCHRO unit, through which the value of the bit b1 and the control level u1 are received. The output of the I1 block is connected to the input of the OR1.
The code value from the output of FPR.1 with a shift of one bit toward the lowest bit is applied to the input of FPR.2. In turn, the output of FPR.2. is connected to the inputs of the I2 circuit block, to the other inputs of which the value of the bit b2 from the RgB register and the control level u2 from SYNCHRO unit are supplied. The output of the I2 block is connected to the input of the OR1 scheme. There are similar connections between FPR.3 ÷ FPR.n–2 and blocks of schemes І3 ÷ Іn–2.
The FPR.n–1 inputs receive the value of the code from the FPR.n–2 output with a shift of one bit toward the lowest bit and the code of the P module from the RgP outputs. The output of FPR.n–1 is connected to the input of the In–1 circuit block, which also receives the value of the high bit bn–1 of the RgB register and the control signal un–1 from the SYNCHRO unit. The output of the In–1 circuit block is connected to the OR1 input. Fig. 2 shows the structure of the FPR, which is used to form a partial remainder ri from the doubled previous remainder by modulo P: ri = 2ri–1modP. 1 П Зн 1 ri
Add 2 MS +1
FPR consists of a binary adder Add and multiplexer MS, which contains blocks of schemes І1, І2, and scheme OR1.
The doubled partial remainder 2ri–1, module reverse code ̅, and a single signal +1 is delivered to the adder inputs. As a result of performing the operation ri = 2ri–1 mod ̅ + 1, a difference with its sign ZN is formed at the output of the adder.
If ZN = 1, the following code 2ri–1 (2ri–1 ˂Р) is transmitted to the FRP outputs. At the same time, transferring from the digit sign Р = 0. If ZN = 0, then the result of subtraction 2ri–1 – Р (2ri–1 ≥ Р) is transferred to the FPR outputs.
Fig. 3 shows the structure of the FIR intermediate remainder generator, which includes the Add adder, FPR, OR2 circuits, and the RgR intermediate remainder register. The output of the RgR register is connected to the Add input, where the Ri–1 value is transferred. It is easy to see that the circuit operates Ri = (ri + Ri–1) modP.
Let’s consider the operation of a modular matrix multiplier. After receiving the operands A, B, and P into the corresponding registers and the binary code, the number of bits multiplier in the SYNCHRO unit is the first clock impulse Clock 1 arrives and code 1 is written to the binary counter. At the same time, output 1 of the SYNCHRO unit produces a high level u0, which is supplied to the input of the circuit block I0. ri Add
FPR
2 RgR
Ri Figure 3: FIR structure
This paper analyzes modern approaches to
modular multiplication and highlights their
strengths and weaknesses. A multiplication
algorithm with step-by-step formation of partial
and intermediate remainders was studied, which,
in turn, does not require preliminary calculations,
and all calculations do not go beyond the range of
the bit grid of the module. As a result, a
synchronous matrix multiplier has been
developed that contains n blocks of circuits I,
n – 1 FPR, and a single FIR with an intermediate
remainder register. The obtained results will be
useful for cryptographic transformations in
systems with increased requirements [
The other inputs of I0 are supplied with the lowest bit of the multiplier b0 and the bits of the multiplier A. With b0 = 1, a partial remainder r0 = R0 is generated at the output of the I0 block, which is written to RgR FIR. After that, the clock signal Clock 2 is delivered to the SYNCHRO unit, and the control level u2 is generated at the output of the SYNCHRO unit, which is sent to the input of I2. The other inputs of I2 are supplied with the value of the bit b2 of the RgB register and the value r2 from the output of FPR.2. The outputs of the I2 circuit block are sent to the input of the OR1 scheme.
Partial remainders r3 ÷ rn are formed in a similar way, which also through schemes OR1 are supplied to the entrance FIR. FIR, receiving partial remainder ri, creates Ri according to the formula Ri = (ri + Ri–1)modP.
Table 1 shows an example of performing a modular multiplication operation in a synchronous matrix multiplier, where А = 2710; B = 2310 = 101112; P = 3510. For convenience, all arithmetic operations are performed in the decimal system.
Verification:
R = (27×23) mod 35 = 621 mod 35 = 2610
R1 = = (r1b1 + R0)modP = = (19+27)mod35 = = 1110
u2 r2 = 2r1modP = = 38 – 35 = 310
R2 = = (r2b2 + R1)modP = = (3 + 11)mod35 = = 1410
u3 r3 = 2r2modP = = 6mod35 = 610
R3 = = (r3b3 + R2)modP = = (6*0 + 14)mod35 = = 1410
u4 r4 = 2r3modP = = 12mod35 = 1210
R4 = = (r4b4 + R3)modP = = (12 + 14)mod35 = = 2610