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 ed25519ts
to be used on platforms where native bigint
s 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 SHA512 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 nobleed25519. When using ed25519
on a
platform that provides native bigint
support, nobleed25519
is preferred.
Usage
Use yarn or NPM in node.js, browser, or React Native:
yarn add @privacyresearch/pred25519
To use with JSBI
and jssha512
import JSBI from 'jsbi'
import sha512 from 'jssha512'
import { makeED } from '@privacyresearch/pred25519'
const ed = makeED(JSBI, sha512.sha512)
const privateKey = ed.utils.randomPrivateKey() // 32byte 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() // 32byte 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  Uint8Array
s  instead of strings
const privateKey: Uint8Array = ed.utils.randomPrivateKey() // 32byte 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.Point
s 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 cofactor8 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 censorshipresistant 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 64byte array to Edwards point representative of an encoded Ristretto point using the censorshipresistant 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 hashtopoint 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)
nobleed25519
Performance Comparison with Running the benchmarks on a MacBook Pro with 2.7 GHz Intel i7 we see that using pred25519
with JSBI for
integer arithmetic is 510 times slower than using the nobleed25519
implementation with native bigint
.
However using pred25519
with
our native BigInt wrapper
yields results much closer to nobleed25519
. In some areas, particularly in verification, pred25519
still
significantly underperforms nobleed25519
, so we see that the cost of abstracting the integer implementation
is real and nobleed25519
should be preferred for environments where the native javascript bbigint
is
available and acceptable.
nobleed25519
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
pred25519
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
pred25519
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)