Cryptography Reference
In-Depth Information
For exponents
e
and moduli
m
of, say,
512
binary places and
M
=2
k
we
obtain the numbers of modular multiplications for the calculation of
a
e
mod
m
as shown in Table 6-1. The table shows as well the memory requirement
for the precomputed powers of
a
mod
m
, which result from the product
(2
k
−
2)
CLINTMAXSHORT
·
sizeof(USHORT)
.
Table 6-1. Requirements for exponentiation
Multiplications
Memory (in Bytes)
k
1
766
0
2
704
1028
3
666
3084
4
644
7196
5
640
15420
6
656
31868
We see from the table that the average number of multiplications reaches a
minimum of 640 at
k
=5
, where the required memory for each larger
k
grows by
approximately a factor of
2
. But what are the time requirements for other orders
of magnitude of the exponents?
Table 6.2 gives information about this. It displays the requirements for
modular multiplication for exponentiation with exponents with various numbers
of binary digits and various values of
M
=2
k
. The exponent length of
768
digits
was included because it is a frequently used key length for the RSA cryptosystem
(see Chapter 17). The favorable numbers of multiplications appear in boldface.
Table 6-2. Numbers of multiplications for typical sizes of exponents and various bases
2
k
Number of Binary Digits in the Exponent
k
32
64
128
512
768
1024
2048
4096
1
45
93
190
766
1150
1534
3070
6142
2
4
88
176
704
1056
1408
2816
5632
3
46
87
170
666
996
1327
2650
5295
4
52
91
170
644
960
1276
2540
5068
5
67
105
181
640
945
1251
2473
4918
6
98
135
209
656
954
1252
2444
4828
7
161
197
271
709
1001
1294
2463
4801
8
288
324
396
828
1116
1404
2555
4858
