Cryptography Reference
In-Depth Information
Key Generation
As discussed earlier, finding an elliptic curve with good crypto-
graphic properties is a nontrivial task. In practice, standardized curves such as the
ones proposed by NIST or the Brainpool consortium are often used. The remaining
computation in the key generation phase is one point multiplication, which can be
done using the double-and-add algorithm.
Signing
During signing we first compute the point
R
, which requires one point
multiplication, and from which
r
immediately follows. For the parameter
s
we have
to invert the ephemeral key, which is done with the extended Euclidean algorithm.
The other main operations are hashing of the message and one reduction modulo
q
.
The point multiplication, which is in most cases by the far the most arithmetic-
intensive operation, can be precomputed by choosing the ephemeral key ahead of
time, e.g., during the idle time of a CPU. Thus, in situations where precomputation
is an option, signing becomes a very fast operation.
Verification
Computing the auxiliary parameters
w
,
u
1
and
u
2
involves straightfor-
ward modular arithmetic. The main computational load occurs during the evaluation
of
Pu
1
A
+
u
2
B
. This can be accomplished by two separate point multiplications.
However, there are specialized methods for simultaneous exponentiations (remem-
ber from Chap. 9 that point multiplication is closely related to exponentiation) which
are faster than two individual point multiplications.
10.5.3 Security
Given that the elliptic curve parameters are chosen correctly, the main analytical at-
tack against ECDSA attempts to solve the elliptic curve discrete logarithm problem.
If an attacker were capable of doing this, he could compute the private key
d
and/or
the ephemeral key. However, the best known ECC attacks have a complexity propor-
tional to the square root of the size of the group in which the DL problem is defined,
i.e., proportional to
√
q
. The parameter length of ECDSA and the corresponding
security levels are given in Table 10.3. We recall that the prime
p
is typically only
slightly larger than
q
, so that all arithmetic for ECDSA is done with operands which
have roughly the bit length of
q
.
The security level of the hash function must also match that of the discrete loga-
rithm problem. The cryptographic strength of a hash function is mainly determined
by the length of its output. More about security of hash functions will be said in
Chap. 11.
The security levels of 128, 192 and 256 were chosen so that they match the
security offered by AES with its three respective key sizes.
More subtle attacks against ECDSA are also possible. For instance, at the begin-
ning of verification it must be checked whether
r
,
s
in order to prevent
a certain attack. Also, protocol-based weaknesses, e.g., reusing the ephemeral key,
must be prevented.
∈{
1
,
2
,...,
q
}
