Using the Elliptic Curve Digital Signature Algorithm effectively

Bernhard Linke, Maxim Integrated

February 02, 2014

Bernhard Linke, Maxim IntegratedFebruary 02, 2014

Manufacturers of nearly all equipment types need to protect their products against the counterfeit components that aftermarket companies will attempt to introduce into the OEM supply chain. Secure authentication provides a strong electronic solution to address this threat.

Traditionally, authentication systems have relied on symmetric algorithms such as secure hash algorithms [1] that require secret keys. The management and protection of the secret keys, however, can be challenging. A welcome alternative to this logistics problem is elliptic curve cryptography (ECC), where all participating devices have a pair of keys called “private key” and “public key.”

The private key is used by the originator to sign a message, and the recipient uses the originator’s public key to verify the authenticity of the signature. If a message is modified on its way to the recipient, the signature verification fails because the original signature is not valid for the modified message. The Digital Signature Standard (DSS), issued by the National Institute of Standards and Technology (NIST), specifies suitable elliptic curves, the computation of key pairs, and digital signatures.[2]

This article discusses the Elliptic Curve Digital Signature Algorithm (ECDSA) and shows how the method can be used in practice.

Elliptic curves
Many readers will associate the term “elliptic” with conic sections from distant school days. An ellipsis is a special case of the general second-degree equation ax² + bxy + cy² + dx + ey + f = 0. Depending on the values of the parameters a to f, the resulting graph could as well be a circle, hyperbola, or parabola. Elliptic curve cryptography uses third-degree equations.

The DSS defines two kinds of elliptic curves for use with ECC: pseudo-random curves, whose coefficients are generated from the output of a seeded cryptographic hash function; and special curves, whose coefficients and underlying field have been selected to optimize the efficiency of the elliptic curve operations. Pseudo-random curves can be defined over prime fields GF(p) as well as binary fields GF(2m).

A prime field is the field GF(p), which contains a prime number p of elements. The elements of this field are the integers modulo p; the field arithmetic is implemented in terms of the arithmetic of integers modulo p. The applicable elliptic curve has the form y² = x³ +ax + b. Figure 1 shows an example of an elliptic curve in the real domain and over a prime field modulo 23. A common characteristic is the vertical symmetry.

Figure 1: Third-degree elliptic curves, real domain (left), over prime field (right)

A binary field is the field GF(2m), which contains 2m elements for some m (called the degree of the field). The elements of this field are the bit strings of length m; the field arithmetic is implemented in terms of operations on the bits. The applicable elliptic curve has the form y² + xy = x³ + ax² + b.

Although there is a virtually unlimited number of possible curves that meet the equation, only a small number of curves is relevant for ECC. These curves are referenced as NIST Recommended Elliptic Curves in FIPS publication 186. Each curve is defined by its name and domain parameters set, which consists of the Prime Modulus p, the Prime Order n, the Coefficient a, the Coefficient b, and the x and y coordinates of the Base Point G(x,y) on the curve. Table 1, for example, shows the domain parameters of curve P-192, which is a pseudo-random curve over a prime field. For more examples, see Reference 2. The numeric portion of the curve’s name indicates the length of the private key in bits. The size of public key and the digital signature is twice the length of the private key.

Table 1: Domain parameters of Curve P-192

Mathematical background
Elliptic curve cryptography involves scalars and points. Typically, scalars are represented with lower-case letters, while points are represented as upper-case letters, as in Table 1. Three numerical operations are defined for scalars: addition (+), multiplication (*) and inversion (-1). There are two numerical operations for points: addition (+) and multiplication (×). Although the symbol “+” is used for scalars and points, a point addition follows different rules than the scalar addition. These operations apply to curves over prime fields, as well as curves over binary fields. Algebraic formulae to perform these computations are found in Reference 3.

Computations needed for ECDSA authentication are the generation of a key pair (private key, public key), the computation of a signature, and the verification of a signature. The corresponding equations are found in public literature.[2] [3] [4] Unfortunately, different authors use their own conventions, which makes it difficult to follow their explanations. To bridge this gap, the equations are included here, strictly adhering to the conventions above.

Key pair generation
Before an ECDSA authenticator can function, it needs to know its private key. The public key is derived from the private key and the domain parameters. The key pair must reside in the authenticator’s memory. As the name implies, the private key is not accessible from the outside world. The public key, in contrast, must be openly read accessible. Figure 2 illustrates the generation of the key pair.

Figure 2: Key pair generation process

A random number generator is started and, when its operation is completed, delivers the numeric value that becomes the private key d (a scalar). Next, the public key Q(x,y) is computed according to Equation 1 through point multiplication:

Signature computation
A digital signature allows the recipient of a message to verify the message’s authenticity using the authenticator’s public key. First, the variable-length message is converted to a fixed-length message digest h(m) using a secure hash algorithm.[1] A secure hash has the following distinctive properties:
  • irreversibility—it is computationally infeasible to determine the message from its digest;
  • collision resistance—it is impractical to find more than one message that produces a given digest; and
  • high avalanche effect—any change in the message produces a significant change in the digest. After the message digest is computed, a random number generator is activated to provide a value k for the elliptic curve computations. Figure 3 illustrates the process.

Figure 3: Signature computation process

The signature consists of two integer numbers, r and s. Equation 2 shows the computation of r from the random number k and the base point G(x,y):

To be valid, r must be different from zero. In the rare case when r is 0, a new random number, k, must be generated and r needs to be computed again.

After r is successfully computed, s is computed according to Equation 3 using scalar operations. Inputs are the message digest h(m); the private key d; r; and the random number k:

To be valid, s must be different from zero. If s is 0, a new random number k must be generated and both r and s need to be computed again.

< Previous
Page 1 of 2
Next >

Loading comments...