Digital Signal Processing Reference
In-Depth Information
2.2.3
Other Ideas for Arithmetic Borrowed from Signal Processing
Cryptographic application as well as signal processing require arithmetic-intensive
operations, hence there are several ideas that were applied in both. Examples
computation in frequency domain etc.
Nowadays ever faster arithmetic is demanded e.g. for RSA cryptosystems due
to the constant improvements in factoring and the resulting requirements for even
longer key sizes. In order to achieve that, the Residue Number System is an
alternative to the common radix representation. RNS arithmetic is a very old idea
which relies on the Chinese Remainder Theorem (CRT) and it provides a good
means for very long integer arithmetic.
Let
x
a
denote an RNS representation of
x
, then:
x
a
=(
x
[
a
1
]
,
x
[
a
2
]
,...,
x
[
a
n
])
(3)
where,
x
[
a
i
]=
x
mod
a
i
.Theset
a
=
{
a
1
,
a
2
,...,
a
n
}
is called a base (of size
n
). It is
required that
gcd
(
a
i
,
a
j
)=
1for
i
=
j
. CRT implies that the integer
x
which satisfies
n
i
0
a
.
A well known advantage of RNS is that to add, subtract and multiply such
numbers we only need to compute the addition, subtraction and multiplication of
their components, of size much smaller than the original modulus. Also carry-free
arithmetic makes parallelization possible. The final result is obtained by means of
the CRT. The disadvantage of an RNS representation is the overhead introduced
by the input and output conversions from binary to RNS and vice versa. It is
also difficult to perform division. To overcome this disadvantage, a combination
Montgomery brings a higher speed for both ECC and Pairing implementations on
Exponent recoding techniques for modular exponentiation (as used for RSA)
replace the binary representation of an exponent with a representation which has
recoding have been proposed in the literature. Here we mention the signed-digit
representation. Consider an integer representation of the form
k
≤
x
<
∏
1
a
i
is uniquely represented by
x
=
l
i
0
s
i
2
i
,where
=
∑
=
s
i
∈{−
. This is called the (binary) signed digit (SD) representation (see
3 can be represented as
1
,
0
,
1
}
10 1
)
2
,where1
1. It is said that an
SD representation is
sparse
if it has no adjacent non-zero digits. A sparse SD
representation is also called a
non-adjacent form
(NAF). Every integer
k
has a
unique NAF which has the minimum weight of any signed digit representation of
k
.
For RSA, the NAF techniques are not beneficial because they assume performing
the division operation, which should be avoided due to the complexity of the
operation. However, for ECC it is considered advantageous because the Hamming
weight of the scalar is minimal. Also in this case “
(
011
)
2
or
(
=
−
1” means point subtraction
instead of addition, which is an addition of the inverse point. More precisely, the
−
