Cryptography Reference
In-Depth Information
)
∗
is chosen and
exponent. Then prior to deciphering
b
, a random
r
∈
(
Z
/n
Z
b
≡
r
e
(mod
n
) is computed, followed by
c
≡
(
b
)
d
(mod
n
). Then the
b
·
computer sets
c
=
c
r
−
1
(mod
n
) thereby exponentiating a random
b
with
d
that is totally unknown to Eve, thereby thwarting her attack.
·
Power Cryptanalysis Attack
A section, albeit small, is deserving for another outstanding idea from
Kocher, called
power cryptanalysis
. By a very careful measurement of the com-
puter's
power consumption
during decryption, Eve could recover the secret key.
This works since during multiprecision multiplications the computer's power
consumption is necessarily higher than it would normally be. Hence, if Eve
measures the length of these high consumption episodes she can easily decide
when the computer is performing one or two multiplications, and this gives away
the bits of
d
. The only protection is some kind of physical shielding of the power
output. See
http://www.cryptography.com/resources/whitepapers/DPA.html
.
Low Public RSA Exponent Attacks
For the sake of e8ciency, one would like to use small public RSA exponents.
However, one has to be careful not to compromise security in so doing. One
typically used public exponent is, surprisingly,
e
= 3. However, if the same
message
m
, in a single block, is sent to three different entities, having pairwise
relatively prime RSA moduli
n
j
, with
m<n
j
for
j
=1
,
2
,
3, this allows recovery
of the plaintext. Here is how it is done. Using the Chinese remainder theorem,
there is a solution to
x
m
3
(mod
n
i
) for each
i
=1
,
2
,
3. Since
m
3
<
n
1
n
2
n
3
, then
x
=
m
3
. By computing the cube root of the integer
x
, we retrieve
m
. Furthermore, this attack can be generalized to show that a plaintext
m
can be recovered if
e
is the RSA enciphering exponent and
m
is sent to
k
≡
c
i
≡
e
recipients with pairwise relatively prime RSA moduli
n
i
such that
m<n
i
for
i
=1
,
2
,...,k
. Recognizing these issues, certain experts have suggestions.
The authors of [149] suggest: “Values such as 3 and 17 can no longer be
recommended, but commonly used values such as 2
16
+1=65
,
537 still seem to
be fine. If one prefers to stay on the safe side one may select an odd 32-bit or 64-
bit public exponent at random.” One of the reasons they suggest 2
16
+1 is that
(65537)
10
= (10000000000000001)
2
, so encryption using the repeated squaring
method needs only 16 modular squarings and 1 modular multiplication; and
here to recover the plaintext by the generalized method of the above paragraph
would require sending the same message to 2
16
+ 1 entities, not likely to occur.
In any case, this generalized method of attack can be thwarted by padding a
randomly generated bitstring of suitable length to the plaintext message prior to
encryption. In fact, this is something discussed in the security section on page
174, namely, the necessity of preprocessing plaintext before the RSA cipher is
employed. However, one has to be careful that the padding itself is secure.
For instance, the attack in the paragraph above works because the messages
are linearly related, allowing use of the Chinese Remainder Theorem. In fact,
a generalization of results by Coppersmith (see [61]), were given by Hastad in
[120], called the
Strong Hastad Broadcast Attack
.. He proved that
any
fixed
≥
Search WWH ::
Custom Search