Efficient adaptation of the Karatsuba algorithm for implementing on FPGA very large scale multipliers for cryptographic algorithms

Abstract

Here, we present a modified version of the Karatsuba algorithm to facilitate the FPGA-based implementation of three signed multipliers: 32-bit × 32-bit, 128-bit x 128-bit, and 512-bit × 512-bit. We also implement the conventional 32-bit × 32-bit multiplier for comparative purposes. The Karatsuba algorithm is preferable for multiplications with very large operands such as 64-bit × 64-bit, 128-bit × 128-bit, 256-bit × 256-bit, 512-bit × 512-bit multipliers and up. Experimental results show that the Karatsuba multiplier uses less hardware in the FPGA compared to the conventional multiplier. The Xilinx xc7k325tfbg900 FPGA using the Genesis 2 development board is used to implement the proposed scheme. The results obtained are promising for applications that require rapid implementation and reconfiguration of cryptographic algorithms. Here, we present a modified version of the Karatsuba algorithm to facilitate the FPGA-based implementation of three signed multipliers: 32-bit × 32-bit, 128-bit x 128-bit, and 512-bit × 512-bit. We also implement the conventional 32-bit × 32-bit multiplier for comparative purposes. The Karatsuba algorithm is preferable for multiplications with very large operands such as 64-bit × 64-bit, 128-bit × 128-bit, 256-bit × 256-bit, 512-bit × 512-bit multipliers and up. Experimental results show that the Karatsuba multiplier uses less hardware in the FPGA compared to the conventional multiplier. The Xilinx xc7k325tfbg900 FPGA using the Genesis 2 development board is used to implement the proposed scheme. The results obtained are promising for applications that require rapid implementation and reconfiguration of cryptographic algorithms.