Cryptography Reference
In-Depth Information
Chapter 12
Lattice-Based Fault Attacks on Signatures
Phong Q. Nguyen and Mehdi Tibouchi
Abstract
Since the introduction of the LLL algorithm in 1982, lattice reduction has
proved to be one of the most powerful and versatile tools of public key cryptanalysis.
In particular, it has sometimes been combined with fault injection to break physical
implementations of public key cryptosystems. We present several examples of lattice-
based fault attacks against DSA and RSA signatures, together with the necessary
mathematical background.
12.1 Introduction
A lattice is a regular arrangement of points in space which can be described as
the set of integral linear combinations of certain collections of linearly independent
vectors
b
1
,...,
b
d
called bases. Lattices have infinitely many bases, but some are
more interesting than others; finding interesting lattice bases, consisting of short and
nearly orthogonal vectors, is a mathematical problem with a long history, dating
back to the work of Lagrange and Gauss on quadratic forms in the late eighteenth
and early nineteenth centuries.
However, it was not until around 1980, with the advent of algorithmic number the-
ory, that general procedures for obtaining such interesting bases and solving related
lattice problems were proposed. The starting point of modern lattice reduction is the
seminal 1982 paper by Lenstra et al. [251] introducing the algorithm that became
known as LLL.
This algorithm and its later refinements were quickly recognized as powerful
cryptanalytic tools: they were used by Adleman as early as 1983 [1] in a generalization
of Shamir's attack on the Merkle-Hellman knapsack-based cryptosystem [370]. They
