ECDSA#
The Elliptic Curve Digital Signature Algorithm is a digital signature standard described in FIPS 186. It is a variant of the Digital Signature Algorithm (DSA) based on elliptic-curve cryptography.
Deterministic ECDSA is a variant of this algorithm that does not require the generation of a secret number, thus may be useful for devices without access to a good random number generator such as embedded devices. The verification of signatures produced with this variant remains the same.
According to FIPS 186, “ECDSA and deterministic ECDSA require that the private/public key pairs used for digital signature generation and verification be generated with respect to a particular set of domain parameters. These domain parameters may be common to a group of users and may be public”. They are described in SP 800-186 and summarized below.
Parameter |
Description |
---|---|
The elliptic curve field |
Defined by its size \(q = p^k\), where \(p\) is prime. ECDSA is defined for the finite field GF(\(p\)) and the finite field GC(\(2^m\)). |
The equation of the curve |
Defined by two field elements called \(a\) and \(b\). |
\(G\) |
A base point of (large) prime order on the curve. |
\(n\) |
The order of the point \(G\). |
\(h\) |
The cofactor of \(G\) (equal to the order of the curve divided by \(n\)). |
Type |
The elliptic curve model used. |
Parameter |
Description |
---|---|
\(d\) |
The private key, a integer randomly generated in the interval \([1, n-1]\). |
\(Q\) |
The public key, equal to \(d \times G\). |
\(r\) and \(s\) |
An ECDSA signature is represented by two integers \(0 < r < n\) and \(0 < s < n\). |
Here is a list of elliptic curves approved for use in ECDSA by either the ANSSI or the NIST.
Curve |
ANSSI |
NIST |
---|---|---|
P-224 |
No |
Yes |
P-256 |
Yes |
Yes |
P-384 |
Yes |
Yes |
P-521 |
Yes |
Yes |
B-283 |
Yes |
No |
B-409 |
Yes |
No |
B-571 |
Yes |
No |
FRP256v1 |
Yes |
No |
Some key points to keep in mind regarding this algorithm:
As in public key cryptography in general, the private key must remain secret.
NIST indicates that “Care must be taken to protect implementations against attacks, such as side-channel attacks or fault attacks” (FIPS 186).
“(Deterministic) ECDSA keys shall only be used for the generation and verification of (deterministic) ECDSA digital signatures” (FIPS 186).
It is important to verify the correctness of the group arithmetic computations:
Check that the points used and the results belong to the curve.
Particularly for deterministic signature schemes or embedded devices.
Measures to prevent small subgroup attacks [TODO: expand].
The comparable security strength[1] is \(\text{len}(n)/2\) where \(\text{len}(n)\) is the bit length of \(n\).
The security strength of the hash function must be at least the same as the security strength associated with the bit length of \(n\).
The same domain parameters may be used for more than one purpose, however using different domain parameters reduces the risk of using key pairs for more than one purpose.
ECDSA requires the generation of a random per-message secret number, while deterministic ECDSA derives it from the key and the message. This number must remain secret and its generation must be unbiased. Section 7.3 of ANSSI’s Guide de sélection d’algorithmes cryptographiques describes its recommended methods of generating random numbers.
An approved hash function or XOF (SHAKE128 or SHAKE256) and approved random bit generator shall be used when generating signatures.
Family |
Parameter size (in bits) |
Source |
---|---|---|
SHA-2 |
224, 256, 384, 512, 256 (SHA-512/224), 256 (SHA-512/256) |
|
SHA-3 |
256, 384, 512 |
|
XOF |
SHAKE128, SHAKE256 |
ANSSI rules and recommendations#
Discrete logarithm for elliptic curves defined over GF(\(p\))#
RègleECp
Use subgroups whose order is a multiple of a prime number that is at least 250 bits long.
When using curves whose security relies of a mathematical problem that is easier than the generic elliptic curve discrete logarithm problem for elliptic curves defined over \(GF(p)\), the problem must verify the corresponding rules.
RecommandationECp
It is recommended to use subgroups whose order is prime (instead of being a multiple of a prime number).
Compliant curves
FRP256v1 (JORF0241-16.10.2011), P-256, P-384, P-521 (FIPS 186), brainpoolP256r1, brainpoolP384r1, or brainpoolP512r1 (RFC 5639).
Discrete logarithm for elliptic curves defined over GF(\(2^n\))#
RègleEc2
The order of the subgroup must be a multiple of a prime number that is at least 250 bits long.
The parameter \(n\) must be a prime number.
When using curves whose security relies of a mathematical problem that is easier than the generic elliptic curve discrete logarithm problem for elliptic curves defined over \(GF(2^n)\), the problem must verify the corresponding rules.
RecommandationEC2
It is recommended to use subgroups whose order is prime (instead of being the multiple of a prime).
Compliant curves
B-283, B-409, and B-571 (FIPS 186).
Hash functions#
RègleHash
The minimal size of the resulting digest is 256 bits.
The best known attack allowing to find collisions requires at least \(2^{h/2}\) digests.
RecommandationHash
The use of hash function for whom “partial attacks” are known is discouraged.
Compliant hash functions
SHA-256 (FIPS 180-4) is compliant.
Non-compliant hash functions
SHA-1 is not compliant:
It produces a 160-bit output, so it doesn’t follow RègleHash-1.
It is vulnerable to a collision attack with complexity \(2^{63} < 2^{80}\), so it doesn’t follow RègleHash-2.
Asymmetric signature#
RecommandationSignAsym
It is recommended to use an asymmetric signature mechanism that has a security proof.
Compliant signature mechanisms
ECDSA is compliant when using curves FRP256v1, P-256, P-384, P-521, B-283, B-409, and B-571.
Asymmetric keypairs#
RègleGestAsym
The same asymmetric key pair may not be used for more than one purpose.
Hierarchically important keys, such as root keys, must be generated and used by compliant mechanisms.