1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

//! Traits for arithmetic operations on elliptic curve field elements.

pub use core::ops::{Add, AddAssign, Mul, Neg, Sub, SubAssign};

use crypto_bigint::{ArrayEncoding, ByteArray, Integer};

#[cfg(feature = "arithmetic")]
use {group::Group, subtle::CtOption};

#[cfg(feature = "digest")]
use digest::FixedOutput;

/// Perform an inversion on a field element (i.e. base field element or scalar)
pub trait Invert {
    /// Field element type
    type Output;

    /// Invert a field element.
    fn invert(&self) -> Self::Output;
}

#[cfg(feature = "arithmetic")]
impl<F: ff::Field> Invert for F {
    type Output = CtOption<F>;

    fn invert(&self) -> CtOption<F> {
        ff::Field::invert(self)
    }
}

/// Linear combination.
///
/// This trait enables crates to provide an optimized implementation of
/// linear combinations (e.g. Shamir's Trick), or otherwise provides a default
/// non-optimized implementation.
// TODO(tarcieri): replace this with a trait from the `group` crate? (see zkcrypto/group#25)
#[cfg(feature = "arithmetic")]
#[cfg_attr(docsrs, doc(cfg(feature = "arithmetic")))]
pub trait LinearCombination: Group {
    /// Calculates `x * k + y * l`.
    fn lincomb(x: &Self, k: &Self::Scalar, y: &Self, l: &Self::Scalar) -> Self {
        (*x * k) + (*y * l)
    }
}

/// Modular reduction.
pub trait Reduce<UInt: Integer + ArrayEncoding>: Sized {
    /// Perform a modular reduction, returning a field element.
    fn from_uint_reduced(n: UInt) -> Self;

    /// Interpret the given byte array as a big endian integer and perform
    /// a modular reduction.
    fn from_be_bytes_reduced(bytes: ByteArray<UInt>) -> Self {
        Self::from_uint_reduced(UInt::from_be_byte_array(bytes))
    }

    /// Interpret the given byte array as a little endian integer and perform a
    /// modular reduction.
    fn from_le_bytes_reduced(bytes: ByteArray<UInt>) -> Self {
        Self::from_uint_reduced(UInt::from_le_byte_array(bytes))
    }

    /// Interpret a digest as a big endian integer and perform a modular
    /// reduction.
    #[cfg(feature = "digest")]
    #[cfg_attr(docsrs, doc(cfg(feature = "digest")))]
    fn from_be_digest_reduced<D>(digest: D) -> Self
    where
        D: FixedOutput<OutputSize = UInt::ByteSize>,
    {
        Self::from_be_bytes_reduced(digest.finalize_fixed())
    }

    /// Interpret a digest as a little endian integer and perform a modular
    /// reduction.
    #[cfg(feature = "digest")]
    #[cfg_attr(docsrs, doc(cfg(feature = "digest")))]
    fn from_le_digest_reduced<D>(digest: D) -> Self
    where
        D: FixedOutput<OutputSize = UInt::ByteSize>,
    {
        Self::from_le_bytes_reduced(digest.finalize_fixed())
    }
}

/// Modular reduction to a non-zero output.
///
/// This trait is primarily intended for use by curve implementations such
/// as the `k256` and `p256` crates.
///
/// End users should use the [`Reduce`] impl on
/// [`NonZeroScalar`][`crate::NonZeroScalar`] instead.
pub trait ReduceNonZero<UInt: Integer + ArrayEncoding>: Sized {
    /// Perform a modular reduction, returning a field element.
    fn from_uint_reduced_nonzero(n: UInt) -> Self;
}