Implementation of the RSA Algorithm on a DataFlow Architecture

This paper presents a dataflow-based implementation of the RSA, a popular algorithm used in the public-key cryptography. The RSA implementation relies on Montgomery reduction method that is used to make the encryption/decryption process more efficient. Montgomery method improves a modular exponentiation process which constitutes the algorithm computational core. An appropriate scheduling of the Montgomery word-based operations is chosen among several options from the open literature and accordingly implemented in C. Common CPU architectures suffer from the fixed word granularity constrained by the register width. On the other side, reconfigurable platforms often lack compiler support to provide high level system design. In this paper, we rely on Maxeler dataflow platform that offers the best from both worlds. Maxeler is a FPGA platform that offers a Java extension for hardware description. Algorithm modifications necessary for offloading the word-based multiplication to a dataflow engine are proposed. Our results show that multiplication accounts for about 40% of the total CPU encryption time. We have shown that multiplication part can be improved by approximately 70%, leading total improvement to 28%, according to the Amdahl's law. Directions for further potential improvements are also discussed.