elliptic_curve/
ops.rs

1//! Traits for arithmetic operations on elliptic curve field elements.
2
3pub use bigint::{Invert, Reduce, modular::Retrieve};
4pub use core::ops::{Add, AddAssign, Mul, MulAssign, Neg, Shr, ShrAssign, Sub, SubAssign};
5
6use crate::CurveGroup;
7use ff::{BatchInverter, Field};
8use group::Group;
9
10/// Perform a batched inversion on a slice of field elements (i.e. base field elements or scalars)
11/// at an amortized cost that should be practically as efficient as a single inversion, writing
12/// the field element inversions into `element`, and utilizing `scratch` as temporary storage.
13///
14/// Note: the [`ff`] crate also provides [`ff::BatchInvert`], however that trait has a hard
15/// requirement on `alloc` whereas this one is always available, even in `no_alloc` contexts.
16///
17/// # Panics
18/// If `elements` and `scratch` are not the same length.
19pub trait BatchInvert: Field {
20    /// Inverts each field element in `elements` (when non-zero). Zero-valued elements are
21    /// left as zero.
22    ///
23    /// `scratch_space` is a slice of field elements that can be freely overwritten.
24    ///
25    /// Returns the inverse of the product of all non-zero field elements.
26    ///
27    /// # Panics
28    /// If `elements.len() != scratch_space.len()`.
29    fn batch_invert_in_place(elements: &mut [Self], scratch_space: &mut [Self]) -> Self {
30        BatchInverter::invert_with_external_scratch(elements, scratch_space)
31    }
32
33    /// Variable-time batch inversion.
34    ///
35    /// <div class="warning">
36    /// <b>Security Warning</b>
37    ///
38    /// This should NOT be used on secret values!
39    /// </b>
40    fn batch_invert_in_place_vartime(elements: &mut [Self], scratch_space: &mut [Self]) -> Self {
41        // Call the constant-time implementation by default
42        Self::batch_invert_in_place(elements, scratch_space)
43    }
44}
45
46/// Perform a doubling (i.e. `self + self`).
47pub trait Double: Sized {
48    /// Double this value, returning the doubled result.
49    #[must_use]
50    fn double(&self) -> Self;
51
52    /// Double this value in-place, assigning `self + self` to `self`.
53    #[inline]
54    fn double_in_place(&mut self) {
55        *self = self.double();
56    }
57}
58
59/// Linear combination.
60///
61/// This trait enables optimized implementations of linear combinations (e.g. Shamir's Trick).
62///
63/// It's generic around `PointsAndScalars` to allow overlapping impls. For example, const generic
64/// impls can use the input size to determine the size needed to store temporary variables.
65pub trait LinearCombination<PointsAndScalars>: CurveGroup
66where
67    PointsAndScalars: AsRef<[(Self, Self::Scalar)]> + ?Sized,
68{
69    /// Calculates `x1 * k1 + ... + xn * kn`.
70    fn lincomb(points_and_scalars: &PointsAndScalars) -> Self {
71        points_and_scalars
72            .as_ref()
73            .iter()
74            .copied()
75            .map(|(point, scalar)| point * scalar)
76            .sum()
77    }
78
79    /// Calculates `x1 * k1 + ... + xn * kn`.
80    ///
81    /// This is equivalent to [`LinearCombination::lincomb`] except
82    /// that it may leak the value of the points and/or scalars due to
83    /// variable-time behavior.
84    fn lincomb_vartime(points_and_scalars: &PointsAndScalars) -> Self {
85        Self::lincomb(points_and_scalars)
86    }
87}
88
89/// Variable-time equivalent of the [`Mul`] trait.
90///
91/// Should always compute the same results as [`Mul`], but may provide a faster implementation.
92///
93/// <div class="warning">
94/// <b>Security Warning</b>
95///
96/// Variable-time operations should only be used on non-secret values, and may potentially leak
97/// secret values!
98/// </div>
99pub trait MulVartime<Rhs = Self>: Mul<Rhs> {
100    /// Multiply `self` by `rhs` in variable-time.
101    fn mul_vartime(self, rhs: Rhs) -> <Self as Mul<Rhs>>::Output;
102}
103
104/// Variable-time multiplication by the generator of the curve group.
105///
106/// <div class="warning">
107/// <b>Security Warning</b>
108///
109/// Variable-time operations should only be used on non-secret values, and may potentially leak
110/// secret values!
111/// </div>
112pub trait MulByGeneratorVartime: Group + for<'a> MulVartime<&'a Self::Scalar> {
113    /// Multiply by the generator of the prime-order subgroup.
114    ///
115    /// Variable-time equivalent of [`Group::mul_by_generator`].
116    fn mul_by_generator_vartime(scalar: &Self::Scalar) -> Self {
117        Self::generator().mul_vartime(scalar)
118    }
119
120    /// Multiply `a` by the generator of the prime-order subgroup, adding the result to the point
121    /// `P` multiplied by the scalar `b`, i.e. compute `aG + bP`.
122    ///
123    /// This operation is the core of many signature verification algorithms.
124    fn mul_by_generator_and_mul_add_vartime(a: &Self::Scalar, b: &Self::Scalar, p: &Self) -> Self {
125        Self::mul_by_generator_vartime(a) + p.mul_vartime(b)
126    }
127}
128
129/// Modular reduction to a non-zero output.
130///
131/// This trait is primarily intended for use by curve implementations such
132/// as the `k256` and `p256` crates.
133///
134/// End users should use the [`Reduce`] impl on
135/// [`NonZeroScalar`][`crate::NonZeroScalar`] instead.
136pub trait ReduceNonZero<T>: Reduce<T> {
137    /// Perform a modular reduction, returning a field element.
138    fn reduce_nonzero(n: &T) -> Self;
139}
elliptic_curve/ops.rs

elliptic_curve/
ops.rs
