NIST Recommended Elliptic Curve Functions#

Elliptic Curve Notation#

There are several kinds of defining equation for elliptic curves, but this section deals with Weierstrass equations. For the prime finite field GF(p), p>3, the Weierstrass equation is E : y²= x³+ a*x + b, where a and b are integers modulo p. Number of points on the elliptic curve E is denoted by #E.

For purpose of cryptography some additional parameters are presented:

n - prime divisor of #E and the order of point G
G - the point on curve E generated subgroup of the order n

The set of p, a, b, n and G parameters are Elliptic Curve (EC) domain parameter. This section deals with three NIST recommended Elliptic Curves those domain parameters are known and published in [SEC2] (Standards for Efficient Cryptography Group, “Recommended Elliptic Curve Domain Parameters”, SEC 2, September 2000).

Elliptic Curve Key Pair#

Private key is a positive integer u in the range [1, n-1]. Public key V, which is the point on elliptic curve E, where V = [u]*G. In cryptography, there are two types of key pairs: regular (or longterm) and ephemeral (or nonce - number that can only be used once). From the math point of view, they are similar.

ECDSA signature generation#

Input:

The EC domain parameters p, a, b, n and G
The signer’s regular u and ephemeral k private keys
The message representative, which is an integer f>=0

Output: The signature, which is a pair of integers (r, s), where r and s belongs the range [1. r-1].

Operation:

Compute an ephemeral public key K = [k]G. Let K = (x, y)
Compute an integer r = x mod n
Compute an integer s = (k^-1)*(f + u*r) mod n
Return (r, s) as signature

ECDHE generation of shared secret#