Crate ed448_goldilocks 

RustCrypto: Ed448-Goldilocks Elliptic Curve

THIS CODE HAS NOT BEEN AUDITED OR REVIEWED. USE AT YOUR OWN RISK.

About

This crate provides a pure Rust implementation of Curve448, Edwards, and Decaf. It is intended to be portable, fast, and safe.

Usage

use ed448_goldilocks::{
    Ed448, EdwardsPoint, CompressedEdwardsY, EdwardsScalar,
    elliptic_curve::Generate,
    shake::Shake256
};
use elliptic_curve::{consts::U84, Field, group::GroupEncoding};
use hash2curve::{ExpandMsgXof, GroupDigest};

let secret_key = EdwardsScalar::TWO;
let public_key = EdwardsPoint::GENERATOR * &secret_key;

assert_eq!(public_key, EdwardsPoint::GENERATOR + EdwardsPoint::GENERATOR);

let secret_key = EdwardsScalar::generate();
let public_key = EdwardsPoint::GENERATOR * &secret_key;
let compressed_public_key = public_key.to_bytes();

assert_eq!(compressed_public_key.len(), 57);

let hashed_scalar = hash2curve::hash_to_scalar::<Ed448, <Ed448 as GroupDigest>::ExpandMsg, U84>(&[b"test"], &[b"test DST"]).unwrap();
let input = hex_literal::hex!("8108d09ce4ea5707d44a6e52d75f290d0a0801cd5e366b9a0e6f72c75246ea5042963192c01703749adb0f5a4b1ab0586ccc6cf58cfd6d0e00");
let expected_scalar = EdwardsScalar::from_canonical_bytes(&input.into()).unwrap();
assert_eq!(hashed_scalar, expected_scalar);

let hashed_point = Ed448::hash_from_bytes(&[b"test"], &[b"test", b" DST"]).unwrap();
let expected = hex_literal::hex!("ff5af3430905789691f01a54feb6275dc6a28a4f7e99c1c6ef261fe665428f986723060f44d4410ed4dcf33255f53bed07e068084fdb68f980");
let expected_point = CompressedEdwardsY(expected).decompress().unwrap().to_edwards();
assert_eq!(hashed_point, expected_point);

let hashed_point = Ed448::hash_from_bytes(&[b"test"], &[b"test DST"]).unwrap();
assert_eq!(hashed_point, expected_point);

Field Choice

The field size is a Solinas trinomial prime 2^448 - 2^224 -1. This prime is called the Goldilocks prime.

Curves

This repository implements three curves explicitly and another curve implicitly.

The three explicitly implemented curves are:

• Ed448-Goldilocks

• Curve448

• Twisted-Goldilocks

Ed448-Goldilocks Curve

• The goldilocks curve is an Edwards curve with affine equation x^2 + y^2 = 1 - 39081x^2y^2 .
• This curve was defined by Mike Hamburg in https://eprint.iacr.org/2015/625.pdf.
• The cofactor of this curve over the goldilocks prime is 4.

Twisted-Goldilocks Curve

• The twisted goldilocks curve is a Twisted Edwards curve with affine equation y^2 - x^2 = 1 - 39082x^2y^2 .
• This curve is also defined in https://eprint.iacr.org/2015/625.pdf.
• The cofactor of this curve over the goldilocks prime is 4.

Isogeny

• This curve is 2-isogenous to Ed448-Goldilocks. Details of the isogeny can be found here: https://www.shiftleft.org/papers/isogeny/isogeny.pdf.

Curve448

This curve is 2-isogenous to Ed448-Goldilocks. Details of Curve448 can be found here: https://tools.ietf.org/html/rfc7748.

The main usage of this curve is for X448.

N.B. In that document there is an Edwards curve that is birationally equivalent to Curve448, with a large d value. This curve is not implemented and to my knowledge, has no utility.

Strategy

The main strategy for group arithmetic on Ed448-Goldilocks is to perform the 2-isogeny to map the point to the Twisted-Goldilocks curve, then use the faster Twisted Edwards formulas to perform scalar multiplication. Computing the 2-isogeny then the dual isogeny will pick up a factor of 4 once we map the point back to the Ed448-Goldilocks curve, so the scalar must be adjusted by a factor of 4. Adjusting the scalar is dependent on the point and the scalar. More details can be found in the 2-isogenous paper.

Decaf

The Decaf strategy [link paper] is used to build a group of prime order from the Twisted Goldilocks curve. The Twisted Goldilocks curve is used as it has faster formulas. We can also use Curve448 or Ed448-Goldilocks. Decaf takes advantage of an isogeny with a Jacobi Quartic curve which is not explicitly defined. Details of this can be found here: https://www.shiftleft.org/papers/decaf/decaf.pdf. However, to my knowledge there is no documentation for the Decaf protocol implemented in this repository, which is a tweaked version of the original decaf protocol linked in the paper.

Completed Point vs Extensible Point

Deviating from Curve25519-Dalek, this library will implement Extensible points instead of Completed Points. Due to the following observation:

• There is a cost of 3/4 Field multiplications to switch from the CompletedPoint. So if we were to perform repeated doubling, this would add an extra cost for each doubling in projective form. More details on the ExtensiblePoint can be found here [3.2]: https://www.shiftleft.org/papers/fff/fff.pdf

Credits

The library design was taken from Dalek’s design of Curve25519. The code for Montgomery curve arithmetic was also taken from Dalek’s library.

The golang implementation of Ed448 and libdecaf were used as references.

Special thanks to Mike Hamburg for answering all the questions asked regarding Decaf and goldilocks.

This library adds hash_to_curve and serialization of structs.

License

All crates licensed under either of

• Apache License, Version 2.0
• MIT license

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

serde support

When the serde feature of this crate is enabled, Serialize and Deserialize are impl’d for the following types:

• CompressedDecaf
• CompressedEdwardsY
• EdwardsPoint
• Scalar
• SigningKey
• VerifyingKey

Please see type-specific documentation for more information.

Re-exports

pub use elliptic_curve;

pub use hash2curve;

pub use rand_core;

pub use shake;

pub use subtle;

pub use elliptic_curve::pkcs8;

pub use signature;

Modules

curve 🔒

decaf 🔒

edwards 🔒

field 🔒

macros 🔒

Internal macros.

montgomery 🔒

sign 🔒

Ed448 digital signatures implementation

Structs

AffinePoint

Affine point on untwisted curve

CompressedDecaf

A compressed decaf point

CompressedEdwardsY

Represents a point on the Compressed Twisted Edwards Curve in little endian format where the most significant bit is the sign bit and the remaining 448 bits represent the y-coordinate

Context

Ed448 contexts as used by Ed448ph.

Decaf448

Decaf448 curve.

DecafAffinePoint

Affine point on the twisted curve

DecafPoint

A Decaf point in the Twisted Edwards curve

Ed448

Edwards448 curve.

EdwardsPoint

Represent points on the (untwisted) edwards curve using Extended Homogenous Projective Co-ordinates (x, y) -> (X/Z, Y/Z, Z, T) a = 1, d = -39081 XXX: Make this more descriptive Should this be renamed to EdwardsPoint so that we are consistent with Dalek crypto? Necessary as ExtendedPoint is not regular lingo?

MontgomeryPoint

A point in Montgomery form

PreHasherXmd

Signing pre-hasher for Ed448ph with a fixed output size

PreHasherXof

Signing pre-hasher for Ed448ph with a xof output

ProjectiveMontgomeryPoint

A Projective point in Montgomery form

PublicKeyBytes

Ed448 public key serialized as bytes.

Scalar

Shared scalar for Ed448 and Decaf448. Use EdwardsScalar and DecafScalar directly.

Signature

Ed448 signature.

SigningKey

Signing key for Ed448

VerifyingKey

Ed448 public key as defined in [RFC8032 § 5.2.5]

Enums

SigningError

Signing errors

Constants

ALGORITHM_ID

The AlgorithmIdentifier for Ed448 as defined in [RFC8410 §2]

ALGORITHM_OID

The OID for Ed448 as defined in [RFC8410 §2]

MODULUS_LIMBS

The modulus of the scalar field as a sequence of 14 32-bit limbs

ORDER

The order of the scalar field

PUBLIC_KEY_LENGTH

Length of a public key in bytes

SECRET_KEY_LENGTH

Length of a secret key in bytes

SIGNATURE_LENGTH

Length of a signature in bytes

WIDE_ORDER

The wide order of the scalar field

Traits

PreHash

Signing hash trait for Ed448ph

Type Aliases

Decaf448FieldBytes

Bytes of the Decaf448 field

Decaf448NonZeroScalar

Non-zero scalar of the Decaf448 scalar

DecafScalar

Decaf448 scalar field.

DecafScalarBytes

The number of bytes needed to represent the scalar field

Ed448FieldBytes

Serialized byte representation of an Ed448 field element.

Ed448NonZeroScalar

Non-zero scalar of the Ed448 scalar

EdwardsScalar

Ed448 scalar field.

EdwardsScalarBytes

The number of bytes needed to represent the scalar field

SecretKey

Ed448 secret key as defined in [RFC8032 § 5.2.5]

WideDecafScalarBytes

The number of bytes needed to represent the safely create a scalar from a random bytes

WideEdwardsScalarBytes

The number of bytes needed to represent the safely create a scalar from a random bytes