1206 lines
36 KiB
Rust
1206 lines
36 KiB
Rust
//! This module contains implementations for the Pallas and Vesta elliptic curve
|
|
//! groups.
|
|
|
|
use core::cmp;
|
|
use core::fmt;
|
|
use core::iter::Sum;
|
|
use core::ops::{Add, Mul, Neg, Sub};
|
|
|
|
#[cfg(feature = "alloc")]
|
|
use alloc::boxed::Box;
|
|
|
|
use ff::{Field, PrimeField};
|
|
use group::{
|
|
cofactor::{CofactorCurve, CofactorGroup},
|
|
prime::{PrimeCurve, PrimeCurveAffine, PrimeGroup},
|
|
Curve as _, Group as _, GroupEncoding,
|
|
};
|
|
use rand::RngCore;
|
|
use subtle::{Choice, ConditionallySelectable, ConstantTimeEq, CtOption};
|
|
|
|
#[cfg(feature = "alloc")]
|
|
use ff::WithSmallOrderMulGroup;
|
|
|
|
use super::{Fp, Fq};
|
|
|
|
#[cfg(feature = "alloc")]
|
|
use crate::arithmetic::{Coordinates, CurveAffine, CurveExt};
|
|
|
|
macro_rules! new_curve_impl {
|
|
(($($privacy:tt)*), $name:ident, $name_affine:ident, $iso:ident, $base:ident, $scalar:ident,
|
|
$curve_id:literal, $a_raw:expr, $b_raw:expr, $curve_type:ident) => {
|
|
/// Represents a point in the projective coordinate space.
|
|
#[derive(Copy, Clone, Debug)]
|
|
#[cfg_attr(feature = "repr-c", repr(C))]
|
|
$($privacy)* struct $name {
|
|
x: $base,
|
|
y: $base,
|
|
z: $base,
|
|
}
|
|
|
|
impl $name {
|
|
const fn curve_constant_a() -> $base {
|
|
$base::from_raw($a_raw)
|
|
}
|
|
|
|
const fn curve_constant_b() -> $base {
|
|
$base::from_raw($b_raw)
|
|
}
|
|
}
|
|
|
|
/// Represents a point in the affine coordinate space (or the point at
|
|
/// infinity).
|
|
#[derive(Copy, Clone)]
|
|
#[cfg_attr(feature = "repr-c", repr(C))]
|
|
$($privacy)* struct $name_affine {
|
|
x: $base,
|
|
y: $base,
|
|
}
|
|
|
|
impl fmt::Debug for $name_affine {
|
|
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
|
|
if self.is_identity().into() {
|
|
write!(f, "Infinity")
|
|
} else {
|
|
write!(f, "({:?}, {:?})", self.x, self.y)
|
|
}
|
|
}
|
|
}
|
|
|
|
impl group::Group for $name {
|
|
type Scalar = $scalar;
|
|
|
|
fn random(mut rng: impl RngCore) -> Self {
|
|
loop {
|
|
let x = $base::random(&mut rng);
|
|
let ysign = (rng.next_u32() % 2) as u8;
|
|
|
|
let x3 = x.square() * x;
|
|
let y = (x3 + $name::curve_constant_b()).sqrt();
|
|
if let Some(y) = Option::<$base>::from(y) {
|
|
let sign = y.is_odd().unwrap_u8();
|
|
let y = if ysign ^ sign == 0 { y } else { -y };
|
|
|
|
let p = $name_affine {
|
|
x,
|
|
y,
|
|
};
|
|
break p.to_curve();
|
|
}
|
|
}
|
|
}
|
|
|
|
impl_projective_curve_specific!($name, $base, $curve_type);
|
|
|
|
fn identity() -> Self {
|
|
Self {
|
|
x: $base::zero(),
|
|
y: $base::zero(),
|
|
z: $base::zero(),
|
|
}
|
|
}
|
|
|
|
fn is_identity(&self) -> Choice {
|
|
self.z.is_zero()
|
|
}
|
|
}
|
|
|
|
#[cfg(feature = "alloc")]
|
|
#[cfg_attr(docsrs, doc(cfg(feature = "alloc")))]
|
|
impl group::WnafGroup for $name {
|
|
fn recommended_wnaf_for_num_scalars(num_scalars: usize) -> usize {
|
|
// Copied from bls12_381::g1, should be updated.
|
|
const RECOMMENDATIONS: [usize; 12] =
|
|
[1, 3, 7, 20, 43, 120, 273, 563, 1630, 3128, 7933, 62569];
|
|
|
|
let mut ret = 4;
|
|
for r in &RECOMMENDATIONS {
|
|
if num_scalars > *r {
|
|
ret += 1;
|
|
} else {
|
|
break;
|
|
}
|
|
}
|
|
|
|
ret
|
|
}
|
|
}
|
|
|
|
#[cfg(feature = "alloc")]
|
|
#[cfg_attr(docsrs, doc(cfg(feature = "alloc")))]
|
|
impl CurveExt for $name {
|
|
type ScalarExt = $scalar;
|
|
type Base = $base;
|
|
type AffineExt = $name_affine;
|
|
|
|
const CURVE_ID: &'static str = $curve_id;
|
|
|
|
impl_projective_curve_ext!($name, $iso, $base, $curve_type);
|
|
|
|
fn a() -> Self::Base {
|
|
$name::curve_constant_a()
|
|
}
|
|
|
|
fn b() -> Self::Base {
|
|
$name::curve_constant_b()
|
|
}
|
|
|
|
fn new_jacobian(x: Self::Base, y: Self::Base, z: Self::Base) -> CtOption<Self> {
|
|
let p = $name { x, y, z };
|
|
CtOption::new(p, p.is_on_curve())
|
|
}
|
|
|
|
fn jacobian_coordinates(&self) -> ($base, $base, $base) {
|
|
(self.x, self.y, self.z)
|
|
}
|
|
|
|
fn is_on_curve(&self) -> Choice {
|
|
// Y^2 = X^3 + AX(Z^4) + b(Z^6)
|
|
// Y^2 - (X^2 + A(Z^4))X = b(Z^6)
|
|
|
|
let z2 = self.z.square();
|
|
let z4 = z2.square();
|
|
let z6 = z4 * z2;
|
|
(self.y.square() - (self.x.square() + $name::curve_constant_a() * z4) * self.x)
|
|
.ct_eq(&(z6 * $name::curve_constant_b()))
|
|
| self.z.is_zero()
|
|
}
|
|
}
|
|
|
|
impl group::Curve for $name {
|
|
type AffineRepr = $name_affine;
|
|
|
|
fn batch_normalize(p: &[Self], q: &mut [Self::AffineRepr]) {
|
|
assert_eq!(p.len(), q.len());
|
|
|
|
let mut acc = $base::one();
|
|
for (p, q) in p.iter().zip(q.iter_mut()) {
|
|
// We use the `x` field of $name_affine to store the product
|
|
// of previous z-coordinates seen.
|
|
q.x = acc;
|
|
|
|
// We will end up skipping all identities in p
|
|
acc = $base::conditional_select(&(acc * p.z), &acc, p.is_identity());
|
|
}
|
|
|
|
// This is the inverse, as all z-coordinates are nonzero and the ones
|
|
// that are not are skipped.
|
|
acc = acc.invert().unwrap();
|
|
|
|
for (p, q) in p.iter().rev().zip(q.iter_mut().rev()) {
|
|
let skip = p.is_identity();
|
|
|
|
// Compute tmp = 1/z
|
|
let tmp = q.x * acc;
|
|
|
|
// Cancel out z-coordinate in denominator of `acc`
|
|
acc = $base::conditional_select(&(acc * p.z), &acc, skip);
|
|
|
|
// Set the coordinates to the correct value
|
|
let tmp2 = tmp.square();
|
|
let tmp3 = tmp2 * tmp;
|
|
|
|
q.x = p.x * tmp2;
|
|
q.y = p.y * tmp3;
|
|
|
|
*q = $name_affine::conditional_select(&q, &$name_affine::identity(), skip);
|
|
}
|
|
}
|
|
|
|
fn to_affine(&self) -> Self::AffineRepr {
|
|
let zinv = self.z.invert().unwrap_or($base::zero());
|
|
let zinv2 = zinv.square();
|
|
let x = self.x * zinv2;
|
|
let zinv3 = zinv2 * zinv;
|
|
let y = self.y * zinv3;
|
|
|
|
let tmp = $name_affine {
|
|
x,
|
|
y,
|
|
};
|
|
|
|
$name_affine::conditional_select(&tmp, &$name_affine::identity(), zinv.is_zero())
|
|
}
|
|
}
|
|
|
|
impl PrimeGroup for $name {}
|
|
|
|
impl CofactorGroup for $name {
|
|
type Subgroup = $name;
|
|
|
|
fn clear_cofactor(&self) -> Self {
|
|
// This is a prime-order group, with a cofactor of 1.
|
|
*self
|
|
}
|
|
|
|
fn into_subgroup(self) -> CtOption<Self::Subgroup> {
|
|
// Nothing to do here.
|
|
CtOption::new(self, 1.into())
|
|
}
|
|
|
|
fn is_torsion_free(&self) -> Choice {
|
|
// Shortcut: all points in a prime-order group are torsion free.
|
|
1.into()
|
|
}
|
|
}
|
|
|
|
impl PrimeCurve for $name {
|
|
type Affine = $name_affine;
|
|
}
|
|
|
|
impl CofactorCurve for $name {
|
|
type Affine = $name_affine;
|
|
}
|
|
|
|
impl GroupEncoding for $name {
|
|
type Repr = [u8; 32];
|
|
|
|
fn from_bytes(bytes: &Self::Repr) -> CtOption<Self> {
|
|
$name_affine::from_bytes(bytes).map(Self::from)
|
|
}
|
|
|
|
fn from_bytes_unchecked(bytes: &Self::Repr) -> CtOption<Self> {
|
|
// We can't avoid curve checks when parsing a compressed encoding.
|
|
$name_affine::from_bytes(bytes).map(Self::from)
|
|
}
|
|
|
|
fn to_bytes(&self) -> Self::Repr {
|
|
$name_affine::from(self).to_bytes()
|
|
}
|
|
}
|
|
|
|
impl<'a> From<&'a $name_affine> for $name {
|
|
fn from(p: &'a $name_affine) -> $name {
|
|
p.to_curve()
|
|
}
|
|
}
|
|
|
|
impl From<$name_affine> for $name {
|
|
fn from(p: $name_affine) -> $name {
|
|
p.to_curve()
|
|
}
|
|
}
|
|
|
|
impl Default for $name {
|
|
fn default() -> $name {
|
|
$name::identity()
|
|
}
|
|
}
|
|
|
|
impl ConstantTimeEq for $name {
|
|
fn ct_eq(&self, other: &Self) -> Choice {
|
|
// Is (xz^2, yz^3, z) equal to (x'z'^2, yz'^3, z') when converted to affine?
|
|
|
|
let z = other.z.square();
|
|
let x1 = self.x * z;
|
|
let z = z * other.z;
|
|
let y1 = self.y * z;
|
|
let z = self.z.square();
|
|
let x2 = other.x * z;
|
|
let z = z * self.z;
|
|
let y2 = other.y * z;
|
|
|
|
let self_is_zero = self.is_identity();
|
|
let other_is_zero = other.is_identity();
|
|
|
|
(self_is_zero & other_is_zero) // Both point at infinity
|
|
| ((!self_is_zero) & (!other_is_zero) & x1.ct_eq(&x2) & y1.ct_eq(&y2))
|
|
// Neither point at infinity, coordinates are the same
|
|
}
|
|
}
|
|
|
|
impl PartialEq for $name {
|
|
fn eq(&self, other: &Self) -> bool {
|
|
self.ct_eq(other).into()
|
|
}
|
|
}
|
|
|
|
impl cmp::Eq for $name {}
|
|
|
|
impl ConditionallySelectable for $name {
|
|
fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
|
|
$name {
|
|
x: $base::conditional_select(&a.x, &b.x, choice),
|
|
y: $base::conditional_select(&a.y, &b.y, choice),
|
|
z: $base::conditional_select(&a.z, &b.z, choice),
|
|
}
|
|
}
|
|
}
|
|
|
|
impl<'a> Neg for &'a $name {
|
|
type Output = $name;
|
|
|
|
fn neg(self) -> $name {
|
|
$name {
|
|
x: self.x,
|
|
y: -self.y,
|
|
z: self.z,
|
|
}
|
|
}
|
|
}
|
|
|
|
impl Neg for $name {
|
|
type Output = $name;
|
|
|
|
fn neg(self) -> $name {
|
|
-&self
|
|
}
|
|
}
|
|
|
|
impl<T> Sum<T> for $name
|
|
where
|
|
T: core::borrow::Borrow<$name>,
|
|
{
|
|
fn sum<I>(iter: I) -> Self
|
|
where
|
|
I: Iterator<Item = T>,
|
|
{
|
|
iter.fold(Self::identity(), |acc, item| acc + item.borrow())
|
|
}
|
|
}
|
|
|
|
impl<'a, 'b> Add<&'a $name> for &'b $name {
|
|
type Output = $name;
|
|
|
|
fn add(self, rhs: &'a $name) -> $name {
|
|
if bool::from(self.is_identity()) {
|
|
*rhs
|
|
} else if bool::from(rhs.is_identity()) {
|
|
*self
|
|
} else {
|
|
let z1z1 = self.z.square();
|
|
let z2z2 = rhs.z.square();
|
|
let u1 = self.x * z2z2;
|
|
let u2 = rhs.x * z1z1;
|
|
let s1 = self.y * z2z2 * rhs.z;
|
|
let s2 = rhs.y * z1z1 * self.z;
|
|
|
|
if u1 == u2 {
|
|
if s1 == s2 {
|
|
self.double()
|
|
} else {
|
|
$name::identity()
|
|
}
|
|
} else {
|
|
let h = u2 - u1;
|
|
let i = (h + h).square();
|
|
let j = h * i;
|
|
let r = s2 - s1;
|
|
let r = r + r;
|
|
let v = u1 * i;
|
|
let x3 = r.square() - j - v - v;
|
|
let s1 = s1 * j;
|
|
let s1 = s1 + s1;
|
|
let y3 = r * (v - x3) - s1;
|
|
let z3 = (self.z + rhs.z).square() - z1z1 - z2z2;
|
|
let z3 = z3 * h;
|
|
|
|
$name {
|
|
x: x3, y: y3, z: z3
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
impl<'a, 'b> Add<&'a $name_affine> for &'b $name {
|
|
type Output = $name;
|
|
|
|
fn add(self, rhs: &'a $name_affine) -> $name {
|
|
if bool::from(self.is_identity()) {
|
|
rhs.to_curve()
|
|
} else if bool::from(rhs.is_identity()) {
|
|
*self
|
|
} else {
|
|
let z1z1 = self.z.square();
|
|
let u2 = rhs.x * z1z1;
|
|
let s2 = rhs.y * z1z1 * self.z;
|
|
|
|
if self.x == u2 {
|
|
if self.y == s2 {
|
|
self.double()
|
|
} else {
|
|
$name::identity()
|
|
}
|
|
} else {
|
|
let h = u2 - self.x;
|
|
let hh = h.square();
|
|
let i = hh + hh;
|
|
let i = i + i;
|
|
let j = h * i;
|
|
let r = s2 - self.y;
|
|
let r = r + r;
|
|
let v = self.x * i;
|
|
let x3 = r.square() - j - v - v;
|
|
let j = self.y * j;
|
|
let j = j + j;
|
|
let y3 = r * (v - x3) - j;
|
|
let z3 = (self.z + h).square() - z1z1 - hh;
|
|
|
|
$name {
|
|
x: x3, y: y3, z: z3
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
impl<'a, 'b> Sub<&'a $name> for &'b $name {
|
|
type Output = $name;
|
|
|
|
fn sub(self, other: &'a $name) -> $name {
|
|
self + (-other)
|
|
}
|
|
}
|
|
|
|
impl<'a, 'b> Sub<&'a $name_affine> for &'b $name {
|
|
type Output = $name;
|
|
|
|
fn sub(self, other: &'a $name_affine) -> $name {
|
|
self + (-other)
|
|
}
|
|
}
|
|
|
|
#[allow(clippy::suspicious_arithmetic_impl)]
|
|
impl<'a, 'b> Mul<&'b $scalar> for &'a $name {
|
|
type Output = $name;
|
|
|
|
fn mul(self, other: &'b $scalar) -> Self::Output {
|
|
// TODO: make this faster
|
|
|
|
let mut acc = $name::identity();
|
|
|
|
// This is a simple double-and-add implementation of point
|
|
// multiplication, moving from most significant to least
|
|
// significant bit of the scalar.
|
|
//
|
|
// We don't use `PrimeFieldBits::.to_le_bits` here, because that would
|
|
// force users of this crate to depend on `bitvec` where they otherwise
|
|
// might not need to.
|
|
//
|
|
// NOTE: We skip the leading bit because it's always unset (we are turning
|
|
// the 32-byte repr into 256 bits, and $scalar::NUM_BITS = 255).
|
|
for bit in other
|
|
.to_repr()
|
|
.iter()
|
|
.rev()
|
|
.flat_map(|byte| (0..8).rev().map(move |i| Choice::from((byte >> i) & 1u8)))
|
|
.skip(1)
|
|
{
|
|
acc = acc.double();
|
|
acc = $name::conditional_select(&acc, &(acc + self), bit);
|
|
}
|
|
|
|
acc
|
|
}
|
|
}
|
|
|
|
impl<'a> Neg for &'a $name_affine {
|
|
type Output = $name_affine;
|
|
|
|
fn neg(self) -> $name_affine {
|
|
$name_affine {
|
|
x: self.x,
|
|
y: -self.y,
|
|
}
|
|
}
|
|
}
|
|
|
|
impl Neg for $name_affine {
|
|
type Output = $name_affine;
|
|
|
|
fn neg(self) -> $name_affine {
|
|
-&self
|
|
}
|
|
}
|
|
|
|
impl<'a, 'b> Add<&'a $name> for &'b $name_affine {
|
|
type Output = $name;
|
|
|
|
fn add(self, rhs: &'a $name) -> $name {
|
|
rhs + self
|
|
}
|
|
}
|
|
|
|
impl<'a, 'b> Add<&'a $name_affine> for &'b $name_affine {
|
|
type Output = $name;
|
|
|
|
fn add(self, rhs: &'a $name_affine) -> $name {
|
|
if bool::from(self.is_identity()) {
|
|
rhs.to_curve()
|
|
} else if bool::from(rhs.is_identity()) {
|
|
self.to_curve()
|
|
} else {
|
|
if self.x == rhs.x {
|
|
if self.y == rhs.y {
|
|
self.to_curve().double()
|
|
} else {
|
|
$name::identity()
|
|
}
|
|
} else {
|
|
let h = rhs.x - self.x;
|
|
let hh = h.square();
|
|
let i = hh + hh;
|
|
let i = i + i;
|
|
let j = h * i;
|
|
let r = rhs.y - self.y;
|
|
let r = r + r;
|
|
let v = self.x * i;
|
|
let x3 = r.square() - j - v - v;
|
|
let j = self.y * j;
|
|
let j = j + j;
|
|
let y3 = r * (v - x3) - j;
|
|
let z3 = h + h;
|
|
|
|
$name {
|
|
x: x3, y: y3, z: z3
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
impl<'a, 'b> Sub<&'a $name_affine> for &'b $name_affine {
|
|
type Output = $name;
|
|
|
|
fn sub(self, other: &'a $name_affine) -> $name {
|
|
self + (-other)
|
|
}
|
|
}
|
|
|
|
impl<'a, 'b> Sub<&'a $name> for &'b $name_affine {
|
|
type Output = $name;
|
|
|
|
fn sub(self, other: &'a $name) -> $name {
|
|
self + (-other)
|
|
}
|
|
}
|
|
|
|
#[allow(clippy::suspicious_arithmetic_impl)]
|
|
impl<'a, 'b> Mul<&'b $scalar> for &'a $name_affine {
|
|
type Output = $name;
|
|
|
|
fn mul(self, other: &'b $scalar) -> Self::Output {
|
|
// TODO: make this faster
|
|
|
|
let mut acc = $name::identity();
|
|
|
|
// This is a simple double-and-add implementation of point
|
|
// multiplication, moving from most significant to least
|
|
// significant bit of the scalar.
|
|
//
|
|
// We don't use `PrimeFieldBits::.to_le_bits` here, because that would
|
|
// force users of this crate to depend on `bitvec` where they otherwise
|
|
// might not need to.
|
|
//
|
|
// NOTE: We skip the leading bit because it's always unset (we are turning
|
|
// the 32-byte repr into 256 bits, and $scalar::NUM_BITS = 255).
|
|
for bit in other
|
|
.to_repr()
|
|
.iter()
|
|
.rev()
|
|
.flat_map(|byte| (0..8).rev().map(move |i| Choice::from((byte >> i) & 1u8)))
|
|
.skip(1)
|
|
{
|
|
acc = acc.double();
|
|
acc = $name::conditional_select(&acc, &(acc + self), bit);
|
|
}
|
|
|
|
acc
|
|
}
|
|
}
|
|
|
|
impl PrimeCurveAffine for $name_affine {
|
|
type Curve = $name;
|
|
type Scalar = $scalar;
|
|
|
|
impl_affine_curve_specific!($name, $base, $curve_type);
|
|
|
|
fn identity() -> Self {
|
|
Self {
|
|
x: $base::zero(),
|
|
y: $base::zero(),
|
|
}
|
|
}
|
|
|
|
fn is_identity(&self) -> Choice {
|
|
self.x.is_zero() & self.y.is_zero()
|
|
}
|
|
|
|
fn to_curve(&self) -> Self::Curve {
|
|
$name {
|
|
x: self.x,
|
|
y: self.y,
|
|
z: $base::conditional_select(&$base::one(), &$base::zero(), self.is_identity()),
|
|
}
|
|
}
|
|
}
|
|
|
|
impl group::cofactor::CofactorCurveAffine for $name_affine {
|
|
type Curve = $name;
|
|
type Scalar = $scalar;
|
|
|
|
fn identity() -> Self {
|
|
<Self as PrimeCurveAffine>::identity()
|
|
}
|
|
|
|
fn generator() -> Self {
|
|
<Self as PrimeCurveAffine>::generator()
|
|
}
|
|
|
|
fn is_identity(&self) -> Choice {
|
|
<Self as PrimeCurveAffine>::is_identity(self)
|
|
}
|
|
|
|
fn to_curve(&self) -> Self::Curve {
|
|
<Self as PrimeCurveAffine>::to_curve(self)
|
|
}
|
|
}
|
|
|
|
impl GroupEncoding for $name_affine {
|
|
type Repr = [u8; 32];
|
|
|
|
fn from_bytes(bytes: &[u8; 32]) -> CtOption<Self> {
|
|
let mut tmp = *bytes;
|
|
let ysign = Choice::from(tmp[31] >> 7);
|
|
tmp[31] &= 0b0111_1111;
|
|
|
|
$base::from_repr(tmp).and_then(|x| {
|
|
CtOption::new(Self::identity(), x.is_zero() & (!ysign)).or_else(|| {
|
|
let x3 = x.square() * x;
|
|
(x3 + $name::curve_constant_b()).sqrt().and_then(|y| {
|
|
let sign = y.is_odd();
|
|
|
|
let y = $base::conditional_select(&y, &-y, ysign ^ sign);
|
|
|
|
CtOption::new(
|
|
$name_affine {
|
|
x,
|
|
y,
|
|
},
|
|
Choice::from(1u8),
|
|
)
|
|
})
|
|
})
|
|
})
|
|
}
|
|
|
|
fn from_bytes_unchecked(bytes: &Self::Repr) -> CtOption<Self> {
|
|
// We can't avoid curve checks when parsing a compressed encoding.
|
|
Self::from_bytes(bytes)
|
|
}
|
|
|
|
fn to_bytes(&self) -> [u8; 32] {
|
|
// TODO: not constant time
|
|
if bool::from(self.is_identity()) {
|
|
[0; 32]
|
|
} else {
|
|
let (x, y) = (self.x, self.y);
|
|
let sign = y.is_odd().unwrap_u8() << 7;
|
|
let mut xbytes = x.to_repr();
|
|
xbytes[31] |= sign;
|
|
xbytes
|
|
}
|
|
}
|
|
}
|
|
|
|
#[cfg(feature = "alloc")]
|
|
#[cfg_attr(docsrs, doc(cfg(feature = "alloc")))]
|
|
impl CurveAffine for $name_affine {
|
|
type ScalarExt = $scalar;
|
|
type Base = $base;
|
|
type CurveExt = $name;
|
|
|
|
fn is_on_curve(&self) -> Choice {
|
|
// y^2 - x^3 - ax ?= b
|
|
(self.y.square() - (self.x.square() + &$name::curve_constant_a()) * self.x).ct_eq(&$name::curve_constant_b())
|
|
| self.is_identity()
|
|
}
|
|
|
|
fn coordinates(&self) -> CtOption<Coordinates<Self>> {
|
|
CtOption::new(Coordinates { x: self.x, y: self.y }, !self.is_identity())
|
|
}
|
|
|
|
fn from_xy(x: Self::Base, y: Self::Base) -> CtOption<Self> {
|
|
let p = $name_affine {
|
|
x, y,
|
|
};
|
|
CtOption::new(p, p.is_on_curve())
|
|
}
|
|
|
|
fn a() -> Self::Base {
|
|
$name::curve_constant_a()
|
|
}
|
|
|
|
fn b() -> Self::Base {
|
|
$name::curve_constant_b()
|
|
}
|
|
}
|
|
|
|
impl Default for $name_affine {
|
|
fn default() -> $name_affine {
|
|
$name_affine::identity()
|
|
}
|
|
}
|
|
|
|
impl<'a> From<&'a $name> for $name_affine {
|
|
fn from(p: &'a $name) -> $name_affine {
|
|
p.to_affine()
|
|
}
|
|
}
|
|
|
|
impl From<$name> for $name_affine {
|
|
fn from(p: $name) -> $name_affine {
|
|
p.to_affine()
|
|
}
|
|
}
|
|
|
|
impl ConstantTimeEq for $name_affine {
|
|
fn ct_eq(&self, other: &Self) -> Choice {
|
|
self.x.ct_eq(&other.x) & self.y.ct_eq(&other.y)
|
|
}
|
|
}
|
|
|
|
impl PartialEq for $name_affine {
|
|
fn eq(&self, other: &Self) -> bool {
|
|
self.ct_eq(other).into()
|
|
}
|
|
}
|
|
|
|
impl cmp::Eq for $name_affine {}
|
|
|
|
impl ConditionallySelectable for $name_affine {
|
|
fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
|
|
$name_affine {
|
|
x: $base::conditional_select(&a.x, &b.x, choice),
|
|
y: $base::conditional_select(&a.y, &b.y, choice),
|
|
}
|
|
}
|
|
}
|
|
|
|
impl_binops_additive!($name, $name);
|
|
impl_binops_additive!($name, $name_affine);
|
|
impl_binops_additive_specify_output!($name_affine, $name_affine, $name);
|
|
impl_binops_additive_specify_output!($name_affine, $name, $name);
|
|
impl_binops_multiplicative!($name, $scalar);
|
|
impl_binops_multiplicative_mixed!($name_affine, $scalar, $name);
|
|
|
|
#[cfg(feature = "gpu")]
|
|
impl ec_gpu::GpuName for $name_affine {
|
|
fn name() -> alloc::string::String {
|
|
ec_gpu::name!()
|
|
}
|
|
}
|
|
};
|
|
}
|
|
|
|
macro_rules! impl_projective_curve_specific {
|
|
($name:ident, $base:ident, special_a0_b5) => {
|
|
fn generator() -> Self {
|
|
// NOTE: This is specific to b = 5
|
|
|
|
const NEGATIVE_ONE: $base = $base::neg(&$base::one());
|
|
const TWO: $base = $base::from_raw([2, 0, 0, 0]);
|
|
|
|
Self {
|
|
x: NEGATIVE_ONE,
|
|
y: TWO,
|
|
z: $base::one(),
|
|
}
|
|
}
|
|
|
|
fn double(&self) -> Self {
|
|
// http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#doubling-dbl-2009-l
|
|
//
|
|
// There are no points of order 2.
|
|
|
|
let a = self.x.square();
|
|
let b = self.y.square();
|
|
let c = b.square();
|
|
let d = self.x + b;
|
|
let d = d.square();
|
|
let d = d - a - c;
|
|
let d = d + d;
|
|
let e = a + a + a;
|
|
let f = e.square();
|
|
let z3 = self.z * self.y;
|
|
let z3 = z3 + z3;
|
|
let x3 = f - (d + d);
|
|
let c = c + c;
|
|
let c = c + c;
|
|
let c = c + c;
|
|
let y3 = e * (d - x3) - c;
|
|
|
|
let tmp = $name {
|
|
x: x3,
|
|
y: y3,
|
|
z: z3,
|
|
};
|
|
|
|
$name::conditional_select(&tmp, &$name::identity(), self.is_identity())
|
|
}
|
|
};
|
|
($name:ident, $base:ident, general) => {
|
|
/// Unimplemented: there is no standard generator for this curve.
|
|
fn generator() -> Self {
|
|
unimplemented!()
|
|
}
|
|
|
|
fn double(&self) -> Self {
|
|
// http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-dbl-2007-bl
|
|
//
|
|
// There are no points of order 2.
|
|
|
|
let xx = self.x.square();
|
|
let yy = self.y.square();
|
|
let a = yy.square();
|
|
let zz = self.z.square();
|
|
let s = ((self.x + yy).square() - xx - a).double();
|
|
let m = xx.double() + xx + $name::curve_constant_a() * zz.square();
|
|
let x3 = m.square() - s.double();
|
|
let a = a.double();
|
|
let a = a.double();
|
|
let a = a.double();
|
|
let y3 = m * (s - x3) - a;
|
|
let z3 = (self.y + self.z).square() - yy - zz;
|
|
|
|
let tmp = $name {
|
|
x: x3,
|
|
y: y3,
|
|
z: z3,
|
|
};
|
|
|
|
$name::conditional_select(&tmp, &$name::identity(), self.is_identity())
|
|
}
|
|
};
|
|
}
|
|
|
|
#[cfg(feature = "alloc")]
|
|
macro_rules! impl_projective_curve_ext {
|
|
($name:ident, $iso:ident, $base:ident, special_a0_b5) => {
|
|
fn hash_to_curve<'a>(domain_prefix: &'a str) -> Box<dyn Fn(&[u8]) -> Self + 'a> {
|
|
use super::hashtocurve;
|
|
|
|
Box::new(move |message| {
|
|
let mut us = [Field::ZERO; 2];
|
|
hashtocurve::hash_to_field($name::CURVE_ID, domain_prefix, message, &mut us);
|
|
let q0 = hashtocurve::map_to_curve_simple_swu::<$base, $name, $iso>(
|
|
&us[0],
|
|
$name::THETA,
|
|
$name::Z,
|
|
);
|
|
let q1 = hashtocurve::map_to_curve_simple_swu::<$base, $name, $iso>(
|
|
&us[1],
|
|
$name::THETA,
|
|
$name::Z,
|
|
);
|
|
let r = q0 + &q1;
|
|
debug_assert!(bool::from(r.is_on_curve()));
|
|
hashtocurve::iso_map::<$base, $name, $iso>(&r, &$name::ISOGENY_CONSTANTS)
|
|
})
|
|
}
|
|
|
|
/// Apply the curve endomorphism by multiplying the x-coordinate
|
|
/// by an element of multiplicative order 3.
|
|
fn endo(&self) -> Self {
|
|
$name {
|
|
x: self.x * $base::ZETA,
|
|
y: self.y,
|
|
z: self.z,
|
|
}
|
|
}
|
|
};
|
|
($name:ident, $iso:ident, $base:ident, general) => {
|
|
/// Unimplemented: hashing to this curve is not supported
|
|
fn hash_to_curve<'a>(_domain_prefix: &'a str) -> Box<dyn Fn(&[u8]) -> Self + 'a> {
|
|
unimplemented!()
|
|
}
|
|
|
|
/// Unimplemented: no endomorphism is supported for this curve.
|
|
fn endo(&self) -> Self {
|
|
unimplemented!()
|
|
}
|
|
};
|
|
}
|
|
|
|
macro_rules! impl_affine_curve_specific {
|
|
($name:ident, $base:ident, special_a0_b5) => {
|
|
fn generator() -> Self {
|
|
// NOTE: This is specific to b = 5
|
|
|
|
const NEGATIVE_ONE: $base = $base::neg(&$base::from_raw([1, 0, 0, 0]));
|
|
const TWO: $base = $base::from_raw([2, 0, 0, 0]);
|
|
|
|
Self {
|
|
x: NEGATIVE_ONE,
|
|
y: TWO,
|
|
}
|
|
}
|
|
};
|
|
($name:ident, $base:ident, general) => {
|
|
/// Unimplemented: there is no standard generator for this curve.
|
|
fn generator() -> Self {
|
|
unimplemented!()
|
|
}
|
|
};
|
|
}
|
|
|
|
new_curve_impl!(
|
|
(pub),
|
|
Ep,
|
|
EpAffine,
|
|
IsoEp,
|
|
Fp,
|
|
Fq,
|
|
"pallas",
|
|
[0, 0, 0, 0],
|
|
[5, 0, 0, 0],
|
|
special_a0_b5
|
|
);
|
|
new_curve_impl!(
|
|
(pub),
|
|
Eq,
|
|
EqAffine,
|
|
IsoEq,
|
|
Fq,
|
|
Fp,
|
|
"vesta",
|
|
[0, 0, 0, 0],
|
|
[5, 0, 0, 0],
|
|
special_a0_b5
|
|
);
|
|
new_curve_impl!(
|
|
(pub(crate)),
|
|
IsoEp,
|
|
IsoEpAffine,
|
|
Ep,
|
|
Fp,
|
|
Fq,
|
|
"iso-pallas",
|
|
[
|
|
0x92bb4b0b657a014b,
|
|
0xb74134581a27a59f,
|
|
0x49be2d7258370742,
|
|
0x18354a2eb0ea8c9c,
|
|
],
|
|
[1265, 0, 0, 0],
|
|
general
|
|
);
|
|
new_curve_impl!(
|
|
(pub(crate)),
|
|
IsoEq,
|
|
IsoEqAffine,
|
|
Eq,
|
|
Fq,
|
|
Fp,
|
|
"iso-vesta",
|
|
[
|
|
0xc515ad7242eaa6b1,
|
|
0x9673928c7d01b212,
|
|
0x81639c4d96f78773,
|
|
0x267f9b2ee592271a,
|
|
],
|
|
[1265, 0, 0, 0],
|
|
general
|
|
);
|
|
|
|
impl Ep {
|
|
/// Constants used for computing the isogeny from IsoEp to Ep.
|
|
pub const ISOGENY_CONSTANTS: [Fp; 13] = [
|
|
Fp::from_raw([
|
|
0x775f6034aaaaaaab,
|
|
0x4081775473d8375b,
|
|
0xe38e38e38e38e38e,
|
|
0x0e38e38e38e38e38,
|
|
]),
|
|
Fp::from_raw([
|
|
0x8cf863b02814fb76,
|
|
0x0f93b82ee4b99495,
|
|
0x267c7ffa51cf412a,
|
|
0x3509afd51872d88e,
|
|
]),
|
|
Fp::from_raw([
|
|
0x0eb64faef37ea4f7,
|
|
0x380af066cfeb6d69,
|
|
0x98c7d7ac3d98fd13,
|
|
0x17329b9ec5253753,
|
|
]),
|
|
Fp::from_raw([
|
|
0xeebec06955555580,
|
|
0x8102eea8e7b06eb6,
|
|
0xc71c71c71c71c71c,
|
|
0x1c71c71c71c71c71,
|
|
]),
|
|
Fp::from_raw([
|
|
0xc47f2ab668bcd71f,
|
|
0x9c434ac1c96b6980,
|
|
0x5a607fcce0494a79,
|
|
0x1d572e7ddc099cff,
|
|
]),
|
|
Fp::from_raw([
|
|
0x2aa3af1eae5b6604,
|
|
0xb4abf9fb9a1fc81c,
|
|
0x1d13bf2a7f22b105,
|
|
0x325669becaecd5d1,
|
|
]),
|
|
Fp::from_raw([
|
|
0x5ad985b5e38e38e4,
|
|
0x7642b01ad461bad2,
|
|
0x4bda12f684bda12f,
|
|
0x1a12f684bda12f68,
|
|
]),
|
|
Fp::from_raw([
|
|
0xc67c31d8140a7dbb,
|
|
0x07c9dc17725cca4a,
|
|
0x133e3ffd28e7a095,
|
|
0x1a84d7ea8c396c47,
|
|
]),
|
|
Fp::from_raw([
|
|
0x02e2be87d225b234,
|
|
0x1765e924f7459378,
|
|
0x303216cce1db9ff1,
|
|
0x3fb98ff0d2ddcadd,
|
|
]),
|
|
Fp::from_raw([
|
|
0x93e53ab371c71c4f,
|
|
0x0ac03e8e134eb3e4,
|
|
0x7b425ed097b425ed,
|
|
0x025ed097b425ed09,
|
|
]),
|
|
Fp::from_raw([
|
|
0x5a28279b1d1b42ae,
|
|
0x5941a3a4a97aa1b3,
|
|
0x0790bfb3506defb6,
|
|
0x0c02c5bcca0e6b7f,
|
|
]),
|
|
Fp::from_raw([
|
|
0x4d90ab820b12320a,
|
|
0xd976bbfabbc5661d,
|
|
0x573b3d7f7d681310,
|
|
0x17033d3c60c68173,
|
|
]),
|
|
Fp::from_raw([
|
|
0x992d30ecfffffde5,
|
|
0x224698fc094cf91b,
|
|
0x0000000000000000,
|
|
0x4000000000000000,
|
|
]),
|
|
];
|
|
|
|
/// Z = -13
|
|
pub const Z: Fp = Fp::from_raw([
|
|
0x992d30ecfffffff4,
|
|
0x224698fc094cf91b,
|
|
0x0000000000000000,
|
|
0x4000000000000000,
|
|
]);
|
|
|
|
/// `(F::ROOT_OF_UNITY.invert().unwrap() * z).sqrt().unwrap()`
|
|
pub const THETA: Fp = Fp::from_raw([
|
|
0xca330bcc09ac318e,
|
|
0x51f64fc4dc888857,
|
|
0x4647aef782d5cdc8,
|
|
0x0f7bdb65814179b4,
|
|
]);
|
|
}
|
|
|
|
impl Eq {
|
|
/// Constants used for computing the isogeny from IsoEq to Eq.
|
|
pub const ISOGENY_CONSTANTS: [Fq; 13] = [
|
|
Fq::from_raw([
|
|
0x43cd42c800000001,
|
|
0x0205dd51cfa0961a,
|
|
0x8e38e38e38e38e39,
|
|
0x38e38e38e38e38e3,
|
|
]),
|
|
Fq::from_raw([
|
|
0x8b95c6aaf703bcc5,
|
|
0x216b8861ec72bd5d,
|
|
0xacecf10f5f7c09a2,
|
|
0x1d935247b4473d17,
|
|
]),
|
|
Fq::from_raw([
|
|
0xaeac67bbeb586a3d,
|
|
0xd59d03d23b39cb11,
|
|
0xed7ee4a9cdf78f8f,
|
|
0x18760c7f7a9ad20d,
|
|
]),
|
|
Fq::from_raw([
|
|
0xfb539a6f0000002b,
|
|
0xe1c521a795ac8356,
|
|
0x1c71c71c71c71c71,
|
|
0x31c71c71c71c71c7,
|
|
]),
|
|
Fq::from_raw([
|
|
0xb7284f7eaf21a2e9,
|
|
0xa3ad678129b604d3,
|
|
0x1454798a5b5c56b2,
|
|
0x0a2de485568125d5,
|
|
]),
|
|
Fq::from_raw([
|
|
0xf169c187d2533465,
|
|
0x30cd6d53df49d235,
|
|
0x0c621de8b91c242a,
|
|
0x14735171ee542778,
|
|
]),
|
|
Fq::from_raw([
|
|
0x6bef1642aaaaaaab,
|
|
0x5601f4709a8adcb3,
|
|
0xda12f684bda12f68,
|
|
0x12f684bda12f684b,
|
|
]),
|
|
Fq::from_raw([
|
|
0x8bee58e5fb81de63,
|
|
0x21d910aefb03b31d,
|
|
0xd6767887afbe04d1,
|
|
0x2ec9a923da239e8b,
|
|
]),
|
|
Fq::from_raw([
|
|
0x4986913ab4443034,
|
|
0x97a3ca5c24e9ea63,
|
|
0x66d1466e9de10e64,
|
|
0x19b0d87e16e25788,
|
|
]),
|
|
Fq::from_raw([
|
|
0x8f64842c55555533,
|
|
0x8bc32d36fb21a6a3,
|
|
0x425ed097b425ed09,
|
|
0x1ed097b425ed097b,
|
|
]),
|
|
Fq::from_raw([
|
|
0x58dfecce86b2745e,
|
|
0x06a767bfc35b5bac,
|
|
0x9e7eb64f890a820c,
|
|
0x2f44d6c801c1b8bf,
|
|
]),
|
|
Fq::from_raw([
|
|
0xd43d449776f99d2f,
|
|
0x926847fb9ddd76a1,
|
|
0x252659ba2b546c7e,
|
|
0x3d59f455cafc7668,
|
|
]),
|
|
Fq::from_raw([
|
|
0x8c46eb20fffffde5,
|
|
0x224698fc0994a8dd,
|
|
0x0000000000000000,
|
|
0x4000000000000000,
|
|
]),
|
|
];
|
|
|
|
/// Z = -13
|
|
pub const Z: Fq = Fq::from_raw([
|
|
0x8c46eb20fffffff4,
|
|
0x224698fc0994a8dd,
|
|
0x0000000000000000,
|
|
0x4000000000000000,
|
|
]);
|
|
|
|
/// `(F::ROOT_OF_UNITY.invert().unwrap() * z).sqrt().unwrap()`
|
|
pub const THETA: Fq = Fq::from_raw([
|
|
0x632cae9872df1b5d,
|
|
0x38578ccadf03ac27,
|
|
0x53c3808d9e2f2357,
|
|
0x2b3483a1ee9a382f,
|
|
]);
|
|
}
|