License | BSD-style |
---|---|

Maintainer | Olivier Chéron <olivier.cheron@gmail.com> |

Stability | experimental |

Portability | unknown |

Safe Haskell | None |

Language | Haskell2010 |

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:

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`

.- 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.
- 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.

## Synopsis

- data Scalar
- data Point
- scalarGenerate :: MonadRandom randomly => randomly Scalar
- scalarDecodeLong :: ByteArrayAccess bs => bs -> CryptoFailable Scalar
- scalarEncode :: ByteArray bs => Scalar -> bs
- pointDecode :: ByteArrayAccess bs => bs -> CryptoFailable Point
- pointEncode :: ByteArray bs => Point -> bs
- pointHasPrimeOrder :: Point -> Bool
- toPoint :: Scalar -> Point
- scalarAdd :: Scalar -> Scalar -> Scalar
- scalarMul :: Scalar -> Scalar -> Scalar
- pointNegate :: Point -> Point
- pointAdd :: Point -> Point -> Point
- pointDouble :: Point -> Point
- pointMul :: Scalar -> Point -> Point
- pointMulByCofactor :: Point -> Point
- pointsMulVarTime :: Scalar -> Scalar -> Point -> Point

# Documentation

A scalar modulo prime order of curve edwards25519.

A point on curve edwards25519.

# 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

pointNegate :: Point -> Point #

Negate a point.

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