Cryptography Reference
In-Depth Information
Signature
To sign a message
m
, the signer picks
k
uniformly at random in
{
0
,
1
,...,
q
−
1
}
and sets
H
(
m
)
+
α
r
g
k
r
:=
(
mod
p
)(
mod
q
)
and
s
:=
(
mod
q
).
k
The signature is the pair
(
r
,
s
)
.
Verification
The verifier considers
(
r
,
s
)
as a valid signature of
m
if
?
=
(
g
wh
wh
r
β
mod
p
)(
mod
q
)
where
h
=
H
(
m
)
and
w
=
1
/
s
(
mod
q
)
.
Recommended Parameters
The original Digital Signature Standard required
p
to be between 512 and 1
024
bits long,
q
to be 160 bits long, and the hash function
H
to be SHA-1. The current
version also allows parameter sizes of
,
(
2
,
048
,
224
)
,
(
2
,
048
,
256
)
and
(
3
,
072
,
256
)
with SHA-2 as a hash function.
12.3.2 Attack Model
Faulty signatures are valid DSA signatures
(
r
i
,
s
i
)
where the
least significant bits
of the corresponding nonces
k
i
are all 0.
Such faulty signatures are obtained in practice by causing a glitch in the signing
device during the generation of the nonce: since
k
is generated by loading a series
of random bytes into memory, fault injection makes it possible to skip part of the
loop involved in that generation, resulting in clear least significant bits. A timing
analysis of the power trace then makes it possible to check whether the generation
has actually been faulty, by examining if it is shorter than a normal execution or not.
12.3.3 Description of the Attack
Given sufficiently many faulty signatures, the secret key
can be recovered using a
technique based on lattices [185, 304]. The idea is to use the congruence
α
