Cryptography Reference
In-Depth Information
10.3.3 Security
First, we must make sure that the verifier has the correct public key. Otherwise,
the attack sketched in Sect. 10.2.3 is applicable. Other attacks are described in the
following.
Computing Discrete Logarithms
The security of the signature scheme relies on the discrete logarithm problem (DLP).
If Oscar is capable of computing discrete logarithms, he can compute the private key
d from
as well as the ephemeral key k E from r . With this knowledge, he can sign
arbitrary messages on behalf of the signer. Hence the Elgamal parameters must be
chosen such that the DLP is intractable. We refer to Sect. 8.3.3 for a discussion of
possible discrete logarithm attacks. One of the key requirements is that the prime p
should be at least 1024-bit long. We have also make sure that small subgroup attacks
are not possible. In order to counter this attack, in practice primitive elements
β
α
are used to generate a subgroup of prime order. In such groups, all elements are
primitive and small subgroups do not exist.
Reuse of the Ephemeral Key
If the signer reuses the ephemeral key k E , an attacker can easily compute the private
key a . This constitutes a complete break of the system. Here is how the attack works.
Oscar observes two digital signatures and messages of the form ( x , ( r , s )).Ifthe
two messages x 1 and x 2 have the same ephemeral key k E , Oscar can detect this since
the two r values are the same because they were constructed as r 1 = r 2 =
k E .The
α
two s values are different, and Oscar obtains the following two expressions:
dr ) k 1
E
s 1
( x 1
mod p
1
(10.2)
dr ) k 1
E
s 2
( x 2
mod p
1
(10.3)
This is an equation system with the two unknowns d , which is Bob's private key (!)
and the ephemeral key k E . By multiplying both equations by k E it becomes a linear
system of equations which can be solved easily. Oscar simply subtracts the second
equation from the first one, yielding:
x 2 ) k 1
E
s 1
s 2
( x 1
mod p
1
from which the ephemeral key follows as
x 1
x 2
k E
mod p
1 .
s 1
s 2
Search WWH ::




Custom Search