p384/arithmetic/
field.rs

1//! Field arithmetic modulo p = 2^{384} − 2^{128} − 2^{96} + 2^{32} − 1
2//!
3//! Arithmetic implementations are extracted Rust code from the Coq fiat-crypto
4//! libraries.
5//!
6//! # License
7//!
8//! Copyright (c) 2015-2020 the fiat-crypto authors
9//!
10//! fiat-crypto is distributed under the terms of the MIT License, the
11//! Apache License (Version 2.0), and the BSD 1-Clause License;
12//! users may pick which license to apply.
13
14#![allow(
15    clippy::should_implement_trait,
16    clippy::suspicious_op_assign_impl,
17    clippy::unused_unit,
18    clippy::unnecessary_cast,
19    clippy::too_many_arguments,
20    clippy::identity_op
21)]
22
23#[cfg_attr(target_pointer_width = "32", path = "field/p384_32.rs")]
24#[cfg_attr(target_pointer_width = "64", path = "field/p384_64.rs")]
25mod field_impl;
26
27use self::field_impl::*;
28use crate::{FieldBytes, NistP384};
29use core::{
30    iter::{Product, Sum},
31    ops::{AddAssign, MulAssign, Neg, SubAssign},
32};
33use elliptic_curve::{
34    bigint::{self, Limb, U384},
35    ff::PrimeField,
36    subtle::{Choice, ConstantTimeEq, CtOption},
37};
38
39/// Constant representing the modulus
40/// p = 2^{384} − 2^{128} − 2^{96} + 2^{32} − 1
41pub(crate) const MODULUS: U384 = U384::from_be_hex(FieldElement::MODULUS);
42
43/// Element of the secp384r1 base field used for curve coordinates.
44#[derive(Clone, Copy, Debug)]
45pub struct FieldElement(pub(super) U384);
46
47primeorder::impl_mont_field_element!(
48    NistP384,
49    FieldElement,
50    FieldBytes,
51    U384,
52    MODULUS,
53    fiat_p384_montgomery_domain_field_element,
54    fiat_p384_from_montgomery,
55    fiat_p384_to_montgomery,
56    fiat_p384_add,
57    fiat_p384_sub,
58    fiat_p384_mul,
59    fiat_p384_opp,
60    fiat_p384_square
61);
62
63impl FieldElement {
64    /// Compute [`FieldElement`] inversion: `1 / self`.
65    pub fn invert(&self) -> CtOption<Self> {
66        CtOption::new(self.invert_unchecked(), !self.is_zero())
67    }
68
69    /// Returns the multiplicative inverse of self.
70    ///
71    /// Does not check that self is non-zero.
72    const fn invert_unchecked(&self) -> Self {
73        let words = impl_field_invert!(
74            self.to_canonical().as_words(),
75            Self::ONE.0.to_words(),
76            Limb::BITS,
77            bigint::nlimbs!(U384::BITS),
78            fiat_p384_mul,
79            fiat_p384_opp,
80            fiat_p384_divstep_precomp,
81            fiat_p384_divstep,
82            fiat_p384_msat,
83            fiat_p384_selectznz,
84        );
85
86        Self(U384::from_words(words))
87    }
88
89    /// Returns the square root of self mod p, or `None` if no square root
90    /// exists.
91    pub fn sqrt(&self) -> CtOption<Self> {
92        // p mod 4 = 3 -> compute sqrt(x) using x^((p+1)/4) =
93        // x^9850501549098619803069760025035903451269934817616361666987073351061430442874217582261816522064734500465401743278080
94        let t1 = *self;
95        let t10 = t1.square();
96        let t11 = t1 * t10;
97        let t110 = t11.square();
98        let t111 = t1 * t110;
99        let t111000 = t111.sqn(3);
100        let t111111 = t111 * t111000;
101        let t1111110 = t111111.square();
102        let t1111111 = t1 * t1111110;
103        let x12 = t1111110.sqn(5) * t111111;
104        let x24 = x12.sqn(12) * x12;
105        let x31 = x24.sqn(7) * t1111111;
106        let x32 = x31.square() * t1;
107        let x63 = x32.sqn(31) * x31;
108        let x126 = x63.sqn(63) * x63;
109        let x252 = x126.sqn(126) * x126;
110        let x255 = x252.sqn(3) * t111;
111        let x = ((x255.sqn(33) * x32).sqn(64) * t1).sqn(30);
112        CtOption::new(x, x.square().ct_eq(&t1))
113    }
114
115    /// Returns self^(2^n) mod p.
116    fn sqn(&self, n: usize) -> Self {
117        let mut x = *self;
118        for _ in 0..n {
119            x = x.square();
120        }
121        x
122    }
123}
124
125impl PrimeField for FieldElement {
126    type Repr = FieldBytes;
127
128    const MODULUS: &'static str = "fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffff0000000000000000ffffffff";
129    const NUM_BITS: u32 = 384;
130    const CAPACITY: u32 = 383;
131    const TWO_INV: Self = Self::from_u64(2).invert_unchecked();
132    const MULTIPLICATIVE_GENERATOR: Self = Self::from_u64(19);
133    const S: u32 = 1;
134    const ROOT_OF_UNITY: Self = Self::from_hex("fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffff0000000000000000fffffffe");
135    const ROOT_OF_UNITY_INV: Self = Self::ROOT_OF_UNITY.invert_unchecked();
136    const DELTA: Self = Self::from_u64(49);
137
138    #[inline]
139    fn from_repr(bytes: FieldBytes) -> CtOption<Self> {
140        Self::from_bytes(&bytes)
141    }
142
143    #[inline]
144    fn to_repr(&self) -> FieldBytes {
145        self.to_bytes()
146    }
147
148    #[inline]
149    fn is_odd(&self) -> Choice {
150        self.is_odd()
151    }
152}
153
154#[cfg(test)]
155mod tests {
156    use super::FieldElement;
157    use elliptic_curve::ff::PrimeField;
158    use primeorder::impl_primefield_tests;
159
160    /// t = (modulus - 1) >> S
161    const T: [u64; 6] = [
162        0x000000007fffffff,
163        0x7fffffff80000000,
164        0xffffffffffffffff,
165        0xffffffffffffffff,
166        0xffffffffffffffff,
167        0x7fffffffffffffff,
168    ];
169
170    impl_primefield_tests!(FieldElement, T);
171
172    /// Basic tests that field inversion works.
173    #[test]
174    fn invert() {
175        let one = FieldElement::ONE;
176        assert_eq!(one.invert().unwrap(), one);
177
178        let three = one + &one + &one;
179        let inv_three = three.invert().unwrap();
180        assert_eq!(three * &inv_three, one);
181
182        let minus_three = -three;
183        let inv_minus_three = minus_three.invert().unwrap();
184        assert_eq!(inv_minus_three, -inv_three);
185        assert_eq!(three * &inv_minus_three, -one);
186    }
187
188    #[test]
189    fn sqrt() {
190        let one = FieldElement::ONE;
191        let two = one + &one;
192        let four = two.square();
193        assert_eq!(four.sqrt().unwrap(), two);
194    }
195}
p384/arithmetic/field.rs

p384/arithmetic/
field.rs
