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
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141

//! A `FieldElement` represents an element of the finite field
//! modulo `2^252 + 27742317777372353535851937790883648493`.
//!
//! The `FieldElement` type is an alias for one of the backend
//! implementations.
//!
//! `ConstantTimeEq` and `PartialEq` traits have been implemented
//! here since they will be the samme across all of the different backends.
//!
//! # Examples
//! ```rust
//! use zerocaf::field::FieldElement;
//! use zerocaf::traits::ops::*;
//! use zerocaf::constants::EDWARDS_D;
//!
//! use subtle::Choice;
//! use rand::rngs::OsRng;
//!
//! // You can create a FieldElement from a byte-array as follows:
//! let a = FieldElement::from_bytes(&[0u8;32]);
//!
//! // You ca also create a FieldElement from an uint type as follows:
//! let b = FieldElement::from(126296u128);
//! let c = FieldElement::from(126297u64);
//!
//! // You can create random FieldElements by calling:
//! let rand = FieldElement::random(&mut OsRng);
//!
//! // The last way of creating a FieldElement it by calling the
//! // constructor. THIS IS NOT RECOMMENDED since NO checks about
//! // the correctness of the input will be done at all.
//! // It can be done as follows:
//! let d: FieldElement = FieldElement([0, 1, 0, 0, 0]); // d = 2^52.
//! assert!(d == FieldElement::two_pow_k(52u64));
//!
//! // All of the basuc modular operations are implemented
//! // for FieldElement type:
//! let mut res = &a + &b; // Performs a + b (mod l).
//! res = a - b; // Performs a - b (mod l).
//! res = a * b; // Performs a * b (mod l).
//! res = a.square(); // Performs a^2 (mod l).
//! res = -&a; // Performs Negation over the modulo l.
//! res = a.pow(&b); // Performs Modular exponentiation.
//! res = a.mod_sqrt(Choice::from(1u8)).unwrap(); //Performs
//! // modular sqrt.
//! // Returs `None` if the input is not a QR on the field.
//! // Returns Some(result) if everything is correct.
//!
//! // Division has been also implemented. Remember that when we write
//! // a/b (mod l), we are indeed performing a * inverse_mod(b, l) (mod l).
//! assert!((-b / c) == EDWARDS_D);
//!
//! // Dividing by two even FieldElements is recommended through the `Half`
//! // trait implmementation since it's much faster.
//! if a.is_even() {
//!     let half_a = &a.half(); // This will panic if a isn't even.
//! };
//!
//! // We can finally perform inversion modulo l for a FieldElement:
//! let inv_a = &c.inverse(); // Performs a^-1 (mod l).
//!
//! // You can export your `FieldElement` as an slice of 32 bytes in Little
//! // Endian encoding by:
//! let c_bytes: [u8; 32] = c.to_bytes();
//! ```
//!
//! `PartialOrd`, `Ord`, `PartialEq` and `Eq` are also implemented for
//! `FieldElement` type.
//!
//! All `std::core::ops traits -> (Add, Sub, Mul, Div)` are implemented
//! for both, `&FieldElement` and `FieldElement`.

use core::cmp::PartialEq;

use subtle::{Choice, ConditionallySelectable, ConstantTimeEq};

use rand::{CryptoRng, Rng};

use curve25519_dalek::scalar::Scalar;

use crate::backend;

#[cfg(feature = "u64_backend")]
pub use backend::u64::field::*;
/// A `FieldElement` represents an element of the field
/// `2^252 + 27742317777372353535851937790883648493`
///
/// The `FieldElement` type is an alias for one of the platform-specific
/// implementations.
#[cfg(feature = "u64_backend")]
pub type FieldElement = backend::u64::field::FieldElement;

impl PartialEq for FieldElement {
    fn eq(&self, other: &FieldElement) -> bool {
        self.ct_eq(other).unwrap_u8() == 1u8
    }
}

impl ConstantTimeEq for FieldElement {
    /// Test equality between two `FieldElement`s.  Since the
    /// internal representation is not canonical, the field elements
    /// are normalized to wire format before comparison.
    fn ct_eq(&self, other: &FieldElement) -> Choice {
        self.to_bytes().ct_eq(&other.to_bytes())
    }
}

impl ConditionallySelectable for FieldElement {
    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
        FieldElement([
            u64::conditional_select(&a.0[0], &b.0[0], choice),
            u64::conditional_select(&a.0[1], &b.0[1], choice),
            u64::conditional_select(&a.0[2], &b.0[2], choice),
            u64::conditional_select(&a.0[3], &b.0[3], choice),
            u64::conditional_select(&a.0[4], &b.0[4], choice),
        ])
    }
}

impl Into<Scalar> for &FieldElement {
    fn into(self) -> Scalar {
        Scalar::from_bytes_mod_order(self.to_bytes())
    }
}

impl FieldElement {
    /// Generate a valid FieldElement choosen uniformly using user-
    /// provided rng.
    ///
    /// By `rng` we mean any Rng that implements: `Rng` + `CryptoRng`.
    pub fn random<T>(rand: &mut T) -> FieldElement
    where
        T: Rng + CryptoRng,
    {
        let mut bytes = [0u8; 32];
        rand.fill_bytes(&mut bytes);
        // Ensure that the value is lower than `FIELD_L`.
        bytes[31] &= 0b0000_0111;
        FieldElement::from_bytes(&bytes)
    }
}