curve1174

package module
v0.2.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jan 3, 2022 License: MIT Imports: 10 Imported by: 0

README

curve1174

curve1174 is a Go library implementing operations on Curve1174. It's Edwards curve with equation

x^2+y^2 = 1-1174x^2y^2

over finite field Fp, p=2^251-9. It was introduced by Bernstein, Hamburg, Krasnova, and Lange in 2013

Build Go Report Card

Installation

curve1174 is compatible with modern Go releases in module mode, with Go installed:

go get github.com/probakowski/curve1174

will resolve and add the package to the current development module, along with its dependencies.

Alternatively the same can be achieved if you use import in a package:

import "github.com/probakowski/curve1174"

and run go get without parameters.

Finally, to use the top-of-trunk version of this repo, use the following command:

go get github.com/probakowski/curve1174@master

Usage

Each point on curve is represented by curve1174.Point object. Base point is provided in curve1174.Base, identity element of the curve (x=0, y=1) is curve1174.E.

API is similar to math/big package. The receiver denotes result and the method arguments are operation's operands. For instance, given three *Point values a,b and c, the invocation

c.Add(a,b)

computes the sum a + b and stores the result in c, overwriting whatever value was held in c before. Operations permit aliasing of parameters, so it is perfectly ok to write

sum.Add(sum, x)

to accumulate values x in a sum.

(By always passing in a result value via the receiver, memory use can be much better controlled. Instead of having to allocate new memory for each result, an operation can reuse the space allocated for the result value, and overwrite that value with the new result in the process.)

Methods usually return the incoming receiver as well, to enable simple call chaining.

Operations on curve return point in extended coordinates. To get simple x/y value they have to be converted to affine coordinates with (*Point).ToAffine method. This call is expensive so be sure to avoid it for intermediate values if possible.

All operations (both in the underlying field and on the curve) are designed to be constant time (time doesn't depend on points/elements selected).

On amd64 there's specialized assembler code to speed up operations, you can disable it with tag curve1174_purego. The code is generated in from gen/asm.go using avo.

Base point multiplication on the curve uses precomputed table that greatly speeds up computation in common cases (like generating public key). It costs ~131kB of heap, you can disable it with tag curve1174_no_precompute. If you can spend more heap you can use tag curve1174_precompute_big which is even faster but eats up 1MB of heap.

Finally, *Point and *FieldElement satisfy fmt package's Formatter interface for formatted printing.

Documentation

Overview

Package curve1174 implements operations on Curve1174. It's Edwards curve with equation `x^2+y^2 = 1-1174x^2y^2` over finite field `Fp, p=2^251-9`. It was introduced by Bernstein, Hamburg, Krasnova, and Lange(https://eprint.iacr.org/2013/325) in 2013.

Each point on curve is represented by `curve1174.Point` object. Base point is provided in `curve1174.Base`, identity element of the curve (`x=0, y=1`) is `curve1174.E`.

API is similar to `math/big` package. The receiver denotes result and the method arguments are operation's operands. For instance, given three `*Point` values a,b and c, the invocation 

c.Add(a,b)

computes the sum a + b and stores the result in c, overwriting whatever value was held in c before. Operations permit aliasing of parameters, so it is perfectly ok to write 

sum.Add(sum, x)

to accumulate values x in a sum.

(By always passing in a result value via the receiver, memory use can be much better controlled. Instead of having to allocate new memory for each result, an operation can reuse the space allocated for the result value, and overwrite that value with the new result in the process.)

Methods usually return the incoming receiver as well, to enable simple call chaining.

Operations on curve return point in extended coordinates. To get simple x/y value they have to be converted to affine coordinates with `(*Point).ToAffine` method. This call is expensive so be sure to avoid it for intermediate values if possible.

All operations (both in the underlying field and on the curve) are designed to be constant time (time doesn't depend on points/elements selected).

On amd64 there's specialized assembler code to speed up operations, you can disable it with tag `curve1174_purego`. The code is generated in from `gen/asm.go` using `avo`(https://github.com/mmcloughlin/avo).

Base point multiplication on the curve uses precomputed table that greatly speeds up computation in common cases (like generating public key). It costs ~131kB of heap, you can disable it with tag `curve1174_no_precompute`. If you can spend more heap you can use tag `curve1174_precompute_big` which is even faster but eats up 1MB of heap.

Finally, `*Point` and `*FieldElement` satisfy fmt package's Formatter interface for formatted printing.

Index

Constants

View Source 
const P0 uint64 = 0xfffffffffffffff7

P0 is 1st (lowest) digit (base 2^64) of P=2^251-9

View Source 
const P1 uint64 = 0xffffffffffffffff

P1 is 2nd digit (base 2^64) of P=2^251-9

View Source 
const P2 uint64 = 0xffffffffffffffff

P2 is 3rd digit (base 2^64) of P=2^251-9

View Source 
const P3 uint64 = 0x07ffffffffffffff

P3 is 4th (highest) digit (base 2^64) of P=2^251-9

Variables

View Source 
var Base = &Point{
	X: FieldElement{0x16123f27bce29eda, 0xc021d96a492ecd65, 0x9343aee7c029a190, 0x37fbb0cea308c47},
	Y: FieldElement{0xa4ccb1bf9b46360e, 0x4fe2dee2af3f976b, 0x6656841169840e0c, 0x6b72f82d47fb7cc},
	Z: *UOne,
	T: FieldElement{0xfb1ebfece06620ec, 0x9c6c6daf574e84cb, 0x5083299c2d40b958, 0x18b74129cf1e5d9},
}

Base is base point of curve in affine coordinates (Base.Z == 1)

View Source 
var E = &Point{
	X: UZero,
	Y: *UOne,
	Z: *UOne,
	T: UZero,
}

E is identity element of curve's group (x:0, y:1)

View Source 
var P, _ = new(big.Int).SetString("7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7", 16)

P is order of F_p, 2^251-9

View Source 
var UOne = &FieldElement{1}

UOne represents 1

View Source 
var UP = &FieldElement{P0, P1, P2, P3}

UP represents 2^251-9

Functions

This section is empty.

Types

type FieldElement 

type FieldElement [4]uint64

FieldElement is element of finite field F_p, p=2^251-9 

var UZero FieldElement

UZero represents 0

func FromBigInt 

func FromBigInt(b1 *big.Int) *FieldElement

FromBigInt returns field element with the same value as provided big.Int

func (*FieldElement) Add 

func (out *FieldElement) Add(p, p2 *FieldElement) *FieldElement

Add adds two field elements mod 2^251-9. Execution time doesn't depend on values

func (*FieldElement) Cmp 

func (out *FieldElement) Cmp(p2 *FieldElement) int

Cmp compares 2 field elements. Can be used for sorting

func (*FieldElement) Equals 

func (out *FieldElement) Equals(p2 *FieldElement) bool

Equals checks if 2 field elements has the same value

func (*FieldElement) Format 

func (out *FieldElement) Format(s fmt.State, c rune)

Format to implement fmt.Formatter interface

func (*FieldElement) Inverse 

func (out *FieldElement) Inverse(p2 *FieldElement) *FieldElement

Inverse sets out to be inverse of p2 mod 2^251-9 (out * p2 == 1 | 2^251-9). It uses Euler's theorem and computes inverse by raising p2 to power 2^251-11 (m=2^251-9 is prime, a^-1 == a^(m-2) | m). Execution time doesn't depend on value

func (*FieldElement) IsOne 

func (out *FieldElement) IsOne() bool

IsOne checks if out==1

func (*FieldElement) IsZero 

func (out *FieldElement) IsZero() bool

IsZero checks if out==0

func (*FieldElement) Mod 

func (out *FieldElement) Mod(p *FieldElement) *FieldElement

Mod returns number mod 2^251-9. Execution time doesn't depend on values

func (*FieldElement) Mul 

func (out *FieldElement) Mul(p, p2 *FieldElement) *FieldElement

Mul multiplies two field elements mod 2^251-9. Execution time doesn't depend on values

func (*FieldElement) Mul2 

func (out *FieldElement) Mul2(p *FieldElement) *FieldElement

Mul2 multiplies field element by 2 mod 2^251-9. Execution time doesn't depend on values

func (*FieldElement) MulD 

func (out *FieldElement) MulD(p *FieldElement) *FieldElement

MulD multiplies field element by 1174 mod 2^251-9. Execution time doesn't depend on values

func (*FieldElement) Set 

func (out *FieldElement) Set(p2 *FieldElement) *FieldElement

Set sets one field element to be equal to the other. Execution time doesn't depend on values

func (*FieldElement) SetBigInt 

func (out *FieldElement) SetBigInt(b1 *big.Int) *FieldElement

SetBigInt sets field elements to value from *big.Int.

func (*FieldElement) Sqr 

func (out *FieldElement) Sqr(p *FieldElement) *FieldElement

Sqr squares field element mod 2^251-9. Execution time doesn't depend on values

func (*FieldElement) String 

func (out *FieldElement) String() string

func (*FieldElement) Sub 

func (out *FieldElement) Sub(p, p2 *FieldElement) *FieldElement

Sub subtracts two field elements mod 2^251-9. Execution time doesn't depend on values

func (*FieldElement) ToBigInt 

func (out *FieldElement) ToBigInt() *big.Int

ToBigInt returns element value as *big.Int

type Point 

type Point struct {
	X FieldElement
	Y FieldElement
	Z FieldElement
	T FieldElement
}

Point represents point on curve. It supports projective and extended coordinates

func (*Point) Add 

func (p *Point) Add(p1,
	p2 *Point) *Point

Add adds any two points on curve and store results in p. Formula based on https://www.hyperelliptic.org/EFD/g1p/auto-twisted-extended.html#addition-add-2008-hwcd

func (*Point) AddZ1 

func (p *Point) AddZ1(p1,
	p2 *Point) *Point

AddZ1 adds two points on curve and store results in p. p2 has to be in affine coordinates (p2.Z == 1) Formula based on https://www.hyperelliptic.org/EFD/g1p/auto-twisted-extended.html#addition-madd-2008-hwcd

func (*Point) Double 

func (p *Point) Double(dp *Point) *Point

Double doubles point on curve and store result in p (p = dp+dp) Formula based on https://www.hyperelliptic.org/EFD/g1p/auto-twisted-extended.html#doubling-dbl-2008-hwcd

func (*Point) DoubleZ1 

func (p *Point) DoubleZ1(dp *Point) *Point

DoubleZ1 doubles point on curve and store result in p (p = dp+dp). dp has to be in affine coordinates (dp.Z == 1) Formula based on https://www.hyperelliptic.org/EFD/g1p/auto-twisted-extended.html#doubling-mdbl-2008-hwcd

func (*Point) Equals 

func (p *Point) Equals(p2 *Point) bool

Equals checks if two points have exactly the same representation (all components must be equal)

func (*Point) Format 

func (p *Point) Format(s fmt.State, c rune)

Format to implement fmt.Formatter interface

func (*Point) ScalarBaseMult 

func (p *Point) ScalarBaseMult(b *FieldElement) *Point

ScalarBaseMult multiplies base point Base by scalar b (b<2^251-9) and stores result in p. Execution time doesn't depend on b.

func (*Point) ScalarMult 

func (p *Point) ScalarMult(sp *Point,
	b *FieldElement) *Point

ScalarMult multiplies point on curve sp by scalar b (b<2^251-9) and stores result in p. Execution time doesn't depend on b.

func (*Point) Set 

func (p *Point) Set(p2 *Point) *Point

Set p to be exactly the same as p2

func (*Point) String 

func (p *Point) String() string

func (*Point) ToAffine 

func (p *Point) ToAffine(pp *Point) *Point

ToAffine transforms point pp to affine coordinates and store result in p (p.Z==1)

Source Files

View all Source files

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.