Cryptography Reference
In-Depth Information
If gcd(
s
1
−
= 1, the equation has multiple solutions for
k
E
, and Oscar has
to verify which is the correct one. In any case, using
k
E
, Oscar can now also compute
the private key through either Eq. (10.2) or Eq. (10.3):
s
2
,
p
−
1)
x
1
−
s
1
k
E
r
d
≡
mod
p
−
1
.
With the knowledge of the private key
d
and the public key parameters, Oscar can
now freely sign any documents on Bob's behalf. In order to avoid the attack, fresh
ephemeral keys stemming from a random number generator should be used for every
digital signature.
An attack with small numbers is given in the next example.
Example 10.3.
Let's assume the situation where Oscar eavesdrops on the following
two messages that were previously signed with Bob's private key and that use the
same ephemeral key
k
E
:
1. (
x
1
,
(
r
,
s
1
)) = (26
,
(3
,
26)),
2. (
x
2
,
(
r
,
s
2
)) = (13
,
(3
,
1)).
Additionally, Oscar knows Bob's public key, which is given as
(
p
,
α
,
β
)=(29
,
2
,
7)
.
With this information, Oscar is now able to compute the ephemeral key
x
1
−
x
2
≡
−
k
E
mod
p
1
s
1
−
s
2
26
−
13
≡
1
≡
13
·
9
26
−
≡
5 mod 28
and finally reveal Bob's private key
d
:
x
1
−
s
1
·
k
E
≡
−
d
mod
p
1
r
26
−
26
·
5
≡
≡
8
·
19
3
≡
12 mod 28
.
Existential Forgery Attack
Similar to the case of RSA digital signatures, it is also possible that an attacker gen-
erates a valid signature for a
random
message
x
. The attacker, Oscar, impersonates
Bob, i.e., Oscar claims to Alice that he is in fact Bob. The attack works as follows:
