Cryptography Reference
In-Depth Information
ratio between RSA encryption with 1024 bit and RSA with 512 bit if the Karat-
suba algorithm is used in both cases? Again, assume that full-length exponents
are being used.
7.15.
(Advanced problem!) There are ways to improve the square-and-multiply al-
gorithm, that is, to reduce the number of operations required. Although the number
of squarings is fixed, the number of multiplications can be reduced. Your task is to
come up with a modified version of the square-and-multiply algorithm which re-
quires fewer multiplications. Give a detailed description of how the new algorithm
works and what the complexity is (number of operations).
Hint: Try to develop a generalization of the square-and-multiply algorithm which
processes more than one bit at a time. The basic idea is to handle
k
(e.g.,
k
= 3)
exponent bit per iteration rather than one bit in the original square-and-multiply
algorithm.
7.16.
Let us now investigate side-channel attacks against RSA. In a simple imple-
mentation of RSA without any countermeasures against side-channel leakage, the
analysis of the current consumption of the microcontroller in the decryption part
directly yields the private exponent. Figure 7.5 shows the power consumption of an
implementation of the square-and-multiply algorithm. If the microcontroller com-
putes a squaring or a multiplication, the power consumption increases. Due to the
small intervals in between the loops, every iteration can be identified. Furthermore,
for each round we can identify whether a single squaring (short duration) or a squar-
ing followed by a multiplication (long duration) is being computed.
1. Identify the respective rounds in the figure and mark these with S for squaring or
SM for squaring and multiplication.
2. Assume the square-and-multiply algorithm has been implemented such that the
exponent is being scanned from left to right. Furthermore, assume that the start-
ing values have been initialized. What is the private exponent
d
?
3. This key belongs to the RSA setup with the primes
p
= 67 and
q
= 103 and
e
= 257. Verify your result. (Note that in practice an attacker wouldn't know the
values of
p
and
q
.)
