ff_zeroize/
lib.rs

1//! This crate provides traits for working with finite fields.
2
3// Catch documentation errors caused by code changes.
4#![deny(intra_doc_link_resolution_failure)]
5#![allow(unused_imports)]
6
7#[cfg(feature = "derive")]
8#[macro_use]
9extern crate ff_derive_zeroize as ff_derive;
10
11#[cfg(feature = "derive")]
12pub use ff_derive::*;
13
14#[macro_use]
15extern crate zeroize;
16
17use rand_core::RngCore;
18use std::error::Error;
19use std::fmt;
20use std::io::{self, Read, Write};
21
22/// This trait represents an element of a field.
23pub trait Field:
24    Sized + Eq + Copy + Clone + Send + Sync + fmt::Debug + fmt::Display + 'static
25{
26    /// Returns an element chosen uniformly at random using a user-provided RNG.
27    fn random<R: RngCore + ?std::marker::Sized>(rng: &mut R) -> Self;
28
29    /// Returns the zero element of the field, the additive identity.
30    fn zero() -> Self;
31
32    /// Returns the one element of the field, the multiplicative identity.
33    fn one() -> Self;
34
35    /// Returns true iff this element is zero.
36    fn is_zero(&self) -> bool;
37
38    /// Squares this element.
39    fn square(&mut self);
40
41    /// Doubles this element.
42    fn double(&mut self);
43
44    /// Negates this element.
45    fn negate(&mut self);
46
47    /// Adds another element to this element.
48    fn add_assign(&mut self, other: &Self);
49
50    /// Subtracts another element from this element.
51    fn sub_assign(&mut self, other: &Self);
52
53    /// Multiplies another element by this element.
54    fn mul_assign(&mut self, other: &Self);
55
56    /// Computes the multiplicative inverse of this element, if nonzero.
57    fn inverse(&self) -> Option<Self>;
58
59    /// Exponentiates this element by a power of the base prime modulus via
60    /// the Frobenius automorphism.
61    fn frobenius_map(&mut self, power: usize);
62
63    /// Exponentiates this element by a number represented with `u64` limbs,
64    /// least significant digit first.
65    fn pow<S: AsRef<[u64]>>(&self, exp: S) -> Self {
66        let mut res = Self::one();
67
68        let mut found_one = false;
69
70        for i in BitIterator::new(exp) {
71            if found_one {
72                res.square();
73            } else {
74                found_one = i;
75            }
76
77            if i {
78                res.mul_assign(self);
79            }
80        }
81
82        res
83    }
84}
85
86/// This trait represents an element of a field that has a square root operation described for it.
87pub trait SqrtField: Field {
88    /// Returns the Legendre symbol of the field element.
89    fn legendre(&self) -> LegendreSymbol;
90
91    /// Returns the square root of the field element, if it is
92    /// quadratic residue.
93    fn sqrt(&self) -> Option<Self>;
94}
95
96/// This trait represents a wrapper around a biginteger which can encode any element of a particular
97/// prime field. It is a smart wrapper around a sequence of `u64` limbs, least-significant digit
98/// first.
99pub trait PrimeFieldRepr:
100    Sized
101    + Copy
102    + Clone
103    + Eq
104    + Ord
105    + Send
106    + Sync
107    + Default
108    + fmt::Debug
109    + fmt::Display
110    + 'static
111    + AsRef<[u64]>
112    + AsMut<[u64]>
113    + From<u64>
114    + zeroize::Zeroize
115{
116    /// Subtract another represetation from this one.
117    fn sub_noborrow(&mut self, other: &Self);
118
119    /// Add another representation to this one.
120    fn add_nocarry(&mut self, other: &Self);
121
122    /// Compute the number of bits needed to encode this number. Always a
123    /// multiple of 64.
124    fn num_bits(&self) -> u32;
125
126    /// Returns true iff this number is zero.
127    fn is_zero(&self) -> bool;
128
129    /// Returns true iff this number is odd.
130    fn is_odd(&self) -> bool;
131
132    /// Returns true iff this number is even.
133    fn is_even(&self) -> bool;
134
135    /// Performs a rightwise bitshift of this number, effectively dividing
136    /// it by 2.
137    fn div2(&mut self);
138
139    /// Performs a rightwise bitshift of this number by some amount.
140    fn shr(&mut self, amt: u32);
141
142    /// Performs a leftwise bitshift of this number, effectively multiplying
143    /// it by 2. Overflow is ignored.
144    fn mul2(&mut self);
145
146    /// Performs a leftwise bitshift of this number by some amount.
147    fn shl(&mut self, amt: u32);
148
149    /// Writes this `PrimeFieldRepr` as a big endian integer.
150    fn write_be<W: Write>(&self, mut writer: W) -> io::Result<()> {
151        use byteorder::{BigEndian, WriteBytesExt};
152
153        for digit in self.as_ref().iter().rev() {
154            writer.write_u64::<BigEndian>(*digit)?;
155        }
156
157        Ok(())
158    }
159
160    /// Reads a big endian integer into this representation.
161    fn read_be<R: Read>(&mut self, mut reader: R) -> io::Result<()> {
162        use byteorder::{BigEndian, ReadBytesExt};
163
164        for digit in self.as_mut().iter_mut().rev() {
165            *digit = reader.read_u64::<BigEndian>()?;
166        }
167
168        Ok(())
169    }
170
171    /// Writes this `PrimeFieldRepr` as a little endian integer.
172    fn write_le<W: Write>(&self, mut writer: W) -> io::Result<()> {
173        use byteorder::{LittleEndian, WriteBytesExt};
174
175        for digit in self.as_ref().iter() {
176            writer.write_u64::<LittleEndian>(*digit)?;
177        }
178
179        Ok(())
180    }
181
182    /// Reads a little endian integer into this representation.
183    fn read_le<R: Read>(&mut self, mut reader: R) -> io::Result<()> {
184        use byteorder::{LittleEndian, ReadBytesExt};
185
186        for digit in self.as_mut().iter_mut() {
187            *digit = reader.read_u64::<LittleEndian>()?;
188        }
189
190        Ok(())
191    }
192}
193
194#[derive(Debug, PartialEq)]
195pub enum LegendreSymbol {
196    Zero = 0,
197    QuadraticResidue = 1,
198    QuadraticNonResidue = -1,
199}
200
201/// An error that may occur when trying to interpret a `PrimeFieldRepr` as a
202/// `PrimeField` element.
203#[derive(Debug)]
204pub enum PrimeFieldDecodingError {
205    /// The encoded value is not in the field
206    NotInField(String),
207}
208
209impl Error for PrimeFieldDecodingError {
210    fn description(&self) -> &str {
211        match *self {
212            PrimeFieldDecodingError::NotInField(..) => "not an element of the field",
213        }
214    }
215}
216
217impl fmt::Display for PrimeFieldDecodingError {
218    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
219        match *self {
220            PrimeFieldDecodingError::NotInField(ref repr) => {
221                write!(f, "{} is not an element of the field", repr)
222            }
223        }
224    }
225}
226
227/// This represents an element of a prime field.
228pub trait PrimeField: Field {
229    /// The prime field can be converted back and forth into this biginteger
230    /// representation.
231    type Repr: PrimeFieldRepr + From<Self>;
232
233    /// Interpret a string of numbers as a (congruent) prime field element.
234    /// Does not accept unnecessary leading zeroes or a blank string.
235    fn from_str(s: &str) -> Option<Self> {
236        if s.is_empty() {
237            return None;
238        }
239
240        if s == "0" {
241            return Some(Self::zero());
242        }
243
244        let mut res = Self::zero();
245
246        let ten = Self::from_repr(Self::Repr::from(10)).unwrap();
247
248        let mut first_digit = true;
249
250        for c in s.chars() {
251            match c.to_digit(10) {
252                Some(c) => {
253                    if first_digit {
254                        if c == 0 {
255                            return None;
256                        }
257
258                        first_digit = false;
259                    }
260
261                    res.mul_assign(&ten);
262                    res.add_assign(&Self::from_repr(Self::Repr::from(u64::from(c))).unwrap());
263                }
264                None => {
265                    return None;
266                }
267            }
268        }
269
270        Some(res)
271    }
272
273    /// Convert this prime field element into a biginteger representation.
274    fn from_repr(_: Self::Repr) -> Result<Self, PrimeFieldDecodingError>;
275
276    /// Convert a biginteger representation into a prime field element, if
277    /// the number is an element of the field.
278    fn into_repr(&self) -> Self::Repr;
279
280    /// Returns the field characteristic; the modulus.
281    fn char() -> Self::Repr;
282
283    /// How many bits are needed to represent an element of this field.
284    const NUM_BITS: u32;
285
286    /// How many bits of information can be reliably stored in the field element.
287    const CAPACITY: u32;
288
289    /// Returns the multiplicative generator of `char()` - 1 order. This element
290    /// must also be quadratic nonresidue.
291    fn multiplicative_generator() -> Self;
292
293    /// 2^s * t = `char()` - 1 with t odd.
294    const S: u32;
295
296    /// Returns the 2^s root of unity computed by exponentiating the `multiplicative_generator()`
297    /// by t.
298    fn root_of_unity() -> Self;
299}
300
301/// An "engine" is a collection of types (fields, elliptic curve groups, etc.)
302/// with well-defined relationships. Specific relationships (for example, a
303/// pairing-friendly curve) can be defined in a subtrait.
304pub trait ScalarEngine: Sized + 'static + Clone {
305    /// This is the scalar field of the engine's groups.
306    type Fr: PrimeField + SqrtField;
307}
308
309#[derive(Debug)]
310pub struct BitIterator<E> {
311    t: E,
312    n: usize,
313}
314
315impl<E: AsRef<[u64]>> BitIterator<E> {
316    pub fn new(t: E) -> Self {
317        let n = t.as_ref().len() * 64;
318
319        BitIterator { t, n }
320    }
321}
322
323impl<E: AsRef<[u64]>> Iterator for BitIterator<E> {
324    type Item = bool;
325
326    fn next(&mut self) -> Option<bool> {
327        if self.n == 0 {
328            None
329        } else {
330            self.n -= 1;
331            let part = self.n / 64;
332            let bit = self.n - (64 * part);
333
334            Some(self.t.as_ref()[part] & (1 << bit) > 0)
335        }
336    }
337}
338
339#[test]
340fn test_bit_iterator() {
341    let mut a = BitIterator::new([0xa953d79b83f6ab59, 0x6dea2059e200bd39]);
342    let expected = "01101101111010100010000001011001111000100000000010111101001110011010100101010011110101111001101110000011111101101010101101011001";
343
344    for e in expected.chars() {
345        assert!(a.next().unwrap() == (e == '1'));
346    }
347
348    assert!(a.next().is_none());
349
350    let expected = "1010010101111110101010000101101011101000011101110101001000011001100100100011011010001011011011010001011011101100110100111011010010110001000011110100110001100110011101101000101100011100100100100100001010011101010111110011101011000011101000111011011101011001";
351
352    let mut a = BitIterator::new([
353        0x429d5f3ac3a3b759,
354        0xb10f4c66768b1c92,
355        0x92368b6d16ecd3b4,
356        0xa57ea85ae8775219,
357    ]);
358
359    for e in expected.chars() {
360        assert!(a.next().unwrap() == (e == '1'));
361    }
362
363    assert!(a.next().is_none());
364}
365
366pub use self::arith_impl::*;
367
368mod arith_impl {
369    /// Calculate a - b - borrow, returning the result and modifying
370    /// the borrow value.
371    #[inline(always)]
372    pub fn sbb(a: u64, b: u64, borrow: &mut u64) -> u64 {
373        let tmp = (1u128 << 64) + u128::from(a) - u128::from(b) - u128::from(*borrow);
374
375        *borrow = if tmp >> 64 == 0 { 1 } else { 0 };
376
377        tmp as u64
378    }
379
380    /// Calculate a + b + carry, returning the sum and modifying the
381    /// carry value.
382    #[inline(always)]
383    pub fn adc(a: u64, b: u64, carry: &mut u64) -> u64 {
384        let tmp = u128::from(a) + u128::from(b) + u128::from(*carry);
385
386        *carry = (tmp >> 64) as u64;
387
388        tmp as u64
389    }
390
391    /// Calculate a + (b * c) + carry, returning the least significant digit
392    /// and setting carry to the most significant digit.
393    #[inline(always)]
394    pub fn mac_with_carry(a: u64, b: u64, c: u64, carry: &mut u64) -> u64 {
395        let tmp = (u128::from(a)) + u128::from(b) * u128::from(c) + u128::from(*carry);
396
397        *carry = (tmp >> 64) as u64;
398
399        tmp as u64
400    }
401}
ff_zeroize/lib.rs

ff_zeroize/
lib.rs
