ristretto

package module
v1.2.3 Latest Latest
Warning

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

 Go to latest Published: Mar 16, 2023 License: MIT Imports: 11 Imported by: 80

README

go-ristretto

Many cryptographic schemes need a group of prime order. Popular and efficient elliptic curves like (Edwards25519 of ed25519 fame) are rarely of prime order. There is, however, a convenient method to construct a prime order group from such curves, called Ristretto proposed by Mike Hamburg.

This is a pure Go implementation of the group operations on the Ristretto prime-order group built from Edwards25519. Documentation is on godoc.

Example: El'Gamal encryption

// Generate an El'Gamal keypair
var secretKey ristretto.Scalar
var publicKey ristretto.Point

secretKey.Rand() // generate a new secret key
publicKey.ScalarMultBase(&secretKey) // compute public key

// El'Gamal encrypt a random curve point p into a ciphertext-pair (c1,c2)
var p ristretto.Point
var r ristretto.Scalar
var c1 ristretto.Point
var c2 ristretto.Point
p.Rand()
r.Rand()
c2.ScalarMultBase(&r)
c1.PublicScalarMult(&publicKey, &r)
c1.Add(&c1, &p)

// Decrypt (c1,c2) back to p
var blinding, p2 ristretto.Point
blinding.ScalarMult(&c2, &secretKey)
p2.Sub(&c1, &blinding)

fmt.Printf("%v", bytes.Equal(p.Bytes(), p2.Bytes()))
// Output:
// true

Compatibility with ristretto255 RFC draft

An RFC has been proposed to standardise Ristretto over Ed25519. This RFC is compatible with go-ristretto. There is one caveat: one should use Point.DeriveDalek instead of Point.Derive to derive a point from a string.

References

The curve and Ristretto implementation is based on the unpublished PandA library by Chuengsatiansup, Ribarski and Schwabe, see cref/cref.c. The old generic radix 25.5 field operations borrow from Adam Langley's ed25519. The amd64 optimized field arithmetic are from George Tankersley's ed25519 patch, which in turn is based on SUPERCOP's amd64-51-30k by Bernstein, Duif, Lange, Schwabe and Yang. The new generic radix 51 field operations are also based on amd64-51-30k. The variable-time scalar multiplication code is based on that of curve25519-dalek. The Lizard encoding was proposed by Bram Westerbaan. The quick RistrettoElligator inversion for it is joint work with Bram Westerbaan and Mike Hamburg.

other platforms

Changes

1.2.3 (16-03-2023)
  • Panic when reading randomness fails.
1.2.2 (29-07-2022)
  • Add Point.ConditionalSet() and Scalar.ConditionalSet().
1.2.1 (08-11-2021)
  • Add Scalar.SetUint64().
1.2.0 (17-02-2021)
  • Add Point.Double(). See issue #21.
  • To align more closely with the RFC, Point.SetBytes() and Point.UnmarshalBinary() will now reject points with non-canonical encodings. See #20.
1.1.1 (24-09-2019)
  • Only use bits.Add64 from Go 1.13 onwards to make sure we're constant-time on non-amd64 platforms. Thanks @Yawning; see issue #17.
1.1.0 (13-05-2019)

  • Add support for the Lizard 16-bytes-to-point-injection. See ristretto.Point.{SetLizard(), Lizard(),LizardInto()}.

  • Add Scalar.DeriveShort() to derive a half-length scalar. (Warning: half-length scalars are unsafe in almost every application.)

  • (internal) Add ExtendedPoint.RistrettoElligator2Inverse() to compute all preimages of a given point up-to Ristretto equivalence of CompletedPoint.SetRistrettoElligator2().

Documentation

Overview

Pure Go implementation of the Ristretto prime-order group built from the Edwards curve Edwards25519.

Many cryptographic schemes need a group of prime order. Popular and efficient elliptic curves like (Edwards25519 of `ed25519` fame) are rarely of prime order. There is, however, a convenient method to construct a prime order group from such curves, using a method called Ristretto proposed by Mike Hamburg.

This package implements the Ristretto group constructed from Edwards25519. The Point type represents a group element. The API mimics that of the math/big package. For instance, to set c to a+b, one writes 

var c ristretto.Point
c.Add(&a, &b) // sets c to a + b

Warning: contrary to math.Big's interface, an uninitialized Point is not the same thing as the zero (neutral element) of the group: 

var c ristretto.Point // c is uninitialized now --- not zero!
c.SetZero() // c is zero now; ready to use!

Most methods return the receiver, so that function can be chained: 

s.Add(&a, &b).Add(&s, &c)  // sets s to a + b + c

The order of the Ristretto group is l = 2^252 + 27742317777372353535851937790883648493 = 7237005577332262213973186563042994240857116359379907606001950938285454250989. The Scalar type implement the numbers modulo l and also has an API similar to math/big.

Example 
// Generate an El'Gamal keypair
var secretKey ristretto.Scalar
var publicKey ristretto.Point

secretKey.Rand()                     // generate a new secret key
publicKey.ScalarMultBase(&secretKey) // compute public key

// El'Gamal encrypt a random curve point p into a ciphertext-pair (c1,c2)
var p ristretto.Point
var r ristretto.Scalar
var c1 ristretto.Point
var c2 ristretto.Point
p.Rand()
r.Rand()
c2.ScalarMultBase(&r)
c1.PublicScalarMult(&publicKey, &r)
c1.Add(&c1, &p)

// Decrypt (c1,c2) back to p
var blinding, p2 ristretto.Point
blinding.ScalarMult(&c2, &secretKey)
p2.Sub(&c1, &blinding)

fmt.Printf("%v", bytes.Equal(p.Bytes(), p2.Bytes()))

Output:

true

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Point 

type Point edwards25519.ExtendedPoint

Represents an element of the Ristretto group over Edwards25519.

Warning: an uninitialized Point is not the same thing as a zero. Use the SetZero() method to set an (uninitialized) Point to zero.

func (*Point) Add 

func (p *Point) Add(q, r *Point) *Point

Sets p to q + r. Returns p.

func (*Point) Bytes 

func (p *Point) Bytes() []byte

Returns a packed version of p.

func (*Point) BytesInto 

func (p *Point) BytesInto(buf *[32]byte) *Point

Packs p into the given buffer. Returns p.

func (*Point) ConditionalSet added in v1.2.2 

func (p *Point) ConditionalSet(q *Point, b int32)

Set p to q if b=1 in constant-time. b must be either 0 or 1.

func (*Point) Derive 

func (p *Point) Derive(buf []byte) *Point

Sets p to the point derived from the buffer using SHA512 and Elligator2. Returns p.

NOTE curve25519-dalek uses a different (more conservative) method to derive a point from raw data with a hash. This is implemented in Point.DeriveDalek().

func (*Point) DeriveDalek 

func (p *Point) DeriveDalek(data []byte) *Point

Sets p to the point derived from the buffer using SHA512 and Elligator2 in the fashion of curve25519-dalek.

NOTE See also Derive(), which is a different method which is twice as fast, but which might not be as secure as this method.

func (*Point) Double added in v1.2.0 

func (p *Point) Double(q *Point) *Point

Sets p to q + q. Returns p.

func (*Point) Equals 

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

Returns whether p == q

func (*Point) EqualsI 

func (p *Point) EqualsI(q *Point) int32

Returns 1 if p == q and 0 otherwise.

func (*Point) Lizard added in v1.1.0 

func (p *Point) Lizard() []byte

Decodes 16 bytes encoded into this point using SetLizard().

Returns nil if this point does not contain data encoded using Lizard.

See SetLizard() for notes on usage.

func (*Point) LizardInto added in v1.1.0 

func (p *Point) LizardInto(buf *[16]byte) error

Decodes 16 bytes into the given buffer encoded into this point using SetLizard().

See SetLizard() for notes on usage.

func (*Point) MarshalBinary 

func (p *Point) MarshalBinary() ([]byte, error)

Implements encoding/BinaryMarshaler. Use BytesInto, if convenient, instead.

func (*Point) MarshalText 

func (p *Point) MarshalText() ([]byte, error)

func (*Point) Neg 

func (p *Point) Neg(q *Point) *Point

Sets p to -q. Returns p.

func (*Point) PublicScalarMult 

func (p *Point) PublicScalarMult(q *Point, s *Scalar) *Point

Sets p to s * q assuming s is *not* secret. Returns p.

Warning: this method uses a non-constant time implementation and thus leaks information about s. Use this function only if s is public knowledge.

func (*Point) PublicScalarMultBase 

func (p *Point) PublicScalarMultBase(s *Scalar) *Point

Sets p to s * B, where B is the edwards25519 basepoint. Returns p.

Warning: this method uses a non-constant time implementation and thus leaks information about s. Use this function only if s is public knowledge.

func (*Point) PublicScalarMultTable 

func (p *Point) PublicScalarMultTable(t *ScalarMultTable, s *Scalar) *Point

Sets p to s * q, where q is the point for which the table t was computed. Returns p.

Warning: this method uses a non-constant time implementation and thus leaks information about s. Use this function only if s is public knowledge.

func (*Point) Rand 

func (p *Point) Rand() *Point

Sets p to a random point. Returns p.

func (*Point) ScalarMult 

func (p *Point) ScalarMult(q *Point, s *Scalar) *Point

Sets p to s * q. Returns p.

func (*Point) ScalarMultBase 

func (p *Point) ScalarMultBase(s *Scalar) *Point

Sets p to s * B, where B is the edwards25519 basepoint. Returns p.

func (*Point) ScalarMultTable 

func (p *Point) ScalarMultTable(t *ScalarMultTable, s *Scalar) *Point

Sets p to s * q, where q is the point for which the table t was computed. Returns p.

func (*Point) Set 

func (p *Point) Set(q *Point) *Point

Sets p to q. Returns p

func (*Point) SetBase 

func (p *Point) SetBase() *Point

Sets p to the Edwards25519 basepoint. Returns p

func (*Point) SetBytes 

func (p *Point) SetBytes(buf *[32]byte) bool

Sets p to the point encoded in buf using Bytes(). Not every input encodes a point. Returns whether the buffer encoded a point.

func (*Point) SetElligator 

func (p *Point) SetElligator(buf *[32]byte) *Point

Sets p to the point corresponding to buf using the Elligator2 encoding.

In contrast to SetBytes() (1) Every input buffer will decode to a point and (2) SetElligator() is not injective: for every point there are approximately four buffers that will encode to it.

func (*Point) SetLizard added in v1.1.0 

func (p *Point) SetLizard(data *[16]byte) *Point

Encode 16 bytes into a point using the Lizard method.

Use Lizard() or LizardInto() to decode the bytes from a Point.

Notes on usage:

  • If you want to create a Point from random data, you should rather create a random Point with Point.Rand() and then use (a hash of) Point.Bytes() as the random data.

  • If you want to derive a Point from data, but you do not care about decoding the data back from the point, you should use the Point.Derive() method instead.

  • There are some (and with high probability at most 80) inputs to SetLizard() which cannot be decoded. The chance that you hit such an input is around 1 in 2^122.

    In Lizard there are 256 - 128 - 3 = 125 check bits to pick out the right preimage among at most eight. Conservatively assuming there are seven other preimages, the chance that one of them passes the check as well is given by:

    1 - (1 - 2^-125)^7 = 7*2^-125 + 21*2^-250 - ... =~ 2^(-125 - 2log(7)) = 2^-122.192...

    Presuming a random hash function, the number of "bad" inputs is binomially distributed with n=2^128 and p=2^-122.192... For such large n, the Poisson distribution with lambda=n*p=56 is a very good approximation. In fact: the cumulative distribution function (CDF) of the Poission distribution is larger than that of the binomial distribution for k > lambda.[1] The value of the former on k=80 is larger than 0.999 and so with a probability of 99.9%, there are fewer than 80 bad inputs.

    [1] See "Some Inequalities Among Binomial and Poisson Probabilities" by Anderson and Samuels in Proc. Fifth Berkeley Symp. on Math. Statist. and Prob., Vol. 1 (Univ. of Calif. Press, 1967).

func (*Point) SetZero 

func (p *Point) SetZero() *Point

Sets p to zero (the neutral element). Returns p.

func (Point) String 

func (p Point) String() string

func (*Point) Sub 

func (p *Point) Sub(q, r *Point) *Point

Sets p to q - r. Returns p.

func (*Point) UnmarshalBinary 

func (p *Point) UnmarshalBinary(data []byte) error

Implements encoding/BinaryUnmarshaler. Use SetBytes, if convenient, instead.

func (*Point) UnmarshalText 

func (p *Point) UnmarshalText(txt []byte) error

type Scalar 

type Scalar [8]uint32

A number modulo the prime l, where l is the order of the Ristretto group over Edwards25519.

The scalar s is represented as an array s[0], ... s[7] with 0 <= s[i] < 2^32 and s = s[0] + s[1] * 2^32 + s[2] * 2^64 + ... + s[7] * 2^224.

func (*Scalar) Add 

func (s *Scalar) Add(a, b *Scalar) *Scalar

Sets s to a + b. Returns s.

func (*Scalar) BigInt 

func (s *Scalar) BigInt() *big.Int

Returns s as a big.Int.

Warning: operations on big.Ints are not constant-time: do not use them for cryptography unless you're sure this is not an issue.

func (*Scalar) Bytes 

func (s *Scalar) Bytes() []byte

Bytes() returns a little-endian packed version of s. See also BytesInto().

func (*Scalar) BytesInto 

func (s *Scalar) BytesInto(buf *[32]byte) *Scalar

Encode s little endian into buf. Returns s.

func (*Scalar) ConditionalSet added in v1.2.2 

func (s *Scalar) ConditionalSet(t *Scalar, b int32)

Set s to t if b=1 in constant-time. b must be either 0 or 1.

func (*Scalar) Derive 

func (s *Scalar) Derive(buf []byte) *Scalar

Derive sets s to the scalar derived from the given buffer using SHA512 and Scalar.SetReduced() Returns s.

func (*Scalar) DeriveShort added in v1.1.0 

func (s *Scalar) DeriveShort(buf []byte) *Scalar

Derive sets s to the half-length scalar derived from the given buffer using SHA512. Returns s

Warning: half-length scalars are insecure in almost every application.

func (*Scalar) Equals 

func (s *Scalar) Equals(a *Scalar) bool

Equals returns whether s is equal to a.

func (*Scalar) EqualsI 

func (s *Scalar) EqualsI(a *Scalar) int32

EqualsI returns 1 if s is equal to a, otherwise 0.

func (*Scalar) Inverse 

func (s *Scalar) Inverse(t *Scalar) *Scalar

Sets s to 1/t. Returns s.

func (*Scalar) IsNonZeroI 

func (s *Scalar) IsNonZeroI() int32

IsNonZeroI returns 1 if s is non-zero and 0 otherwise.

func (*Scalar) MarshalBinary 

func (s *Scalar) MarshalBinary() ([]byte, error)

Implements encoding/BinaryMarshaler. Use BytesInto, if convenient, instead.

func (*Scalar) MarshalText 

func (s *Scalar) MarshalText() ([]byte, error)

func (*Scalar) Mul 

func (s *Scalar) Mul(a, b *Scalar) *Scalar

Sets s to a * b. Returns s.

func (*Scalar) MulAdd 

func (s *Scalar) MulAdd(a, b, c *Scalar) *Scalar

Sets s to a * b + c. Returns s.

func (*Scalar) MulSub 

func (s *Scalar) MulSub(a, b, c *Scalar) *Scalar

Sets s to a * b - c. Returns s.

func (*Scalar) Neg 

func (s *Scalar) Neg(a *Scalar) *Scalar

Sets s to -a. Returns s.

func (*Scalar) Rand 

func (s *Scalar) Rand() *Scalar

Sets s to a random scalar. Returns s.

func (*Scalar) Set 

func (s *Scalar) Set(t *Scalar) *Scalar

Sets s to t. Returns s.

func (*Scalar) SetBigInt 

func (s *Scalar) SetBigInt(x *big.Int) *Scalar

Sets s to x modulo l.

Warning: operations on big.Ints are not constant-time: do not use them for cryptography unless you're sure this is not an issue.

func (*Scalar) SetBytes 

func (s *Scalar) SetBytes(x *[32]byte) *Scalar

Sets s to x mod l, where x is interpreted little endian and the top 3 bits are ignored. Returns s.

func (*Scalar) SetOne 

func (s *Scalar) SetOne() *Scalar

Sets s to 1. Returns s.

func (*Scalar) SetReduced 

func (s *Scalar) SetReduced(t *[64]byte) *Scalar

Sets s to t mod l, where t is interpreted little endian. Returns s.

func (*Scalar) SetUint64 added in v1.2.1 

func (s *Scalar) SetUint64(x uint64) *Scalar

Sets s to x.

func (*Scalar) SetZero 

func (s *Scalar) SetZero() *Scalar

Sets s to 0. Returns s.

func (*Scalar) Square 

func (s *Scalar) Square(a *Scalar) *Scalar

Sets s to a*a. Returns s.

func (Scalar) String 

func (s Scalar) String() string

func (*Scalar) Sub 

func (s *Scalar) Sub(a, b *Scalar) *Scalar

Sets s to a - b. Returns s.

func (*Scalar) UnmarshalBinary 

func (s *Scalar) UnmarshalBinary(data []byte) error

Implements encoding/BinaryUnmarshaler. Use SetBytes, if convenient, instead.

func (*Scalar) UnmarshalText 

func (s *Scalar) UnmarshalText(txt []byte) error

type ScalarMultTable 

type ScalarMultTable edwards25519.ScalarMultTable

A table to speed up scalar multiplication of a fixed point

func (*ScalarMultTable) Compute 

func (t *ScalarMultTable) Compute(p *Point)

Fills the table for point p.

Source Files

View all Source files

Directories

Path Synopsis
A C implementation of the Ristretto group based on the PandA library by Chuengsatiansup, Ribarski and Schwabe, which we use as a reference of our pure Go implementation.
 A C implementation of the Ristretto group based on the PandA library by Chuengsatiansup, Ribarski and Schwabe, which we use as a reference of our pure Go implementation.
Go implementation of the elliptic curve Edwards25519 of which the Ristretto group is a subquotient.
 Go implementation of the elliptic curve Edwards25519 of which the Ristretto group is a subquotient.

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.