Cryptography Reference
In-Depth Information
In this chapter, we present a survey of the application of fault attacks to different
RSA implementations, classical and more sophisticated. After giving a presenta-
tion of the RSA cryptosystem and its classical implementation, we chronologically
review these attacks and some of the proposed countermeasures. Although the first
attacks focused their efforts on exploiting perturbations of secret elements or related
operations (see Sect.
7.3
), recent works have addressed the security of public ele-
ments (see Sect.
7.4
). This new trend is all the more interesting since public elements
are usually handled in a less secure way than private ones. Furthermore, it may lead
to powerful attacks regardless of the perturbation induced.
7.2 RSA Implementations
The celebrated RSA was invented in 1977 by Rivest et al. [349]. This method was the
first cryptographic algorithm instantiating the principle of public key cryptography,
introduced earlier, as a concept, by Diffie and Hellman [121]. Nowadays, RSA is
certainly the most widely used algorithm to ensure the security of communications
or transactions.
The RSA security relies on the Integer Factorization Problem (IFP). The best
known method for solving an instance of this problem is the Number Field Sieve,
whose complexity is sub-exponential with respect to the size of the RSA field [252].
To the best of our knowledge, the larger RSA modulus ever factored by this method
has a bit length of 768 [232]. As a consequence, this method cannot be used today
to factor practically sized moduli (i.e. 1,024 or 2,048 bits).
In practice, the RSA can be derived in both standard and CRT modes. The standard
mode is the straightforward way for implementing RSA. Its principle is recalled
below. The CRT mode of RSA, where CRT stands for Chinese Remainder Theorem,
is usually used to perform efficient signatures in embedded systems. Further details
about CRT-RSA implementations can be found in [283, 330].
7.2.1 Standard RSA
7.2.1.1 Key Generation
Let
N
, the public modulus, be the product of two large prime numbers
p
and
q
.The
bit length of
N
, denoted by
n
, also stands for the RSA length. Let
e
be the public
exponent, coprime to
ϕ(
N
)
=
(
p
−
1
)
·
(
q
−
1
)
, where
ϕ(
·
)
denotes Euler's totient
function. Then the pair
K
p
=
(
,
)
is the RSA public key, which is spread over a
network. The public key exponent
e
is linked to the private key exponent
d
by the
following equation:
N
e
e
·
d
≡
1
(
mod
ϕ(
N
)).
This exponent is also called private key
K
s
, which is kept secret by its owner.
