Finite field arithmetic

Ristretto255 is a prime order elliptic curve group based on Curve25519. It can be used as a building block for cryptographic protocols such as Zero-knowledge proofs of knowledge, ElGamal encryption or Schnorr signatures.

Two high-level classes are defined to wrap the libsodium API:

  • Ristretto255Scalar is the finite field over the set of integers modulo the prime 2 ** 252 + 27742317777372353535851937790883648493 and the four operations addition, subtraction, multiplication and division. Each operation takes two elements from the set and computes another element from the same set. Most operations are accessible through operator overloading.

  • Ristretto255Point is the cyclic group with points from the Curve25519 elliptic curve. Thanks to the Ristretto construction, all elements in the group are unique, and each element (other than the identity) is a generator of the complete group. The order of Ristretto255Scalar matches this group’s order. The basic operation in the group is point addition. Repeated addition of the same point is called multiplicaton.

An isomorphism exists between the two groups. This means that for scalars s, t and a point p equations such as this hold: p * (s + t) == (p * s) + (p * t).

Scalar field

Each instance of Ristretto255Scalar is a scalar value (integer reduced modulo the group order). The internal representation is a 32 byte array in little-endian order.

The operators and methods support arguments of various python types. They are automatically reduced modulo the group order and converted into the internal representation.

Argument types can be mixed:

from fractions import Fraction
from nacl.ristretto import Ristretto255Scalar

r = Ristretto255Scalar(42) / 11 * Fraction(5, 7) * (b"\x21" + bytes(31)) - -10
print(int(r))

100

Following table shows how to translate from libsodium functions:

Translating from libsodium to Ristretto255Scalar

libsodium

PyNaCl

crypto_core_ristretto255_nonreducedscalarbytes()

Ristretto255Scalar.NONREDUCED_SIZE

crypto_core_ristretto255_scalarbytes()

Ristretto255Scalar.SIZE

crypto_core_ristretto255_scalar_random(u)

u = Ristretto255Scalar.random()

crypto_core_ristretto255_scalar_reduce(u, h)

u = Ristretto255Scalar.reduce(h)

crypto_core_ristretto255_scalar_invert(u, s)

u = s.inverse

crypto_core_ristretto255_scalar_complement(u, s)

u = s.complement

crypto_core_ristretto255_scalar_add(u, s, t)

u = s + t

crypto_core_ristretto255_scalar_sub(u, s, t)

u = s - t

crypto_core_ristretto255_scalar_mul(u, s, t)

u = s * t

crypto_core_ristretto255_scalar_mul(u, s, t.inverse)

u = s / t

crypto_core_ristretto255_scalar_negate(u, s)

u = -s

sodium_memcmp(s, t, 32)

s == t

sodium_is_zero(s, 32)

bool(s)

Ristretto group

The multiplication operators take a scalar as operand which must be one of the types from above list. All other operands and arguments must be points.

Argument types can be mixed:

from fractions import Fraction
from nacl.ristretto import Ristretto255Point, Ristretto255Scalar

p = Ristretto255Point.random()
q = (p * Fraction(5, 7) - p) * Ristretto255Scalar(7)
print(bytes(p * 2 + q).hex())

0000000000000000000000000000000000000000000000000000000000000000

Following table shows how to translate from libsodium functions:

Translating from libsodium to Ristretto255Point

libsodium

PyNaCl

crypto_core_ristretto255_bytes()

Ristretto255Point.SIZE

crypto_core_ristretto255_hashbytes()

Ristretto255Point.HASH_SIZE

crypto_core_ristretto255_is_valid_point(p)

r = Ristretto255Point(p)

crypto_core_ristretto255_from_hash(r, h)

r = Ristretto255Point.from_hash(h)

crypto_core_ristretto255_random(r)

r = Ristretto255Point.random()

crypto_scalarmult_ristretto255_base(r, s)

r = Ristretto255Point.base_mul(s)

crypto_scalarmult_ristretto255(r, -1, p)

r = -p

crypto_core_ristretto255_add(r, p, q)

r = p + q

crypto_core_ristretto255_sub(r, p, q)

r = p - q

crypto_scalarmult_ristretto255(r, s, p)

r = p * s

sodium_memcmp(p, q, 32)

p == q

sodium_is_zero(p, 32)

bool(p)

Examples

There are two code examples for ElGamal encryption and Shamir’s Secret Sharing in the test cases. Two simpler examples follow:

Secure two-party computation

This is the example from libsodium:

from os import urandom
from nacl.ristretto import Ristretto255Point, Ristretto255Scalar

## First party: Send blinded p(x) ##
x = urandom(Ristretto255Point.HASH_SIZE)

# Compute px = p(x), a group element derived from x
px = Ristretto255Point.from_hash(x)

# Compute a = p(x) * g^r
r = Ristretto255Scalar.random()
gr = Ristretto255Point.base_mul(r)
a = px + Ristretto255Point.base_mul(r)


## Second party: Send g^k and a^k ##
k = Ristretto255Scalar.random()

# Compute v = g^k
v = Ristretto255Point.base_mul(k)

# Compute b = a^k
b = a * k


## First party: Unblind f(x) ##

# Compute f(x) = b * v^(-r)
#              = (p(x) * g^r)^k * (g^k)^(-r)
#              = (p(x) * g)^k * g^(-k)
#              = p(x)^k
fx = b - v * r

# Compare result
print(px * k == fx)

True

Schnorr signature

The Schnorr signature scheme can adopted to use Ristretto255:

from nacl.ristretto import Ristretto255Point, Ristretto255Scalar
import hashlib


## Choosing parameters ##

# Agree on group of prime order
G = Ristretto255Point

# Choose a random generator
g = G.random()

# Agree on a cryptographic hash function; needs to have 512 bits output
H = lambda data: Ristretto255Scalar.reduce(hashlib.sha3_512(data).digest())


## Key generation ##

# Choose a private signing key
x = Ristretto255Scalar.random()

# Compute the public verification key
y = g * x


## Signing ##

# Message to sign
M = b"Lorem ipsum dolor sit amet"

# Choose a random nonce
k = Ristretto255Scalar.random()

# Computate the signature
r = g * k
e = H(bytes(r) + M)
s = k - x * e

# Signature is the scalars (s, e)


## Verifying ##

r_v = g * s + y * e
e_v = H(bytes(r_v) + M)

if e_v == e:
    print("Signature verified")


## Key leakage from nonce reuse ##

# Another message to sign
M_ = b"consectetur adipiscing elit"

# Reuse nonce. Don't do that!
k_ = k

# Computate the signature
r_ = g * k_
e_ = H(bytes(r_) + M_)
s_ = k_ - x * e_

# Compute private key
x_ = (s_ - s) / (e - e_)

if g * x_ == y:
    print("Key was leaked")

Signature verified
Key was leaked