Ed25519 and Ristretto255 with Injectable BigInt and Hash Dependencies

This is an efficient implementation of ed25519 that can be used with any integer arithmetic library that implements a standard interface based on JSBI. This allows ed25519-ts to be used on platforms where native bigints are not available (e.g. React Native) or with other libraries that may have different performance or security characteristics. The package also allows injection of a SHA-512 dependency, allowing users to select native versions when possible and best alternatives when not.

Cryptographic features include:

• Direct support for EdDSA signing and verification
• Can be used for asymmetric encryption
• Provides ristretto255 support and elligator encoding/decoding.

The core logic is a direct modification of noble-ed25519. When using ed25519 on a platform that provides native bigint support, noble-ed25519 is preferred.

Usage

Use yarn or NPM in node.js, browser, or React Native:

yarn add @privacyresearch/pr-ed25519

To use with JSBI and js-sha512

import JSBI from 'jsbi'
import sha512 from 'js-sha512'
import { makeED } from '@privacyresearch/pr-ed25519'

const ed = makeED(JSBI, sha512.sha512)

const privateKey = ed.utils.randomPrivateKey() // 32-byte Uint8Array or string.
const msgHash = 'aaaabbbbaaaabbbbaaaabbbbaaaabbbbaaaabbbbaaaabbbbaaaabbbbaaaabbbb'

const publicKey = await ed.getPublicKey(privateKey)
const signature = await ed.sign(msgHash, privateKey)
const signatureIsValid = await ed.verify(signature, msgHash, publicKey)

In the code examples below we will assume a variable ed has been created as above.

Signing and Verification

The basics of signing can be seen in the example above, however there are some subtleties of type. Below we extend the example with (superfluous) type annotations so that we see more clearly what was happening in the example.

const privateKey: Uint8Array = ed.utils.randomPrivateKey() // 32-byte Uint8Array or string.
const msgHash: string = 'aaaabbbbaaaabbbbaaaabbbbaaaabbbbaaaabbbbaaaabbbbaaaabbbbaaaabbbb'

// The publicKey is a Uint8Array because privateKey is Uint8Array | BIT | number.
// If privateKey were a (hex) string, then pubKey would be too
const publicKey: Uint8Array = await ed.getPublicKey(privateKey)

// Since msgHash is a (hex) string, signature is also a (hex) string
const signature: string = await ed.sign(msgHash, privateKey)
const signatureIsValid = await ed.verify(signature, msgHash, publicKey)

Now we can change this to pass binary data - Uint8Arrays - instead of strings

const privateKey: Uint8Array = ed.utils.randomPrivateKey() // 32-byte Uint8Array or string.
const msgHash: Uint8Array = hexToBytes('aaaabbbbaaaabbbbaaaabbbbaaaabbbbaaaabbbbaaaabbbbaaaabbbbaaaabbbb')

// The publicKey is a Uint8Array because privateKey is Uint8Array | BIT | number.
// If privateKey were a (hex) string, then pubKey would be too
const publicKey: Uint8Array = await ed.getPublicKey(privateKey)

// Since msgHash is a Uint8Array, signature is also a Uint8Array
const signature: Uint8Array = await ed.sign(msgHash, privateKey)
const signatureIsValid = await ed.verify(signature, msgHash, publicKey)

Curve Arithmetic

Curve points can be manipulated either as affine points (using only (x,y) coordinates) or extended points (using (x,y,z,t) coordinates). Affine points are represented by the class ed.Point which implements the interface PointBase<BIT> and has static methods implementing PointStatic<BIT> code. Extended points are represented by the class ed.ExtendedPoint which implements the interface ExtendedPointBase<BIT> and has static methods implementing ExtendedPointStatic<BIT> code.

Manipulation of these points is straightforward. We can add, negate, subtract, and multiply by scalars:

// Make some scalars
const scalar6 = Ints.BigInt(6)
const scalar7 = Ints.BigInt(7)
const scalar21 = Ints.BigInt(21)
const scalar42 = Ints.BigInt(42)

// Create some curve points by multiplying the scalars by our base point
const P6 = ed.ExtendedPoint.BASE.multiply(scalar6)
const P7 = ed.ExtendedPoint.BASE.multiply(scalar7)
const P21 = ed.ExtendedPoint.BASE.multiply(scalar21)
const P42 = ed.ExtendedPoint.BASE.multiply(scalar42)

// Now arithmetic works as expected
P6.add(P6.negate()).equals(ed.ExtendedPoint.ZERO) //true
P6.multiply(scalar7).equals(P42) // true
P7.add(P7).add(P7).equals(P21) // true
P42.subtract(P42).equals(P21) //true

The same operations could be carried out on ed.Points too, but keep in mind that internally each operation will convert an affine point to an extended point, so it is slightly more efficient to work directly with extended points.

Extended points also offer another multiplication option that is not constant time: multiplyUnsafe. This can be used in situations where timing attacks are not a concern, for example in signature verification where all inputs are public. Here we see it used in the last line of the signature verification function:

// If sig is valid, we're in the torsion subgroup. Multiply by 8 will give zero.
return RPh.subtract(Gs).multiplyUnsafe(toBigInt(8)).equals(ExtendedPointClass.ZERO)

Ristretto

Many cryptographic protocols require use of a prime order group. Ed25519 is not prime order, but it does have a prime order subgroup of index 8. There are ad hoc ways to force points into this subgroup, such as multiplying points by 8, but these mangle points and require new security proofs. Other curves with prime order groups have slower arithmetic operations. We want both the speed of Ed25519 and the security of a prime order group.

Ristretto gives us us this by working in the quotient group of our cofactor-8 curve modulo its torsion subgroup: E/E[8]. For Ed25519 is a prime order group whose elements are cosets of the torsion subgroup E[8]. Done naively this approach would produce large encodings - each coset contains 8 Edwards points - and expensive equality tests. Ristretto avoids these problems and provides compact encodings, efficient equality checks, and a censorship-resistant elligator based mapping from general bit strings to Ristretto points. With implementations of Ristretto available in multiple programming languages, this also gives a programmer easy interoperability with other systems, making it easy to use, say, Rust on a server and TypeScript on a client.

To use these with this library you can perform all arithmetic with ExtendedPoint objects (the map from the Edwards curve to the Ristretto group is a homomorphism). When using the curve in a protocol that requires a prime order group, use the functions:

• extendedPoint.toRistrettoBytes(): Uint8Array to produce the canonical encoding of a Ristretto point. (Our Edwards point is mapped to a Ristretto point and then encoded.)
• ed.ExtendedPoint.fromRistrettoBytes(bytes: Uint8Array): ExtendedPointBase<BIT> to compute an Edwards point representative of an encoded Ristretto point.
• ed.ExtendedPoint.fromRistrettoHash(bytes: Uint8Array): ExtendedPointBase<BIT> to map an arbitrary 64-byte array to Edwards point representative of an encoded Ristretto point using the censorship-resistant Elligator mapping.
• extendedPoint.ristrettoEquals(other: ExtendedPointBase<BIT>): boolean to check whether two Edwards points represent the same Ristretto point.

For example:

// Hash a string to encode it as an extended point with elligator
const h = sha512('hyvä hyvä')
const point = ed.ExtendedPoint.fromRistrettoHash(h)
const encoded = point.toRistrettoBytes() // Uint8Array

// we could now send `encoded` over the wire to a server as part of a protocol, etc...
const decoded = ed.ExtendedPoint.fromRistrettoBytes(encoded)

point.equals(decoded) // MAYBE false!
point.ristrettoEquals(decoded) // ALWAYS true

expect(encoded).toEqual(decoded.toRistrettoBytes()) // Always true

Other Protocols: An OPRF

As mentioned above, we can use this implementation of Ristretto255 directly in cryptographic protocols that require a prime order group. As an example, here we implement an Oblivious Pseudorandom Function [OPRF] protocol as described in Burns, et al. replacing their hash-to-point function with the Ristretto/Elligator hash.

Client prepares a message

function prepareOPRFClientMessage(oprfInput: Uint8Array, bSecret: Uint8Array): Uint8Array {
  const A = ed.ExtendedPoint.fromRistrettoHash(oprfInput)
  const B = A.multiply(ed.keyUtils.encodePrivate(bSecret))
  return B.toRistrettoBytes()
}

const bSecret = ed.utils.randomPrivateKey()
const rawMessage = 'my secret OPRF input'
const hashed = sha512(rawMessage)
const maskedInput = prepareOPRFClientMessage(hashed, bSecret)

storeSecretInSession(bSecret) // We will need this to unmask server response
sendMessageToServer(maskedInput)

Server applies function to masked input

function prepareServerOPRFMessage(clientOPRFMessage: Uint8Array, serverOPRFKey: Uint8Array): Uint8Array {
  const B = ed.ExtendedPoint.fromRistrettoBytes(clientOPRFMessage)
  const k = ed.keyUtils.encodePrivate(serverOPRFKey)
  const C = B.multiply(k)
  return C.toRistrettoBytes()
}

const serverOPRFMessage = prepareServerOPRFMessage(clientOPRFMessage, serverOPRFKey)
sendMEssageToClient(serverOPRFMEssage)

Client unmasks the response

// Retrieve bSecret for session
function receiveServerMessage(cBytes: Uint8Array, bSecret: Uint8Array): Uint8Array {
  const C = ed.ExtendedPoint.fromRistrettoBytes(cBytes)
  const b = ed.keyUtils.encodePrivate(bSecret)
  const bInv = ed.math.invert(b, ed.CURVE.n)
  const D = C.multiply(bInv)
  return D.toRistrettoBytes()
}

const oprfOutput = receiveServerMessage(serverOPRFMessage, bSecret)
// Now remove algebraic content before using the bits
const outputForUsage = sha256(oprfOutput)

Performance Comparison with noble-ed25519

Running the benchmarks on a MacBook Pro with 2.7 GHz Intel i7 we see that using pr-ed25519 with JSBI for integer arithmetic is 5-10 times slower than using the noble-ed25519 implementation with native bigint. However using pr-ed25519 with our native BigInt wrapper yields results much closer to noble-ed25519. In some areas, particularly in verification, pr-ed25519 still significantly underperforms noble-ed25519, so we see that the cost of abstracting the integer implementation is real and noble-ed25519 should be preferred for environments where the native javascript bbigint is available and acceptable.

noble-ed25519 benchmarks:

Benchmarking
Initialized: 63ms
RAM: rss=34.2mb heap=13.7mb used=7.3mb ext=1.0mb

getPublicKey 1 bit x 2,962 ops/sec @ 337μs/op
getPublicKey(utils.randomPrivateKey()) x 3,113 ops/sec @ 321μs/op
sign x 1,464 ops/sec @ 682μs/op
verify x 316 ops/sec @ 3ms/op
verifyBatch x 394 ops/sec @ 2ms/op
Point.fromHex decompression x 5,452 ops/sec @ 183μs/op
ristretto255#fromHash x 2,790 ops/sec @ 358μs/op
ristretto255 round x 1,332 ops/sec @ 750μs/op
RAM: rss=56.9mb heap=25.2mb used=12.2mb ext=1.4mb arr=0.3mb

pr-ed25519 with JSBI benchmarks:

Benchmarking
Initialized: 346ms
RAM: rss=52.1mb heap=25.2mb used=15.5mb ext=1.0mb

getPublicKey 1 bit x 793 ops/sec @ 1ms/op
getPublicKey(utils.randomPrivateKey()) x 825 ops/sec @ 1ms/op
sign x 350 ops/sec @ 2ms/op
verify x 32 ops/sec @ 30ms/op
verifyBatch x 39 ops/sec @ 25ms/op
Point.fromHex decompression x 836 ops/sec @ 1ms/op
ristretto255#fromHash x 374 ops/sec @ 2ms/op
ristretto255 round x 210 ops/sec @ 4ms/op
RAM: rss=81.1mb heap=44.6mb used=12.8mb ext=1.4mb arr=0.3mb

pr-ed25519 with native BigInt:

Benchmarking
Initialized: 78ms
RAM: rss=36.4mb heap=13.7mb used=6.3mb ext=1.0mb

getPublicKey 1 bit x 2,944 ops/sec @ 339μs/op
getPublicKey(utils.randomPrivateKey()) x 3,137 ops/sec @ 318μs/op
sign x 1,446 ops/sec @ 691μs/op
verify x 210 ops/sec @ 4ms/op
verifyBatch x 216 ops/sec @ 4ms/op
Point.fromHex decompression x 4,933 ops/sec @ 202μs/op
ristretto255#fromHash x 2,478 ops/sec @ 403μs/op
ristretto255 round x 1,179 ops/sec @ 847μs/op
RAM: rss=59.0mb heap=26.0mb used=12.6mb ext=1.4mb arr=0.3mb

License

(c) 2021 Privacy Research, LLC (https://privacyresearch.io), see LICENSE file. Portions (c) 2019 Paul Miller (https://paulmillr.com)