p256/arithmetic/
field.rs

1//! Field arithmetic modulo p = 2^{224}(2^{32} − 1) + 2^{192} + 2^{96} − 1
2
3#![allow(clippy::assign_op_pattern, clippy::op_ref)]
4
5use elliptic_curve::{bigint::cpubits, ops::BatchInvert};
6
7cpubits! {
8    32 => {
9        #[path = "field/field32.rs"]
10        mod field_impl;
11    }
12    64 => {
13        #[path = "field/field64.rs"]
14        mod field_impl;
15    }
16}
17
18use core::ops::Mul;
19use elliptic_curve::{
20    bigint::U256,
21    ff::PrimeField,
22    subtle::{Choice, ConstantTimeEq, CtOption},
23};
24
25#[cfg(doc)]
26use {
27    core::ops::{Add, Neg, Sub},
28    elliptic_curve::{
29        ff::{self, Field},
30        subtle::ConditionallySelectable,
31    },
32};
33
34/// Constant representing the modulus: p = 2^{224}(2^{32} − 1) + 2^{192} + 2^{96} − 1
35const MODULUS_HEX: &str = "ffffffff00000001000000000000000000000000ffffffffffffffffffffffff";
36
37primefield::monty_field_params!(
38    name: FieldParams,
39    modulus: MODULUS_HEX,
40    uint: U256,
41    byte_order: primefield::ByteOrder::BigEndian,
42    multiplicative_generator: 6,
43    doc: "Montgomery parameters for the NIST P-256 field modulus: p = 2^{224}(2^{32} − 1) + 2^{192} + 2^{96} − 1."
44);
45
46primefield::monty_field_element!(
47    name: FieldElement,
48    params: FieldParams,
49    uint: U256,
50    doc: "Element in the finite field modulo p = 2^{224}(2^{32} − 1) + 2^{192} + 2^{96} − 1."
51);
52
53impl FieldElement {
54    /// Decode [`FieldElement`] from [`U256`] converting it into Montgomery form.
55    ///
56    /// Does *not* perform a check that the field element does not overflow the modulus.
57    ///
58    /// Used incorrectly this can lead to invalid results!
59    pub(crate) const fn from_uint_unchecked(w: U256) -> Self {
60        Self::multiply(
61            &Self::from_montgomery(w),
62            &Self::from_montgomery(*FieldParams::PARAMS.r2()),
63        )
64    }
65
66    /// Returns self + rhs mod p
67    pub const fn add(&self, rhs: &Self) -> Self {
68        Self::from_montgomery(field_impl::add(
69            self.0.as_montgomery(),
70            rhs.0.as_montgomery(),
71        ))
72    }
73
74    /// Returns 2 * self.
75    pub const fn double(&self) -> Self {
76        self.add(self)
77    }
78
79    /// Returns self - rhs mod p
80    pub const fn sub(&self, rhs: &Self) -> Self {
81        Self::from_montgomery(field_impl::sub(
82            self.0.as_montgomery(),
83            rhs.0.as_montgomery(),
84        ))
85    }
86
87    /// Negate element.
88    pub const fn neg(&self) -> Self {
89        Self::sub(&Self::ZERO, self)
90    }
91
92    /// Translate a field element out of the Montgomery domain.
93    #[inline]
94    pub(crate) const fn to_canonical(self) -> U256 {
95        field_impl::to_canonical(self.0.as_montgomery())
96    }
97
98    /// Returns self * rhs mod p
99    pub const fn multiply(&self, rhs: &Self) -> Self {
100        let (lo, hi): (U256, U256) = self.0.as_montgomery().widening_mul(rhs.0.as_montgomery());
101        Self::from_montgomery(field_impl::montgomery_reduce(&lo, &hi))
102    }
103
104    /// Returns self * self mod p
105    pub const fn square(&self) -> Self {
106        // Schoolbook multiplication.
107        self.multiply(self)
108    }
109
110    /// Returns the multiplicative inverse of self, if self is non-zero.
111    pub fn invert(&self) -> CtOption<Self> {
112        self.0.invert().map(Self)
113    }
114
115    /// Returns the multiplicative inverse of self, if self is non-zero.
116    pub fn invert_vartime(&self) -> CtOption<Self> {
117        self.0.invert_vartime().map(Self)
118    }
119
120    /// Returns the square root of self mod p, or `None` if no square root exists.
121    pub fn sqrt(&self) -> CtOption<Self> {
122        // We need to find alpha such that alpha^2 = beta mod p. For secp256r1,
123        // p ≡ 3 mod 4. By Euler's Criterion, beta^(p-1)/2 ≡ 1 mod p. So:
124        //
125        //     alpha^2 = beta beta^((p - 1) / 2) mod p ≡ beta^((p + 1) / 2) mod p
126        //     alpha = ± beta^((p + 1) / 4) mod p
127        //
128        // Thus sqrt can be implemented with a single exponentiation.
129
130        let t11 = self.mul(&self.square());
131        let t1111 = t11.mul(&t11.sqn(2));
132        let t11111111 = t1111.mul(t1111.sqn(4));
133        let x16 = t11111111.sqn(8).mul(t11111111);
134        let sqrt = x16
135            .sqn(16)
136            .mul(x16)
137            .sqn(32)
138            .mul(self)
139            .sqn(96)
140            .mul(self)
141            .sqn(94);
142
143        CtOption::new(
144            sqrt,
145            (&sqrt * &sqrt).ct_eq(self), // Only return Some if it's the square root.
146        )
147    }
148
149    /// Returns self^(2^n) mod p
150    const fn sqn(&self, n: usize) -> Self {
151        Self(self.0.sqn_vartime(n))
152    }
153
154    /// Construct a field element from a [`U256`] in Montgomery form.
155    #[inline]
156    pub(crate) const fn from_montgomery(uint: U256) -> Self {
157        Self(primefield::MontyFieldElement::<
158            FieldParams,
159            { FieldParams::LIMBS },
160        >::from_montgomery(uint))
161    }
162}
163
164impl BatchInvert for FieldElement {}
165
166#[cfg(test)]
167mod tests {
168    use super::{FieldElement, FieldParams, cpubits};
169    use crate::{FieldBytes, U256, test_vectors::field::DBL_TEST_VECTORS};
170    use elliptic_curve::{array::Array, bigint::modular::ConstMontyParams};
171
172    cpubits! {
173        64 => { use proptest::{num::u64::ANY, prelude::*}; }
174    }
175
176    primefield::test_primefield!(FieldElement, U256);
177
178    /// Ensures the legacy `R2` constant is computed the same way as the `crypto-bigint`
179    /// implementation.
180    // TODO(tarcieri): since we know this works, it can probably be removed in future refactoring
181    #[test]
182    fn r2() {
183        let expected_r2 =
184            U256::from_be_hex("00000004fffffffdfffffffffffffffefffffffbffffffff0000000000000003");
185        assert_eq!(FieldParams::PARAMS.r2(), &expected_r2);
186    }
187
188    #[test]
189    fn from_bytes() {
190        assert_eq!(
191            FieldElement::from_bytes(&FieldBytes::default()).unwrap(),
192            FieldElement::ZERO
193        );
194        assert_eq!(
195            FieldElement::from_bytes(&Array([
196                0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
197                0, 0, 0, 1
198            ]))
199            .unwrap(),
200            FieldElement::ONE
201        );
202        assert!(bool::from(
203            FieldElement::from_bytes(&Array([0xff; 32])).is_none()
204        ));
205    }
206
207    #[test]
208    fn to_bytes() {
209        assert_eq!(FieldElement::ZERO.to_bytes(), FieldBytes::default());
210        assert_eq!(
211            FieldElement::ONE.to_bytes(),
212            [
213                0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
214                0, 0, 0, 1
215            ]
216        );
217    }
218
219    #[test]
220    fn repeated_add() {
221        let mut r = FieldElement::ONE;
222        for item in DBL_TEST_VECTORS {
223            assert_eq!(r.to_bytes().as_slice(), item);
224            r = r + &r;
225        }
226    }
227
228    #[test]
229    fn repeated_double() {
230        let mut r = FieldElement::ONE;
231        for item in DBL_TEST_VECTORS {
232            assert_eq!(r.to_bytes().as_slice(), item);
233            r = r.double();
234        }
235    }
236
237    #[test]
238    fn repeated_mul() {
239        let mut r = FieldElement::ONE;
240        let two = r + &r;
241        for item in DBL_TEST_VECTORS {
242            assert_eq!(r.to_bytes().as_slice(), item);
243            r = r * &two;
244        }
245    }
246
247    #[test]
248    fn negation() {
249        let two = FieldElement::ONE.double();
250        let neg_two = -two;
251        assert_eq!(two + &neg_two, FieldElement::ZERO);
252        assert_eq!(-neg_two, two);
253    }
254
255    #[test]
256    fn pow_vartime() {
257        let one = FieldElement::ONE;
258        let two = one + &one;
259        let four = two.square();
260        assert_eq!(two.pow_vartime(&U256::from_u64(2)), four);
261    }
262
263    cpubits! {
264        64 => {
265            proptest! {
266                /// This checks behaviour well within the field ranges, because it doesn't set the
267                /// highest limb.
268                #[test]
269                fn add_then_sub(
270                    a0 in ANY,
271                    a1 in ANY,
272                    a2 in ANY,
273                    b0 in ANY,
274                    b1 in ANY,
275                    b2 in ANY,
276                ) {
277                    let a = FieldElement::from_montgomery(U256::from_words([a0, a1, a2, 0]));
278                    let b = FieldElement::from_montgomery(U256::from_words([b0, b1, b2, 0]));
279                    assert_eq!(a.add(&b).sub(&a), b);
280                }
281            }
282        }
283    }
284}
p256/arithmetic/field.rs

p256/arithmetic/
field.rs
