240
D. Gorodecky and T. Villa
mixed-radix approach [16] must be applied, in all cases decreasing significantly the
performance of the conversion. In practice both problems are solved by choosing
from a small set of special moduli, which limits the applicability of RNS.
11.3 Computation of the Modulo Function
The modulus function calculation (X(mod P )) is a basic arithmetic operation in
cryptography and in the residue number system (RNS). In both cases one must
handle huge numbers X with hundreds and thousands of bits. However, there is
a significant difference between the two areas in the requirements to compute
X(mod P ). The value of P in cryptography is a prime number or one which can be
factored with 2 or rarely 3 factors, i.e., P = p 1 · p 2 · p 3 , where p 1 , p 2 , p 3 are prime
numbers. In RNS, P can be factored with n factors, where n can be of the order
of a few dozens, i.e., P = p 1 · p 2 · . . . · p n . Despite this difference, the hardware
implementation of the modulus function is a bottleneck for both areas.
A major limitation when processing large numbers in RNS is the complexity of
hardware realization of converters (left and right blocks in Fig. 11.1). This is due to
the fact that to compute the modulus function and to recover the positional representation one should perform division, modular multiplication, and comparison. There
are different approaches to solve this problem (e.g., [3, 5, 23]), but, mostly, they are
restricted with respect to the modular values (e.g., mod 2 k −1, mod 2 k , mod 2 k +1)
and to the number of operands.
Cryptography demands that the factors of P be as hard as possible. This fact
significantly increases the complexity of hardware realization, since an efficient
hardware implementation of X(mod P ) for an arbitrary P is unknown. In RNS all
factors of P are known. Moreover p 1 , p 2 , . . . , p n are selected as special numbers
for which it is known an efficient hardware realization. But the problem is that the
set of special numbers, for which efficient algorithms are known, is very limited.
This is the main fact which restricts wide RNS deployment.
There are existing [13] approaches for X(modP ) design in hardware, but they are
sequential or/and they exhibit high hardware costs and low performance compared
with approaches for special number sets.
A unit for modulus function computation can be designed with sequential
elements, but they require bigger areas and they are slower compared with combinational approaches. On the other hand, the availability of memory allows to compute
X(mod P ) for arbitrary value of P and to pipeline the computation. Sequential
realizations may store pre-calculated values of the modulus function [10, 13], or
be computed by an automaton model [22], or they may resort to pipelining using
a chain of homogeneous arithmetic blocks [2]. A pipelining model is based on
combinational logic, where pipelining stages are separated by triggers (latches).
More recent designs avoid the use of memory elements and use combinational logic
to a large extent, and shortly we will consider some of them.
D. Gorodecky and T. Villa
mixed-radix approach [16] must be applied, in all cases decreasing significantly the
performance of the conversion. In practice both problems are solved by choosing
from a small set of special moduli, which limits the applicability of RNS.
11.3 Computation of the Modulo Function
The modulus function calculation (X(mod P )) is a basic arithmetic operation in
cryptography and in the residue number system (RNS). In both cases one must
handle huge numbers X with hundreds and thousands of bits. However, there is
a significant difference between the two areas in the requirements to compute
X(mod P ). The value of P in cryptography is a prime number or one which can be
factored with 2 or rarely 3 factors, i.e., P = p 1 · p 2 · p 3 , where p 1 , p 2 , p 3 are prime
numbers. In RNS, P can be factored with n factors, where n can be of the order
of a few dozens, i.e., P = p 1 · p 2 · . . . · p n . Despite this difference, the hardware
implementation of the modulus function is a bottleneck for both areas.
A major limitation when processing large numbers in RNS is the complexity of
hardware realization of converters (left and right blocks in Fig. 11.1). This is due to
the fact that to compute the modulus function and to recover the positional representation one should perform division, modular multiplication, and comparison. There
are different approaches to solve this problem (e.g., [3, 5, 23]), but, mostly, they are
restricted with respect to the modular values (e.g., mod 2 k −1, mod 2 k , mod 2 k +1)
and to the number of operands.
Cryptography demands that the factors of P be as hard as possible. This fact
significantly increases the complexity of hardware realization, since an efficient
hardware implementation of X(mod P ) for an arbitrary P is unknown. In RNS all
factors of P are known. Moreover p 1 , p 2 , . . . , p n are selected as special numbers
for which it is known an efficient hardware realization. But the problem is that the
set of special numbers, for which efficient algorithms are known, is very limited.
This is the main fact which restricts wide RNS deployment.
There are existing [13] approaches for X(modP ) design in hardware, but they are
sequential or/and they exhibit high hardware costs and low performance compared
with approaches for special number sets.
A unit for modulus function computation can be designed with sequential
elements, but they require bigger areas and they are slower compared with combinational approaches. On the other hand, the availability of memory allows to compute
X(mod P ) for arbitrary value of P and to pipeline the computation. Sequential
realizations may store pre-calculated values of the modulus function [10, 13], or
be computed by an automaton model [22], or they may resort to pipelining using
a chain of homogeneous arithmetic blocks [2]. A pipelining model is based on
combinational logic, where pipelining stages are separated by triggers (latches).
More recent designs avoid the use of memory elements and use combinational logic
to a large extent, and shortly we will consider some of them.