An Efficient Single Core Flexible Processor Architecture for 4096-bit Montgomery Modular Multiplication and Exponentiation
Eduardo C. Culau, Grégory Calegari Marchesan, Nelson R. Weirich, Leonardo Londero de Oliveira · 2018
This paper presents timing efficient and low cost hardware customization of a single core general purpose processor architecture for Montgomery Modular Multiplication (MMM) and exponentiation. MMM demands a lot of computation time and is the key for efficient cryptography applications. Our hybrid approach consists in elaborating an optimized C code (software) while customizing a Tensilica® Xtensa processor instruction set architecture in order to accelerate MMM. We substitute the Standard Multiplication (grade school multiplication) with a complexity order ofO(n2) by a Karatsuba multiplication with a complexity ofO(n1.585), so that all the critical hardware components are shared. Moreover, the proposed design was developed to deal with modulus length of 1024 up to 4096-bit. The architecture was described in Tensilica®Instruction Extension (TIE) language and synthesized in Cadence®Xtensa Xplorer. Experiments show that our design can perform the modular exponentiation algorithm with 167k gates in 414,708,349 cycles considering 4096-bit modulus length in a lightweight processor configuration without a cache memory.