Cryptol.PrimeEC

This module provides fast primitives for elliptic curve cryptography defined on Z p for prime p > 3. These are exposed in cryptol by importing the built-in module PrimeEC. The primary primitives exposed here are the doubling and addition primitives in the ECC group as well as scalar multiplication and the "twin" multiplication primitive, which simultaneously computes the addition of two scalar multiplies.

This module makes heavy use of some GHC internals regarding the representation of the Integer type, and the underlying GMP primitives in order to speed up the basic modular arithmetic operations.

Documentation

data PrimeModulus

Simple newtype wrapping the BigNat value of the modulus of the underlying field Z p. This modulus is required to be prime.

primeModulus :: Integer -> PrimeModulus

Inject an integer value into the PrimeModulus type. This modulus is required to be prime.

data ProjectivePoint

Points in the projective plane represented in homogenous coordinates.

Constructors

ProjectivePoint

Fields

• px :: !BigNat
• py :: !BigNat
• pz :: !BigNat

integerToBigNat :: Integer -> BigNat

Coerce an integer value to a BigNat. This operation only really makes sense for nonnegative values, but this condition is not checked.

bigNatToInteger :: BigNat -> Integer

ec_double :: PrimeModulus -> ProjectivePoint -> ProjectivePoint

Compute the elliptic curve group doubling operation. In other words, if S is a projective point on a curve, this operation computes S+S in the ECC group.

In geometric terms, this operation computes a tangent line to the curve at S and finds the (unique) intersection point of this line with the curve, R; then returns the point R', which is R reflected across the x axis.

ec_add_nonzero :: PrimeModulus -> ProjectivePoint -> ProjectivePoint -> ProjectivePoint

Compute the elliptic curve group addition operation for values known not to be the identity. In other words, if S and T are projective points on a curve, with nonzero z coordinate this operation computes S+T in the ECC group.

In geometric terms, this operation computes a line that passes through S and T, and finds the (unique) other point R where the line intersects the curve; then returns the point R', which is R reflected across the x axis. In the special case where S == T, we instead call the ec_double operation, which instead computes a tangent line to S .

ec_mult :: PrimeModulus -> Integer -> ProjectivePoint -> ProjectivePoint

Given an integer k and a projective point S, compute the scalar multiplication kS, which is S added to itself k times.

ec_twin_mult :: PrimeModulus -> Integer -> ProjectivePoint -> Integer -> ProjectivePoint -> ProjectivePoint

Given an integer j and a projective point S, together with another integer k and point T compute the "twin" scalar the scalar multiplication jS + kT. This computation can be done essentially the same number of modular arithmetic operations as a single scalar multiplication by doing some additional bookkeeping and setup.