p521/arithmetic/
field.rs

1//! Field arithmetic modulo p = 2^{521} − 1
2//!
3//! Arithmetic implementations have been synthesized using fiat-crypto.
4//!
5//! # License
6//!
7//! Copyright (c) 2015-2020 the fiat-crypto authors
8//!
9//! fiat-crypto is distributed under the terms of the MIT License, the
10//! Apache License (Version 2.0), and the BSD 1-Clause License;
11//! users may pick which license to apply.
12
13#![allow(
14    clippy::should_implement_trait,
15    clippy::suspicious_op_assign_impl,
16    clippy::unused_unit,
17    clippy::unnecessary_cast,
18    clippy::too_many_arguments,
19    clippy::identity_op,
20    rustdoc::bare_urls
21)]
22
23// TODO(tarcieri): 32-bit backend?
24#[path = "field/p521_64.rs"]
25mod field_impl;
26mod loose;
27
28pub(crate) use self::loose::LooseFieldElement;
29
30use self::field_impl::*;
31use crate::{FieldBytes, NistP521, U576};
32use core::{
33    fmt::{self, Debug},
34    iter::{Product, Sum},
35    ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign},
36};
37use elliptic_curve::{
38    ff::{self, Field, PrimeField},
39    generic_array::GenericArray,
40    rand_core::RngCore,
41    subtle::{Choice, ConditionallySelectable, ConstantTimeEq, ConstantTimeLess, CtOption},
42    zeroize::DefaultIsZeroes,
43    Error, FieldBytesEncoding,
44};
45
46use super::util::u576_to_le_bytes;
47
48/// Constant representing the modulus serialized as hex.
49/// p = 2^{521} − 1
50const MODULUS_HEX: &str = "00000000000001ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff";
51
52pub(crate) const MODULUS: U576 = U576::from_be_hex(MODULUS_HEX);
53
54/// Element of the secp521r1 base field used for curve coordinates.
55#[derive(Clone, Copy)]
56pub struct FieldElement(pub(crate) fiat_p521_tight_field_element);
57
58impl FieldElement {
59    /// Zero element.
60    pub const ZERO: Self = Self::from_u64(0);
61
62    /// Multiplicative identity.
63    pub const ONE: Self = Self::from_u64(1);
64
65    /// Number of bytes in the serialized representation.
66    const BYTES: usize = 66;
67
68    /// Create a [`FieldElement`] from a canonical big-endian representation.
69    pub fn from_bytes(repr: &FieldBytes) -> CtOption<Self> {
70        let uint = <U576 as FieldBytesEncoding<NistP521>>::decode_field_bytes(repr);
71        Self::from_uint(uint)
72    }
73
74    /// Decode [`FieldElement`] from a big endian byte slice.
75    pub fn from_slice(slice: &[u8]) -> elliptic_curve::Result<Self> {
76        if slice.len() != Self::BYTES {
77            return Err(Error);
78        }
79
80        Option::from(Self::from_bytes(GenericArray::from_slice(slice))).ok_or(Error)
81    }
82
83    /// Decode [`FieldElement`] from [`U576`].
84    pub fn from_uint(uint: U576) -> CtOption<Self> {
85        let is_some = uint.ct_lt(&MODULUS);
86        CtOption::new(Self::from_uint_unchecked(uint), is_some)
87    }
88
89    /// Parse a [`FieldElement`] from big endian hex-encoded bytes.
90    ///
91    /// Does *not* perform a check that the field element does not overflow the order.
92    ///
93    /// This method is primarily intended for defining internal constants.
94    pub(crate) const fn from_hex(hex: &str) -> Self {
95        Self::from_uint_unchecked(U576::from_be_hex(hex))
96    }
97
98    /// Convert a `u64` into a [`FieldElement`].
99    pub const fn from_u64(w: u64) -> Self {
100        Self::from_uint_unchecked(U576::from_u64(w))
101    }
102
103    /// Decode [`FieldElement`] from [`U576`].
104    ///
105    /// Does *not* perform a check that the field element does not overflow the order.
106    ///
107    /// Used incorrectly this can lead to invalid results!
108    pub(crate) const fn from_uint_unchecked(w: U576) -> Self {
109        Self(fiat_p521_from_bytes(&u576_to_le_bytes(w)))
110    }
111
112    /// Returns the big-endian encoding of this [`FieldElement`].
113    pub fn to_bytes(self) -> FieldBytes {
114        let mut ret = fiat_p521_to_bytes(&self.0);
115        ret.reverse();
116        GenericArray::clone_from_slice(&ret)
117    }
118
119    /// Determine if this [`FieldElement`] is odd in the SEC1 sense: `self mod 2 == 1`.
120    ///
121    /// # Returns
122    ///
123    /// If odd, return `Choice(1)`.  Otherwise, return `Choice(0)`.
124    pub fn is_odd(&self) -> Choice {
125        Choice::from(self.0[0] as u8 & 1)
126    }
127
128    /// Determine if this [`FieldElement`] is even in the SEC1 sense: `self mod 2 == 0`.
129    ///
130    /// # Returns
131    ///
132    /// If even, return `Choice(1)`.  Otherwise, return `Choice(0)`.
133    pub fn is_even(&self) -> Choice {
134        !self.is_odd()
135    }
136
137    /// Determine if this [`FieldElement`] is zero.
138    ///
139    /// # Returns
140    ///
141    /// If zero, return `Choice(1)`.  Otherwise, return `Choice(0)`.
142    pub fn is_zero(&self) -> Choice {
143        self.ct_eq(&Self::ZERO)
144    }
145
146    /// Add elements.
147    #[allow(dead_code)] // TODO(tarcieri): currently unused
148    pub(crate) const fn add_loose(&self, rhs: &Self) -> LooseFieldElement {
149        LooseFieldElement(fiat_p521_add(&self.0, &rhs.0))
150    }
151
152    /// Double element (add it to itself).
153    #[allow(dead_code)] // TODO(tarcieri): currently unused
154    #[must_use]
155    pub(crate) const fn double_loose(&self) -> LooseFieldElement {
156        Self::add_loose(self, self)
157    }
158
159    /// Subtract elements, returning a loose field element.
160    #[allow(dead_code)] // TODO(tarcieri): currently unused
161    pub(crate) const fn sub_loose(&self, rhs: &Self) -> LooseFieldElement {
162        LooseFieldElement(fiat_p521_sub(&self.0, &rhs.0))
163    }
164
165    /// Negate element, returning a loose field element.
166    #[allow(dead_code)] // TODO(tarcieri): currently unused
167    pub(crate) const fn neg_loose(&self) -> LooseFieldElement {
168        LooseFieldElement(fiat_p521_opp(&self.0))
169    }
170
171    /// Add two field elements.
172    pub const fn add(&self, rhs: &Self) -> Self {
173        Self(fiat_p521_carry_add(&self.0, &rhs.0))
174    }
175
176    /// Subtract field elements.
177    pub const fn sub(&self, rhs: &Self) -> Self {
178        Self(fiat_p521_carry_sub(&self.0, &rhs.0))
179    }
180
181    /// Negate element.
182    pub const fn neg(&self) -> Self {
183        Self(fiat_p521_carry_opp(&self.0))
184    }
185
186    /// Double element (add it to itself).
187    #[must_use]
188    pub const fn double(&self) -> Self {
189        self.add(self)
190    }
191
192    /// Multiply elements.
193    pub const fn multiply(&self, rhs: &Self) -> Self {
194        LooseFieldElement::mul(&self.relax(), &rhs.relax())
195    }
196
197    /// Square element.
198    pub const fn square(&self) -> Self {
199        self.relax().square()
200    }
201
202    /// Returns self^(2^n) mod p
203    const fn sqn(&self, n: usize) -> Self {
204        let mut x = self.square();
205        let mut i = 1;
206        while i < n {
207            x = x.square();
208            i += 1;
209        }
210        x
211    }
212
213    /// Returns `self^exp`, where `exp` is a little-endian integer exponent.
214    ///
215    /// **This operation is variable time with respect to the exponent.**
216    ///
217    /// If the exponent is fixed, this operation is effectively constant time.
218    pub const fn pow_vartime(&self, exp: &[u64]) -> Self {
219        let mut res = Self::ONE;
220        let mut i = exp.len();
221
222        while i > 0 {
223            i -= 1;
224
225            let mut j = 64;
226            while j > 0 {
227                j -= 1;
228                res = res.square();
229
230                if ((exp[i] >> j) & 1) == 1 {
231                    res = Self::multiply(&res, self);
232                }
233            }
234        }
235
236        res
237    }
238
239    /// Compute [`FieldElement`] inversion: `1 / self`.
240    pub fn invert(&self) -> CtOption<Self> {
241        CtOption::new(self.invert_unchecked(), !self.is_zero())
242    }
243
244    /// Returns the multiplicative inverse of self.
245    ///
246    /// Does not check that self is non-zero.
247    const fn invert_unchecked(&self) -> Self {
248        // Adapted from addchain: github.com/mmcloughlin/addchain
249        let z = self.square();
250        let z = self.multiply(&z);
251        let t0 = z.sqn(2);
252        let z = z.multiply(&t0);
253        let t0 = z.sqn(4);
254        let z = z.multiply(&t0);
255        let t0 = z.sqn(8);
256        let z = z.multiply(&t0);
257        let t0 = z.sqn(16);
258        let z = z.multiply(&t0);
259        let t0 = z.sqn(32);
260        let z = z.multiply(&t0);
261        let t0 = z.square();
262        let t0 = self.multiply(&t0);
263        let t0 = t0.sqn(64);
264        let z = z.multiply(&t0);
265        let t0 = z.square();
266        let t0 = self.multiply(&t0);
267        let t0 = t0.sqn(129);
268        let z = z.multiply(&t0);
269        let t0 = z.square();
270        let t0 = self.multiply(&t0);
271        let t0 = t0.sqn(259);
272        let z = z.multiply(&t0);
273        let z = z.sqn(2);
274        self.multiply(&z)
275    }
276
277    /// Returns the square root of self mod p, or `None` if no square root
278    /// exists.
279    ///
280    /// # Implementation details
281    /// If _x_ has a sqrt, then due to Euler's criterion this implies x<sup>(p - 1)/2</sup> = 1.
282    /// 1. x<sup>(p + 1)/2</sup> = x.
283    /// 2. There's a special property due to _p ≡ 3 (mod 4)_ which implies _(p + 1)/4_ is an integer.
284    /// 3. We can rewrite `1.` as x<sup>((p+1)/4)<sup>2</sup></sup>
285    /// 4. x<sup>(p+1)/4</sup> is the square root.
286    /// 5. This is simplified as (2<sup>251</sup> - 1 + 1) /4 = 2<sup>519</sup>
287    /// 6. Hence, x<sup>2<sup>519</sup></sup> is the square root iff _result.square() == self_
288    pub fn sqrt(&self) -> CtOption<Self> {
289        let sqrt = self.sqn(519);
290        CtOption::new(sqrt, sqrt.square().ct_eq(self))
291    }
292
293    /// Relax a tight field element into a loose one.
294    pub(crate) const fn relax(&self) -> LooseFieldElement {
295        LooseFieldElement(fiat_p521_relax(&self.0))
296    }
297}
298
299impl AsRef<fiat_p521_tight_field_element> for FieldElement {
300    fn as_ref(&self) -> &fiat_p521_tight_field_element {
301        &self.0
302    }
303}
304
305impl Default for FieldElement {
306    fn default() -> Self {
307        Self::ZERO
308    }
309}
310
311impl Debug for FieldElement {
312    /// Formatting machinery for [`FieldElement`]
313    ///
314    /// # Why
315    /// ```ignore
316    /// let fe1 = FieldElement([9, 0, 0, 0, 0, 0, 0, 0, 0]);
317    /// let fe2 = FieldElement([
318    ///     8,
319    ///     0,
320    ///     288230376151711744,
321    ///     288230376151711743,
322    ///     288230376151711743,
323    ///     288230376151711743,
324    ///     288230376151711743,
325    ///     288230376151711743,
326    ///     144115188075855871,
327    /// ]);
328    /// ```
329    ///
330    /// For the above example, deriving [`core::fmt::Debug`] will result in returning 2 different
331    /// strings, which are in reality the same due to p521's unsaturated math, instead print the
332    /// output as a hex string in big-endian.
333    ///
334    /// This makes debugging easier.
335    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
336        let mut bytes = fiat_p521_to_bytes(&self.0);
337        bytes.reverse();
338
339        let formatter = base16ct::HexDisplay(&bytes);
340        f.debug_tuple("FieldElement")
341            .field(&format_args!("0x{formatter:X}"))
342            .finish()
343    }
344}
345
346impl Eq for FieldElement {}
347impl PartialEq for FieldElement {
348    fn eq(&self, rhs: &Self) -> bool {
349        self.ct_eq(rhs).into()
350    }
351}
352
353impl From<u32> for FieldElement {
354    fn from(n: u32) -> FieldElement {
355        Self::from_uint_unchecked(U576::from(n))
356    }
357}
358
359impl From<u64> for FieldElement {
360    fn from(n: u64) -> FieldElement {
361        Self::from_uint_unchecked(U576::from(n))
362    }
363}
364
365impl From<u128> for FieldElement {
366    fn from(n: u128) -> FieldElement {
367        Self::from_uint_unchecked(U576::from(n))
368    }
369}
370
371impl ConditionallySelectable for FieldElement {
372    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
373        let mut ret = Self::ZERO;
374
375        for i in 0..ret.0.len() {
376            ret.0[i] = u64::conditional_select(&a.0[i], &b.0[i], choice);
377        }
378
379        ret
380    }
381}
382
383impl ConstantTimeEq for FieldElement {
384    fn ct_eq(&self, other: &Self) -> Choice {
385        let a = fiat_p521_to_bytes(&self.0);
386        let b = fiat_p521_to_bytes(&other.0);
387        a.ct_eq(&b)
388    }
389}
390
391impl DefaultIsZeroes for FieldElement {}
392
393impl Field for FieldElement {
394    const ZERO: Self = Self::ZERO;
395    const ONE: Self = Self::ONE;
396
397    fn random(mut rng: impl RngCore) -> Self {
398        // NOTE: can't use ScalarPrimitive::random due to CryptoRng bound
399        let mut bytes = <FieldBytes>::default();
400
401        loop {
402            rng.fill_bytes(&mut bytes);
403            if let Some(fe) = Self::from_bytes(&bytes).into() {
404                return fe;
405            }
406        }
407    }
408
409    fn is_zero(&self) -> Choice {
410        Self::ZERO.ct_eq(self)
411    }
412
413    #[must_use]
414    fn square(&self) -> Self {
415        self.square()
416    }
417
418    #[must_use]
419    fn double(&self) -> Self {
420        self.double()
421    }
422
423    fn invert(&self) -> CtOption<Self> {
424        self.invert()
425    }
426
427    fn sqrt(&self) -> CtOption<Self> {
428        self.sqrt()
429    }
430
431    fn sqrt_ratio(num: &Self, div: &Self) -> (Choice, Self) {
432        ff::helpers::sqrt_ratio_generic(num, div)
433    }
434}
435
436impl PrimeField for FieldElement {
437    type Repr = FieldBytes;
438
439    const MODULUS: &'static str = MODULUS_HEX;
440    const NUM_BITS: u32 = 521;
441    const CAPACITY: u32 = 520;
442    const TWO_INV: Self = Self::from_u64(2).invert_unchecked();
443    const MULTIPLICATIVE_GENERATOR: Self = Self::from_u64(3);
444    const S: u32 = 1;
445    const ROOT_OF_UNITY: Self = Self::from_hex("00000000000001fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe");
446    const ROOT_OF_UNITY_INV: Self = Self::ROOT_OF_UNITY.invert_unchecked();
447    const DELTA: Self = Self::from_u64(9);
448
449    #[inline]
450    fn from_repr(bytes: FieldBytes) -> CtOption<Self> {
451        Self::from_bytes(&bytes)
452    }
453
454    #[inline]
455    fn to_repr(&self) -> FieldBytes {
456        self.to_bytes()
457    }
458
459    #[inline]
460    fn is_odd(&self) -> Choice {
461        self.is_odd()
462    }
463}
464
465//
466// `core::ops` impls
467//
468
469impl Add for FieldElement {
470    type Output = FieldElement;
471
472    #[inline]
473    fn add(self, rhs: FieldElement) -> FieldElement {
474        Self::add(&self, &rhs)
475    }
476}
477
478impl Add<&FieldElement> for FieldElement {
479    type Output = FieldElement;
480
481    #[inline]
482    fn add(self, rhs: &FieldElement) -> FieldElement {
483        Self::add(&self, rhs)
484    }
485}
486
487impl Add<&FieldElement> for &FieldElement {
488    type Output = FieldElement;
489
490    #[inline]
491    fn add(self, rhs: &FieldElement) -> FieldElement {
492        FieldElement::add(self, rhs)
493    }
494}
495
496impl AddAssign<FieldElement> for FieldElement {
497    #[inline]
498    fn add_assign(&mut self, other: FieldElement) {
499        *self = *self + other;
500    }
501}
502
503impl AddAssign<&FieldElement> for FieldElement {
504    #[inline]
505    fn add_assign(&mut self, other: &FieldElement) {
506        *self = *self + other;
507    }
508}
509
510impl Sub for FieldElement {
511    type Output = FieldElement;
512
513    #[inline]
514    fn sub(self, rhs: FieldElement) -> FieldElement {
515        Self::sub(&self, &rhs)
516    }
517}
518
519impl Sub<&FieldElement> for FieldElement {
520    type Output = FieldElement;
521
522    #[inline]
523    fn sub(self, rhs: &FieldElement) -> FieldElement {
524        Self::sub(&self, rhs)
525    }
526}
527
528impl Sub<&FieldElement> for &FieldElement {
529    type Output = FieldElement;
530
531    #[inline]
532    fn sub(self, rhs: &FieldElement) -> FieldElement {
533        FieldElement::sub(self, rhs)
534    }
535}
536
537impl SubAssign<FieldElement> for FieldElement {
538    #[inline]
539    fn sub_assign(&mut self, other: FieldElement) {
540        *self = *self - other;
541    }
542}
543
544impl SubAssign<&FieldElement> for FieldElement {
545    #[inline]
546    fn sub_assign(&mut self, other: &FieldElement) {
547        *self = *self - other;
548    }
549}
550
551impl Mul for FieldElement {
552    type Output = FieldElement;
553
554    #[inline]
555    fn mul(self, rhs: FieldElement) -> FieldElement {
556        self.relax().mul(&rhs.relax())
557    }
558}
559
560impl Mul<&FieldElement> for FieldElement {
561    type Output = FieldElement;
562
563    #[inline]
564    fn mul(self, rhs: &FieldElement) -> FieldElement {
565        self.relax().mul(&rhs.relax())
566    }
567}
568
569impl Mul<&FieldElement> for &FieldElement {
570    type Output = FieldElement;
571
572    #[inline]
573    fn mul(self, rhs: &FieldElement) -> FieldElement {
574        self.relax().mul(&rhs.relax())
575    }
576}
577
578impl MulAssign<&FieldElement> for FieldElement {
579    #[inline]
580    fn mul_assign(&mut self, other: &FieldElement) {
581        *self = *self * other;
582    }
583}
584
585impl MulAssign for FieldElement {
586    #[inline]
587    fn mul_assign(&mut self, other: FieldElement) {
588        *self = *self * other;
589    }
590}
591
592impl Neg for FieldElement {
593    type Output = FieldElement;
594
595    #[inline]
596    fn neg(self) -> FieldElement {
597        Self::neg(&self)
598    }
599}
600
601//
602// `core::iter` trait impls
603//
604
605impl Sum for FieldElement {
606    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
607        iter.reduce(core::ops::Add::add).unwrap_or(Self::ZERO)
608    }
609}
610
611impl<'a> Sum<&'a FieldElement> for FieldElement {
612    fn sum<I: Iterator<Item = &'a FieldElement>>(iter: I) -> Self {
613        iter.copied().sum()
614    }
615}
616
617impl Product for FieldElement {
618    fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
619        iter.reduce(core::ops::Mul::mul).unwrap_or(Self::ONE)
620    }
621}
622
623impl<'a> Product<&'a FieldElement> for FieldElement {
624    fn product<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
625        iter.copied().product()
626    }
627}
628
629#[cfg(test)]
630mod tests {
631    use super::FieldElement;
632    use elliptic_curve::ff::PrimeField;
633    use hex_literal::hex;
634    use primeorder::{
635        impl_field_identity_tests, impl_field_invert_tests, impl_field_sqrt_tests,
636        impl_primefield_tests,
637    };
638
639    /// t = (modulus - 1) >> S
640    const T: [u64; 9] = [
641        0xffffffffffffffff,
642        0xffffffffffffffff,
643        0xffffffffffffffff,
644        0xffffffffffffffff,
645        0xffffffffffffffff,
646        0xffffffffffffffff,
647        0xffffffffffffffff,
648        0xffffffffffffffff,
649        0x00000000000000ff,
650    ];
651
652    impl_field_identity_tests!(FieldElement);
653    impl_field_invert_tests!(FieldElement);
654    impl_field_sqrt_tests!(FieldElement);
655    impl_primefield_tests!(FieldElement, T);
656
657    /// Regression test for RustCrypto/elliptic-curves#965
658    #[test]
659    fn decode_invalid_field_element_returns_err() {
660        let overflowing_bytes = hex!("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF");
661        let ct_option = FieldElement::from_bytes(overflowing_bytes.as_ref().into());
662        assert!(bool::from(ct_option.is_none()));
663    }
664}
p521/arithmetic/field.rs

p521/arithmetic/
field.rs
