lib.rs

#![no_std]
#![cfg_attr(docsrs, feature(doc_auto_cfg))]
#![doc(
    html_logo_url = "https://raw.githubusercontent.com/RustCrypto/meta/master/logo.svg",
    html_favicon_url = "https://raw.githubusercontent.com/RustCrypto/meta/master/logo.svg"
)]
#![forbid(unsafe_code)]
#![warn(missing_docs, rust_2018_idioms, unused_qualifications)]
#![doc = include_str!("../README.md")]

mod dev;
mod fiat;
mod monty;

pub use crate::monty::{MontyFieldElement, MontyFieldParams, compute_t};
pub use array::typenum::consts;
pub use bigint;
pub use bigint::hybrid_array as array;
pub use ff;
pub use rand_core;
pub use subtle;
pub use zeroize;

/// Byte order used when encoding/decoding field elements as bytestrings.
#[derive(Debug)]
pub enum ByteOrder {
    /// Big endian.
    BigEndian,

    /// Little endian.
    LittleEndian,
}

/// Implements a field element type whose internal representation is in
/// Montgomery form, providing a combination of trait impls and inherent impls
/// which are `const fn` where possible.
///
/// Accepts a set of `const fn` arithmetic operation functions as arguments.
///
/// # Inherent impls
/// - `const ZERO: Self`
/// - `const ONE: Self` (multiplicative identity)
/// - `pub fn from_bytes`
/// - `pub fn from_slice`
/// - `pub fn from_uint`
/// - `fn from_uint_unchecked`
/// - `pub fn to_bytes`
/// - `pub fn to_canonical`
/// - `pub fn is_odd`
/// - `pub fn is_zero`
/// - `pub fn double`
///
/// NOTE: field implementations must provide their own inherent impls of
/// the following methods in order for the code generated by this macro to
/// compile:
///
/// - `pub fn invert`
/// - `pub fn sqrt`
///
/// # Trait impls
/// - `ConditionallySelectable`
/// - `ConstantTimeEq`
/// - `ConstantTimeGreater`
/// - `ConstantTimeLess`
/// - `Default`
/// - `DefaultIsZeroes`
/// - `Eq`
/// - `Field`
/// - `PartialEq`
///
/// ## Ops
/// - `Add`
/// - `AddAssign`
/// - `Sub`
/// - `SubAssign`
/// - `Mul`
/// - `MulAssign`
/// - `Neg`
/// - `Shr`
/// - `ShrAssign`
/// - `Invert`
#[macro_export]
macro_rules! field_element_type {
    (
        $fe:tt,
        $bytes:ty,
        $uint:ty,
        $modulus:expr,
        $decode_uint:path,
        $encode_uint:path
    ) => {
        impl $fe {
            /// Zero element.
            pub const ZERO: Self = Self(<$uint>::ZERO);

            /// Multiplicative identity.
            pub const ONE: Self = Self::from_uint_unchecked(<$uint>::ONE);

            /// Create a [`
            #[doc = stringify!($fe)]
            /// `] from a canonical big-endian representation.
            pub fn from_bytes(repr: &$bytes) -> $crate::subtle::CtOption<Self> {
                Self::from_uint($decode_uint(repr))
            }

            /// Decode [`
            #[doc = stringify!($fe)]
            /// `] from a big endian byte slice.
            pub fn from_slice(slice: &[u8]) -> Option<Self> {
                let array = <$bytes>::try_from(slice).ok()?;
                Self::from_bytes(&array).into()
            }

            /// Decode [`
            #[doc = stringify!($fe)]
            /// `]
            /// from [`
            #[doc = stringify!($uint)]
            /// `] converting it into Montgomery form:
            ///
            /// ```text
            /// w * R^2 * R^-1 mod p = wR mod p
            /// ```
            pub fn from_uint(uint: $uint) -> $crate::subtle::CtOption<Self> {
                use $crate::subtle::ConstantTimeLess as _;
                let is_some = uint.ct_lt(&$modulus);
                $crate::subtle::CtOption::new(Self::from_uint_unchecked(uint), is_some)
            }

            /// Parse a [`
            #[doc = stringify!($fe)]
            /// `] from big endian hex-encoded bytes.
            ///
            /// Does *not* perform a check that the field element does not overflow the order.
            ///
            /// This method is primarily intended for defining internal constants.
            #[allow(dead_code)]
            pub(crate) const fn from_hex(hex: &str) -> Self {
                Self::from_uint_unchecked(<$uint>::from_be_hex(hex))
            }

            /// Convert a `u64` into a [`
            #[doc = stringify!($fe)]
            /// `].
            pub const fn from_u64(w: u64) -> Self {
                Self::from_uint_unchecked(<$uint>::from_u64(w))
            }

            /// Returns the big-endian encoding of this [`
            #[doc = stringify!($fe)]
            /// `].
            pub fn to_bytes(self) -> $bytes {
                $encode_uint(&self.to_canonical())
            }

            /// Determine if this [`
            #[doc = stringify!($fe)]
            /// `] is odd in the SEC1 sense: `self mod 2 == 1`.
            ///
            /// # Returns
            ///
            /// If odd, return `Choice(1)`.  Otherwise, return `Choice(0)`.
            pub fn is_odd(&self) -> $crate::subtle::Choice {
                use $crate::bigint::Integer;
                self.to_canonical().is_odd()
            }

            /// Determine if this [`
            #[doc = stringify!($fe)]
            /// `] is even in the SEC1 sense: `self mod 2 == 0`.
            ///
            /// # Returns
            ///
            /// If even, return `Choice(1)`.  Otherwise, return `Choice(0)`.
            pub fn is_even(&self) -> $crate::subtle::Choice {
                !self.is_odd()
            }

            /// Determine if this [`
            #[doc = stringify!($fe)]
            /// `] is zero.
            ///
            /// # Returns
            ///
            /// If zero, return `Choice(1)`.  Otherwise, return `Choice(0)`.
            pub fn is_zero(&self) -> $crate::subtle::Choice {
                self.ct_eq(&Self::ZERO)
            }

            /// Returns `self^exp`, where `exp` is a little-endian integer exponent.
            ///
            /// **This operation is variable time with respect to the exponent.**
            ///
            /// If the exponent is fixed, this operation is constant time.
            pub const fn pow_vartime(&self, exp: &[u64]) -> Self {
                let mut res = Self::ONE;
                let mut i = exp.len();

                while i > 0 {
                    i -= 1;

                    let mut j = 64;
                    while j > 0 {
                        j -= 1;
                        res = res.square();

                        if ((exp[i] >> j) & 1) == 1 {
                            res = res.multiply(self);
                        }
                    }
                }

                res
            }
        }

        impl $crate::ff::Field for $fe {
            const ZERO: Self = Self::ZERO;
            const ONE: Self = Self::ONE;

            fn try_from_rng<R: $crate::rand_core::TryRngCore + ?Sized>(
                rng: &mut R,
            ) -> ::core::result::Result<Self, R::Error> {
                let mut bytes = <$bytes>::default();

                loop {
                    rng.try_fill_bytes(&mut bytes)?;
                    if let Some(fe) = Self::from_bytes(&bytes).into() {
                        return Ok(fe);
                    }
                }
            }

            fn is_zero(&self) -> Choice {
                Self::ZERO.ct_eq(self)
            }

            fn square(&self) -> Self {
                self.square()
            }

            fn double(&self) -> Self {
                self.double()
            }

            fn invert(&self) -> CtOption<Self> {
                self.invert()
            }

            fn sqrt(&self) -> CtOption<Self> {
                self.sqrt()
            }

            fn sqrt_ratio(num: &Self, div: &Self) -> (Choice, Self) {
                $crate::ff::helpers::sqrt_ratio_generic(num, div)
            }
        }

        $crate::field_op!($fe, Add, add, add);
        $crate::field_op!($fe, Sub, sub, sub);
        $crate::field_op!($fe, Mul, mul, multiply);

        impl ::core::ops::AddAssign<$fe> for $fe {
            #[inline]
            fn add_assign(&mut self, other: $fe) {
                *self = *self + other;
            }
        }

        impl ::core::ops::AddAssign<&$fe> for $fe {
            #[inline]
            fn add_assign(&mut self, other: &$fe) {
                *self = *self + other;
            }
        }

        impl ::core::ops::SubAssign<$fe> for $fe {
            #[inline]
            fn sub_assign(&mut self, other: $fe) {
                *self = *self - other;
            }
        }

        impl ::core::ops::SubAssign<&$fe> for $fe {
            #[inline]
            fn sub_assign(&mut self, other: &$fe) {
                *self = *self - other;
            }
        }

        impl ::core::ops::MulAssign<&$fe> for $fe {
            #[inline]
            fn mul_assign(&mut self, other: &$fe) {
                *self = *self * other;
            }
        }

        impl ::core::ops::MulAssign for $fe {
            #[inline]
            fn mul_assign(&mut self, other: $fe) {
                *self = *self * other;
            }
        }

        impl ::core::ops::Neg for $fe {
            type Output = $fe;

            #[inline]
            fn neg(self) -> $fe {
                <$fe>::neg(&self)
            }
        }

        impl ::core::ops::Neg for &$fe {
            type Output = $fe;

            #[inline]
            fn neg(self) -> $fe {
                <$fe>::neg(self)
            }
        }

        impl ::core::fmt::Debug for $fe {
            fn fmt(&self, f: &mut ::core::fmt::Formatter<'_>) -> ::core::fmt::Result {
                write!(f, "{}(0x{:X})", stringify!($fe), &self.0)
            }
        }

        impl Default for $fe {
            fn default() -> Self {
                Self::ZERO
            }
        }

        impl Eq for $fe {}
        impl PartialEq for $fe {
            fn eq(&self, rhs: &Self) -> bool {
                self.0.ct_eq(&(rhs.0)).into()
            }
        }

        impl From<u32> for $fe {
            fn from(n: u32) -> $fe {
                Self::from_uint_unchecked(<$uint>::from(n))
            }
        }

        impl From<u64> for $fe {
            fn from(n: u64) -> $fe {
                Self::from_uint_unchecked(<$uint>::from(n))
            }
        }

        impl From<u128> for $fe {
            fn from(n: u128) -> $fe {
                Self::from_uint_unchecked(<$uint>::from(n))
            }
        }

        impl From<$fe> for $bytes {
            fn from(fe: $fe) -> Self {
                <$bytes>::from(&fe)
            }
        }

        impl From<&$fe> for $bytes {
            fn from(fe: &$fe) -> Self {
                fe.to_repr()
            }
        }

        impl From<$fe> for $uint {
            fn from(fe: $fe) -> $uint {
                <$uint>::from(&fe)
            }
        }

        impl From<&$fe> for $uint {
            fn from(fe: &$fe) -> $uint {
                fe.to_canonical()
            }
        }

        impl ::core::iter::Sum for $fe {
            #[allow(unused_qualifications)]
            fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
                iter.reduce(core::ops::Add::add).unwrap_or(Self::ZERO)
            }
        }

        impl<'a> ::core::iter::Sum<&'a $fe> for $fe {
            fn sum<I: Iterator<Item = &'a $fe>>(iter: I) -> Self {
                iter.copied().sum()
            }
        }

        impl ::core::iter::Product for $fe {
            #[allow(unused_qualifications)]
            fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
                iter.reduce(core::ops::Mul::mul).unwrap_or(Self::ONE)
            }
        }

        impl<'a> ::core::iter::Product<&'a $fe> for $fe {
            fn product<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
                iter.copied().product()
            }
        }

        impl $crate::bigint::Invert for $fe {
            type Output = CtOption<Self>;

            fn invert(&self) -> CtOption<Self> {
                self.invert()
            }
        }

        impl $crate::subtle::ConditionallySelectable for $fe {
            fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
                Self(<$uint>::conditional_select(&a.0, &b.0, choice))
            }
        }

        impl $crate::subtle::ConstantTimeEq for $fe {
            fn ct_eq(&self, other: &Self) -> $crate::subtle::Choice {
                self.0.ct_eq(&other.0)
            }
        }

        impl $crate::subtle::ConstantTimeGreater for $fe {
            fn ct_gt(&self, other: &Self) -> $crate::subtle::Choice {
                self.0.ct_gt(&other.0)
            }
        }

        impl $crate::subtle::ConstantTimeLess for $fe {
            fn ct_lt(&self, other: &Self) -> $crate::subtle::Choice {
                self.0.ct_lt(&other.0)
            }
        }

        impl $crate::zeroize::DefaultIsZeroes for $fe {}
    };
}

/// Emit a `core::ops` trait wrapper for an inherent method which is expected to be provided by a
/// backend arithmetic implementation (e.g. `fiat-crypto`)
#[macro_export]
macro_rules! field_op {
    ($fe:tt, $op:tt, $func:ident, $inner_func:ident) => {
        impl ::core::ops::$op for $fe {
            type Output = $fe;

            #[inline]
            fn $func(self, rhs: $fe) -> $fe {
                <$fe>::$inner_func(&self, &rhs)
            }
        }

        impl ::core::ops::$op<&$fe> for $fe {
            type Output = $fe;

            #[inline]
            fn $func(self, rhs: &$fe) -> $fe {
                <$fe>::$inner_func(&self, rhs)
            }
        }

        impl ::core::ops::$op<&$fe> for &$fe {
            type Output = $fe;

            #[inline]
            fn $func(self, rhs: &$fe) -> $fe {
                <$fe>::$inner_func(self, rhs)
            }
        }
    };
}