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
2
= x
3
+ 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#Eand the order of pointG
- G- the point on curveEgenerated 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 parametersp, a, b, nandG
- The signer's regularuand ephemeralkprivate keys
- The message representative, which is an integerf>=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 keyK = [k]G. Let K = (x, y)
- Compute an integerr = x mod n
- Compute an integers = (k-1)*(f + u*r) mod n
- Return(r, s)as signature
ECDHE generation of shared secret
Input:
- The EC domain parametersp, a, b, nandG
- The own ephemeral private keyu
- The party's ephemeral public keyW
Output: The derived shared secret value
z
, which is the GF(p)
field element
Operation:
- Compute an EC pointP = [u]W, P=(xp, yp)
- Letz = xp
- Return shared secretz