Cryptography Reference
In-Depth Information
Even though factoring has become easier than the RSA designers had assumed 30
years ago, factoring RSA moduli beyond a certain size still is out of reach.
Table 7.3
Summary of RSA factoring records since 1991
Decimal digits Bit length
Date
100
330
April 1991
110
364
April 1992
120
397
June 1993
129
426
April 1994
140
463
February 1999
155
512
August 1999
200
664
May 2005
Of historical interest is the 129-digit modulus which was published in a column
by Martin Gardner in
Scientific American
in 1997. It was estimated that the best
factoring algorithms of that time would take 40 trillion (4
10
13
) years. However,
factoring methods improved considerably, particularly during the 1980s and 1990s,
and it took in fact less than 30 years.
Which exact length the RSA modulus should have is the topic of much discus-
sion. Until recently, many RSA applications used a bit length of 1024 bits as default.
Today it is believed that it might be possible to factor 1024-bit numbers within a pe-
riod of about 10-15 years, and intelligence organizations might be capable of doing
it possibly even earlier. Hence, it is recommended to choose RSA parameters in the
range of 2048-4096 bits for long-term security.
ยท
Side-Channel Attacks
A third and entirely different family of attacks are side-channel attacks. They exploit
information about the private key which is leaked through physical channels such as
the power consumption or the timing behavior. In order to observe such channels, an
attacker must typically have direct access to the RSA implementation, e.g., in a cell
phone or a smart card. Even though side-channel attacks are a large and active field
of research in modern cryptography and beyond the scope of this topic, we show
one particularly impressive such attack against RSA in the following.
Figure 7.4 shows the power trace of an RSA implementation on a microproces-
sor. More precisely, it shows the electric current drawn by the processor over time.
Our goal is to extract the private key
d
which is used during the RSA decryption.
We clearly see intervals of high activity between short periods of less activity. Since
the main computational load of RSA is the squarings and multiplication during the
exponentiation, we conclude that the high-activity intervals correspond to those two
operations. If we look more closely at the power trace, we see that there are high
activity intervals which are short and others which are longer. In fact, the longer
ones appear to be about twice as long. This behavior is explained by the square-
and-multiply algorithm. If an exponent bit has the value 0, only a squaring is per-
