Elliptic Curves

8.16

Elliptic Curves🔗ℹ

package: ec

Provides Racket implementations of elliptic curve arithmetic over prime fields in Jacobian coordinates, efficient integer multiplication in the elliptic curve group, affine/Jacobian coordinate conversion, and [SEC1] point serialization.

Provides parameters for several popular cryptographic elliptic curves.

This library should not be used to process information that must be kept secret. No effort has been made to secure this implementation against side-channel attacks.

For common cryptographic operations over elliptic curves, please see the crypto module.

1 Curves🔗ℹ

struct
(struct curve (a b P Gx Gy n bytes))
  a : integer?
  b : integer?
  P : exact-nonnegative-integer?
  Gx : exact-nonnegative-integer?
  Gy : exact-nonnegative-integer?
  n : exact-nonnegative-integer?
  bytes : exact-nonnegative-integer?

Represents the elliptic curve y2 = x3 + ax + b over the prime field ℤ/Pℤ together with a point (Gx, Gy) that generates a cyclic group of order n.

When (de)serializing points in SEC format, assumes each coordinate has length bytes bytes.

struct
(struct jacobian-point (x y z id curve))
  x : exact-nonnegative-integer?
  y : exact-nonnegative-integer?
  z : exact-nonnegative-integer?
  id : boolean?
  curve : curve?

When id is not #f, represents the point at infinity. Otherwise, represents a point on the elliptic curve curve with doubling-oriented XYZ Jacobian coordinates (x, y, z).

struct
(struct affine-point (x y id curve))
  x : exact-nonnegative-integer?
  y : exact-nonnegative-integer?
  id : boolean?
  curve : curve

When id is not #f, represents the point at infinity. Otherwise, represents a point on the elliptic curve curve with affine coordinates (x, y). These coordinates are field elements that satisfy the curve equation y2 = x3 + ax + b if and only if the point is on the curve.

procedure
(affine->jacobian p) → jacobian-point?
p : affine-point?

Changes coordinates of a point from affine to Jacobian. This operation is cheap.

procedure
(jacobian->affine p) → affine-point?
p : jacobian-point?

Changes coordinates of a point from Jacobian to affine. This operation is expensive because it requires finding the inverse of a field element.

procedure
(on-curve? p) → boolean?
p : affine-point?

Checks whether p satisfies the elliptic curve equation y2 = x3 + ax + b for the curve associated with p.

2 Curve Operations🔗ℹ

procedure
(ecdub p) → jacobian-point?
p : jacobian-point?

Doubles an elliptic curve point.

procedure
(ec+ p q) → jacobian-point?
p : jacobian-point?
q : jacobian-point?

Adds two elliptic curve points p and q. If p and q are equal, this function will dispatch to ecdub.

procedure
(dG c d) → jacobian-point?
c : curve?
d : exact-nonnegative-integer?

Multiplies the generator of curve c by d. This is the same as calling dO on (Gx, Gy) and d.

procedure
(dO O d) → jacobian-point?
O : jacobian-point?
d : exact-nonnegative-integer?

Multiplies curve point O by d. The same result could be achieved by repeatedly adding O to itself d times, but dO is much more efficient.

3 SEC Point Representation🔗ℹ

procedure
(point->sec p [#:compressed? compressed?]) → bytes?
p : affine-point?
compressed? : any/c = #t

Serializes point p to its [SEC1] representation. When compressed? is #f, both coordinates are stored. Otherwise, only the x coordinate and the parity of the y coordinate are stored.

procedure
(sec->point c s) → affine-point?
c : curve?
s : bytes?

Deserializes the SEC representation s of a point on curve c.

4 Parameters🔗ℹ

value
secp112r1 : curve?
value
secp112r2 : curve?
value
secp128r1 : curve?
value
secp128r2 : curve?
value
secp160k1 : curve?
value
secp160r1 : curve?
value
secp160r2 : curve?
value
secp192k1 : curve?
value
secp192r1 : curve?
value
secp224k1 : curve?
value
secp224r1 : curve?
value
secp256k1 : curve?
value
secp256r1 : curve?
value
secp384r1 : curve?
value
secp521r1 : curve?

[SEC2] recommended curve parameters.

Bibliography🔗ℹ

[SEC1]		Certicom Research, “SEC 1: Elliptic Curve Cryptography, version 2.0.” 2009. https://www.secg.org/sec1-v2.pdf
[SEC2]		Certicom Research, “SEC 2: Recommended Elliptic Curve Domain Parameters, version 1.0.” 2000. https://www.secg.org/SEC2-Ver-1.0.pdf

1	Curves
2	Curve Operations
3	SEC Point Representation
4	Parameters
	Bibliography