One of the most popular and effective methods of information security is cryptographic, that can be realized in software as well as in hardware tools. Hardware cryptographic devices are oriented on confidentiality ensuring put some actual problems must be solved. For the purpose to raise the performance of computing devices productivity, it is necessary to use number systems without the disadvantages of the radix numeration system. This is due to the fact that while performing on multi-digit numbers arithmetic operations represented in the positional system, it becomes necessary to take into account inter-bit transfers that far slows down the computation speed and complicates the calculator structure. The new ways search to improve the computing devices performance led researchers to an objective conclusion that in this direction of the positional number system all possibilities have been exhausted. In order to boost productivity of computing devices, it is necessary to use number systems without such disadvantages.
Topical tendencies of computer equipment and system development require the elaboration of high-performance computing devices, including information security. By information and communication networks and the integrating devices development the need for creating efficient cryptographic transformations hardware solutions will grow. For example, hardware cryptographic devices are few times faster than software cryptographic tools. But hardware tools have some problems that must be solved to provide efficient confidentiality ensuring. 2.
There are tasks leading to calculations when the integer values variables far exceed the
maximum range of typical computing devices, defined by the hardware-supported
machine word length [
For example, concerning ECC or RSA cryptosystems, the main difficulty in
cryptographic transformations is first of all due to the need to perform sequential
modular multiplication by multi-digit numbers [
The value of each numeric character (number) in the designation of a number depends
on its position or digit in the traditional radix numeration system. However, besides this,
there are also so-called “non - radix numeration system”, one of which is the “residue
number system” (RNS) [
The residue number system is a data representation system in computational arithmetic, where integer is denoted by a set of smaller numbers.
In the residue number system, a positive integer is represented as a sequence of residues or deductions:
A (a1, a2 ,, an ).
From dividing to set positive integers p1, p2 ,, pn , that are called as system basis. i numbers are derived in such a way: (1) (2) A i A pi , i 1, n,
pi where A / pi means whole part from dividing A by pi . From (2) it follows, that number i -bit i of number A is the least positive remainder of the dividing A by pi and i pi . In this case, the digits formation of each bit is carried out independently of each other. In accordance with the Chinese theorem on remainder number representation A in the form (1) will be unique if the numbers are pi pairwise simple. The range volume of representable numbers in this case is equals to P p1, p2 ,..., pn . In this case, similarly to the radix numeration system, the range of representable numbers grows as a product of bases, and the digit bits of numbers grows as the sum of the digit capacity of the same bases.
The main privileges that make it possible to effectively use modular arithmetic in some
fields of computing technology are: a high level of natural parallelism at the number
system level, that is related to the absence of digits transfer in addition and
multiplication, as well as the absence of error propagation. In contrast to the radix
numeration system, all vector elements are equivalent, and an error in one of them leads
only to a dynamic range reduction. This fact allows you to design devices of high
fallover protection and error correction [
These features ensure good advantages for RNS over the radix number system at modular operations of addition, subtraction and multiplication. This is especially true if multi-digit numbers act as operands.
Strategic pathway in RNS application in computing is the development of cryptographic
information security tools. The research team headed by R.G. Biyashev proposed
modular encryption and digital signature generation algorithms based on the
nonpositional polynomial number system (NPNS) [
Nowadays, the residual numbers system (RNS) is often applied for the development of efficient and high-performance special-purpose processes. RNS is widely applied in cryptography. For example, modular arithmetic allows to create an effective cryptographic systems hardware implementation. The non-positional number systems application allows us to accelerate slow computations in asymmetric encryption algorithms and increase reliability.
The developed non-positional encryption systems, as a cryptographic strength criterion, applies not the key length, but the cryptographic strength of the cryptoalgorithms themselves. The use of non-positional polynomial number systems (NPNS) also makes possible to increase the algorithms efficiency, as in accordance with NPNS rules, all arithmetic operations can be performed in parallel using the modules of the NPNS bases.
For the implementation of the developed algorithms in the form of modules combined into a cryptographic security system (CSS) works on program efficiency are carried out. As well as, work is being carried out to build software and hardware and hardware implementations of cryptographic information security symmetric algorithms based on the NPNS.
As hardware-software and hardware implementation has the best speed characteristics, the cryptographic algorithm integrity is guaranteed and allows to optimize many of the mathematical operations adopted in encryption algorithms. For developed algorithms software and hardware implementation, parts of the procedures are implemented in hardware.
The basic device for non-positional polynomial number systems is a device for multiplying polynomials modulo an irreducible polynomial, where data encryption and decryption routine calculations are performed.
In this research, we consider an approach to polynomials multiplying A(x) and B(x) modulo an irreducible polynomial P(x), that is, A(x) B(x) mod P(x), where deg A(x), deg B(x) deg P(x).
In each multiplication process step, the partial remainder ri is calculated by the former partial remainder shaper by adding modulo two double the previous partial remainder 2ri1 , with the result of the logical multiplication of the polynomial A(x) (multiplicand) by the next high bit of the polynomial B(x) – multiplier modulo irreducible polynomial P(x).
Then the i -th partial remainder is determined by the formula: ri (2ri1 A(x) bi ) mod P(x), where bi is the i -th high bit of the binary image of the polynomial B(x), (bi 0,1). A is the binary image of the polynomial A(x). P is binary image of the irreducible polynomial P(x).
The considered multiplier functional diagram is shown in Fig.1.
The device includes RgA for binary image storing of the polynomial A(x) (multiplicative), shifting the RgB register for the binary image of the polynomial storing B(x) (multiplier), the RgR register for storing the binary image of an irreducible polynomial (module), adder AD1, where modulo 2 sum up the doubled previous remainder 2ri1 with the multiplicand A(x) with bi1 1, forming Ci 2ri1 bi1 A(x) . Modulo-two adder (AD2), together with a multiplexer (MS), modifies Ci modulo P(x). Register RgR serves to store intermediate remainders. Additionally, the multiplier contains a subtracting timing pulse (COUNT), where, at the end of the operation, the “End of Operation” signal is generated. T Trigger, that allow the passage of timing pulses into the circuit.
We consider the multiplier operation. By “START” signal, the binary A(x), B(x) and
P(x) polynomials coefficients are received by the blocks of the I1, I2, I3 diagrams, respectively, in the registers RgA(x) and RgB(x), RgP(x). Besides this, by “START” signal, the binary code (k) of the multiplier digits number is received in the TP count. The “Start” signal prior to reaching at the single trigger input T is delayed on the DL.1 delay line. The delay on LZ.1 is determined by the total delay time on RgA(x), I6, AD1, AD2, MS and the recording time of the remainder in the RgR register and the delay time is shifted by Shf (L1). Upon the “Start” signal is reached the trigger input T and translates it into a single state, that allows the first timing pulse TP1 to pass from the output of the I4 diagram. At this point in the RgR register, the partial remainder is r0 C , with ri1 1, since 0 egA(x) deg P(x).
The first timing signal RgB(x) is shifted to the left by one digit, while in the high order RgB(x) the value of the next coefficient of the polynomial B(x) bi2 is fixed, provided to the control inputs of the I6 diagrams, and to the other inputs of the polynomial A(x) values coefficients. If, at the same time, bi2 1, then the polynomial coefficients are provided to the right-hand inputs of the AD1 adder. TSI at the time of the RgB(x) shift is delayed by the delay line DL.2 and is provided to the control inputs of diagram I7, and the information inputs are supplied by the remainder from the outputs of the Shf diagrams(L1) (L1) 2ri1 .
From I7 output , the doubled remainder is provided to the left inputs of the AD1 adder. When bi2 1, the output of this adder is C12ri1 A(x) .
If bi2 0, C1 2r0 . Next, the C1 value is provided to the left inputs of the adder modulo 2 (AD2). Moreover, if C1 P(x), then the multiplexer (MS) outputs the value C1 and is written to the RgR register forming the value r1 .
If C1 P(x), then the MS multiplexer outputs the result C1 P(x) , shaping also the value r1 . Further, the remainder r1 is shifted one digit to the left by the Shf shifter (L1). At this point, the I4 diagram output of the receives the TP2 timing pulse shifting the contents of the RgB(x) register. AD 1, RgA(x) inputs are provided depending on the value of bi3, and the second inputs are provided with the bits of the residual r1 multiplied by two. AD1 output, the C2 value is formed and with the help of the adder AD2 and the multiplexer MS, C2 is modulo, shaping the remainder r2. It is noteworthy that when each timing pulse reaches, a unit is subtracted from the TP count. Upon n 1 timing signal reaches the RgR register, the result of multiplying the polynomials modulo the irreducible polynomial is generated and the TPC is set to “0” and the counter generates a “end of operation” signal that sets the trigger T to the zero position, preventing the next timing signal from passing output diagram I4. At the time of last remainder shaping signal "end of operation" are delayed on the delay line DL.3. After that, the result is given to the outputs by the diagram I8. If to consider an example of multiplying polynomials modulo an irreducible polynomial in the multiplier diagram shown in Figure 1.
Let A(x) x4 x 1, B(x) x4 x2 1, P(x) x5 x2 1. as C3 P(x) C3 101010
P( x) 100101 r4 001111 C4 001101
P( x) 100101 r5 001101 Checking: (x4 x 1) (x4 x2 1) (x3 x2 1), accordingly binary display of this polinomial – 011012.
This algorithm was tested on Nexys 4 Artix-7 FPGA Board. Figure 2 contains diagram for encoding and decoding the number A in hexadecimal. The precondition research for is the growing need to create efficient hardware solutions for cryptographic transformations and the difficulties that arise in using the radix numeration system.
As was stated above, the basic privileges of nonpositional number system applying is the absence of transfer of digits in the operations of addition and multiplication, and, consequently, the parallel operations possibility on each of the bases of the system, which significantly speeds up the calculation process. It stands to mention that most modern general-purpose processors are not able to effectively perform nonpositional number system calculations.
For the most effective implementation of computing devices based on the residual number system, it is required to develop non-standard circuit solutions that effectively perform calculations in a nonpositional number system.