Elliptic Curves
1 Curves
curve
jacobian-point
affine-point
affine->jacobian
jacobian->affine
on-curve?
2 Curve Operations
ecdub
ec+
d  G
d  O
3 SEC Point Representation
point->sec
sec->point
4 Parameters
secp112r1
secp112r2
secp128r1
secp128r2
secp160k1
secp160r1
secp160r2
secp192k1
secp192r1
secp224k1
secp224r1
secp256k1
secp256r1
secp384r1
secp521r1
Bibliography
7.8

Elliptic Curves

Marc Burns <marc@kn0x.io>

 (require ec) 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