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.

ECDSA domain parameters#

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.
ECDSA signature parameters#

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.

Elliptic curves for ECDSA#

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.

Hash function and XOFs for ECDSA#

Family

Parameter size (in bits)

Source

SHA-2

224, 256, 384, 512, 256 (SHA-512/224), 256 (SHA-512/256)

FIPS 180-4

SHA-3

256, 384, 512

FIPS 202

XOF

SHAKE128, SHAKE256

FIPS 202

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.

    1. 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

  1. It is recommended to use subgroups whose order is prime (instead of being a multiple of a prime number).

Discrete logarithm for elliptic curves defined over GF(\(2^n\))#

RègleEc2

  1. The order of the subgroup must be a multiple of a prime number that is at least 250 bits long.

  2. The parameter \(n\) must be a prime number.

  3. 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

  1. It is recommended to use subgroups whose order is prime (instead of being the multiple of a prime).

  • Compliant curves

Hash functions#

RègleHash

  1. The minimal size of the resulting digest is 256 bits.

  2. The best known attack allowing to find collisions requires at least \(2^{h/2}\) digests.

RecommandationHash

  1. The use of hash function for whom “partial attacks” are known is discouraged.

  • Compliant hash functions

  • 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

  1. 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

  1. The same asymmetric key pair may not be used for more than one purpose.

  2. Hierarchically important keys, such as root keys, must be generated and used by compliant mechanisms.