High-speed devices for modular reduction with minimal hardware costs

Abstract

Asymmetric cryptosystems have an important advantage over symmetric systems, since only the public key is transmitted. However, asymmetric cryptographic algorithms have a lower speed compared to symmetric ones. When encrypting and decrypting in asymmetric cryptographic algorithms, complex and cumbersome procedures are used to raise very large numbers to a power modulo (modular exponentiation). In this case, the most resource-consuming operation is the modular reduction operation. One of the solutions to improve performance is the development of high-speed circuit solutions for modular reduction, the main task of which is to obtain the remainder of the division of a reducible number by the module. The structure of a high-speed former of partial remainders based on one binary adder and three comparison circuits is proposed, which can significantly decrease the hardware costs of devices for reducing numbers of multi bits in modulus. Based on the proposed former of partial remainders, a block diagram of a high-speed device for reducing the number modulo with sequential action was developed. Using this principle, a structural block diagram of a device of sequential action of a matrix type is developed. Based on the matrix circuit, a pipelined matrix circuit for reducing the number modulo is designed to process the data stream. A formula is given for estimating the gain in time when processing data streams. Algorithmic validation and verification of the high-speed devices for modular reduction with minimal hardware costs of sequential action was carried out on programmable logic-integrated circuits (FPGAs). For this, The Nexys 4 board based on the Artix-7 Field Programmable Gate Array (FPGA) from Xilinx was chosen. Verilog HDL is used to describe the circuit for reducing a number modulo. The results of a timing simulation of the device are presented in the form of time diagrams for a given 8-bit and 16-bit numbers, confirming the correct operation of the device.

Keywords

• modular reduction
• former of partial remainders
• comparators
• high-speed hardware implementation
• fpga