#elliptic-curve #key-exchange #schnorr #ed448-goldilocks #ed448

tiny_ed448_goldilocks

A lean, high performance, pure rust implementation of Ed448-Goldilocks for easy signatures and key exchange

9 releases

0.1.8 Apr 22, 2024
0.1.7 Apr 5, 2024
0.1.5 Mar 4, 2024
0.1.4 Dec 11, 2023

#515 in Cryptography


Used in capycrypt

MIT license

345KB
705 lines

Ed448-Goldilocks

WARNING: This software has not been audited. Use at your own risk.

crates.io Build Status License: MIT

1. Objective:

The Goldilocks variant of curves in Edward's form present a compelling balance of security and performance. We wish to leverage this curve to satisfy that the following group properties hold:

Identities:
0 * G = ๐’ช
G * 1 = G
G + (-G) = ๐’ช
2 * G = G + G
4 * G = 2 * (2 * G)
4 * G > ๐’ช
r * G = ๐’ช
(k + 1) * G = (k * G) + G
k*G = (k % r) * G
(k + t) * G = (k * G) + (t * G)
k * (t * G) = t * (k * G) = (k * t % r) * G

What we want:

  • The fastest possible composition and doubling operations
  • Fixed-time side-channel resistance for scalar and field operations
  • Only the functionality that we need for Schnorr signatures and asymmetric DH, ideally making this implementation as lean as possible.

2. Strategy:

Largely following the approaches of this and this, we perform the following series of transformations during a point / scalar multiplication:

  1. Start in twisted form
  2. Decompose the scalar and recenter to radix 16 between -8 and 8
  3. Create a lookup table of multiples of P mapped to radix 16 digits, with fixed-time lookups to ensure side-channel resistance.
  4. In variable_base_mul, we perform the doublings in twisted form, and the additions and fixed-time conditional negation in projective niels form.
  5. The point is returned in extended form, and finally converted to affine form for user-facing operations.

At a higher level, we have for:

Affine Extended Twisted Projective Niels
(x, y) (x, y, z, t) (x, y, z, t1, t2) (y + x, y - x, td, z)

Then our scalar multiplication would follow:

Affine โ†’ Extended โ†’ Twisted โ†’ Projective Niels โ†’ Twisted โ†’ Extended โ†’ Affine

3. Fixed-Time

The lookup table for the decomposed scalar is computed and traversed in fixed-time:

/// Selects a projective niels point from a lookup table in fixed-time
pub fn select(&self, index: u32) -> ProjectiveNielsPoint {
    let mut result = ProjectiveNielsPoint::id_point();
    for i in 1..9 {
        let swap = index.ct_eq(&(i as u32));
        result.conditional_assign(&self.0[i - 1], swap);
    }
    result
}

This ensures fixed-time multiplication without the need for a curve point in Montgomery form. Further, we make use of the crypto-bigint library which ensures fixed-time operations for our Scalar type. Field elements are represented by the fiat-crypto p448-solinas-64 prime field. It is formally verified and heavily optimized at the machine-level.

4. Signatures and DH:

Using this crate as the elliptic-curve backend for capyCRYPT, we have:

Schnorr Signatures:

 use capycrypt::{
    Signable,
    KeyPair,
    Message,
    sha3::aux_functions::byte_utils::get_random_bytes
};
/// # Schnorr Signatures
/// Signs a [`Message`] under passphrase pw.
///
/// ## Algorithm:
/// * `s` โ† kmac_xof(pw, โ€œโ€, 448, โ€œSKโ€); s โ† 4s
/// * `k` โ† kmac_xof(s, m, 448, โ€œNโ€); k โ† 4k
/// * `๐‘ˆ` โ† k*๐‘ฎ;
/// * `โ„Ž` โ† kmac_xof(๐‘ˆโ‚“ , m, 448, โ€œTโ€); ๐‘ โ† (๐‘˜ โ€“ โ„Ž๐‘ ) mod r
/// ```
fn sign(&mut self, key: &KeyPair, d: u64) {
    self.d = Some(d);

    let s: Scalar = bytes_to_scalar(kmac_xof(&key.priv_key, &[], 448, "SK", self.d.unwrap()))
        * (Scalar::from(4_u64));

    let s_bytes = scalar_to_bytes(&s);

    let k: Scalar =
        bytes_to_scalar(kmac_xof(&s_bytes, &self.msg, 448, "N", d)) * (Scalar::from(4_u64));

    let U = ExtendedPoint::generator() * k;
    let ux_bytes = U.to_affine().x.to_bytes().to_vec();
    let h = kmac_xof(&ux_bytes, &self.msg, 448, "T", d);
    let h_big = bytes_to_scalar(h.clone());
    let z = k - (h_big.mul_mod_r(&s));
    self.sig = Some(Signature { h, z })
}

5. Benchmarks

Run with:

cargo bench

Approximate runtimes for Intelยฎ Coreโ„ข i7-10710U ร— 12 on 5mb random data:

Operation ~Time (ms) OpenSSL (ms)
Encrypt 75
Decrypt 75
Sign 42 15
Verify 18

Our custom SHA3 performs as good as OpenSSL, but at this time we don't know what the hashing backend is for the experiments on that end. So some of this overhead might come from the use of SHA3 vs a more optimized hasher on OpenSSL's part like SHA2 for instance. Still, this performance is vastly superior to our previous attempt at using exclusively affine coordinates.

Acknowledgements

The authors wish to sincerely thank Dr. Paulo Barreto for consultation on the fixed-time operations and his work in the field in general. We also wish to extend gratitude to the curve-dalek authors here and here for the excellent reference implementations and exemplary instances of rock-solid cryptography. Thanks to otsmr for the callout on the original attempt at an affine-coordinate Montgomery ladder.

Dependencies

~6.5MB
~138K SLoC