SECTION 10.2 RSA CRYPTOSYSTEM 309
unconcealed message is a message that encrypts to itself (cannot be concealed). It has
been proven that there are always some messages that are encrypted to themselves.
Because the encryption exponent normally is odd, there are some plaintexts that are
encrypted to themselves such as P = 0 and P = 1. Although there are more, if the
encrypting exponent is selected carefully, the number of these message is negligible.
The encrypting program can always check if the calculated ciphertext is the same as
the plaintext and reject the plaintext before submitting the ciphertext.
Attacks on the Modulus
The main attack on RSA, as discussed previously, is the factorization attack. The fac-
torization attack can be considered an attack on the low modulus. However, because we
have already discussed this attack, we will concentrate on another attack on the modu-
lus: the common modulus attack.
Common Modulus Attack The common modulus attack can be launched if a com-
munity uses a common modulus, n. For example, people in a community might let a
trusted party select p and q, calculate n and φ(n), and create a pair of exponents (e
i
, d
i
)
for each entity. Now assume Alice needs to send a message to Bob. The ciphertext to
Bob is C = P
e
B
mod n. Bob uses his private exponent, d
B
, to decrypt his message, P =
C
d
B
mod n. The problem is that Eve can also decrypt the message if she is a member of
the community and has been assigned a pair of exponents (e
E
and d
E
), as we learned in
the section “Low Decryption Exponent Attack”. Using her own exponents (e
E
and d
E
),
Eve can launch a probabilistic attack to factor n and find Bob’s d
B
. To thwart this type
of attack, the modulus must not be shared. Each entity needs to calculate her or his own
modulus.
Attacks on Implementation
Previous attacks were based on the underlying structure of RSA. As Dan Boneh has
shown, there are several attacks on the implementation of RSA. We mention two of
these attacks: the timing attack and the power attack.
Timing Attack Paul Kocher elegantly demonstrated a ciphertext-only attack, called
the timing attack. The attack is based on the fast-exponential algorithm discussed in
Chapter 9. The algorithm uses only squaring if the corresponding bit in the private
exponent d is 0; it uses both squaring and multiplication if the corresponding bit is 1. In
other words, the timing required to do each iteration is longer if the corresponding bit is
1. This timing difference allows Eve to find the value of bits in d, one by one.
Assume that Eve has intercepted a large number of ciphertexts, C
1
to C
m
. Also
assume that Eve has observed how long it takes for Bob to decrypt each ciphertext, T
1
to T
m
. Eve, who knows how long it takes for the underlying hardware to calculate a
multiplication operation, calculated t
1
to t
m
, where t
i
is the time required to calculate
the multiplication operation Result = Result × C
i
mod n.
Eve can use Algorithm 10.5, which is a simplified version of the algorithm used in
practice, to calculate all bits in d (d
0
to d
k−1
).
The algorithm sets d
0
= 1 (because d should be odd) and calculates new values for
T
i
’s (decryption time related to d
1
to d
k−1
). The algorithm then assumes the next bit is 1