elliptic_curve/
ops.rs

1//! Traits for arithmetic operations on elliptic curve field elements.
2
3pub use core::ops::{Add, AddAssign, Mul, Neg, Shr, ShrAssign, Sub, SubAssign};
4
5use crypto_bigint::Integer;
6use group::Group;
7use subtle::{Choice, ConditionallySelectable, CtOption};
8
9#[cfg(feature = "alloc")]
10use alloc::vec::Vec;
11
12/// Perform an inversion on a field element (i.e. base field element or scalar)
13pub trait Invert {
14    /// Field element type
15    type Output;
16
17    /// Invert a field element.
18    fn invert(&self) -> Self::Output;
19
20    /// Invert a field element in variable time.
21    ///
22    /// ⚠️ WARNING!
23    ///
24    /// This method should not be used with secret values, as its variable-time
25    /// operation can potentially leak secrets through sidechannels.
26    fn invert_vartime(&self) -> Self::Output {
27        // Fall back on constant-time implementation by default.
28        self.invert()
29    }
30}
31
32/// Perform a batched inversion on a sequence of field elements (i.e. base field elements or scalars)
33/// at an amortized cost that should be practically as efficient as a single inversion.
34pub trait BatchInvert<FieldElements: ?Sized>: Invert + Sized {
35    /// The output of batch inversion. A container of field elements.
36    type Output: AsRef<[Self]>;
37
38    /// Invert a batch of field elements.
39    fn batch_invert(
40        field_elements: &FieldElements,
41    ) -> CtOption<<Self as BatchInvert<FieldElements>>::Output>;
42}
43
44impl<const N: usize, T> BatchInvert<[T; N]> for T
45where
46    T: Invert<Output = CtOption<Self>>
47        + Mul<Self, Output = Self>
48        + Copy
49        + Default
50        + ConditionallySelectable,
51{
52    type Output = [Self; N];
53
54    fn batch_invert(field_elements: &[Self; N]) -> CtOption<[Self; N]> {
55        let mut field_elements_multiples = [Self::default(); N];
56        let mut field_elements_multiples_inverses = [Self::default(); N];
57        let mut field_elements_inverses = [Self::default(); N];
58
59        let inversion_succeeded = invert_batch_internal(
60            field_elements,
61            &mut field_elements_multiples,
62            &mut field_elements_multiples_inverses,
63            &mut field_elements_inverses,
64        );
65
66        CtOption::new(field_elements_inverses, inversion_succeeded)
67    }
68}
69
70#[cfg(feature = "alloc")]
71impl<T> BatchInvert<[T]> for T
72where
73    T: Invert<Output = CtOption<Self>>
74        + Mul<Self, Output = Self>
75        + Copy
76        + Default
77        + ConditionallySelectable,
78{
79    type Output = Vec<Self>;
80
81    fn batch_invert(field_elements: &[Self]) -> CtOption<Vec<Self>> {
82        let mut field_elements_multiples: Vec<Self> = vec![Self::default(); field_elements.len()];
83        let mut field_elements_multiples_inverses: Vec<Self> =
84            vec![Self::default(); field_elements.len()];
85        let mut field_elements_inverses: Vec<Self> = vec![Self::default(); field_elements.len()];
86
87        let inversion_succeeded = invert_batch_internal(
88            field_elements,
89            field_elements_multiples.as_mut(),
90            field_elements_multiples_inverses.as_mut(),
91            field_elements_inverses.as_mut(),
92        );
93
94        CtOption::new(
95            field_elements_inverses.into_iter().collect(),
96            inversion_succeeded,
97        )
98    }
99}
100
101/// Implements "Montgomery's trick", a trick for computing many modular inverses at once.
102///
103/// "Montgomery's trick" works by reducing the problem of computing `n` inverses
104/// to computing a single inversion, plus some storage and `O(n)` extra multiplications.
105///
106/// See: https://iacr.org/archive/pkc2004/29470042/29470042.pdf section 2.2.
107fn invert_batch_internal<
108    T: Invert<Output = CtOption<T>> + Mul<T, Output = T> + Default + ConditionallySelectable,
109>(
110    field_elements: &[T],
111    field_elements_multiples: &mut [T],
112    field_elements_multiples_inverses: &mut [T],
113    field_elements_inverses: &mut [T],
114) -> Choice {
115    let batch_size = field_elements.len();
116    if batch_size == 0
117        || batch_size != field_elements_multiples.len()
118        || batch_size != field_elements_multiples_inverses.len()
119    {
120        return Choice::from(0);
121    }
122
123    field_elements_multiples[0] = field_elements[0];
124    for i in 1..batch_size {
125        // $ a_n = a_{n-1}*x_n $
126        field_elements_multiples[i] = field_elements_multiples[i - 1] * field_elements[i];
127    }
128
129    field_elements_multiples[batch_size - 1]
130        .invert()
131        .map(|multiple_of_inverses_of_all_field_elements| {
132            field_elements_multiples_inverses[batch_size - 1] =
133                multiple_of_inverses_of_all_field_elements;
134            for i in (1..batch_size).rev() {
135                // $ a_{n-1} = {a_n}^{-1}*x_n $
136                field_elements_multiples_inverses[i - 1] =
137                    field_elements_multiples_inverses[i] * field_elements[i];
138            }
139
140            field_elements_inverses[0] = field_elements_multiples_inverses[0];
141            for i in 1..batch_size {
142                // $ {x_n}^{-1} = a_{n}^{-1}*a_{n-1} $
143                field_elements_inverses[i] =
144                    field_elements_multiples_inverses[i] * field_elements_multiples[i - 1];
145            }
146        })
147        .is_some()
148}
149
150/// Linear combination.
151///
152/// This trait enables crates to provide an optimized implementation of
153/// linear combinations (e.g. Shamir's Trick), or otherwise provides a default
154/// non-optimized implementation.
155// TODO(tarcieri): replace this with a trait from the `group` crate? (see zkcrypto/group#25)
156pub trait LinearCombination: Group {
157    /// Calculates `x * k + y * l`.
158    fn lincomb(x: &Self, k: &Self::Scalar, y: &Self, l: &Self::Scalar) -> Self {
159        (*x * k) + (*y * l)
160    }
161}
162
163/// Linear combination (extended version).
164///
165/// This trait enables providing an optimized implementation of
166/// linear combinations (e.g. Shamir's Trick).
167// TODO(tarcieri): replace the current `LinearCombination` with this in the next release
168pub trait LinearCombinationExt<PointsAndScalars>: group::Curve
169where
170    PointsAndScalars: AsRef<[(Self, Self::Scalar)]> + ?Sized,
171{
172    /// Calculates `x1 * k1 + ... + xn * kn`.
173    fn lincomb_ext(points_and_scalars: &PointsAndScalars) -> Self {
174        points_and_scalars
175            .as_ref()
176            .iter()
177            .copied()
178            .map(|(point, scalar)| point * scalar)
179            .sum()
180    }
181}
182
183/// Blanket impl of the legacy [`LinearCombination`] trait for types which impl the new
184/// [`LinearCombinationExt`] trait for 2-element arrays.
185impl<P: LinearCombinationExt<[(P, Self::Scalar); 2]>> LinearCombination for P {
186    fn lincomb(x: &Self, k: &Self::Scalar, y: &Self, l: &Self::Scalar) -> Self {
187        Self::lincomb_ext(&[(*x, *k), (*y, *l)])
188    }
189}
190
191/// Multiplication by the generator.
192///
193/// May use optimizations (e.g. precomputed tables) when available.
194// TODO(tarcieri): replace this with `Group::mul_by_generator``? (see zkcrypto/group#44)
195pub trait MulByGenerator: Group {
196    /// Multiply by the generator of the prime-order subgroup.
197    #[must_use]
198    fn mul_by_generator(scalar: &Self::Scalar) -> Self {
199        Self::generator() * scalar
200    }
201}
202
203/// Modular reduction.
204pub trait Reduce<Uint: Integer>: Sized {
205    /// Bytes used as input to [`Reduce::reduce_bytes`].
206    type Bytes: AsRef<[u8]>;
207
208    /// Perform a modular reduction, returning a field element.
209    fn reduce(n: Uint) -> Self;
210
211    /// Interpret the given bytes as an integer and perform a modular reduction.
212    fn reduce_bytes(bytes: &Self::Bytes) -> Self;
213}
214
215/// Modular reduction to a non-zero output.
216///
217/// This trait is primarily intended for use by curve implementations such
218/// as the `k256` and `p256` crates.
219///
220/// End users should use the [`Reduce`] impl on
221/// [`NonZeroScalar`][`crate::NonZeroScalar`] instead.
222pub trait ReduceNonZero<Uint: Integer>: Reduce<Uint> + Sized {
223    /// Perform a modular reduction, returning a field element.
224    fn reduce_nonzero(n: Uint) -> Self;
225
226    /// Interpret the given bytes as an integer and perform a modular reduction
227    /// to a non-zero output.
228    fn reduce_nonzero_bytes(bytes: &Self::Bytes) -> Self;
229}
elliptic_curve/ops.rs

elliptic_curve/
ops.rs
