Cryptography Reference
In-Depth Information
7.5 Speed-up Techniques for RSA
As we learned in Sect. 7.4, RSA involves exponentiation with very long numbers.
Even if the low-level arithmetic involving modular multiplication and squaring as
well as the square-and-multiply algorithm are implemented carefully, performing a
full RSA exponentiation with operands of length 1024 bit or beyond is computa-
tionally intensive. Thus, people have studied speed-up techniques for RSA since its
invention. We introduce two of the most popular general acceleration techniques in
the following.
7.5.1 Fast Encryption with Short Public Exponents
A surprisingly simple and very powerful trick can be used when RSA operations
with the public key e are concerned. This is in practice encryption and, as we'll
learn later, verification of an RSA digital signature. In this situation, the public key
e can be chosen to be a very small value. In practice, the three values e = 3, e = 17
and e = 2 16 + 1 are of particular importance. The resulting complexities when using
these public keys are given in Table 7.1.
Table 7.1 Complexity of RSA exponentiation with short public exponents
Public key e
e as binary string #MUL + #SQ
3
11 2
3
17
10001 2
5
2 16 + 1 1 0000 0000 0000 0001 2
17
These complexities should be compared to the 1 . 5 t multiplications and squarings
that are required for exponents of full length. Here t + 1 is the bit length of the
RSA modulus n , i.e.,
= t + 1. We note that all three exponents listed above
have a low Hamming weight, i.e., number of ones in the binary representation. This
results in a particularly low number of operations for performing an exponentiation.
Interestingly, RSA is still secure if such short exponents are being used. Note that
the private key d still has in general the full bit length t + 1 even though e is short.
An important consequence of the use of short public exponents is that encryption
of a message and verification of an RSA signature is a very fast operation. In fact,
for these two operations, RSA is in almost all practical cases the fastest public-key
scheme available. Unfortunately, there is no such easy way to accelerate RSA when
the private key d is involved, i.e., for decryption and signature generation. Hence,
these two operations tend to be slow. Other public-key algorithms, in particular el-
liptic curves, are often much faster for these two operations. The following section
shows how we can achieve a more moderate speed-up when using the private expo-
nent d .
log 2 n
Search WWH ::




Custom Search