Crypto.ECC.Edwards25519

Arithmetic primitives over curve edwards25519.

Twisted Edwards curves are a familly of elliptic curves allowing complete addition formulas without any special case and no point at infinity. Curve edwards25519 is based on prime 2^255 - 19 for efficient implementation. Equation and parameters are given in RFC 7748.

This module provides types and primitive operations that are useful to implement cryptographic schemes based on curve edwards25519:

• arithmetic functions for point addition, doubling, negation, scalar multiplication with an arbitrary point, with the base point, etc.
• arithmetic functions dealing with scalars modulo the prime order L of the base point

All functions run in constant time unless noted otherwise.

Warnings:

1. Curve edwards25519 has a cofactor h = 8 so the base point does not generate the entire curve and points with order 2, 4, 8 exist. When implementing cryptographic algorithms, special care must be taken using one of the following methods:

   • points must be checked for membership in the prime-order subgroup
   • or cofactor must be cleared by multiplying points by 8

   Utility functions are provided to implement this. Testing subgroup membership with pointHasPrimeOrder is 50-time slower than call pointMulByCofactor.

2. Scalar arithmetic is always reduced modulo L, allowing fixed length and constant execution time, but this reduction is valid only when points are in the prime-order subgroup.
3. Because of modular reduction in this implementation it is not possible to multiply points directly by scalars like 8.s or L. This has to be decomposed into several steps.

Documentation

data Scalar

A scalar modulo prime order of curve edwards25519.

Instances

Eq Scalar

Methods

(==) :: Scalar -> Scalar -> Bool

(/=) :: Scalar -> Scalar -> Bool

Show Scalar

Methods

showsPrec :: Int -> Scalar -> ShowS

show :: Scalar -> String

showList :: [Scalar] -> ShowS

NFData Scalar

Methods

rnf :: Scalar -> ()

data Point

A point on curve edwards25519.

Instances

Eq Point

Methods

(==) :: Point -> Point -> Bool

(/=) :: Point -> Point -> Bool

Show Point

Methods

showsPrec :: Int -> Point -> ShowS

show :: Point -> String

showList :: [Point] -> ShowS

NFData Point

Methods

rnf :: Point -> ()

Scalars

scalarGenerate :: MonadRandom randomly => randomly Scalar

Generate a random scalar.

scalarDecodeLong :: ByteArrayAccess bs => bs -> CryptoFailable Scalar

Deserialize a little-endian number as a scalar. Input array can have any length from 0 to 64 bytes.

Note: it is not advised to put secret information in the 3 lowest bits of a scalar if this scalar may be multiplied to untrusted points outside the prime-order subgroup.

scalarEncode :: ByteArray bs => Scalar -> bs

Serialize a scalar to binary, i.e. a 32-byte little-endian number.

Points

pointDecode :: ByteArrayAccess bs => bs -> CryptoFailable Point

Deserialize a 32-byte array as a point, ensuring the point is valid on edwards25519.

WARNING: variable time

pointEncode :: ByteArray bs => Point -> bs

Serialize a point to a 32-byte array.

Format is binary compatible with PublicKey from module Crypto.PubKey.Ed25519.

pointHasPrimeOrder :: Point -> Bool

Test whether a point belongs to the prime-order subgroup generated by the base point. Result is True for the identity point.

pointHasPrimeOrder p = pointNegate p == pointMul l_minus_one p

Arithmetic functions

toPoint :: Scalar -> Point

Multiplies a scalar with the curve base point.

scalarAdd :: Scalar -> Scalar -> Scalar

Add two scalars.

scalarMul :: Scalar -> Scalar -> Scalar

Multiply two scalars.

pointNegate :: Point -> Point

Negate a point.

pointAdd :: Point -> Point -> Point

Add two points.

pointDouble :: Point -> Point

Add a point to itself.

pointDouble p = pointAdd p p

pointMul :: Scalar -> Point -> Point

Scalar multiplication over curve edwards25519.

Note: when the scalar had reduction modulo L and the input point has a torsion component, the output point may not be in the expected subgroup.

pointMulByCofactor :: Point -> Point

Multiply a point by h = 8.

pointMulByCofactor p = pointMul scalar_8 p

pointsMulVarTime :: Scalar -> Scalar -> Point -> Point

Multiply the point p with s2 and add a lifted to curve value s1.

pointsMulVarTime s1 s2 p = pointAdd (toPoint s1) (pointMul s2 p)

WARNING: variable time