Public-Key Cryptography - A Classical Introduction to Cryptography: Applications for Communications Security - page 237

secret key. We also assume that this device uses the Chinese remainder accelera-
tion: we know that computing y d ((log N ) 3 ). We can

also compute y d mod p and y d mod q and combine them by the Chinese Remain-
der Theorem. Since p and q are half size numbers, doing computation modulo p
(or q ) requires one eighth of this complexity. The exponent d can further be reduced
modulo p

mod N can be done within O

1, and so we get an acceleration by a factor of 8 by
using this trick. Therefore, assuming that the decryptor uses this acceleration trick is
reasonable.

− 1, and modulo q −

Now we assume that we can physically stress the device (by heat, beams, corrupted
input power or clock signals, etc.) so that the device will make errors. Let us just pick
x and compute y x e mod N and send y to the decryptor. We assume that we stress

the decryptor so that an error occurs in the modulo p computation, but not in the
modulo q computation. The decryptor will return x such that x

=

x (mod q ) and ≡

x (mod p ). Therefore, gcd ( x x , x ≡ − N ) = q and we can factorize N and compute

the secret key of the decryptor! 7

This attack is rather an implementation attack in which the adversary gets side
information by quite active attacks.

A more peaceful way to retrieve side information is to measure the computation
time: some microprocessors have a multiplication instruction whose computation time
depends on the input operands. As was shown by Paul Kocher, this information can
be used in order to recover some information about internal computations, and then to
recover the secret keys (see Ref. [103]).

A more sophisticated attack consists in measuring the evolution of the power con-
sumption with time: if we know which program is run by a microprocessor (but we
do not know the key), we can measure with an oscilloscope the power consumed by
the microprocessor for every instruction. The RSA decryption consists of computing a
modular exponentiation to a secret power d . The square-and-multiply method sequen-
tially computes a square and a multiplication for a bit set to 1, or just a square for a bit
set to 0. This is done for every bit of d , sequentially. Presumably, the square operation
and the multiplication will be implemented quite differently, and the power consump-
tion analysis will be able to say when the decryption device makes a multiplication and
when it computes a square. Therefore we will be able to “see” the 0 bits and the 1 bits
of d sequentially! (see Ref. [104]).

This technique can be extended to block ciphers. Assuming that the power depends
on the values of the registers (a memory bit consumes a different power for a bit 0 and
a bit 1), the power analysis can tell what is the Hamming weight (namely the number of
bits set to 1) of all registers. If the computation starts by computing x ⊕ K for a secret

K , since we know x and we can get the Hamming weight of x ⊕ K , by trying several

7

This attack was published in Ref. [35].