Cryptography Reference
In-Depth Information
have been the foundation of many more cryptanalytic results ever since, including
attacks on linear congruential generators [147, 386], RSA signatures with constant
padding [71, 290], implementations of El Gamal signatures [302] and the numer-
ous applications of Coppersmith's techniques for finding small roots of algebraic
equations [101].
In this chapter, we present several recent examples of attacks where these pow-
erful lattice methods were used in conjunction with fault injection to break physical
implementations of cryptographic signature schemes:
•
against DSA (Sect.
12.3
), an attack by Naccache et al. [300], involving the search
for the lattice point closest to a target point in space;
•
against the RSA signature scheme ISO/IEC 9796-2 (Sect.
12.4
), a polynomial
attack by Coron et al. [104] based on results similar to Coppersmith's, and another
attack by Coron et al. [108] based on a rather different technique, namely the
so-called orthogonal lattice technique introduced by Nguyen and Stern in 1997 [307].
12.2 Preliminaries on Lattices
We start with some preliminary definitions and results about lattices. A reader unfa-
miliar with these notions may want to skim through this section in a first reading and
refer back to it later as needed. A similar presentation with a larger scope and more
details can be found in [303, Sect. 6].
12.2.1 Notation and Background
n
endowed with its usual structure as an Euclidean vector space.
Bold letters will denote vectors, usually in row notation. If
x
We will consider
R
=
(
x
1
,...,
x
n
)
and
y
=
(
y
1
,...,
y
n
)
are two vectors, their Euclidean inner product is denoted by
n
x
,
y
=
x
i
y
i
.
i
=
1
The corresponding Euclidean norm is denoted by
x
1
+···+
x
=
x
,
x
=
x
n
.
n
, we define the linear span of
S
, denoted by span
For any subset
S
of
R
(
S
)
,asthe
n
minimal vector subspace of
R
containing
S
.
n
. The vectors
b
i
aresaidtobe
linearly dependent
if there
Let
b
1
,...,
R
b
m
be in
exist scalars
x
1
,...,
x
m
∈ R
which are not all zero and such that:
