Cryptography Reference
In-Depth Information
7.10 Discussion and Further Reading
RSA and Variants
The RSA cryptosystem is widely used in practice and is well
standardized in bodies such as PKCS#1 [149]. Over the years several variants have
been proposed. One generalization is to use a modulus which is composed of more
than two primes. Also proposed have been multipower moduli of the form
n
=
p
2
q
[162] as well as multifactor ones where
n
=
pq r
[45]. In both cases speed-ups by a
factor of approximately 2-3 are possible.
There are also several other crypto schemes which are based on the integer fac-
torization problem. A prominent one is the Rabin scheme [140]. In contrast to RSA,
it can be shown that the Rabin scheme is equivalent to factoring. Thus, it is said
that the cryptosystem is
provable secure
. Other schemes which rely on the hard-
ness of integer factorization include the probabilistic encryption scheme by Blum-
Goldwasser [28] and the Blum Blum Shub pseudo-random number generator [27].
The
Handbook of Applied Cryptography
[120] describes all the schemes mentioned
in a coherent form.
Implementation
The actual performance of an RSA implementation heavily de-
pends on the efficiency of the arithmetic used. Generally speaking, speed-ups are
possible at two levels. On the higher level, improvements of the square-and-multiply
algorithm are an option. One of the fastest methods is the sliding window exponen-
tiation which gives an improvement of about 25% over the square-and-multiply al-
gorithm. A good compilation of exponentiation methods is given in [120, Chap. 14].
On the lower layer, modular multiplication and squaring with long numbers can be
improved. One set of techniques deals with efficient algorithms for modular reduc-
tion. In practice, Montgomery reduction is the most popular choice; see [41] for a
good treatment of software techniques and [72] for hardware. Several alternatives
to the Montgomery method have also been proposed over the years [123]; [120,
Chap. 14]. Another angle to accelerate long number arithmetic is to apply fast mul-
tiplication methods. Spectral techniques such as the fast Fourier transform (FFT) are
usually not applicable because the operands are still too short, but methods such as
the Karatsuba algorithm [99] are very useful. Reference [17] gives a comprehensive
but fairly mathematical treatment of the area of multiplication algorithms, and [172]
describes the Karatsuba method from a practical viewpoint.
Attacks
Breaking RSA analytically has been a subject of intense investigation for
the last 30 years. Especially during the 1980s, major progress in factorization algo-
rithms was made, which was not in small part motivated by RSA. There have been
numerous other attempts to mathematically break RSA, including attacks against
short private exponents. A good survey is given in [32]. More recently, proposals
have been made to build special computers whose sole purpose is to break RSA.
Proposals include an optoelectronic factoring machine [151] and several other ar-
chitectures based on conventional semiconductor technology [152, 79].
Side channel attacks have been systematically studied in academia and industry
since the mid- to late 1990s. RSA, as well as most other symmetric and asymmetric
schemes, are vulnerable against differential power analysis (DPA), which is more
