bwesterb / go-ristretto

Pure Go implementation of the Ristretto prime-order group over Edwards25519

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

• Rust
• Javascript
• C (part of libsodium)

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

go-ristretto's Issues

how to encode message into point on curve

@bwesterb Hi，bwesterb. I wanna implement Elgamal encryption with this library, but it confuses me that how to encode message into point on curve. Is there any sample for this usage. I saw the provided example, but it can not answer my need.

Looking forward to your reply.

Add variable-time arithmetic for public inputs

Currently, all operations are constant-time to prevent secrets being stolen by timing attacks. However, if all values involved are public, using constant-time operations is a waste.

More efficient Double routine

Add(x, x) works, but can probably be improved.

Faster generic scalar arithmatic

Conver to affine representation?

Could you please help me on converting extended point to a affine point (x: bigInt, y:bigInt)

Add `Scalar.Derive`

Optimise field arithmetic with SIMD instructions if available

Optimize Scalar.Square

Add {Point,Scalar}.Equals

ScalarMult is broken?

Hey there, I think 0995efa might have broken ScalarMult (at least for me). Please see the following test case (scalar and result generated with curve25519-dalek) which passes before that commit.

func TestBasePoint(t *testing.T) {
	var buf [32]byte
	var s ristretto.Scalar
	var p1, p2, B ristretto.Point
	B.SetBase()

	tmp, _ := base64.StdEncoding.DecodeString("QekHbzmOtwUfRnheuyj1qyt8HN1WPjW4Jy199/2fQQ8=")
	copy(buf[:], tmp)
	s.SetBytes(&buf)

	tmp, _ = base64.StdEncoding.DecodeString("SqbtfZl5+A1RtHVfzN8HJCLUcC0Bz2kdThR7wRCUbCQ=")
	copy(buf[:], tmp)
	p1.SetBytes(&buf)

	p2.ScalarMult(&B, &s)

	if !p1.Equals(&p2) {
		t.Fatalf("[%v]B = %v != %v", s, p2, p1)
	}
}

Expose precomputation part of scalar multiplication for efficient repeated scalar multiplication of the same point

Instead of

q1.ScalarMult(&p, s1)
q2.ScalarMult(&p, s2)

we might cache the computeScalarWindow5 call with an API like

// p, q1, q2 ristretto.Point;  s1, s2 ristretto.Scalar
var sm ristretto.ScalarMultipleTable
sm.Precompute(&p)  // stores output of, say, computeScalarWindow5
q1.ScalarMultTable(&sm, s1)
q2.ScalarMultTable(&sm, s2)

Point.Equals() always returns true if at least one point is uninitialized.

var a, b ristretto.Point
b.Rand()
flag := a.Equals(b)
flag is true.

Don't ignore the top-order bit when decoding elements

Ideally, all invalid encoding test vectors in the spec should pass.

Add Point.SetElligator "inverse"

The library is vartime on all non-amd64 platforms if built with go 1.12

FieldElement.Mul has a comment like thus: // TODO make sure we only use bits.Add64 if it's constant-time

While "the fallback code is vartime" has thankfully been fixed for Go 1.13 and later, the only platform where bits.Add64 is constant time for Go 1.12 series is amd64. With Go 1.13 the only platforms where both bits.Add64 and bits.Mul64 are fast is limited to amd64, arm64, and ppc64 (for both endian configurations), but at least they are guaranteed to be constant time now.

See:

• https://github.com/golang/go/blob/release-branch.go1.12/src/math/bits/bits.go#L363
• https://github.com/golang/go/blob/release-branch.go1.12/src/cmd/compile/internal/gc/ssa.go#L3500
• https://github.com/golang/go/blob/release-branch.go1.13/src/cmd/compile/internal/gc/ssa.go#L3587

Optimize `Group.Sub`

Adding MulSub and SetReduced32

Would you like MulSub and SetReduced32 in go-ristretto?

MulSub would be identical to MulAdd and would just negate c0-c11

SetRedcued32 would take a 32 byte instead of a 64 byte array that SetReduced takes.

Ristretto Point Compression

I just started using this lib and so far it's being an awesome experience! I'd like to ask about Ristretto point compression. Is there anyway of doing it? If not, is there any plans on implementing it? Is there anyway I could help with it? I can even make a pull request with the implementation if that's the case idk.

`Point` add optimized scalar-multiplication with standard base-point