Cryptography Reference
In-Depth Information
7.9 Implementation in Software and Hardware
RSA is the prime example (almost literally) for a public-key algorithm that is very
computationally intensive. Hence, the implementation of public-key algorithms is
much more crucial than that of symmetric ciphers like 3DES and AES, which are
significantly faster. In order to get an appreciation for the computational load, we
develop a rough estimate for the number of integer multiplications needed for an
RSA operation.
We assume a 2048-bit RSA modulus. For decryption we need on average 3072
squaring and multiplications, each of which involves 2048-bit operands. Let's as-
sume a 32-bit CPU so that each operand is represented by 2048
/
32 = 64 registers.
A single long-number multiplication requires now 64
2
= 4096 integer multiplica-
tions since we have to multiply every register of the first operand with every register
of the second operand. In addition, we have to modulo reduce each of these multipli-
cations. The best algorithms for doing this also require roughly 64
2
= 4096 integer
multiplications. Thus, in total, the CPU has to perform about 4096 + 4096 = 8192
integer multiplications for a single long-number multiplication. Since we have 3072
of these, the number of integer multiplications for one decryption is:
#(32-bit mult) = 3072
×
8192 = 25
,
165
,
824
Of course, using a smaller modulus results in fewer operations, but given that integer
multiplications are among the most costly operations on current CPUs, it is probably
clear that the computational demand is quite impressive. Note that most other public
key schemes have a similar complexity.
The extremely high computational demand of RSA was, in fact, a serious hin-
drance to its adoption in practice after it had been invented. Doing hundreds of
thousands of integer multiplications was out of question with 1970s-style comput-
ers. The only option for RSA implementations with an acceptable run time was
to realize RSA on special hardware chips until the mid- to late 1980s. Even the
RSA inventors investigated hardware architecture in the early days of the algorithm.
Since then much research has focused on ways to quickly perform modular integer
arithmetic. Given the enormous capabilities of state-of-the-art VLSI chips, an RSA
operation can today be done in the range of 100
s on high-speed hardware.
Similarly, due to Moore's Law, RSA implementations in software have become
possible since the late 1980s. Today, a typical decryption operation on a 2 GHz CPU
takes around 10 ms for 2048-bit RSA. Even though this is sufficient for many PC
applications, the throughput is about 100
μ
2048 = 204
,
800 bit/s if one uses RSA
for encryption of large amounts of data. This is quite slow compared to the speed of
many of today's networks. For this reason RSA and other public-key algorithms are
not used for bulk data encryption. Rather, symmetric algorithms are used that are
often faster by a factor of 1000 or so.
×
