Modular reduction with step-by-step using of several bits of the reducible number

Abstract

Although public key cryptography is known to solve the problem of physically secure key exchange, the main drawback of this system is its low performance during encrypting and decrypting data. One of the ways to solve this issue is to increase the speed of the modular reduction operation, one of the basic operations of asymmetric cryptoalgorithms. A new method of step-by-step reduction by the N-bit module P using several bits of the 2Nbit reducible number A in one step is proposed in this paper. The method is based on using multiples of the P and reducing modulo at each step not the entire initial number, but its parts (A1, A2… Ai), which allows to reduce the bit capacity of A. A structural diagram of the hardware implementation of this method are developed. The main unit of the modular reduction device is a block of partial remainder formers, in which the partial remainder is computed using multiples of the P. The circuits are modeled in the Vivado Design Suite computer aided design (CAD) on base Artix-7 Fieldprogrammable gate array (FPGA) device from Xilinx. Optimization of hardware costs is achieved by applying the same comparison circuits to compare different multiples of P with Ai