A Multi-layer Recursive Residue Number System
This addresses the need for efficient, parallelizable hardware implementations in cryptography by enabling large-modulus operations without carries, which is incremental as it builds on existing RNS and Montgomery multiplication methods.
The paper tackles the problem of increasing the dynamical range of Residue Number Systems (RNS) for large moduli (e.g., 2000+ bits) by introducing a multi-layer recursive approach, enabling modular arithmetic operations using only small moduli (e.g., 8-bit) and achieving applications in cryptography like RSA with 2048-bit or 4096-bit moduli.
We present a method to increase the dynamical range of a Residue Number System (RNS) by adding virtual RNS layers on top of the original RNS, where the required modular arithmetic for a modulus on any non-bottom layer is implemented by means of an RNS Montgomery multiplication algorithm that uses the RNS on the layer below. As a result, the actual arithmetic is deferred to the bottom layer. The multiplication algorithm that we use is based on an algorithm by Bajard and Imbert, extended to work with pseudo-residues (remainders with a larger range than the modulus). The resulting Recursive Residue Number System (RRNS) can be used to implement modular addition, multiplication, and multiply-and-accumulate for very large (2000+ bits) moduli, using only modular operations for small (for example 8-bits) moduli. A hardware implementation of this method allows for massive parallelization. Our method can be applied in cryptographic algorithms such as RSA to realize modular exponentiation with a large (2048-bit, or even 4096-bit) modulus. Due to the use of full RNS Montgomery algorithms, the system does not involve any carries, therefore cryptographic attacks that exploit carries cannot be applied.